Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

Ц7100 = 110Ö — OOOj-= 1; r ül0 = 1010 — 000|2 = I . Выбираем /С4 = 1 0 0 :

00 01 11 10

И

После удаления закодированных пар из матрицы М' имеем новую матрицу:

ToTg

00 01 11 10

о1

По матрице М определяем число k, характеризующее качество кодирова­ ния. В числителе дроби записываем сумму кодовых расстояний для каждой пары матрицы М, а в знаменателе — число строчек этой матрицы:

87

5-6. Синтез микропрограммного С-автомата

В первой главе было определено, что в абстрактном С-автомате

При переходе к структурному С-автомату каждый выходной сиг­

но позволяет существенно приблизить модель к реальным физическим задачам.

Поведение устройства, моделью которого является С-автомат, бу­ дем описывать с помощью граф-схем алгоритмов. В этих ГСА внутри операторных вершин наряду с элементами множества У — jt/j, . . . , уп, . . . , yN) — короткими микрооперациями могут записываться элементы множества R = . . . , rq...........Гд) — длинные микро­ операции. Таким образом, каждой операторной вершине ГСА соот­ ветствует пара микрокоманд Yt, Rj (У,- С У, R С R), причем микро­ команда У,- выдается на переходе автомата из одного состояния в дру­ гое, а Rj — в течение всего времени нахождения автомата в состоянии,- соответствующем Rj. Описание работы микропрограммного С-авто- мата поясним на примере рис. 5-9. Приведенная ГСА имеет одну на­ чальную, одну конечную, 7 условных и 9 операторных вершин. Так как для этой ГСА X = [ху, . . . , х6\, У = \уъ . . . , r/6), R = {гу, . . .,

88

Лі), то у соответствующего автомата должно быть пять входных кана­ лов (не считая канала от ГСИ), шесть выходных каналов для коротких

сигналах все компоненты равны нулю. Для простоты в случае выпол­

лишь те компоненты, которые в структурном выходном сигнале при­ нимают значение единицы. Используя такое допущение, можно ска­ зать, что при выполнении микрокоманд У0 и R 0 выходные сигналы не выдаются.

С начальной вершиной ГСА (рис. 5-9) сопоставляется некоторое начальное состояние дискретного устройства, при котором выпол­

то при р = 1 автомат выдаст сигнал ув и перейдет в другое состояние,

как и в случае автомата Мили, входы всех вершин, следующих за начальной и операторными, а также вход конечной вершины отме­ чаются символами аи . . . , ат, . . . , ам . Далее эти отметки отождест­ вляются с состояниями автомата Мили S', который также будем за­ давать обратной таблицей переходов. Очевидно, что автомат S' (табл. 5-11), построенный по рис. 5-9, не учитывает наличия двух ти­ пов микрокоманд, У) и R / . 1

Рассмотрим сначала синтез С-автомата по граф-схеме, в которой внутри операторных вершин, непосредственно предшествующих ко­ нечной, нет длинных микрокоманд.

1 Символы Qi и Q., на рис. 5-9 потребуются в шестой главе.

89

Каждому состоянию as (s= 1, . . . , 4) из второго столбца табл. 5-11 поставим в соответствие Bs — множество всевозможных пар вида (as, Rj), где — длинная микрокоманда, записанная в массиве пе­ реходов в состояние as:

ЯоЖ ®2= ((^2і Тг), (О.т, /'l), (во, Ro)l

В з — {(аз> гз)< (Оз, (Т8, г4))}'> B i= [(ai> Ro)).

Будем говорить, что состояние as порождает множество Bs. Пере­ нумеровав различные пары символами Ьъ Ьй, . . . , получим множество

4

В = U Bs= [blt . . . , £>,}. В пятом столбце табл. 5-11 запишем сим-

сигнала Y t. Табл. 5-12 есть обратная таблица переходов С-автомата, построенного по табл. 5-11. Выходной сигнал типа Rj записан рядом с соответствующим состоянием bj.

Остановимся теперь на случае, когда перед конечной могут стоять операторные вершины, в которых записаны длинные микрокоманды.

90

Пусть, например, при построении автомата S' по некоторой граф-схеме получена обратная таблица переходов, часть которой приведена в табл. 5-13.

При построении С-автомата и в этом случае можно было бы по­ ступить так, как изложено выше, т. е. из множества состояний Вх = = [Ьъ Ь2, Ь3\, порождаемых ах, задать переходы в 612 под действием

сигнала х5х'4. Однако соображения практического характера часто требуют, чтобы автомат после реализации некоторого пути по ГСА от

91