Синтез микропрограммного управляющего автомата (стр. 3 из 7)

При кодировании состояний автомата, в качестве элементов памятикоторого выбраны D-триггеры, следует стремится использовать кодыс меньшим числом "1" в кодовом слове.Для кодирования 10 состояний (a₀ ,…, a₁₀) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце a_sтаблицы 7, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу 8, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.

Таблица 8

As	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
{am}	A0a8a9	a0	a1a2	a2	a3	a4a7	a5	a6	a7a8	a1a3a8a9

Наибольшее количество переходов в состояние a9 - закодируем его кодом К(a9)=0000. Состояниям a0, a2, a5, a8 назначим коды с одной "1": K(a0) =0001, К(a2) =0010, К(a5)=0100, К(a8)=1000. Для кодирования других состояний будем использовать слова с двумя "1" в кодовом слове, К(a1)=0011, К(a3)=0110, К(a4)=1100, К(a6)=0101, К(a7)=1001, стараясь, насколько возможно, использовать соседние с a_s коды для состояний, находящихся в одном столбце таблицы 7.

Кодирования для D-триггеров изображены в таблице 9.

Таблица 9

As	a0	a1	a2	a3	a4	a5	a6	a7	a8	A9
K{as}	0001	0011	0010	0110	1100	0100	0101	1001	1000	0000

Далее коды состояний заносим в соответствующие столбцы прямойтаблицы переходов (таблица 7) и формируем логические выражениядля функций возбуждения.

7.4 Получение логических выражений для функций возбуждения D-триггеров

Логические выражения для каждой функции возбуждения D-триггераполучают по таблице как конъюнкции соответствующих исходных состояний a_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения.

D1= a3x2va6va7x6va8x7

D2= a2x1va3x2va4va5va7x6

D3= a0x1va1x2va2

D4= a0va5va6va8x7x8va9x9

Аналогично составляются логические выражения для функций выходов.

y1= a0x1va1x2va3x2

y2= a0x1va2x1

y3= a0x1va1x2va3x2x3va3x2

y4= a1x2va4x4va5x5

y5= a6

y6= a1x2va4x4

y7= a8x7

y8=a9x9

После выделения общих частей в логических выражениях и некоторогоих упрощения получаем логические уравнения для построения функциональной схемы управляющего автомата.

m=a1x2va4x4

n=a0x1

k=nva1x2va3x2

p=a8x7

q=a2x1

r=a3x2

D1= r v y5 v a7x6 v y7

D2= q v r v a4 v a5 v a7x6

D3= n v y6 v a2

D4= a0 v a5 v y5 v a8x7x8 v a9x9

Аналогично упрощаем логические выражения для функций выходов.

y1= k

y2= n v q

y3= k v rx3

y4= m v a5x5

y5= a6

y6= m

y7= p

y8=a9x9

Цена комбинационной схемы по Квайну для автомата Мили, сиспользованием в качестве элементов памяти D-триггеров, равнаС=59,причем в схеме предполагается использовать 4-входовойдешифратор.

7.5 Кодирование на RS- триггерах

Однаковкачествеэлементов памяти возможноиспользование нетолько D-триггеров, также используются RS-триггеры. Но при использованииRS-триггеров придется перекодировать состояния автомата, кодирование осуществимспособом минимизирующим число переключений элементов памяти.

Для этого сначала выпишем матрицу M - матрицу всехвозможныхпереходов автомата. Состояниям автомата a0 и a1 присвоим коды:К(a0)=0000,К(a1)=0001. Далее из матрицы М составим подматрицу M2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C1 коды с кодовым расстоянием "1" от кодов В2. Закодировав состояние a2, выпишем матрицу М3 для кодирования следующего состояния автомата.Кодирование состояния a3 аналогично a2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами В_i и D_i. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.

00 k₀=0000

01 k₁=0001

12

19 12 B2 ={0001}

22 M2= 22 C1={0011,0101,1001}

M= 2323 D2={0011,0101,1001}

34 W₀₀₁₁=1

39 W₀₁₀₁=1

45 W₁₀₀₁=1

56 k₂=0011

67

78

80

88

89

99

23 B3={0011}

M3= 34 C2={0010,0111,1011}

39 D3={0010,0111,1011}

W₀₀₁₀=1

W₀₁₁₁=1

W₁₀₁₁=1

k₃=0010

34 B4={0 010}

M4= 45 C3={0110,1010}

D4={0110,1010}

W₀₁₁₀=1

W₁₀₁₀=1

k₄=0110

45 B5={0110}

M5= 56 C4={0100,0111,1110}

75 D5={0100,0111,1110}

W₀₁₀₀=1

W₀₁₁₁=1

W₁₁₁₀=1

k₅=0111

56 B6={0111}

M6= 67 C5={0101,1111)}

D6={0101,1111)}

W₀₁₀₁=1

W₁₁₁₁=1

k₆=0101

67 B7={0111,0101}

M7= 75 C5={1111}

78 C6={0100,1101}

D7={1111,0100,1101}

W₁₁₁₁=ô1111-0111ô²+ô1111-0101ô²=1+2=3

W₀₁₀₀=ô0100-0111ô²+ô0100-0101ô²=2+1=3

W₁₁₀₁=ô1101-0111ô²+ô1101-0101ô²=2+1=3

k₇=0100

78 B8={0000,0100}

M8= 80 C0={1000}

88 C7={1100}

89 D8={1000,1100}

W₁₁₀₀=ô1100-0000ô²+ô1100-0100ô²=2+1=3

W₁₀₀₀=ô1000-0000ô²+ô1000-0100ô²=1+2=3

k₈=0100

19 B9={0000,0001,0010,1100}

39 C0={1000}

M9= 89 C1={1001} C3={1010}

90 C8={1000,1101,1110}

99 D9={1000,1001,1010,1101,1110}

D\B	0000	0001	0010	1100	W
1000	1	2	2	1	6
1001	2	1	3	2	8
1010	2	3	1	2	8
1101	3	2	4	1	10
1110	3	4	2	1	10

k₉=1000

Кодирования для RS-триггеров изображены в таблице 10.

Таблица 10

As	a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
K{as}	0000	0001	0011	0010	0110	0111	0101	0100	1100	1000

7.6 Получение логических выражений для функций возбуждения RS-триггеров