Синтез микропрограммного управляющего автомата с жесткой логикой
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
единицу. Отсюда следует, что для получения минимального кодирования необходимо закодировать состояния кодами, содержащими наименьшее количество единиц. Для этого используют инверсные таблицы переходов.
Для RS-триггеров лучше использовать соседнее кодирование, так как именно этот способ минимизирует число переключений ЭП.
В случае счетчиков разность кодов между соседними состояниями должна быть равна единице, тогда переход из одного состояния в другое будет осуществляться подачей на вход счетчика сигнала, увеличивающего или уменьшающего содержимое самого счетчика.
.1 Кодирование состояний для модели Мили на D-триггерах
Таблица 3. Кодирование состояний автомата Мили на 4 D-триггерах.
Исходное состояние amКод amСостояние перехода asКод asВходной сигналВыходной сигналФункции возбужденияa00010a0 a10010 0110~x1 x1- У0, y1D3 D2D3a10110a2 a2 a90100 0100 0000~x2x1x3 ~x2x1~x3 x2y2, y3 - -D2 D2 -a20100a3 a31100 1100x4 ~x4y1, y4, y5, y6 Y1, y6D1D2 D1D2a31100a4 a4 a91010 1010 0000~x2x5 ~x2~x5 x2y2, y3 - -D1D3 D1D3 -a41010a5 a50011 0011x4 ~x4y4, y5, y6, y7 Y6, y7D3D4 D3D4a50011a0 a6 a60010 0001 0001x6 ~x6x7 ~x6~x7y10 y3 -D3 D4 D4a60001a710011y8D1D4a71001a6 a6 a8 a80001 0001 1000 1000~x8x7 ~x8~x7 x8x9 x8~x9y3 - - y9D4 D4 D1 D1a81000a9 a90000 0000x10 ~x10y5, y6,y11 -- -a90000a0 a90010 0000x11 ~x11y12 -D3 -
Cоставляется инверсная таблицу переходов, и состояния автомата кодируются четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц. Инверсная таблица переходов для модели Мили представлена в таблице 4.
Таблица 4
aSа0a1a2a3a4а5a6A7a8a9ama0 a5 a9a0a1a2a3а4a5 a7A6a7a8 a9 a3 a1Коды0010011001001100101000110001100110000000
Наибольшее количество переходов в состояние a9 - закодируем его кодом К(a9)=0000. Для остальных состояний первой строки табл.4 назначим коды с одной "1":
(a0) = 0010, К(a6) = 0001
Для кодирования других состояний будем стараться, насколько возможно, использовать соседние с as коды для состояний, находящихся в одном столбце.
Логические выражения для каждой функции возбуждения D-триггера получают по таблице как конъюнкции соответствующих исходных состояний am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения.
D1=a2 v a3~x2 v a6 v a7x8=a0x1 v a1~x2x1 v a2=a0 v a3~x2 v a4 v a5x6 v a9x11=a4 v a5~x6 v a6 v a7~x8
Аналогично составляются логические выражения для функций выходов.
y0=a0x1=a0x1 v a2=a1~x2x1x3 v a3~x2x5=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7=a2x4 v a4x4=a2x4 v a4x4 v a8x10= a2 v a4 v a8x10=a4=a6=a7x8~x9=a5x6=a8x1012=a9x11
a8x9x12
После выделения общих частей в логических выражениях и некоторого их упрощения получаем логические уравнения для построения функциональной схемы управляющего автомата.
D1=a2 v m v a6 v l=y0 v n v a2=a0 v m v a4 v y10 v y12=a4 v a6 v r
=a0x1=y0 v a2=nx3 v mx5=y2 v x7r= a2x4 v a4x4=y4 v y11= a2 v y5=a4=a6=l~x9=a5x6=a8x10=a9x11
= a3~x2= a7x8= a1~x2x1= a5~x6= a7~x8
r=q v p
Цена комбинационной схемы по Квайну для автомата Мили на 4 D-триггерах С =66.
Кодирование состояний для модели Мили на RS-триггерах
Для кодировки состояний автомата на RS-триггерах воспользуемся эвристическим алгоритмом кодирования, который минимизирует суммарное число изменений элементов памяти на всех переходах автомата.
01). Кодируем первые два состояния : К(0) = 0000
1 К(1) = 0001
9 2) Выбираем следующее незакодированное состояние u = 9
2 1 9
3 3 9
4 M= 8 9
9 9 0
5 9 9
M= 5 0 Составляем список уже закодированных соседних состояний
6 B = {1,0}
7 Список соседних кодов для них
6C(0) = {1000,0100,0010}
8 C(1) = {1001,0101,0011}
9 D= {1001,0101,0011}
0Выбираем код с минимальной функцией W
9 9W(1000) = W(0100) = W(0010) =W(1001) = W(0101) = W(0011) = 3;K(9) = 0010
) u = 2= 1 2
3= {1}, D = {1001, 0101, 0011} K (2) = 0011
) u = 3
3= 3 4
9= {2; 9} C(2) = {0111, 1011}(9) = {0110,1010}= {0111,0110,1011,1010} K(3) = 0110
) u = 4= 3 4
5= {3} D = {0100,0111,1110} K(4) = 0100
) u =5
5= 5 0
6= {4,0}(0) = {1000}(4) = {1100, 0101}= {1000, 1100, 0101}K (5) = 1000
) u=6
6= 6 7
6={5} D={1100,1010,1001}K(6)=1100
) u=7
7= 7 6
8= {6} D = {1101,1110}K(7) = 1101
) u = 8= 7 8
9= {7,9}(7) = {1001,0101,1111}(9) = {1010}= {1001,0101,1111,1010}K(8) = 1010
Таблица 5. Прямая структурная таблица переходов и выходов автомата Мили при кодировке на RS-триггерах
Исходное состояние amКод amСостояние перехода asКод asВходной сигналВыходной сигналФункции возбужденияa00000a0 a10000 0001~x1 x1- у0, y1- S4a10001a2 a2 a90011 0011 0010~x2x1x3 ~x2x1~x3 x2y2, y3 - -S3 S3 S3, R4a20011a3 a30110 0110x4 ~x4y1, y4, y5, y6 y1, y6R4,S2 R4,S2a30110a4 a4 a90100 0100 0010~x2x5 ~x2~x5 x2y2, y3 - -R3 R3 R2a40100a5 a51000 1000x4 ~x4y4, y5, y6, y7 y6, y7R2,S1 R2,S1a51000a0 a6 a60000 1100 1100x6 ~x6x7 ~x6~x7y10 y3 -R1 S2 S2a61100a711011y8S4a71101a6 a6 a8 a81100 1100 1010 1010~x8x7 ~x8~x7 x8x9 x8~x9y3 - - y9R4 R4 R2,S3,R4 R2,S3,R4a81010a9 a90010 0010x10 ~x10y5, y6,y11 -R1 R1a90010a0 a90000 0010x11 ~x11y12 -R3 -
Логические выражения для каждой функции возбуждения RS-триггера получают по таблице как конъюнкции соответствующих исходных состояний am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения.
S1=a4=a2 v a5~x6=a1 v a7x8=a0x1 v a6=a5x6 v a8=a3x2 v a4 v a7x8=a3~x2 v a9x114=a1x2 v a2 v a7
Аналогично составляются логические выражения для функций выходов.
y0=a0x1=a0x1 v a2=a1~x2x1x3 v a3~x2x5=a1~x2x1x3 v a3~x2x5 v a5~x6x7 v a7~x8x7=a2x4 v a4x4=a2x4 v a4x4 v a8x10= a2 v a4 v a8x10=a4=a6=a7x8~x9=a5x6=a8x1012=a9x11
a8x9x12
После выделения общих частей в логических выражениях и некоторого их упрощения получаем логические уравнения для построения функциональной схемы управляющего автомата.
S1=a4=a2 v h=a1 v g=y0 v a6=y10 v a8=a3x2 v a4 v g=t v y12=a1x2 v a2 v a7
Аналогично составляются логические выражения для функций выходов.
y0=a0x1=y0 v a2=a1~x2x1x3 v tx5=y2 v x7(h v a7~x8)=a2x4 v a4x4=y4 v y11= a2 v y5=a4=a6=g~x9=a5x6=a8x10=a9x11=a5~x6= a7x8= a3~x2
Цена комбинационной схемы по Квайну для автомата Мили на 4 RS-триггерах С =71.
.3 Кодирование состояний модели МИЛИ на счётчике
Исходное состояние amКод amСостояние перехода asКод asВходной сигналВыходной сигналФункции возбужденияa00000a0 a10000 0001~x1 x1- у0, y1- Inca10001a2 a2 a90010 0010 1001~x2x1x3 ~x2x1~x3 x2y2, y3