 |
Структурный автомат и кодирование
|
|
|
|
Рассмотренные схемы соединения элементарных автоматов, имеющих один вход и один выход, позволяют представить структурный автомат, имеющим несколько входов и несколько выходов. Поскольку режим работы синхронный, то в момент времени [t] на каждом входе и выходе структурного автомата появляется сигнал. Следовательно, входной и выходной сигналы структурного автомата есть векторы. Если сигналы на входе и выходе элементарных автоматов принадлежат множеству {0, 1}, то для структурного автомата входной и выходной сигналы есть булевы вектора x=(x1, x2,…xn) и
y=(y1, y2,…yp). Синхронный режим работы элементарных автоматов, формирует внутреннее состояние структурного автомата булевым вектором (q1, q2,…qm).
Для определения числа разрядов регистров структурного автомата необходимо знать мощности алфавитов X, Y и Q. Затем вычислить значения log2|X|, log2|Y| и log2|Q|.
Так как число разрядов регистра может быть только целым положительным числом, то
n³log2|X|, где n - целое положительное число,
p³log2|Y|,где p - целое положительное число
m³log2|Q|, где m - целое положительное число.
В этом случае каждый разряд значений функций выходов j и переходов y структурного автомата есть логические функции от булевых векторов x и q, то есть yi[t]=j(q1[t], q2[t],...qm[t], x1[t], x2[t],...xn[t]) и qj[t+1]=y(q1[t], q2[t],...qm[t], x1[t], x2[t],...xn[t]).
Логическая функция j[t] может быть реализована с помощью схем параллельного и последовательного соединения комбинационных автоматов, а логическая функция y[t+1] – с помощью схем обратной связи, реализующих задержку на один такт [t+1].
Поэтому любой конечный автомат при двоичном кодировании его алфавитов есть структурный автомат (см.рис.6.19) c ”памятью”.
Модель современной вычислительной включает операционный и управляющий автоматы.
|
|
|
Операционные автоматы - это блоки памяти, арифметико-логические устройства, каналы обмена информацией и т.п.. Эти блоки и устройства исполняют основные операции при передаче и/или преобразовании информации. Основными элементами таких устройств являются регистры, которые состоят из наборов двоичных разрядов и представляют информацию двоичными кодами. Такие регистры имеют 32 или 64 разряда. Использование операционным автоматом более 10-ти регистров формирует очень большой (до нескольких гигабайт) объем памяти. Поэтому модель операционного автомата есть структурный автомат с бесконечной памятью.
Управляющие автоматы вычислительной машины - это адаптеры, контроллеры, управляющие блоки периферийными устройствами и т. п. Эти блоки и устройства управляют исполнением операции при передаче и/или преобразовании информации. Такие автоматы используют 4-х или 8-и разрядные регистры, то есть управляющие автоматы имеют небольшой (до нескольких килобайт) объем памяти. Поэтому модель управляющего есть структурный автомат с конечной памятью.
Логическое проектирование автоматов
Основными этапами логического проектирования конечного автомата являются:
1) кодирование алфавитов абстрактного автомата;
2) выбор комбинационных автоматов и формирование оператора j;
3) выбор элементов задержки и формирование оператора y;
4) построение логической схемы структурного автомата.
Кодирование алфавитов автомата
Пусть таблицей 6.41 дан минимизированный абстрактный автомат.
| Таблица 6. 41 | Таблица 6. 42 | |||||||
| текущие qi | xÎX | текущие qi | xÎX | |||||
| q1 | q2; 1 | q2; 0 | q3; 0 | 010; 1 | 010; 0 | 011; 0 | ||
| q2 | q1; 0 | q2; 1 | q2; 1 | 001; 0 | 010; 1 | 010; 1 | ||
| q3 | q4; 1 | q2; 0 | q1; 0 | 100; 1 | 010; 0 | 001; 0 | ||
| q4 | q1; 0 | q5; 1 | q4; 1 | 001; 0 | 101; 1 | 100; 1 | ||
| q5 | q3; 0 | q5; 1 | q3; 1 | 011; 0 | 101; 1 | 011;1 |
|
|
|
В данном автомате X={1, 2, 3}, Y={0, 1}, Q={q1, q2, q3, q4, q5}.
Число разрядов в регистрах входа и выхода структурного автомата и в регистре внутренних состояний должно быть:
log2|X|=log23£n=2,
log2|Y|=log22£n=1,
log2|Q|=log25£n=3.
Поведение автомата при кодовом описании сигналов представлено в таблице 6.42.
Автоматы без “памяти”.
Выбор состава и структуры комбинационного автомата начинают с исследования функциональной зависимости булевой функции от компонент булевого вектора. При этом минимизируют число двоичных переменных в описании одной или нескольких, полностью или частично определенных булевых функций. Аналитические приемы минимизации состава и структуры одной, полностью определенной булевой функции были изложены в 1.5.8.
Ниже будет рассмотрен инженерный способ минимизации числа двоичных переменных в описании одной или нескольких, полностью или частично определенных булевых функций.
Формирование оператора j
В основе метода лежит использование таблиц специального вида - диаграмм Вейча или карт Карно.
В диаграммах Вейча каждой клетке присваивается номер, значение которого в двоичной системе счисления записывается в клетку. Каждый разряд кода есть двоичная переменная булевого вектора. Число клеток диаграммы должно быть 2n, где n - число двоичных переменных. Особенность нумерации клеток заключена в том, что любые две рядом расположенные клетки отличаются в кодовой конфигурации не более, чем в одном разряде. Это позволяет для одинаковых значений булевой функции “склеивать” соседние клетки диаграммы и описывать их сокращенными элементарными конъюнкциями или дизъюнкциями двоичных переменных, имеющими одинаковое значение. Так можно объединить по вертикали и/или по горизонтали две, четыре и восемь смежных клеток. Следует обратить внимание, что кодовые конфигурации клеток левого и верхнего краев диаграммы отличаются от кодовых конфигураций клеток правого и нижнего краев также только в одном разряде, что позволяет “склеивать” и крайние клетки.
На рис. 6.20 представлены диаграммы Вейча для булевых векторов (x1, x2, x3), (x1, x2, x3, x4) и (x1, x2, x3, x4, x5, x6). В этих диаграммах каждая клетка таблицы описана двоичным кодом длины три, четыре и шесть. Вне поля таблицы указаны имена двоичных переменных.
|
|
|
На рис. 6.21 представлены карты Карно для булевых векторов (x1, x2, x3), (x1, x2, x3, x4) и (x1, x2, x3, x4, x5, x6). В этих картах нет наборов двоичных переменных, но вне поля таблицы указаны имена булевых переменных. Это позволяет в клетках карты указывать значения булевой функции.
Каждую клетку карты Карно можно описать элементарной конъюнкцией или элементарной дизъюнкцией двоичных переменных, используемых в карте Карно. Если в клетке карты указано значение функции f=1, то эта клетка может быть описана элементарной конъюнкцией СДНФ. И наоборот, если в клетке указано значение f=0, то – элементарной дизъюнкцией СКНФ (см. 1.5.7). Множество клеток карты Карно, где f=1, описывают дизъюнкцией элементарных конъюнкций СДНФ. И наоборот, множество клеток карты Карно, где f=0, описывают конъюнкцией элементарных дизъюнкций СКНФ.
Левый край строки карты Карно примыкает к правому, а верхний соответствующего столбца - к нижнему. Если карту Карно свернуть в трубку, то крайние клетки отличаются между собой значением только одной двоичной переменной (см. рис. 6.20).
| Для f(x1, x2, x3, x4) | |||||||||||||||||||
| X1 | |||||||||||||||||||
| Для f(x1, x2, x3) | X2 | ||||||||||||||||||
| X1 | |||||||||||||||||||
| X2 | X4 | ||||||||||||||||||
| X3 | |||||||||||||||||||
| X3 | |||||||||||||||||||
| Для f(x1, x2, x3, x4, x5, x6) | |||||||||||||||||||
| X5 | X5 | ||||||||||||||||||
| X1 | |||||||||||||||||||
| X2 | |||||||||||||||||||
| X6 | |||||||||||||||||||
| X4 | |||||||||||||||||||
| X6 | |||||||||||||||||||
| X3 | |||||||||||||||||||
| Рис. 6.21. Карты Карно (x1, x2, x3), (x1, x2, x3, x4) и (x1, x2, x3, x4, x5, x6) |
|
|
|
Любые смежные клетки карты Карно также различаются между собой только одной двоичной переменной. Так как смежные и крайние клетки карты Карно различаются между собой значением только одной двоичной переменной, то их можно “склеить” и описать сокращёнными нормальными формами формул, воспользовавшись законами противоречия и дистрибутивности. При объединении двух смежных клеток карты сокращённая конъюнкция (или дизъюнкция) имеют (n-1) двоичную переменную. При объединении четырёх клеток формируется сокращенная нормальная форма, содержащая (n-2) двоичных переменных, а при объединении восьми - (n-3) двоичных переменных.
Пусть булева функция четырех двоичных переменных задана таблицей 6.43 и отображена на карте Карно (см. рис.6.22).
| Таблица 6.43. | |||||||||||
| x1 | x2 | x3 | x4 | j |   x1
| ||||||
| x2 | |||||||||||
| * | x4 | ||||||||||
| * | |||||||||||
  x3
| |||||||||||
| * | Рис 6.22. Карта Карно | ||||||||||
| * | |||||||||||
|
|
|
Анализ карты показывает, что в четырех смежных клетках, описываемых кодами 0111, 0011, 0101 и 0001, булева функция имеет значение “1” ”.
Следовательно, j=1=`x1×x2×x3×x4Ú`x1×`x2×x3×x4Ú `x1×x2×`x3×x4 Ú`x1×`x2×`x3×`x4=`x1×x3×x4×(x2Ú`x2)Ú`x1×`x3×x4×(x2Ú×`x2)= `x1×x3×x4Ú`x1×`x3×x4 =`x1 ×x4×(x3Ú`x3)=`x1 ×x4
В четырех крайних по вертикали клетках, описываемых кодами 0110, 0100, 0010 и 0000 – значение ”0”.
Следовательно, j=0=(x1Ú`x2Ú`x3Úx4)×(x1Ú`x2Úx3Úx4)×(x1Úx2Ú`x3Úx4)×(x1Úx2Úx3Úx4)= =((x1Ú`x2Úx4)Úx3×`x3`)×((x1Úx2Úx4)Úx3×`x3)=(x1Ú`x2Úx4)×(x1Úx2Úx4)= (x1Úx4)Úx2×`x2=(x1Úx4).
Есть по две смежных клетки, имеющих одинаковые значения функции.
Например, для j=1 это клетки, имеющие коды 1100 и 1110, 1110 и 1111, 1111 и 0111, для j=0 - это 1000 и 1001, 1001 и1011, 1000 и 0000.
Булевы функции для этих пар клеток могут быть описаны сокращенными нормальными формами:
j=1=x1×x2×`x4Ú x1×x2×x3Úx2×x3×x4,
j=0=(`x1Úx2Úx3)×(`x1Úx2Ú `x4)×(x2Úx3Úx4).
Множество клеток, в которых булева функция имеет значение “0” или “1”, позволяет сформировать минимальную ДНФ или КНФ из числа сокращенных. На рис.6.23 узором выделены возможные варианты минимальных ДНФ и КНФ.
 a)
| x1
| c) |  x1
| |||||||||
| x2 | x2 | |||||||||||
| * | x4 | * | x4 | |||||||||
| * | * | |||||||||||
| x3
| x3
| |||||||||||
| b) | x1
| d) |  x1
| |||||||||
| x2 | x2 | |||||||||||
| * | * | x4 | ||||||||||
| * | * | |||||||||||
| x3
| x3
|
Рис. 6.23. Карты Карно для таблицы 6.43.
Минимальные ДНФ:
для карты а) jmin(x1, x2, x3, x4)=`x1×x4Úx1×x2×`x4Ú x1×x2×x3 ,
для карты b) jmin(x1, x2, x3, x4)=`x1×x4Úx1×x2×`x4Úx2×x3×x4.
Минимальные КНФ:
для карты c) jmin(x1, x2, x3, x4)=(x1Úx4)×(`x1Úx2Ú`x4))×(`x1Úx2Úx3),
для карты d) jmin(x1, x2, x3, x4)=(x1Úx4)×(`x1Úx2Ú`x4)×(x2Úx3Úx4).
В двух клетках карты не определены значения булевой функции (помечены знаком “*”). Анализ позволяет допустить для кода 1101 значение f=1, для кода 1010 значение f=0.
Тогда минимальная ДНФ jmin(x1, x2, x3, x4)=`x1×x4Úx1×x2,
Минимальная КНФ jmin(x1, x2, x3, x4)=(x1Úx4)×(`x1Úx2).
|
|
|
