Реферат: Синтез микропрограммного управляющего автомата
8.3 Кодирование на D-триггерах
В таблице 15 представлена прямая структурная таблица переходов и выходов автомата Мура. Так как каждому состоянию автомата Мура соответствует свой набор выходных сигналов, то столбец выходных сигналов в таблице помещен следом за столбцом исходных состояний автомата. Проанализируем синтез автомата Мура на D-триггерах.
При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремиться использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 13 состояний (b0, b1, ... , b12) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце bs таблицы, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.
Таблица 16
|
bs |
b0 | b1 | b2 | b3 | b4 | b5 | b6 | B7 | ||
|
{bm} |
b0b8b9b11 | b0 | b1 | b2b3 | b2b3 | b4 | b4b5 | b4b5b6b8 | ||
|
bs |
b8 | b9 | b10 | b11 | b12 | |||||
|
{bm} |
b4b5b6b7b8 | b8b9 | b8b9b10b12 | b8b9b10b12 | b1b4 | |||||
Коды состояний автомата определим по выше описанному методу кодирования состояний при использовании D-триггеров.
Таблица 17
| b | b0 | b1 | b2 | b3 | b4 | b5 | b6 |
| K(b) | 0001 | 0111 | 1110 | 1010 | 0110 | 1100 | 0101 |
| b | b7 | b8 | b9 | b10 | b11 | b12 | |
| K(b) | 0010 | 0000 | 1001 | 0100 | 1000 | 0011 |
8.4 Получение логических выражений для функций возбуждения D-триггеров и функций выходов.
Далее коды состояний заносим в соответствующие столбцы прямой таблицы переходов (таблица 15) и по известному правилу формируем логические выражения для функций возбуждения.
D1= b1x2 v b2x1 v b3x1 v b4x2 v b8x6x7 v b8x6x7x8x9 v b9x7 v b10x9 v b12x9
D2= b0x1 v b1x2 v b2x1 v b3x1 v b4x2(x3 v x3x4) v b5x4 v b8x6x7x8x9 v b9x7x8x9 v b10x9 v
v b12x9
D3= b0x1 v b1 v b2 v b3 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b8x6x4
D4= b0 v b1x2 v b4x2x3x4 v b4x2 v b5x4 v b8x6(x7x8 v x7) v b9(x7x8 v x7) v b11
Так как для автомата Мура функции выходов не зависят от входных сигналов, то в соответствии со вторым столбцом таблицы 15 записываем логические выражения для управляющих сигналов.
y1= b1 v b12
y2= b1 v b4
y3= b1 v b5 v b12
y4= b2 v b6 v b7
y5= b8
y6= b2 v b6
y7= b9
y8=b11
Выделив общие части получаем:
d=b2 v b6
g=b0x1
h=b1x2
i=b4x2
j=x4x5
k=b4x2x3
m=b8x6
n=x7x8
r=b2 v b3
q=mvb9
D1= h v x1r v k v m(x7 v nx9) v b9x7 v b10x9 v b12x9
D2= g v h v x1r v i(x3 v x3x4) v b5x4 v nx9q v x9(b10 v b12)
D3= g v b1 v r v j(k v b5) v x5(b6 v b8x6)
D4= b0 v x2(b1 v b4) v x4(k v b5) v (x7x8 v x7)q v b11
y4= d v b7
y6= d
Цена комбинационной схемы по Квайну для автомата Мура, построенного на D-триггерах, равна С =109, причем в схеме предполагается использовать 4-входовой дешифратор.
8.5 Кодирование на RS-триггерах
Однако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Для этого сначала выпишем матрицу М - матрицу всех возможных переходов автомата. Состояниям автомата b0 и b1 присвоим коды: К(b0)=0000, К(b1)=0001. Далее из матрицы М составим подматрицу М2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C0 и C1 коды с кодовым расстоянием "1" от кодов В2. Для матрицы М2 не имеет значения какой из кодов выбрать, пусть кодом b2 будет 0011. Закодировав состояние b2, выпишем матрицу М3 для кодирования следующего состояния автомата. Кодирование состояния b3 аналогично b2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами Вi и Di. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.
 |
 |
00 k0=0000
01
12 k1=0001
1 12
23 12 B2 ={0001}
24 M2= 23 C1={0011,0101,1001}
M= 33 24 D2={0011,0101,1001}
34 W0011=1
45 W0101=1
46 W1001=1
47 k2=0011
48
4 12 23 B3={0011}
56 M3= 33 C2={0010,0111,1011}
57 34 D3={0010,0111,1011}
58 W0111=1
67 W0010=1
68 W1011=1
78 k3=0010
80
87 24 B4={0011,0010}
88 34 C2={0111,1011} C3={0110,1010}
89 45 D4={0111,1011, 0110,1010}
8 10 M4= 46 W0111=3
8 11 47 W1011=3
90 48 W0110=3
99 4 12 W1010=3
9 10 k4=0110
9 11
10 10 45 B5={0110}
10 11 M5= 56 C4={0100,0111,1110}
11 0 57 D5={0100,0111,1110}
12 10 58 W0100=1
12 11 W0111=1
W1110=1
k5=0100
46 B6={0110,0100}
M6= 56 C4={0111,1110}
67 C5={0101,1100}
68 D6={0111,1110,0101,1100}
| D\B | 0110 | 0100 | W |
| 0111 | 1 | 2 | 3 |
| 1110 | 1 | 2 | 3 |
| 0101 | 2 | 1 | 3 |
| 1100 | 2 | 1 | 3 |
k6=0101
 |
 |
47 B7={0110,0100,0101}
57 C4={0111,1110}
M7= 67 C5={1100}
78 C6={0111,1101}
87 D7={0111,1110,1100,1101}
| D\B | 0110 | 0100 | 0101 | W |
| 0111 | 1 | 2 | 1 | 4 |
| 1110 | 1 | 2 | 3 | 6 |
| 1100 | 2 | 1 | 2 | 5 |
| 1101 | 3 | 2 | 1 | 6 |
k7=0111
80 B8={0000,0110,0100,0101,0111}
48 C0={1000}
58 C4={1110}
68 C5={1100}
M8= 78 C6={1101}
87 C7={1111}
88 D8={0000,1110,1100,1101,1111}
89
8 10
8 11
| D\B | 0000 | 0110 | 0100 | 0101 | 0111 | W |
| 1000 | 1 | 3 | 2 | 3 | 4 | 13 |
| 1110 | 3 | 1 | 2 | 3 | 2 | 11 |
| 1100 | 2 | 2 | 1 | 2 | 3 | 10 |
| 1101 | 3 | 3 | 2 | 1 | 2 | 11 |
| 1111 | 4 | 2 | 3 | 2 | 1 | 12 |
k8=1100
 |
 |
90 B9={0000,1100}
89 C0={1000}
M9= 99 C8={1000,1101,1110}
9 10 D9={1000,1101,1110}
9 11 k9=1000
8
10 B10={1100,1000}
9 10 C8={1101,1110}
M10= 10 10 C9={1001,1010}
