Slides_OEVM_final
.pdf
Лекция 7. Устройство управления:
с жесткой логикой
Кодирование состояний
Каждому такому пути соответствует
конъюнкция:
|
|
e |
e |
R |
e |
, |
||
|
αij = x i1 |
...x iR |
= ∏ x |
ir |
||||
|
|
i1 |
iR |
r=1 ir |
Y2 |
|||
где xir – логическое условие, |
||||||||
|
||||||||
записанное в условной вершине pir |
||||||||
|
|
|
|
|
|
|
Y3 |
|
|
|
xir0 = xir , xir1 |
= xir |
. |
|
|||
|
|
|
|
|||||
|
|
|
Начало |
Y0 |
||
|
|
|
1 |
x1 |
|
|
|
|
|
|
|
|
|
|
Y |
y1y2 |
|
0 |
|
|
|
1 |
|
|
x2 |
0 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
1 |
x3 |
1 |
Y7 |
|
y6y7 |
|
|
y1y3 |
Y |
|
||
|
y4 |
0 |
5 |
|||
|
|
|
|
|||
|
|
|
|
|
|
|
|
x4 |
0 |
|
|
|
|
|
|
0 |
|
|
|
|
1 |
|
x1 |
|
|
|
|
|
|
|
|
|
||
y5y6y7 |
1 |
|
Y6 |
|
y3y4 |
|
|
|
|
|
|||
|
x5 |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
Y4 |
y8 |
|
|
|
|
|
|
|
181 |
|
© С. Г. Мосин, 2007 |
Yk |
Конец |
||
|
||||
|
|
|
||
|
|
|
|
Лекция 7. Устройство управления:
с жесткой логикой
Кодирование состояний
Если между вершинами Yi и Yj H путей, то αij равно дизъюнкции конъюнкций, соответствующих всем
путям: |
|
|
|
H |
. |
|
|
|
|
||
|
αij = åαirh |
Y2 |
|
|
|
|
|
|
h=1 |
|
|
αij – функция перехода от |
Y3 |
||
оператора (микрокоманды) Yi к оператору (микрокоманде) Yj .
© С. Г. Мосин, 2007 |
Yk |
|
|
|
|
Начало |
Y0 |
||
|
|
|
1 |
x1 |
|
|
|
|
|
|
|
|
|
|
Y |
y1y2 |
|
0 |
|
|
|
1 |
|
|
x2 |
0 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
1 |
x3 |
1 |
Y7 |
|
y6y7 |
|
|
y1y3 |
Y |
|
||
|
y4 |
0 |
5 |
|||
|
|
|
|
|||
|
|
|
|
|
|
|
|
x4 |
0 |
|
|
|
|
|
|
0 |
|
|
|
|
1 |
|
x1 |
|
|
|
|
|
|
|
|
|
||
y5y6y7 |
1 |
|
Y6 |
|
y3y4 |
|
|
|
|
|
|||
|
x5 |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
Y4 |
y8 |
|
|
|
|
Конец |
|
|
|
|
182 |
|
|
|
|
|
|
||
Лекция 7. Устройство управления:
с жесткой логикой
Кодирование состояний
Обычно при проектировании цифровых устройств предварительно составляют содержательные граф-схемы алгоритмов, в которых внутри условных и операторных вершин записывают не элементы множеств X и Y, а логические условия и микрооперации в содержательных терминах.
Пример. Для операции деления S / Z. АЛУ содержит сумматор S, где находится делимое, регистр Z (делитель) и регистр Y, где сохраняют частное. СТ – счетчик тактов, ТП – триггер переполнения.
183
© С. Г. Мосин, 2007
Лекция 7. Устройство управления:
с жесткой логикой
Условные вершины:
x1: ЗнакS = ЗнакZ x2: ЗнакS = 1
x3: СТ = 0 x4: СТ = n
Операторные вершины: y1: ЗнакY := 1;
y2: Y := 0; y3: СТ := 0;
y4: ЗнакZ := 0; y5: ЗнакS := 0;
y6: S := S + Z; y7: S := S + Zобр; y8: Y[n] := 1;
y9: CT := CT + 1; y10: S := L1(S); y11: Y := L1(Y); y12: ТП := 1.
© С. Г. Мосин, 2007
|
|
Начало |
|
|
|
Y0 |
Начало |
|
|
|
|
ЗнакZ= |
1 |
|
|
|
x1 |
1 |
|
|
|
|
|
|
|
|
|||
|
|
ЗнакS |
|
|
|
|
0 |
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
ЗнакY := 1; |
|
|
|
Y1 |
y1 |
|
|
|
|
Y := 0; |
|
|
|
|
|
|
|
|
|
СТ := 0; |
|
|
|
Y2 |
y2y3y4y5 |
|
|
|
|
ЗнакZ := 0; |
|
|
|
|
|
||
|
|
ЗнакS := 0; |
|
|
|
|
|
|
|
|
|
ЗнакS = 1 |
1 |
|
|
|
x2 |
1 |
|
|
|
|
|
|
|
|
|
||
|
|
0 |
S := S+Z; |
|
|
|
0 |
Y3 |
y6 |
|
|
S := S+Z ; |
|
|
Y4 |
y7 |
|||
|
|
обр |
|
|
|
|
|
|
|
|
|
ЗнакS = 1 |
1 |
|
|
|
x2 |
1 |
|
|
|
|
|
|
|
|
|
||
|
1 |
0 |
|
|
|
1 |
0 |
|
|
|
СТ = 0 |
|
|
|
x3 |
|
|
||
|
|
|
|
|
|
|
|
||
ТП := 1; |
|
0 |
|
Y8 |
y12 |
|
0 |
|
|
|
Y[n] := 1; |
|
Y5 |
y8 |
|
|
|||
|
|
|
|
|
|
|
|||
|
|
СТ := СТ+1; |
|
|
|
Y6 |
y9 |
|
|
|
1 |
СТ = n |
0 |
|
|
1 |
x4 |
0 |
|
|
|
|
|
|
|
|
184 |
||
Конец |
|
|
S := L (S); |
Yk |
Конец |
|
|
|
|
|
|
|
|
Y7 |
y10y11 |
||||
|
|
|
Y := L11(Y); |
|
|
Лекция 7. Устройство управления:
с жесткой логикой
Синтез микропрограммного автомата Мили
1.Формирование отмеченной ГСА;
2.Построение графа автомата.
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
y |
y |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|||||
|
|
x |
y |
|
4 |
|
|
|
|
|
a |
|
|
|
4 |
1 |
||||
|
|
|
3 |
|
|
|
|
|
|
|
1 |
|
|
|||||||
|
|
x |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
1 |
|
|
|
|
x1 |
|
|
|
|
|
|
x |
|
|
||||
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
y2 |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
x |
|
|
|
|
1x |
|
|||||||||
|
|
8 |
y1 |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
x1 |
2 |
|
|
|
|
2 |
y |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
y3 |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6y |
||||
x |
x |
|
|
y1 |
|
|
|
|
4 |
|
|
|
|
|
|
|
||||
a2 |
|
|
|
y |
|
|
|
|
|
|
|
7 |
||||||||
|
|
|
|
|
|
|
|
|
|
( |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
1 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
- |
|
|
|
|||
|
|
|
|
|
|
y |
3 |
|
|
|
|
|
) |
|
a5 |
|||||
|
|
x y |
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
3 |
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
y |
y |
|
|
|
|
|
|
|
|
|
|
|
x |
|
||||
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
4 |
|
|
|
|
|
|
|
|
|
5 |
|
|
|||||
|
|
|
|
x |
|
|
|
|
|
x |
|
|
|
|||||||
|
|
|
4 |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|||
|
|
x |
|
|
x |
1 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
x |
|
|
y |
y |
|
|
|
|
|
|
|
|
|
4 |
|
a3 |
|
|
|
|
|
|
y |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
5 |
6 |
7 |
a4 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
© С. Г. Мосин, 2007 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
Начало |
Y0 |
|
|
|
|
|
1 |
a1 |
|
|
|
|
|
x1 |
|
|
|
|
|
|
|
|
|
|
|
Y |
y1y2 |
|
0 |
|
|
|
1 |
|
|
x2 |
0 |
|
|
|
|
|
||
|
|
|
a2 |
|
|
|
|
|
1 |
1 |
Y7 |
y6y7 |
|
|
|
x3 |
||||
|
|
|
y1y3 |
Y |
||
|
|
|
0 |
|||
Y2 |
|
y4 |
|
|
5 |
|
|
|
|
|
|||
|
|
a3 |
0 |
|
|
|
|
|
x4 |
|
0 |
|
|
|
1 |
|
x1 |
|
|
|
|
|
|
|
a5 |
||
Y3 |
y5y6y7 |
1 |
|
Y6 |
||
|
y3y4 |
|||||
|
|
a4 |
|
|||
|
|
0 |
|
|
|
|
|
|
x5 |
|
|
|
|
|
1 |
Y4 |
y8 |
|
|
|
|
a1 |
|
|
|
|
|
Yk |
Конец |
|
|
|
|
|
185
Лекция 7. Устройство управления:
с жесткой логикой
Синтез микропрограммного автомата Мили
На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами а1, а2, … по следующим правилам:
1)Символом а1 отмечают вход вершины, следующей за начальной, и вход конечной вершины;
2)Входы всех вершин, следующих за операторными, должны быть отмечены.
3)Если вход вершины отмечают, то только одним символом;
4)Входы различных вершин, за исключением конечной,
отмечают различными символами. |
186 |
© С. Г. Мосин, 2007 |
|
Лекция 7. Устройство управления:
с жесткой логикой
Синтез микропрограммного автомата Мили
Если идти от одной отметки аm к другой отметке as в
направлении ориентации дуг ГСА, то получаем слова вида:
amxmem11...xmRemRYtas
или
a |
m |
xem1 |
...xemR a |
, |
|
m1 |
mR 1 |
|
которые называют путями перехода.
© С. Г. Мосин, 2007
Y2
Y3
Yk
|
|
|
Начало |
Y0 |
||
|
|
|
1 |
a1 |
|
|
|
|
|
x1 |
|
|
|
|
|
|
|
|
|
|
|
Y1 |
y1y2 |
|
0 |
0 |
|
|
|
|
|
x2 |
||
|
|
a2 |
|
|
|
|
|
1 |
1 |
Y7 |
|
y6y7 |
|
|
x3 |
|
||||
|
|
y1y3 |
Y |
|
||
|
y4 |
0 |
5 |
|||
|
|
|
|
|||
|
|
|
|
|
||
|
a3 |
0 |
|
|
|
|
|
x4 |
|
|
|
|
|
|
|
0 |
|
|
|
|
1 |
|
x1 |
|
|
|
|
|
|
|
|
a5 |
||
y5y6y7 |
1 |
|
Y6 |
|
||
|
|
y3y4 |
||||
|
a4 |
|
|
|||
|
0 |
|
|
|
|
|
|
x5 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
Y4 |
y8 |
|
|
|
|
a1 |
|
|
|
|
|
187 |
Конец |
|
|
|
|
|
|
Лекция 7. Устройство управления:
с жесткой логикой
Синтез микропрограммного автомата Мили Правила построения автомата Мили по ГСА:
1. Найти все пути перехода в ГСА. Если при некотором r есть несколько вхождений символа xr в путь перехода, то оставляют только один символ xr.
2. Если при некотором r в путь перехода входят как xr, так xr , то такой путь перехода не рассматривают.
3. Каждому пути перехода amX(am,as)Y(am,as)as ставят в соответствие переход автомата S из состояния аm в состояние as под действием входного сигнала X(аm, as) с выдачей выходного сигнала Y(аm, as).
188
© С. Г. Мосин, 2007
Лекция 7. Устройство управления:
с жесткой логикой
Синтез микропрограммного автомата Мили Правила построения автомата Мили по ГСА:
4.Каждому пути перехода amY(am,as)as ставят в соответствие переход автомата S из состояния аm в состояние as с выдачей выходного сигнала Y(аm, as).
5.Каждому пути перехода amX(am,a1)a1 ставят в соответствие переход автомата S из состояния аm в состояние a1 с выдачей выходного сигнала Y0 (пустой оператор).
189
© С. Г. Мосин, 2007
Лекция 7. Устройство управления:
с жесткой логикой
Синтез микропрограммного автомата Мили Правила построения автомата Мили по ГСА:
В результате выполнения пунктов 1 – 5 строят граф автомата Мили S, содержащий столько состояний, сколько было использовано отметок входов вершин ГСА.
Для автомата, построенного по ГСА, всегда выполняется
необходимое условие детерминированной работы – любое попарное произведение входных сигналов, вызывающих переход из некоторого состояния автомата, равно нулю.
190
© С. Г. Мосин, 2007