ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 121
Скачиваний: 0
Таблица 5-6
Разбиение nL на классы I-эквивалентных состояний автомата Мили
— --- ----------- |
|
|
|
|
|
Класс |
Исходное |
Класс |
Входном сигнал |
Выходной |
|
эквива |
состояние |
перехода |
сигнал |
||
лентности |
|
|
|
|
|
|
|
В 2 |
*1*2 |
Уі |
|
|
Оі |
в 2 |
*1*.| |
} |
3 |
|
В 2 |
*1*2 |
к |
2 |
|
Ві |
|
В 1 |
*1*4 |
к 0 |
|
|
|
|
|
|
|
До
в г
°3
0.1 '
Об
в 3
О?
08
в 4
а0
в2
В2
В,
Ві
в 3
5.1
В3
Ві
В3
В3
В3
Ві
в2
Ві
В 2 Ві
Ві
Ві
ХіЛ *2
' *!*4
*1*2
*1*4
*4*3 . *4*3 *4*3 *4*3
хз
*3
*3
хя
*4
хі
Х4
,хА
1
1
Уі
Y 3
К2
Ко
Y ъ
Yi
Кв К4
Кв К4
Кв
К4
Кз
Кв
Кз
Кв
Кх
Уі
Для минимизации микропрограммного автомата Мура необходимо предварительно найти разбиение множества состояний на классы О-эквивалентности. В каждый такой класс попадут состояния, отме ченные одинаковой микрокомандой. Далее процесс минимизации пол ностью совпадает с минимизацией микропрограммных автоматов Мили.
4* |
83 |
|
Таблица 5-7
Разбиение я 2 на классы 2-эквивалентных состояний автомата Мили
Класс эквивалент ности
^ 1
С а
С ,
^ 4
^ 5
Исходное |
Класс |
Входной сигнал |
Выходной |
СОСТОЯ!!ие |
перехода |
сигнал |
«1
Ö5
о2
о4
оэ
Об
а-
«8
«0
с 2
С3 С,
Сх
С2
Сз
с 2
Сх
С4
с5
с6
С4
с5
с4
С 4
с 2
С 5
^ 2
Cs
Сх
Сх
х 1х 2
Хх-Ч
Х].Т2
Х1А'1
А*ХА*2
ХХХЛ
AjA’o
•V'lx 4
А.|А'д
ата'я
Ä4A3
x t x 3
х 3
хз
х 3
Хз
Хі
Хі
x t
Xi
1
1
V'l
5"з
У 2
Y,
Y X
У з
Y 2
^ 0
п
Y і
Ys
Y i
Ys
Y i
Ys
Yi
Y 3
Y s
Y3
Y 5
Y i
Y x
Таблица 5-8
Таблица переходов минимального автомата Мили
Исходное |
Состояние |
Входной сигнал |
Выходной |
состояние |
перехода |
сигнал |
|
|
o 4 |
ATА2 |
Ух |
«1 |
Оз |
|
Уз |
|
ХхХ2 |
Y 2 |
|
|
|
||
|
Ol |
Х1ХІ |
У* |
84
|
|
|
Продолжение |
|
Исходное |
Состояние |
Входной сигнал |
Выходной |
|
состояние |
перехода |
сигнал |
||
Яз |
ав |
Л'з |
7 5 |
|
ав |
Y* |
|||
а л |
ав |
Х Я |
Ye |
|
°8 |
х 3 |
Д |
||
|
||||
а в |
а А |
Хі |
Y3 |
|
а8 |
Хі |
Y 5 |
||
|
||||
ÜQ |
Оі |
1 |
Д |
5 - 5 . Кодирование состояний микропрограммного автомата
Модификация алгоритма противогоночного кодирования развязы ванием пар переходов, изложенная в § 3-2, может быть использована при кодировании состояний микропрограммных автоматов. В случае абстрактного автомата развязыванию подлежат все пары переходов (іат , а5), (ак, at), происходящих под действием одного и того же вход ного сигнала zf. Очевидно, что аналогом этого в случае микропрограмм
ного автомата |
будет следующее утверждение. Пусть |
(ат, as) |
и (ak, |
|||
а.[) — пара |
переходов, |
происходящих |
под действием |
входных |
сигна |
|
лов X (ат, |
а$) |
и X (ak, |
at). Эта пара |
переходов во избежание |
гонок |
|
должна быть развязана, если X (ат, as) Д X (ak, а,) Ф 0, т. е. сущест вует по крайней мере один набор значений входных переменных, на котором обе функции X (ат, as) и X (ak, а,) принимают значение еди ницы.
Используя это утверждение с учетом сноски на стр. 42 относи тельно синхронных автоматов, согласно которой не подлежат развя
зыванию пары (ат, as), (ak, at), если (am, as) П [я*. ai) =k 0 . Для автомата в табл. 5-8 найдем все пары переходов, которые должны быть развязаны:
[(a2, |
a.i), (а3, ae)], |
[(аь |
а4), |
(а„, |
а8)], [(аь а3), |
(аі, |
а0)]. [(Яі, |
а3), |
|
|
(а4, а8)Ь К«і. |
аз)> |
(ав, |
а4)], |
[(«і, |
ад, (а3, |
а„)], |
|
|
[(аі, |
ai), (0 4 , ав)1 , |
[(%, ад, |
(а4, |
а8)], |
[(аь ад, |
(а„, а8)], |
|
||
|
l(fls, |
ав), |
(Cg, |
а 2)], |
[(Оз, ав), (а4, |
а8)], |
[(а4, а8), |
(ав, а2)]. |
|
После развязывания получаем недоопределенную таблицу кодов
(табл. 5-9).
Минимизация числа разрядов в кодах оказалась невозможной, и после доопределения кода состояния а3 получаем таблицу кодиро
85
вания микропрограммного автомата (табл. 5-10), в котором гонки ис ключены.
|
|
|
Таблица 5-9 |
|
|
|
Таблица 5-10 |
||
Кодирование после развязывания |
|
Противогоночное |
|
||||||
|
пар переходов |
|
|
кодирование |
|
||||
|
И |
Ч |
т3 |
И |
|
Ч |
To |
Ь |
4 |
«1 |
0 |
0 |
1 |
1 |
Оі |
0 |
0 |
1 |
1 |
о3 |
I |
0 |
0 |
— |
Оз |
I |
0 |
0 |
0 |
“4 |
0 |
1 |
1 |
0 |
0.1 |
0 |
1 |
1 |
0 |
°в |
1 |
1 |
0 |
0 |
Oß |
1 |
1 |
0 |
0 |
a S |
1 |
1 |
1 |
1 |
а8 |
1 |
1 |
1 |
1 |
Методы кодирования состоянии с учетом сложности комбинационной схемы, изложенные в 5 3-3, без каких-либо изменении переносятся на микропрограмм ные автоматы. В качестве еще одного примера кодирования, минимизирующего суммарное число изменений элементов памяти на всех переходах, закодируем состояния того же автомата в табл. 5-8. Его матрица пар переходов1
|
|
|
1 |
3 |
|
|
|
|
|
|
|
1 |
4 |
|
|
|
|
|
|
|
3 |
6 |
|
|
|
|
|
|
|
4 |
6 |
|
|
|
|
|
|
|
4 |
8 |
|
|
|
|
|
|
|
6 |
4 |
|
|
|
|
|
|
|
6 |
8 |
|
|
|
|
|
|
|
8 |
I |
|
|
|
|
Положим Кі = 000; |
/С3 = |
001: |
|
|
|
|
|
|
|
|
|
Т2Т3 |
|
|
|
||
|
|
00 |
01 |
|
II 10 |
|
||
|
0 |
1 |
3 |
|
|
|
|
|
|
Ті |
|
|
|
|
|
|
|
|
I |
|
|
|
|
|
|
|
После вычеркивания первой строчки в матрице М : |
|
|||||||
1 |
4 |
|
|
|
|
|
|
|
3 |
6 |
|
|
|
1 |
4 |
|
|
4 |
6 |
|
|
|
|
|||
7=4; /И4 |
4 |
6 |
|
|||||
■М' = 4 |
8 |
04= (П; |
||||||
4 |
8 |
|||||||
6 |
4 |
|
|
|
|
|||
|
|
|
6 |
4 |
|
|||
6 |
8 |
|
|
|
|
|||
|
|
|
|
|
|
|||
8 |
1 |
|
|
|
|
|
|
|
С} ={100, |
010); |
D' = |
c J={100, 010); |
|||||
1 Все обозначения взяты из § 3-3.
86