Синтез микропрограммного управляющего автомата
p6 - проверка результата на нормализованность;
p7 - проверка условия ПРС;
Z - проверка возможности выдачи по ШИВых.
Таким образом, управляющий МПА должен вырабатывать 8 управляющих
сигналов и посылать их в ОА в нужные такты машинного времени в
соответствии с алгоритмом выполнения операции сложения, ориентируясь на 9
осведомительных сигналов, поступающих из ОА, структурная схема которой
представлена на рисунке 1.
5 Реализация содержательной ГСА
Содержательная граф-схема алгоритма представлена на рисунке 2.
Выполнение алгоритма начинается с проверки наличия операндов на ШИВх (блоки
1 и 5). При поступлении первого операнда происходит его занесение в RG1,
RG2, RG3 и CT1, а также обнуление RG4, занесение “001001” в CT2 и сброс
триггеров T1 и T2 (блок 2). Затем в регистр RG4 поступает ДК от первого
операнда (блок 4). При поступлении второго операнда происходит его
занесение в RG2 и CT1 (блок 6). После каждого занесения производится
анализ p3. Если хотя бы в одном случае p3=1 (блоки 3 и 7), значит операнд
равен нулю и значит необходимо обнулить RG4, RG3, CT1, T1 (блок 19) и
перейти к блоку 20. В противном случае продолжается процесс коррекции. Если
p2=0 (блок 8) тогда обнуляется регистр RG4 (блок 9). Если p1=1 (блок 10)
тогда получившаяся в сумматоре SM1 сумма заносится в RG4 (блок 11).
Далее получается псевдопроизведение. Если p4=0 (блок 12), тогда
получившаяся в сумматоре SM1 сумма заносится в RG4 (блок 13). В любом
случае выполняется блок сдвигов (блок 14): содержимое RG1 и RG4 сдвигаются
вправо, CT2 увеличивается на “1“. Далее проверяется p5 (блок 15) - условие
выхода из цикла. Если p5=1, цикл завершается, иначе переход к блоку 12.
Затем производится нормализация. Если p6=0 (блок 16), то выполняется
блок сдвигов (блок 18): содержимое RG4 сдвигается влево, CT2 уменьшается на
“1“.
При сложении характеристик одинакового знака возможно переполнение
разрядной сетки (ПРС). Если p7=1 (блок 17), возникло ПРС и операция
умножения завершается.
Затем результат при Z=1 (блок 21) будет передан по ШИВых (блок 22) в
другие устройства.
6 Построение отмеченной ГСА
Перед разметкой содержательной ГСА поставим возле каждой операторной
вершины управляющие сигналы УА и обеспечивающие выполнение требуемых
действий в соответствии со списком МО операционного автомата.
Совокупность МО для каждой операторной вершины образуют микрокоманды
(МК), список которых приведен в таблице 5.
Таблица 5
|MK |Совокупность МО |
|Y1 |y1,y2,y3 |
|Y2 |y2 |
|Y3 |y3 |
|Y4 |y4 |
|Y5 |y5 |
|Y6 |y4,y6 |
|Y7 |y7 |
|Y8 |y8 |
|Y9 |y1,y3 |
Каждой условной вершине содержательной ГСА поставим в соответствие
один из входных сигналов управляющего автомата X1, … ,X9, список которых
дан в таблице 6.
Таблица 6
|Входной сигнал УА |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |
|Логическое условие ОА|X |p3 |p2 |p1 |p4 |p5 |p6 |p7 |Z |
Далее в полном соответствии с содержательной ГСА строим отмеченную
ГСА (рисунок 3), условным вершинам которой приписывается один из входных
сигналов УА (x1,...,x9), а операторным вершинам - одна из МК (в скобках
указана совокупность МО для каждой МК). Выделение состояний управляющего
МПА возможно в соответствии с моделью Мили или моделью Мура.
На рисунке 3 приведена разметка ГСА для модели Мили символами
a0,а1,...,а9 и для модели Мура - символами b0,b1,...,b12. Таким образам,
если строить управляющий МПА в соответствии с моделью Мили, то он будет
иметь 10 состояний, а в соответствии с моделью Мура - 13 состояний.
Замечание. В двух вершинах ожидания (5 и 20) при разметке по Муру
введены фиктивные состояния автомата b3 и b10.
Явно большее число состояний для модели Мура по сравнению с моделью
Мили не дает достаточных оснований для выбора модели Мили как более
предпочтительной. Сравнение вариантов можно будет выполним лишь на этапе
построения функциональных схем УА, сравнив схемы по сложности и
быстродействию. Поэтому далее будем вести проектирование УА параллельно
для модели Мили и для модели Мура.
7 Синтез МПА в соответствии с моделью Мили
7.1 Построение графа автомата
На основе отмеченной ГСА построен граф автомата Мили (рисунок 4). Граф
автомата Мили имеет 10 вершин, соответствующих состояниям автомата а0,
а1,...,а9, дуги его отмечены входными сигналами, действующими на каждом
переходе (числитель), и набором выходных сигналов, вырабатываемых УА на
данном переходе (знаменатель).
Из приведенного рисунка видно, что с увеличением количества состояний
автомата наглядность графа теряется и больше удобств представляет табличный
способ задания автомата.
7.2 Построение структурной таблицы переходов и выходов
Таблица 7. Прямая структурная таблица переходов и выходов автомата
Мили.
|Исходное| |Состояние | |Входной|Выходные |Функции |
|состояни|Код |перехода |Код |сигнал |сигналы |возбуждения |
|е |am |as |as |X(am,as|Y(am,as) |D-триггеров |
| | | | |) | | |
|a0 |0001 |a0 |0001 |X1 |- |D4 |
| | |a1 |0011 |X1 |Y1(y1,y2,y|D3D4 |
| | | | | |3) | |
|a1 |0011 |a2 |0010 |X2 |Y6(y4,y6) |D3 |
| | |a9 |0000 |X2 |Y9(y1,y3) | |
|a2 |0010 |a2 |0010 |X1 |- |D3 |
| | |a3 |0110 |X1 |Y2(y2) |D2D3 |
|a3 |0110 |a4 |1100 |X2X3 |- |D1D2 |
| | |a4 |1100 |X2X3 |Y3(y3) |D1D2 |
| | |a9 |0000 |X2 |Y9(y1,y3) | |
|a4 |1100 |a5 |0100 |X4 |- |D2 |
| | |a5 |0100 |X4 |Y6(y4,y6) |D2 |
|a5 |0100 |a6 |0101 |X5 |- |D2D4 |
| | |a6 |0101 |X5 |Y4(y4) |D2D4 |
|a6 |0101 |a7 |1001 |1 |Y5(y5) |D1D4 |
|a7 |1001 |a5 |0100 |X6 |- |D2 |
| | |a8 |1000 |X6 |- |D1 |
|a8 |1000 |a0 |0001 |X7X8 |- |D4 |
| | |a8 |1000 |X7 |Y7(y7) |D1 |
| | |a9 |0000 |X7X8 |- | |
|a9 |0000 |a0 |0001 |X9 |- |D4 |
| | |a9 |0000 |X9 |Y8(y8) | |
7.3 Кодирование на D-триггерах
При кодировании состояний автомата, в качестве элементов памяти
которого выбраны D-триггеры, следует стремится использовать коды с меньшим
числом "1" в кодовом слове. Для кодирования 10 состояний (a0 ,…, a10)
необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов
надо выбрать код каждого состояния, ориентируясь на граф и таблицу
переходов: чем чаще в какое-либо состояние происходят переходы из других
состояний, то есть чем чаще оно встречается в столбце as таблицы 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, стараясь, насколько
возможно, использовать соседние с as коды для состояний, находящихся в
одном столбце таблицы 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-триггера
получают по таблице как конъюнкции соответствующих исходных состояний am и
входных сигналов, которые объединены знаками дизъюнкции для всех строк,
содержащих данную функцию возбуждения.
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 и Di. Код с
наименьшей суммой и является наиболее оптимальным, когда все суммы
получились одинаковыми выбираем любой код и кодируем это состояние.
00 k0=0000
01 k1=0001
12
19 12 B2 ={0001}
22 M2= 22 C1={0011,0101,1001}
M= 23 23 D2={0011,0101,1001}
34 W0011=1
39 W0101=1
45 W1001=1
56 k2=0011
67
78
80
88
89
99
23 B3={0011}
M3= 34 C2={0010,0111,1011}
39 D3={0010,0111,1011}
W0010=1
W0111=1
W1011=1
k3=0010
34 B4={0 010}
M4= 45 C3={0110,1010}
D4={0110,1010}
W0110=1
W1010=1
k4=0110
45 B5={0110}
M5= 56 C4={0100,0111,1110}
75 D5={0100,0111,1110}
W0100=1
W0111=1
W1110=1
k5=0111
56 B6={0111}
M6= 67 C5={0101,1111)}
D6={0101,1111)}
W0101=1
W1111=1
k6=0101
67 B7={0111,0101}
M7= 75 C5={1111}
78 C6={0100,1101}
D7={1111,0100,1101}
W1111=(1111-0111(2+(1111-0101(2=1+2=3
W0100=(0100-0111(2+(0100-0101(2=2+1=3
W1101=(1101-0111(2+(1101-0101(2=2+1=3
k7=0100
78 B8={0000,0100}
M8= 80 C0={1000}
88 C7={1100}
89 D8={1000,1100}
W1100=(1100-0000(2+(1100-0100(2=2+1=3
W1000=(1000-0000(2+(1000-0100(2=1+2=3
k8=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 |
k9=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-триггеров
Далее составляем прямую структурную таблицу переходов и выходов
автомата Мили и по известному правилу формируем логические выражения для
функций возбуждения.
Таблица 11. Прямая структурная таблица переходов и выходов автомата
Мили.
|Исходное| |Состояние | |Входной|Выходные |Функции |
|состояни|Код |перехода |Код |сигнал |сигналы |возбуждения |
|е |am |as |as |X(am,as|Y(am,as) |триггеров |
| | | | |) | | |
| | | | | | |RS |T |
|a0 |0000 |a0 |0000 |X1 |- | | |
| | |a1 |0001 |X1 |Y1(y1,y2,y|S4 |T4 |
| | | | | |3) | | |
|a1 |0001 |a2 |0011 |X2 |Y6(y4,y6) |S3 |T3 |
| | |a9 |1000 |X2 |Y9(y1,y3) |S1R4 |T1T4 |
|a2 |0011 |a2 |0011 |X1 |- | | |
| | |a3 |0010 |X1 |Y2(y2) |R4 |T4 |
|a3 |0010 |a4 |0110 |X2X3 |- |S2 |T2 |
| | |a4 |0110 |X2X3 |Y3(y3) |S2 |T2 |
| | |a9 |1000 |X2 |Y9(y1,y3) |S1R3 |T1T3 |
|a4 |0110 |a5 |0111 |X4 |- |S4 |T4 |
| | |a5 |0111 |X4 |Y6(y4,y6) |S4 |T4 |
|a5 |0111 |a6 |0101 |X5 |- |R3 |T3 |
| | |a6 |0101 |X5 |Y4(y4) |R3 |T3 |
|a6 |0101 |a7 |0100 |1 |Y5(y5) |R4 |T4 |
|a7 |0100 |a5 |0111 |X6 |- |R3R4 |T3T4 |
| | |a8 |1100 |X6 |- |S1 |T1 |
|a8 |1100 |a0 |0000 |X7X8 |- |R1R2 |T1T2 |
| | |a8 |1100 |X7 |Y7(y7) | | |
| | |a9 |1000 |X7X8 |- |R2 |T2 |
|a9 |1000 |a0 |0000 |X9 |- |R1 |T1 |
| | |a9 |1000 |X9 |Y8(y8) | | |
Так как мы изменили используемые элементы памяти, то у нас изменятся
логические выражения для функций их возбуждения, а логические выражения для
функций выходов не изменятся.
S1= a1x2 v a3x2 v a7x6
S2= a3x2
S3= a1x2
S4= a0x1 v a4
R1= a8x7x8 v a9x9
R2= a8x7
R3= a3x2 v a5 v a7x6
R4= a1x2 v a2x1 v a6 v a7x6
После упрощения и выделения общих частей, получим:
f= a1x2
g= a3x2
k= a7x6
m= a8x7
p= a3x2
q= a1x2
r= a0x1
h= a2x1
e= r v a1x2 v g
n= q v a4x4
S1= f v g v a7x6
S2= p
S3= q
S4= r v a4
R1= mx8 v a9x9
R2= m
R3= g v a5 v k
R4= f v h v a6 v k
y1= e
y2= r v h
y3= e v px3
y4= n v a5x5
Страницы: 1, 2, 3
|