Загрузка...

Баранов. Введение в теорию автоматов.


Глава третья

КОДИРОВАНИЕ СОСТОЯНИЙ АВТОМАТА

3-1. Гонки в автомате

Как уже отмечалось во второй главе, задача кодирования состоя­ний является одной из основных задач канонического метода струк­турного синтеза автоматов. Напомним, что кодирование заключается в сопоставлении с каждым состоянием автомата набора состояний эле­ментарных автоматов памяти одинаковой длины I (в данном параграфе для простоты ограничимся использованием в качестве элемен­тов памяти триггеров с раздельными входами, которые будем обозна­чать (Т1, …, Ti, …, TI). При кодировании разным состояниям автомата соответствуют разные коды. Так как триггер с раздельными входами может находиться в двух различных состояниях, 0 и 1, то очевидно, что для автомата с М состояниями минимальная длина кода равна .

Переход автомата из одного состояния в другое осу­ществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния ат с кодом 0101 в состояние as с ко­дом 1001, это означает, что триггер T1 переходит из состояния 0 в со­стояние 1, триггер T2 – из состояния 1 в состояние 0, а состояния триггеров Т3
и T4 не изменяются.

Рис. 3-1. Состязания между элементами памяти:

а – некритические, б – критические

При функционировании автомата могут появиться так называе­мые состязания. Явление состязаний возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие вре­мена срабатывания. Кроме того, различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных авто­матов по логическим цепям, имеющим неодинаковую длину. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти со­стязания, т. е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах неко­торых запоминающих элементов до того, как другие участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния ат в состояние as под дейст­вием входного сигнала zf автомат может оказаться в некотором про­межуточном состоянии ak или al в зависимости от того, какой элемент памяти выиграет состязания. Если затем при том же входном сигнале автомат из ak и aj перейдет в состояние as (рис. 3-1, а), то такие со­стязания являются допустимыми, или некритическими. Если же в этом автомате есть переход, например, из ak в  под действием того же сигнала zf (рис. 3-1, б), то автомат может перейти в аj,а не в as и правильность его работы тем самым будет нарушена. Такие состязания называются критическими состязаниями или гонками. При кодировании состояний гонки должны быть устранены. Кодирование с устранением гонок называется противогоночным.

Один из способов ликвидации гонок состоит в тактировании вход­ных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных каналов х1, …, xL имеется еще один канал р от генератора синхроимпульсов (ГСИ), по которому поступает сигнал р = 1 в момент прихода импульса и р = 0 при его отсутствии. В связи с этим входным сигналом на переходе (ат, as) будет не zf, a pzf. Тогда если длительность импульса tp меньше самого короткого пути прохождения тактированного сиг­нала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние ak (рис. 3-1, б) сигнал р равен нулю и, следова­тельно, pzf = 0, что и исключает гонки.

Рис. 3-2. Двойная память

Другой способ ликвидации гонок заключается во введении двойной памяти (рис. 3-2). В этом случае каждый элемент памяти дублируется, при­чем перепись из нижнего элемента памяти в верхний происходит в момент отсутствия тактирующего импульса (р = 0). Сигналы обратной связи для получения функций возбуждения и функций вы­ходов автомата снимаются с верхнего ряда тригге­ров. Таким образом, состязания могут возник­нуть только между нижними триггерами, сигналы обратной связи не смогут измениться до тех пор, пока р не станет равным нулю. Но тогда входной сигнал pzf также равен нулю, а потому гонок быть не может.

Наряду с аппаратурными способами для устранения гонок могут использоваться специальные методы кодирования.

3-2. Противогоночное кодирование состояний

Пусть  и  – две пары двоичных кодов длины I. Пары   и  называются развязанными, если при некотором i  i-й разряд кода принимает одно значение на паре  и противопо­ложное – на паре . В противном случае пары двоичных кодов  и  называются связанными. В работе [15] доказана следую­щая теорема: в автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (ат, as) и (ak, al),  происхо­дящих под действием одного и того же входного сигнала, соответствую­щие пары кодов состояний развязаны (Эта теорема доказана применительно к асинхронным автоматам. Если рассматривать синхронную модель, а устойчивость автомата обеспечивать ка­ким-либо, аппаратным способом, то условие  может быть заменено более сильным: развязывать нужно пары переходов, для которых ). В этой же работе приведен ос­нованный на этой теореме алгоритм противогоночного кодирования состояний конечных автоматов, основная идея которого достаточно проста: последовательно просматривая все пары переходов, для ко­торых имеется хотя бы один общий входной сигнал, осуществляющий эти переходы, следует присвоить разрядам кодов такие значения, чтобы соответствующие пары кодов состояний были развязаны.

Алгоритм противогоночного кодирования заключается в последо­вательном развязывании подлежащих развязыванию пар переходов. На промежуточных этапах алгоритма состояниям автомата будут со­ответствовать коды, значения некоторых разрядов которых могут быть не определены. Такие коды будем называть неполными. В дальнейшем неопределенные разряды кодов отмечаются черточкой. Пусть (ат, as), (ak, al) – пара переходов автомата S, а  – соответственно четверка кодов (быть может, неполных) состояний ат, as, ak, al длины i. Операция развязывания пары переходов (ат, as), (ak, al) сводится к следующему:

1. Положить i = 0. Перейти к п. 2.

2. Если i = 0, то переход к п. 8, иначе переход к п. 3.

3. Если при некотором r  значения r-го разряда чет­верки  образуют набор 0011 или набор 1100, то переход к п. 9, иначе переход к п. 4.

4. Если при некотором r  значения r-го разряда четверки  образуют один из наборов

,

то переход к п. 5, иначе к п. 6.

5. Доопределить неопределенные значения r-го разряда четверки  так, чтобы его значения образовывали набор 0011. Переход к п. 9.

6. Если при некотором r  значения r-го  разряда чет­верки  образуют один из наборов

,

то переход к п. 7, иначе переход к п. 8.

7. Доопределить неопределенные значения r-го разряда четверки  так, чтобы значения этого разряда образовывали набор 1100. Переход к п. 9.

8. Дополнить коды состояний автомата одним неопределенным раз­рядом. Увеличить r на единицу. Переход к п. 4.

9.  Пара переходов (ат, as), (ak, al) развязана.   Конец.

Длина кода, получаемого в результате применения изложенного алгоритма, в большинстве случаев оказывается неминимальной, так как при введении нового разряда кода могут развязываться пары пе­реходов, которые уже были развязаны ранее. В связи с этим жела­тельно минимизировать длину получаемых кодов состояний, что де-лаетея следующим образом. Исключаем один из разрядов кодов, в ре­зультате чего некоторые пары переходов могут оказаться связанными, и применяем алгоритм развязывания пар переходов. После этого ис­ключаем еще один разряд, вновь применяем алгоритм противогоноч-ного кодирования и т. д. до тех пор, пока длина кода не перестанет уменьшаться. Если в результате работы алгоритма значения не всех разрядов будут определены, то их можно доопределить произвольно.

Проиллюстрируем алгоритм противогоночного кодирования на примере автомата, функция переходов которого задана табл. 3-1.

Таблица 3-1. Таблица переходов частичного автомата

a1

a2

a3

a4

a5

a6

a7

z1

z2

z3

a2

a1

a2

a3

a5

a4

a3

a7

a4

a1

a6

a3

a5

a6

a7

Очевидно, что пары  должны  быть  развязаны в каждом из массивов пере­ходов   М1, М2, M3, происходящих под действием сигналов z1, z2, z3.

Развязывание пар переходов в М1
начнем с первого перехода (a1, a2). Со­гласно сформулированной выше теореме пару (а1, а2)
и (а2, а2) развязывать не надо из-за совпадения состояний перехода. Первая пара переходов, которая подлежит развязыванию, есть (а1, а2), (а3, а4). Вводим переменную  и образуем по этой переменной четверку (0011) для состояний а1, а2, а3, а4. Рассматривае­мая пара переходов развязана (табл. 3-2).

Паре переходов (a1, a2), (а4, а4) соответствует четверка (0011) (см. табл. 3-2), т.е. эта пара тоже развязана.

Пара (а1, а2), (а5, a6) образует четверку (00—). Для развязывания этой пары доопределим эту четверку до (0011), для чего состояниям а5, a6 ставим в со­ответствие  (табл. 3-3).

Таблица 3-2. Развязывание пары (a1, a2), (а3, а4)

a1

a2

a3

a4

a5

a6

a7

0

0

1

1

Таблица 3-3. Развязывание пары (а1, а2), (а5, а6)

a1

a2

a3

a4

a5

a6

a7

0

0

1

1

1

1

Из табл. 3-3 видно, что пара (а1, а2), (а5, а6) развязана [(четверка (0011)]. Точно так же развязаны пары, образованные переходом (а2, а2) и всеми после­дующими переходами в M1. Обратимся к паре (а3, а4), (а5, а6). Из табл. 3-3 по­лучаем соответствующую четверку (1111)пара не развязана. Вводим пере­менную  и полагаем для а3
и а4 значение , а для а5 и а6
 (табл. 3-4).

Таблица 3-4. Развязывание пары (a3, a4), (a5, a6)

a1

a2

a3

a4

a5

a6

a7

0

0

1

1

1

1

0

0

1

1

Таблица 3-5. Развязывание пар переходов в массиве М2

a1

a2

a3

a4

a5

a6

a7

0

0

1

1

1

1

1

0

0

0

1

1

1

0

0

1

0

Таблица 3-6. Развязывание пар переходов в массиве М3

a1

a2

a3

a4

a5

a6

a7

0

0

1

1

1

1

1

0

0

0

1

1

0

1

0

0

1

0

0

1

0

1

После этого остальные переходы в М1
тоже развязаны. Аналогично для М2 и M3 получим табл. 3-5 и 3-6.

Переходим к минимизации. Исключаем переменную  (табл. 3-7) и повто­ряем процесс развязывания пар переходов.

Таблица 3-7. Исключение переменной

a1

a2

a3

a4

a5

a6

a7

1

0

0

0

1

1

0

1

0

0

1

0

0

1

1

0

Таблица 3-8. Развязывание пар перехода без

a1

a2

a3

a4

a5

a6

a7

1

0

0

0

1

1

0

1

0

0

1

0

0

0

1

1

0

1

0

0

1

1

Оказывается, что пара (а1, а2), (а5, a6) не развязана, в связи с чем добавляем переменную  и развязываем эту пару (табл. 3-8).

Таблица 3-9. Исключение переменной

a1

a2

a3

a4

a5

a6

a7

1

0

0

1

0

0

0

1

1

0

0

1

0

0

1

1

Таблица 3-10. Результат противогоночного кодирования

a1

a2

a3

a4

a5

a6

a7

1

0

0

1

0

1

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

Все остальные пары развязаны. Далее исключаем переменную  и полу­чаем табл. 3-9 с тремя переменными , в которой после проверки оказы­ваются развязанными все пары.

Рис. 3-3. Графы, не допускающие сосед­него кодирования

Дальнейшая минимизация невозможна, так как для кодиро­вания семи состояний нужно не менее трех переменных. После доопределения прочерков в табл. 3-9 получаем табл. 3-10 противо­гоночного кодирования состояний исходного автомата.

Существует один частный способ кодирования – сосед­нее кодирование состояний автомата, при котором усло­вие отсутствия гонок всегда выполнено. При соседнем ко­дировании любые два состояния, связанные дугой на графе автомата, кодируются наборами, отлича­ющимися состояниями лишь одного элемента памяти. Существует не­сколько алгоритмов соседнего кодирования, один из которых приве­ден в [10].

Соседнее кодирование, однако, не всегда возможно. В работе [14] сформулированы требования к графу автомата, допускающего сосед­нее кодирование:

1. В графе автомата не должно быть циклов с нечетным числом вершин.

2. Два соседних состояния второго порядка не должны иметь бо­лее двух состояний, лежащих между ними. При этом под состояниями второго порядка понимаются два состояния, путь между которыми по графу автомата состоит из двух ребер (независимо от ориентации).

Нa рис. 3-3 приведены два графа, которые не удовлетворяют этим требованиям и не могут быть закодированы соседними кодами.

Таким образом, имеются 4 способа устранения гонок: 1) двойная память; 2) рациональный выбор длительности синхроимпульсов; 3) развязывание пар переходов; 4) соседнее кодирование.

Глава четвертая

ГРАФ-СХЕМЫ АЛГОРИТМОВ

4-1. Микропрограммы работы дискретных устройств

При описании работы широкого класса дискретных систем автома­тики, вычислительной техники и телефонии в большинстве случаев оказывается удобным представить эти системы в виде двух частей: операционного устройства и устройства управления. Так, в вычисли­тельной машине к операционному устройству относят блоки памяти, регистры, сумматоры, каналы передачи информации, шифраторы и дешифраторы, а к устройству управления – ту часть машины, кото­рая, координируя действия всех перечисленных устройств, определяет последовательность переработки информации. Задачей устройства управления является, таким образом, выработка распределенной во времени последовательности управляющих сигналов, под воздейст­вием которых в операционном устройстве осуществляется некоторая операция. Иногда целесообразно многоступенчатое представление дискретной системы. Так, в одних случаях, например при проектиро­вании центрального устройства управления ЦВМ, арифметическое устройство (АУ) в целом рассматривается как часть операционного устройства, тогда как при проектировании самого АУ в нем выде­ляется свой автомат управления, а к операционной части АУ отно­сятся его регистры, сумматор, регистр кодов арифметических опера­ций и счетчик сдвигов.

Задача синтеза операционных устройств вследствие их регуляр­ности и большой повторяемости в настоящее время хорошо изучена и не представляет серьезных трудностей. Иначе обстоит дело с уст­ройством управления, которое является наименее регулярной частью дискретной системы и совершенно не повторяется при переходе от од­ной системы к другой. В связи с этим проектирование устройства уп­равления представляет наибольшую сложность и, более того, часто проектирование системы после выбора основных частей операцион­ного устройства сводится, в основном, к проектированию устройства управления.

Порядок выполнения операций в дискретном устройстве опреде­ляется микропрограммой, представляющей собой совокупность мик­роопераций и логических условий. Под микрооперацией мы будем понимать элементарный процесс переработки информации в дискрет­ной системе или какой-либо ее части, происходящий за время одного такта работы автомата (промежуток между двумя последовательными моментами дискретного автоматного времени) [7]. Для выполнения той или иной микрооперации устройство управления должно выраба­тывать управляющие сигналы, которые будем называть сигналами микроопераций и обозначать строчными буквами с индексами: y1, …, yn, …, yN. Если в устройстве одновременно реализуется несколько микроопераций, то это множество микроопераций назовем микроко­мандой и будем обозначать прописной буквой Y с индексами. Так, если Yt = {уt1, …, уtu, …, ytU} микрокоманда, то микрооперации уt1, …, ytu, …, уtU выполняются одновременно в один и тот же момент автоматного времени. При U = 1 микрокоманда Yt со­стоит из одной микрооперации. Не исключен случай U = О, когда множество микроопераций, образующих микрокоманду, пусто. Микро­команду, состоящую из пустого множества микроопераций, будем обо­значать символом Y0. Реализация такой микрокоманды равносильна отсутствию выполнения каких-либо элементарных операций. В слу­чае синхронных дискретных устройств микрокоманду Y0 удобно ин­терпретировать как пропуск такта, когда не поступают никакие сиг­налы от устройства управления к операционному устройству.

Выполнение микропрограммы состоит в последовательном выпол­нении отдельных микрокоманд. Эта последовательность определяется булевыми функциями  множества двоичных переменных X = {х1, …, xl, …, xL}, поступающих на вход устройства управле­ния. Если в микропрограмме все микрокоманды различны (а если это не так, то их всегда можно перенумеровать), то каждой паре микро­команд Yi, Yj (не исключен случай i = j) соответствует функция  равенство единице которой разрешает выполнение микрокоманды Yj после завершения выполнения микрокоманды Yi. Очевидно, что среди множества функций .(R – число различных микроко­манд в микропрограмме) в каждый момент времени не может быть бо­лее одной, равной единице. В противном случае процесс реализации микропрограммы не был бы детерминированным, т. е. нельзя было бы с определенностью сказать, какая из микрокоманд будет выполняться в следующий момент времени после микрокоманды Yi.

Для записи микропрограмм работы дискретных устройств будем использовать язык граф-схем алгоритмов и логических схем алго­ритмов.

4-2. Граф-схемы алгоритмов

Граф-схема алгоритма (ГСА) – ориентированный связный граф, содержащий вершины четырех типов: начальную, конечную, опера­торную и условную (рис. 4-1).

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. Начальная и операторные вершины имеют по одному выходу, а условная – два выхода, поме­ченных символами 1 и 0. Конечная вершина выходов не имеет. ГСА удовлетворяет следующим условиям:

1.  Содержит конечное число вершин, каждая из которых принад­лежит одному из перечисленных выше типов.

2.  Имеет одну начальную и одну конечную вершины.

3.  Входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу.

4.   Каждый выход соединен только с одним входом.

5.  Любой вход соединяется по крайней мере с одним выходом.

6., Для любой вершины графа существует по крайней мере один

путь из этой вершины к конечной вершине.

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

8.  В каждой условной вершине записывается один из элементов множества X = {х1,, xl, …, xL}, называемого множеством ло­гических условий. Разрешается в различных условных вершинах за­пись одинаковых элементов множества X.

9.  В каждой операторной вершине записывается оператор (микро­команда) Yt – подмножество множества Y = {y1, …, уп, …, yN}, называемого множеством микроопераций:

.

При U = 0 Yt = , что допустимо. Разрешается также запись в различных операторных вершинах одинаковых подмножеств мно­жества микроопераций.

При большом числе дуг, приходящих на один вход вершины, на­глядность графического изображения может потеряться, в связи с чем позволим изображать дуги, входящие в вершины, так, как показано на рис. 4-2.

Рис.  4-1.  Вершины ГСА

Рис. 4-2. Допустимое изображение вершин ГСА

Пример ГСА, содержащей 16 условных и 11 операторных вершин, приведен на рис. 4-3.

Предположим, что в операторных вершинах ГСА записаны опера­торы Y1, …, YT – все разные, так что операторную вершину можно отождествить с записанным в ней оператором. Начальной вершине поставим в соответствие оператор Y0, а конечный – YT+1. Пусть в ГСА имеется путь из вершины Yi (i = 0, 1, …, Т) в вершину Yj (j = 1, …, T+1) вида

      (4-1)

проходящий только через условные вершины рi1, …, piR.

Очевидно, что каждому такому пути соответствует конъюнкция , где  – логическое условие, за­писанное в условной вершине pir;  – символ, приписан­ный выходу условной вершины pir через который проходит путь (4-1); ; .

Если между вершинами Yi и Yj имеется несколько (например, H) путей, проходящих через условные вершины, то  равно дизъюнкции конъюнкций, соответствующих всем путям, т.е. , где  – конъюнкция, соответствующая h-му пути из Yi в Yj. Назо­вем  функцией перехода от оператора (микрокоманды) Yi к опера­тору (микрокоманде) Yj.

Очевидно, что множество функций  является ортогональным  и полным . Полное ортогональное множество функций называют нормальным [8].

Всевозможные наборы значений переменных x1, …, xL обозна­чим через . Определим процесс выполнения ГСА, начи­ная с оператора Y0 (начальный оператор) на произвольной бесконеч­ной последовательности наборов  следующим об­разом (в дальнейшем будем  предполагать, что значения логических условий x1 … xl могут изменяться только в моменты выполнения операторов):

Выписываем оператор Y0.

Рис. 4-3. Пример ГСА

Шаг 1. Придаем переменным x1 … xl значения из набора . Из множества функций перехода  выбираем функцию , принимающую значение единицы на этом наборе . В строчку рядом с Y0 записываем .

.

Шаг 2. Придаем переменным x1 … xl значения из набора . Из множества функций перехода  выбираем функцию , такую, что . В строчку ря­дом с  записываем :

 и т.д.

Пусть перед некоторым q-тым шагом имеем строчку операторов

.

Если на наборе  некоторая функция  равна единице , то в выписанную строчку операторов добавляем . Если оказывается, что , то в строчку вслед за  записываем  (конечный оператор) и процесс выполне­ния ГСА прекращается.

Строчка  называется значением ГСА на последовательности наборов .

Если каждому оператору Yt (t = 0, 1, …, Т + 1) граф-схемы поставлено в соответствие некоторое подмножество Bt логических ус­ловий, элементы которого могут изменяться во время выполнения опе­ратора Yt, то говорят, что задано распределение сдвигов. Распределе­ние сдвигов является дополнительной к ГСА информацией о логика-работы устройств, и эта дополнительная информация может быть ис­пользована для упрощения ГСА.

Пусть процесс выполнения ГСА рассматривается для некоторой последовательности наборов значений логических условий

и пусть набор  предшествует моменту выполнения оператора , а набор  устанавливается непосредственно после выполнения оператора . Последовательность наборов называется допустимой для ГСА при заданном распределении сдвигов, если всякий набор  либо совпадает с набором , либо отличается от него только значениями переменных из множества .

ГСА Г1 и Г2
равносильны при данном распределении сдвигов , если для всякой последовательности наборов, допустимой для ГСА Г1 или Г2
при этом распределении сдвигов, значения этих ГСА совпадают [4].

Описание работы дискретного устройства с помощью граф-схемы алгоритмов поясним на примере рис. 4-3. Приведенная ГСА Г имеет одну начальную, одну конечную, 16 условных и 11 операторных вер­шин. Так как для этой граф-схемы X = {x1, …, x8}, Y = {y1, …, y9}, то у соответствующего дискретного устройства должно быть 8 входных и 9 выходных каналов, т.е. предполагается, что для каждой микрооперации имеется выходной канал. В общем случае, если число микроопераций равно N, т.е. Y = {y1, …, уп, …, yN}, то каж­дому оператору Yt = {уt1, …, ytu, …, ytU}, представляющему подмножество множества микроопераций , соответствует век­торный выходной сигнал (y1, …, уп, …, yN), компоненты которого определяются следующим образом:

В частности, оператору Y0 соответствует выходной сигнал, у ко­торого для всех п = 1, …, N уп = 0 (у1 = … = yN = 0). Для простоты в случае выполнения оператора Yt будем говорить, что вы­даются выходные сигналы уt1, …, ytu, …, уtU, т.е. будем пере­числять лишь те компоненты, которые в соответствующем структур­ном выходном сигнале принимают значение единицы. Используя такое допущение, можно сказать, что при выполнении оператора Y0 выход­ные сигналы не выдаются.

Начальной вершине ГСА соответствует некоторое начальное со­стояние дискретного устройства, при котором выполняется оператор Y0. Если теперь идти из начальной вершины по граф-схеме в направ­лении ориентации дуг графа, выписывая при выходе из условной вер­шины по «1» логическое условие, стоящее в этой вершине, а при вы­ходе по «0» – его отрицание, то, пройдя путь х1, мы придем к опера­торной вершине, в которой записан оператор Y1 = {у1, у2}, путь , или , , .

Этому соответствует следующая работа дискретного устройства. Если в начальном состоянии на вход х1
придет сигнал, равный еди­нице (х1 = 1), то независимо от сигналов на остальных входных ка­налах устройство перейдет в некоторое новое состояние и на первом и втором выходных каналах появятся сигналы, равные единице (у1=  y2 = 1), а на остальных выходных каналах – сигналы, равные нулю. Согласно принятому выше допущению можно сказать, что уст­ройство выдаст выходные сигналы y1, y2, т.е. будет выполнен опера­тор Y1. Таким образом, , т.е. равняется конъюнкции содер­жимого условных вершин, лежащих на пути между вершинами Y0 и Y1 (с учетом выходов по «1» и «0»). Аналогично , , , , .

Остановимся еще на двух частных случаях соответствия между функциями перехода и путями в граф-схеме:

1.  После операторной вершины Y5 непосредственно следует опе­раторная вершина Y10. Поскольку путь между Y5 и Y10 содержит пустое множество условных вершин, а конъюнкция пустого множества логических переменных равна единице, то .

2.  После операторной вершины Y10 стоит условная вершина, один из выходов которой соединен с ее входом. Будем называть такие ус­ловные вершины возвратными. Между Y10
и Y11 есть два пути, в связи с чем . Так как ло­гическое условие , соответствующее второму пути, равно нулю,  фактически определяется только первым путем, поэтому в даль­нейшем будем учитывать лишь те пути через возвратную вершину, которые проходят через выход, не соединенный с ее входом, и будем считать, что на рис. 4-3 имеется один путь вида (4-1) из вершины Y10 в вершину Y11.

Очевидно также, что после оператора Y10 не может выполниться никакой оператор, до тех пор пока х3 не примет значение единицы, т. е. с помощью возвратной вершины можно описывать ожидание в работе дискретных устройств. В связи с этим будем иногда называть возвратную вершину ждущей вершиной.

4-3. Содержательные граф-схемы алгоритмов

Обычно при проектировании различных устройств предварительно составляется так называемая содержательная граф-схема алгоритма, в которой внутри условных и операторных вершин записаны не эле­менты множеств X и Y, а логические условия и микрооперации в со­держательных терминах.

В качестве примера рассмотрим алгоритм выполнения операции деления в арифметическом устройстве (АУ) параллельного действия с фиксированной запятой. АУ содержит накапливающий сумматор (), на котором до начала операции находится делимое, регистр Z (делитель) и регистр Y – на нем после завершения операции полу­чается частное. Проследим выполнение операции деления по содержа­тельной граф-схеме, изображенной на рис. 4-4.

В начале операции определяется знак частного. Если знаки дели­мого и делителя не совпадают (), в знаковый разряд результата (sign Y) записывается единица – частное отрицательно. Если знаки совпадают, то это действие пропускается. Далее сбрасы­ваются регистр Y, счетчик тактов (СТ) и знаковые разряды регистра Z и сумматора. Затем, если знак сумматора равен нулю (вначале он всегда равен нулю, так как в предыдущей микрокоманде его сбро­сили), из делимого вычитается делитель, для чего на сумматор подается обратный   код регистра Z ().  Если на первом такте (СТ = 0) после вычитания на сумматоре оказывается положительное число (), то делимое больше делителя, т.е. имеет место переполнение, и после записи единицы в триггер переполнения (ТП := 1) операция прекращается. Если же , то наращивается счетчик тактов (СТ := СТ + 1),   сумматор и регистр Y сдвигаются на 1 разряд влево ()
и начинается второй такт. Если после вычитания на некотором такте на сумматоре оказы­вается отрицательное число, то на следующем такте вместо вычитания содержимого регистра Z из содержимого сумматора производится их сложение (), т.е. реализуется операция деления без вос­становления остатка. Если на некотором такте, кроме первого, после вычитания на сумматоре получается положительное число (), то в младший п-й разряд результата записывается единица (Y[n] := 1). По прошествии n тактов (СТ = n) операция заканчи­вается. Результат деления записан в регистре Y.

Рис. 4-4. Содержательная ГСА операции деления

Рис. 4-5. ГСА операции деления

После построения содержательной ГСА логические условия и мик­рооперации кодируются символами x1, …, xl, …, xL и y1, …, уп, …, yN соответственно:

Условные вершины

Операторные вершины

,

,

,

,

,

,

,

,

,

,

,

,

,

,

При таком кодировании вершин содержательной ГСА, приведен­ной на рис. 4-4, получим ГСА, изображенную на рис. 4-5.

Глава пятая

СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ

ПО ГРАФ-СХЕМЕ АЛГОРИТМА

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

Конечный автомат, реализующий микропрограмму работы дискрет­ного  устройства,   принято  называть  микропрограммным  автоматом [6,8]. Синтез микропрограммного автомата по граф-схеме алгоритма осуществляется в два этапа:

1.  Получение отмеченной ГСА.

2.  Построение графа автомата.

На этапе получения отмеченной ГСА входы вершин, следующих за оператор­ными, отмечаем символами а1, а2, … по следующим правилам:

а) символом а1
отмечаем вход вершины, следующей  за начальной, а также вход конечной вершины;

б) входы всех вершин, следующих за операторными, должны быть отмечены;

в) если вход вершины отмечается, то только одним символом;

г) входы различных вершин, за исклю­чением конечной, отмечаются различными символами.

Ясно, что для проведения отметок по­требуется конечное число символов. Пред­положим для определенности, что для отметки входов вершин граф-схемы исполь­зовались символы а1, …, ат, …, аM. Результатом 1-го этапа является отме­ченная ГСА, которая служит основой для 2-го этапа – перехода к графу авто­мата.

Применение 1-го этапа к граф-схеме алгоритма операции деления Г на рис. 4-5 дает отмеченную ГСА, изображенную на рис. 5-1.

Если идти от одной отметки ат
к другой отметке as в направлении ориентации  дуг

ГСА, выписывая содержимое лежащих на этом пути вершин, то каждому такому пути можно поставить в соответствие слово в ал­фавите

где

.

Рис. 5-1. Отмеченная ГСА при синтезе автомата Мили

Чтобы подчеркнуть, что выписанное слово соответствует пути из ат в as, будем ограничивать это слово слева и справа символами ат и as соответственно.

В дальнейшем нас будут интересовать слова вида

             (5-1)

или

               (5-2)

Рис. 5-2. Условное изображение

пути перехода между ат и as:

 a – один путь, б – Н путей

Соответствующие этим словам пути на граф-схеме будем называть путями перехода. В пути вида (5-1) неисключен случай R = 0:

amYtas.                         (5-3)

Таким образом, путь вида (5-1) – это путь по ГСА из одной отметки ат в другую отметку as (допустимо аm = as), содержащий одну операторную вершину. Путь вида (5-2) – это путь из некоторой отметки ат в отметку а1
(недо­пустимо ат = а1), проходящий только через условные вершины.

Каждому пути (или слову) вида (5-1) или (5-2) можно поставить в соответствие конъюнкцию

.

Для краткости эти пути будем обозначать атХ (ат, as) Y (ат, as) as и атХ (ат, а1) а1, где Y (am, as) = Yt.

Схематично путь перехода из ат
в as можно изобразить так, как показано на рис. 5-2, а, где волнистая линия соответствует пути через условные вершины.

В тех случаях когда нас будет интересовать не конъюнкция вида , а некоторое множество тех же, что и в конъюнкции, букв {}, мы будем использовать для этого множества то же обозначение, что и для конъюнкции, но с тильдой. Так,

,

но

Может случиться, что между ат
и as имеется несколько путей вида amXh(am, as) Y (am, as) as (h = 1, …, Н), проходящих через одну и ту же операторную вершину (рис. 5-2, б). Будем считать, что этому множеству путей соответствует дизъюнкция , а само множество путей обозначать атХ (ат, as) Y (am, as) as, называя его обобщенным путем перехода.

После получения отмеченной ГСА построим граф автомата Мили S, состояниями которого являются а1, …, ат, …, аM, причем а1 – начальное состояние. Переходы и выходные сигналы в этом автомате определим следующим образом.

Находим все пути перехода на отмеченной ГСА. Если при некото­ром r (r=1, …, R) имеется   несколько вхождений символа  в путь перехода, то все символы , кроме одного, из этого пути уда­ляются. Если при_некотором r (r=1, …, R) в путь перехода входит как хr так и  то такой путь перехода в дальнейшем не рассмат­ривается.

Каждому пути перехода вида  поставим в соответствие переход автомата S из состояния ат в состояние as под действием входного сигнала X(am, as) выдачей выходного сигнала Y (am, as). Каждому пути пе­рехода вида  поставим в со­ответствие переход автомата 5 из состояния ат в состояние as, где ат и as определяются так же, как и раньше. Входной сигнал на этом переходе также равен конъюнкции содержимого условных вершин в этом пути. Так как множество условных вершин в данном случае пусто, а конъюнкция пустого множества переменных равна единице, то соответствующий входной сигнал полагаем равным единице, а вы­ходной сигнал, как и раньше, Y (am, as).

Каждому пути перехода вида атХ (ат, а1) а1 ставим в соответст­вие переход из ат в а1. При этом ат и входной сигнал определяются, как и раньше, а выходной сигнал полагаем равным Y0 (пустой опера­тор).

В результате получаем граф автомата Мили S, имеющий столько же состояний, сколько символов потребовалось для отметки входов вершин ГСА. Граф автомата Мили, соответствующий ГСА на рис. 5-1, приведен на рис. 5-3.

Входными сигналами автомата S, имеющего L входных каналов, является множество L-компонентных векторов , где , а компонента  может принимать два значения: 0 или 1. В то же время, если на ГСА между отметками ат
и as есть, путь перехода атХ (ат, as) Y (am, as) as, проходящий через операторную вер­шину Y (am, as), то дуге графа автомата приписывается входной сигнал X (ат, as) и выходной сигнал Y (am, as). Отличительная особенность микропрограммных автоматов, синтезированных рассмотренным выше способом, состоит в том, что приписанные дугам графа входные сигналы являются элементарными произве­дениями и, таким образом, булевыми функциями тех переменных, которые вхо­дят в соответствующие пути перехода, причем длина этих произведений сущест­венно меньше числа L всех входных переменных. Очевидно, что переход (ат, as) с выдачей выходного сигнала Y (am, as) будет иметь место под действием тех входных наборов из множества , на которых булева функция X (ат, as) принимает значение единицы.

Условие детерминированности работы автомата требует, чтобы любое по­парное произведение входных сигналов, вызывающих переход из некоторого состояния автомата, было равно нулю. Это условие всегда выполняется для ав­томата, построенного по граф-схеме алгоритма. Действительно, если из неко­торого состояния ат есть более одного перехода, то, выбрав произвольно два из них, например в состояния as и аt (не исключен случай s = t, т.е. два перехода в одно и то же состояние) можно убедиться в том, что в конъюнк­циях X (ат, as) и X (ат, at) какая-либо переменная, например хr, встречается в одном случае без инверсии (хr), а в другом случае – с инверсией (). Это объясняется тем, что при определении путей перехода атХ (ат, as) Y (am, as) as и атХ (ат, at) Y (ат, at) at всегда найдется общая для них некоторая условная вершина, в которой записана хr, причем такая, что в первом пути мы выходим из нее по единице, а во втором – по нулю. В силу этого с каждым состоянием ат автомата S можно связать разбиение множества всех входных сигналов – наборов значений пере­менных на входных каналах автомата  на R + 1 попарно не пересе­кающихся классов Е1, …, Е2, …, ER + l, где R – число различных конъюнкций X1, …, Хr, …, ХR, которые приписаны дугам графа автомата S, выходящим из этого состояния ат. Если из ат выходит только одна дуга, которой приписан сигнал единица (случай   пути   amY  (am, as) as,   т.е. когда вершина Y (am, as) следует непосредственно за другой операторной вершиной), то полагаем R = 0.

Рис. 5-3. Автомат Мили, по­строенный по ГСА на рис. 5-1

Очевидно, что каждому набору  однозначно соответствует конституента единицы  – булева функция L переменных, принимающая значение единицы лишь на наборе  и значение нуля на остальных наборах. Тогда к каждому из первых R классов Еr (r= 1, …, R) отнесем те и только те наборы значений входных переменных, для которых соответствующие конституенты единицы поглощаются определяющей этот класс конъюнкцией Хr, т.е.

,            (5-4)

где  r =1, …, R; ; ; ; .

К R + 1-му классу отнесем все остальные наборы:

.                 (5-5)

(А В обозначает разность множества А и В: AB = )

Если R = 0, то образуем один класс, состоящий из всех 2L наборов.

Рассмотренное разбиение множества наборов  на классы по­зволяет определить, какой переход имеет место под действием каждого из этих наборов. Так как функция Хr принимает значение единицы на множестве на­боров Еr (r = 1, …, R), то переход автомата из состояния ат под действием любого входного набора, попадающего в один из Еr классов, и соответствующий выходной сигнал совпадают с переходом автомата под действием определяющей этот класс конъюнкции и с выдаваемым при этом выходным сигналом, тогда как под действием любого набора из ER+1 – класса автомат остается в том же состоя­нии ат
и при этом выдает выходной сигнал Y0
= (0 … 0). При R = 0 под дей­ствием любого входного набора автомат переходит в то же состояние и выдает тот же выходной сигнал, что и под действием сигнала единицы, приписанного дуге графа автомата.

В качестве примера подобного разбиения рассмотрим автомат с L = 3 вход­ными и N = 4 выходными каналами. Пусть из некоторого состояния ат
этого автомата есть два перехода (рис. 5-4). Число элементарных произведений на вы­ходящих из ат дугах R = 2 (Х1 = x1; ). Число возможных входных наборов 2L = 238, и они разбиваются на R + 1 = 3 класса Е1, E2, Е3, первые   два из которых определяются по формуле (5-4), а последний – по (5-5):

Е1={111, 110, 101, 100}; E2={001, 000}; E3,= {010, 011}.

Рис. 5-4.  Подграф авто­мата

В дальнейшем (если не оговорено особо) будем рассматривать автоматы, работа кото­рых тактируется сигналами от генератора синхронизирующих импульсов (ГСИ), т. е. кроме входных каналов x1, …, xL имеется по крайней мере еще один канал р от этого генератора, по которому поступает сигнал р = 1 в момент прихода импульса и р = 0 при его отсутствии. В связи с этим входным сигналом на пере­ходе (ат, as), соответствующем пути атХ (ат, as) Y (am, as) as, будет не X (ат, as), а конъюнкция рХ (ат, as). Договоримся, однако, для простоты символ р не приписывать дугам графа автомата.

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

Синтез автомата Мура по граф-схеме алгоритма также состоит из двух этапов: получения отмеченной ГСА и построения графа автомата. На первом из них начальная, конечная и операторные вершины от­мечаются символами а1, а2, …, аM по следующим правилам:

1. Символом а1
отмечаются начальная и конечная вершины.

2. Различные операторные вершины отмечаются различными сим­волами.

3. Все операторные вершины должны быть отмечены.

При синтезе автомата Мура в отличие от автомата Мили отмечаются не входы вершин, следующих за операторными, а сами операторные вершины. Число отметок, таким образом, оказывается на единицу большим числа операторных вершин в граф-схеме алгоритма. В результате применения рассмотренной процедуры отметки к ГСА на рис. 4-5 получим отмеченную граф-схему, изображенную на рис. 5-5. .

Построение графа автомата Мура начинается с нахождения в от­меченной ГСА путей перехода вида

,             (5-6)

где етr (r = 1, …, R) и  определяются так же, как и в формуле (5-1). Как и ранее, для краткости эти пути будем обозначать атХ (ат, as) as, причем если между ат и as имеется несколько путей  вида amXh (am,  as) as (h = 1, …, Н), то будем считать, что этому множеству путей соответствует дизъюнкция , а само множество путей обозначать amX (am, as) as, называя его обобщенным путем пере­хода

Рис. 5-5. Отмеченная ГСА при синтезе авто­мата Мура.

В пути вида (5-6) не исключено R = 0, когда между операторными вершинами лежит пустое множество условных вершин (вершина, отмеченная символом as, непосредственно следует за вершиной, отмеченной символом ат, и путь вида (5-6)  превращается в путь amas).

После получения отмеченной ГСА строим граф автомата Мура S, состояниями которого являются полученные на предыдущем этапе отметки а1, …, ат, …,аM. Переходы и выходные сигналы в этом автомате определим следующим образом.

Каждому пути перехода атХ (ат, as)
as  поставим в соответ­ствие переход автомата S из состояния ат в состояние as под действием входного сиг­нала X (ат, as), а пути перехода amas – переход из ат в as под действием сигнала единицы. Что касается выходных сигналов, то в каждом состоянии независимо от того, откуда в него произошел переход, выдается выходной сигнал, который записан в опера­торной вершине, отмеченной символом этого состояния.

Очевидно, что пути вида атХ (ат, ат) ат рассматривать не нужно, так как при таком переходе ни состояние, ни выходной сигнал не меняется, что равносильно тому, что ника­кого перехода нет и автомат остается в том же состоянии. Пример подграфа ГСА с таким путем приведен на рис. 5-6, а, из которого видно, что автомат, находящийся под действием входного сигнала  не перей­дет ни в какое другое состояние и будет по-прежнему выдавать выходной сигнал Yl. Нетрудно проверить, что подграф автомата Мура, построенный по рис. 5-6, а, будет точно такой же, что и по рис. 5-6, б, в котором имеется всего один путь перехода из ат в as.

На рис. 5-7 приведен граф автомата, построенный по отмеченной ГСА на рис. 5-5.

Рис. 5-6. Два подграфа ГСА, приводящие к одному и тому же подграфу автомата Мура:

 а – без воз­вратной верши­ны, б – с воз­вратной верши­ной

Рис. 5-7. Граф автомата Мура, построенного по ГСА на рис. 5-5

Замечание в конце § 5-1 относительно тактирования входных сигналов остается в силе и для автоматов Мура, которые в дальнейшем будем синтезировать рас­смотренным выше методом.

5-3. Таблицы переходов микропрограммного автомата

При использовании графов для задания автоматов с большим чис­лом состояний и переходов наглядность теряется, поэтому оказывается предпочтительным задавать эти графы в виде списков. В связи с этим введем понятие таблицы переходов микропрограммного автомата. В случае автомата Мили эта таблица (табл. 5-1) имеет четыре столбца.

Если между состояниями ат
и as имеется переход под действием входного сигнала X (ат, as) с выдачей выходного сигнала Y (am, as), то в первом столбце помещается ат – исходное состояние, во втором – состояние перехода as (состояние, в которое осуществляется переход), в третьем – входной сигнал X (ат, as), а в четвертом – выходной Y (am, as).

Иногда на переходе (ат, as) выдается не один, а множество выход­ных сигналов – микрокоманд Y (am, as) = {Y1
(am, as), …, Yj (am, as), …, YJ (am, as)}, причем в общем случае один и тот же выходной

Таблица 5-1.  Прямая таблица переходов автомата Мили

Исходное состояние

Состояние перехода

Входной сигнал

Выходной сигнал

a1

a2

a3

x1

y1

y2y3y4y5

a2

a3

1

y2y3y4y5

a3

a4

a4

x2

y6

y7

a4

a1

a5

a6

x2

y12

y8

y9

a5

a6

1

y9

a6

a1

a3

x4

y10y11

сигнал Yj (am, as) может выдаваться также под действием множества сигналов Хj1 (ат, as), …, Xjh (am, as), …, XjH (am, as). Тогда в таблице последовательно перечисляются все пути перехода, начиная с путей, соответствующих Y1
(am, as). Для выходного сигнала Yj(am, as) в таблице переходов будет Н строчек:

Прямой таблицей переходов микропрограммного автомата назо­вем таблицу, в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т.д. Табл. 5-1 яв­ляется примером такой таблицы для автомата Мили на рис. 5-3. В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно так же, но сначала запи­сываются все переходы в первое состояние, затем во второе и т.д. (табл. 5-2 для того же автомата).

Таблица 5-2. Обратная таблица переходов автомата Мили

Исходное состояние

Состояние перехода

Входной сигнал

Выходной сигнал

a4

a6

a1

x4

y12

a1

a2

y1

a1

a2

a6

a3

x1

1

y2, y3, y4, y5

y2, y3, y4, y5

y10, y11

a3

a3

a4

x2

y6

y7

a4

a5

y8

a4

a5

a6

x2

1

y9

y9

В случае автомата Мура можно обойтись всего тремя столбцами, записывая выходной сигнал в прямой таблице рядом с соответствую­щим ему исходным состоянием, а в обратной — рядом с состоянием перехода. Прямая и обратная таблицы переходов для автомата Мура на рис. 5-7 приведены в табл. 5-3 и 5-4.

Таблица 5-3. Прямая таблица переходов автомата Мура

Исходное состояние

Состояние перехода

Входной сигнал

a1(–)

a2

a3

x1

a2 (y1)

a3

1

a3 (y2, y3, y4,
y5)

a4

a5

x2

a4 (y7)

a6

a7

a9

x2

a5 (y6)

a6

a7

a9

x2

a6 (y8)

a7

1

a7 (y9)

a1

a8

x4

a8 (y10, y11)

a4

a5

x2

a9 (y12)

a1

1

Таблица 5-4. Обратная таблица переходов автомата Мура

Исходное состояние

Состояние перехода

Входной сигнал

a7

a9

a1(–)

x4

1

a1

a2 (y1)

a1

a2

a3 (y2, y3, y4,
y5)

x1

1

a3

a8

a4 (y7)

a3

a8

a5 (y6)

x2

x2

a4

a5

a6 (y8)

a4

a5

a6

a7 (y9)

x2

x2

1

a7

a8 (y10, y11)

a4

a5

a9 (y12)

Очевидно, что таблицу переходов микропрограммного автомата (прямую или обратную) целесообразно составлять непосредственно по отмеченной граф-схеме алгоритма, записывая в нее все пути пере­хода, т. е. не нужно предварительно рисовать граф автомата, по­скольку эта таблица и есть граф, заданный в виде списка.

5-4. Минимизация микропрограммных автоматов

Изложенный в первой главе метод минимизации полностью опреде­ленных абстрактных автоматов можно модифицировать для миними­зации микропрограммных автоматов. Напомним, что два состояния автомата Мили будут одноэквивалентными, если под действием оди­наковых входных сигналов они выдают одинаковые выходные сигналы. В связи с этим для выяснения одноэквивалентности состояний аi и аj микропрограммного автомата необходимо сравнить множества микро­команд, выдаваемых на переходах из этих состояний. Пусть, например, эти множества совпадают и равны {Y1, …, Yt, …, YT}, причем микрокоманда Yt выдается под действием сигналов Xi(Yt) и Xj(Yt) для состояний аi и aj соответственно. Тогда, очевидно, аi и аj будут одноэквивалентны, если эквивалентны функции Xi (Yt) и Xj(Yt) для всех t = 1, …, Т. В табл. 5-5 приведен микропрограммный ав­томат Мили, синтезированный по ГСА на рис. 5-8.

После нахождения указанным способом одноэквивалентных со­стояний получаем разбиение  множества этого автомата на четыре класса:

;

.

Два состояния ai и аj микропрограммного автомата будут k-эквивалентны, если выполняются следующие условия:

1. ai и aj (k–1)-эквивалентны.

2. Если  и  – множества классов (k– 1)-эквивалентных состоя­ний, в которые есть переходы из аi и аj соответственно, то Ri = Rj, т.е. Ni = Nj = N и Rin = Rjn = Rn для всех п = 1, …, N.

3. Если  и  – множества   микрокоманд,   выдаваемых   соответст­венно на переходах из ai и аj в состояния из некоторого (k–1)-го класса эквивалентности Rn, то Yi = Yj, т.е. Тi
= Тj = Т и Yit = Yjt = Yt для всех t = 1, …, Т.

Рис. 5-8. Отмеченная граф-схема алгоритма

4. Если Yt – микрокоманда из п. 3, выдаваемая под действием сигналов Xi(Yt) и Хj(Yt) из состояний ai и аj соответственно, то Xi эквивалентно Xj.

Результаты разбиения  сведены в табл. 5-6, в которой вместо состояний перехода указаны их классы эквивалентности.

По табл. 5-6 получаем разбиение  (табл. 5-7) на классы 2-эквивалентных состояний:

Если выполнить следующее разбиение (), то оно совпадает с  а потому  есть разбиение на классы эквивалентных состояний. Вы­бирая из каждого класса эквивалентности по одному состоянию, получаем множество А’ = {а1, а3, а4, а6, а8} состояний минимального микропрограммного автомата Мили. При выборе представителя из некоторого класса в А’ целесообразно выбирать состояния с наимень­шим числом строчек в таблице переходов, именно поэтому из класса С2 взято а4. Таблица переходов минимального автомата (табл. 5-8) получена из табл. 5-5 вычеркиванием массивов переходов из состоя­ний, не вошедших в A’, и заменой в столбце «состояние перехода», не вошедших в A’, состояний на эквивалентные из множества А’.

Таблица 5-5. Автомат Мили, построенный по ГСА на рис. 5-8

Исходное состояние

Состояние перехода

Входной сигнал

Выходной сигнал

a1

a2

a3

a4

a5

x1x4

Y1

Y3

Y2

Y6

a2

a6

a8

a6

a9

x4x3

Y5

Y4

Y5

Y4

a3

a6

a7

x3

Y5

Y4

a4

a6

a8

x3

Y5

Y4

a5

a2

a3

a4

a5

x1x4

Y1

Y3

Y2

Y6

a6

a2

a9

x4

Y3

Y5

a7

a4

a8

x4

Y3

Y5

a8

a5

1

Y1

a9

a1

1

Y1

 

Таблица 5-6. Разбиение  на классы 1-эквивалентных состояний автомата Мили

Класс эквивалентности

Исходное состояние

Класс перехода

Входной сигнал

Выходной сигнал

B1

a1

B2

B2

B2

B1

Y1

Y3

Y2

Y6

a5

B2

B2

B2

B1

Y1

Y3

Y2

Y6

B2

a2

B3

B4

B3

B4

Y5

Y4

Y5

Y4

a3

B3

B3

Y5

Y4

a4

B3

B4

Y5

Y4

B3

a6

B2

B4

Y3

Y5

a7

B2

B4

Y3

Y5

B4

a8

B1

1

Y1

a9

B1

1

Y1

Для минимизации микропрограммного автомата Мура необходимо предварительно найти разбиение множества состояний на классы 0-эквивалентности. В каждый такой класс попадут состояния, отме­ченные одинаковой микрокомандой. Далее процесс минимизации пол­ностью совпадает с минимизацией микропрограммных автоматов Мили.

 

Таблица 5-7. Разбиение  на классы 2-эквивалентных состояний автомата Мили

Класс эквивалентности

Исходное состояние

Класс перехода

Входной сигнал

Выходной сигнал

C1

a1

C2

C3

C2

C1

Y1

Y3

Y2

Y6

a5

C2

C3

C2

C1

Y1

Y3

Y2

Y6

C2

a2

C4

C5

C4

C5

Y5

Y4

Y5

Y4

a4

C4

C5

Y5

Y4

C3

a3

C4

C4

Y5

Y4

C4

a6

C2

C5

Y3

Y5

a7

C2

C5

Y3

Y5

C5

a8

C1

1

Y1

a9

C1

1

Y1

Таблица 5-8. Таблица переходов минимального автомата Мили

Исходное состояние

Состояние перехода

Входной сигнал

Выходной сигнал

a1

a4

a3

a4

a1

Y1

Y3

Y2

Y6

a3

a6

a6

Y5

Y4

a4

a6

a8

Y5

Y4

a6

a4

a8

Y3

Y5

a8

a1

1

Y1

 

Глава шестая

СИНТЕЗ ЛОГИЧЕСКОЙ СХЕМЫ

МИКРОПРОГРАММНОГО АВТОМАТА

6-1. Структурная таблица микропрограммного автомата

Структурные таблицы микропрограммного автомата являются пасширением таблиц переходов, рассмотренных в §5-3. Структурная таблица автомата Мили (табл. 6-1) имеет семь столбцов.

Состояния аm из которых осуществляются переходы, указываются в первом столбце. Коды этих состояний К(am) после кодирования за­носятся во второй столбец. В третьем и четвертом столбцах записываются состояния as, в которые происходят переходы, и их коды К(as). Пятый и шестой столбцы содержат входные X(ат, as) и выходные сигналы Y (am, as), входящие в пути перехода. В седьмом столбце таб­лицы перечисляются обязательные функции возбуждения , вырабатываемые на соответствующих переходах.

Таблица 6-1. Общий вид структурной таблицы

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательные функции возбуждения

Если между двумя состояниями имеется несколько путей пере­хода, даже содержащие один и тот же выходной сигнал, для каждого пути отводится в таблице отдельная строчка, в связи с чем в каждой строке столбца «Входной сигнал» содержится ровно одна конъюнкция.

Таблица 6-2. Прямая структурная таблица автомата Мили

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательные функции возбуждения

a1

001

a2

a3

010

011

y1

y2, y3, y4, y5

a2

010

a3

011

1

y2, y3, y4, y5

a3

011

a4

a4

100

100

y6

y7

a4

100

a1

a5

a6

001

101

110

y12

y8

y9

a5

101

a6

110

1

y9

a6

110

a1

a3

001

011

y10, y11

Структурные таблицы, так же как и таблицы переходов микропро­граммного автомата, могут быть прямые и обратные. В прямой таб­лице последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т. д. Табл. 6-2 представляет собой пря­мую структурную таблицу автомата Мили, построенную по таблице переходов 5-1.

Для простоты в этой таблице в качестве кода каждого состояния взят двоичный эквивалент его номера, например K(а3) = 011, K(а4) = 100 и т.д. В обратной структурной таблице столбцы обозначены так же, но сначала записываются все переходы в первое состояние, затем во второе и т. д. В табл. 6-3 приведена обратная структурная таблица того же автомата.

Таблица 6-3. Обратная структурная таблица автомата Мили

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательные функции возбуждения

a4

a6

100

110

a1

001

y12

a1

001

a2

010

y1

a1

a2

a6

001

010

110

a3

011

y2, y3, y4, y5

y2, y3, y4, y5

y10, y11

a3

a3

011

011

a4

100

y6

y7

a4

100

a5

101

y8

a4

a5

100

101

a6

110

1

y9

y9

Структурные таблицы автомата Мура – как прямая, так и обрат­ная будут иметь на один столбец меньше, так как выходной сигнал в них записывается рядом с исходным состоянием (в прямой таблице) или с состоянием перехода (в обратной). В табл. 6-4 построена обрат­ная структурная таблица автомата Мура, таблица переходов которого представлена таблицей 5-4.

Таблица 6-4. Обратная структурная таблица автомата Мура

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнал

Обязательные функции возбуждения

a7

a9

0111

1001

a1 (–)

0001

1

a1

0001

a7 (y2)

0010

a1

a2

0001

0010

a3

(y2, y3, y4, y5)

0011

1

a3

a8

0011

1000

a4 (y7)

0100

a3

a8

0011

1000

a5 (y6)

0101

a4

a5

0100

0101

a6 (y8)

0110

a4

a5

a6

0100

0101

0110

a7 (y9)

0111

1

a7

0111

a8 (y10, y11)

1000

a4

a5

0100

0101

a9 (y12)

1001

6-2. Построение схемы по структурной таблице

Структурный синтез микропрограммного автомата проиллюстри­руем на примере автомата Мили, синтезированного по ГСА на рис. 6-1. После отметки состояний (рис. 6-1) построим обратную структурную таблицу микропрограммного автомата (табл. 6-5).

Так как структурная таблица представляет собой граф микропро­граммного автомата, заданный в виде списка, из этой таблицы можно получать выражения функций возбуждения и функций выходов ана­логично тому, как это делалось ранее при графическом методе структурного синтеза автоматов. Так, для  и  из табл. 6-5 имеем:

                       (6-1)

Однако для встречающихся на практике микропрограммных авто­ подобные выражения очень сложны: они представляют собой

Рис. 6-1. Отмеченная ГСА

систему из десятков и сотен функций десятков и сотен переменных. В этом случае известные классические методы минимизации булевых функций, работающие с выражениями в классе нормальных форм, ока­зываются неприемлемыми. Кроме того, практика показала, что ос­новное сокращение объема схемы происходит не за счет минимизации в нормальных формах, а в результате выделения ряда функций и подфункций, допускающих совместную минимизацию, и представле­ния систем функций в виде декомпозиции.

Первым шагом при минимизации логической схемы микропрограмм­ного автомата является объединенное построение компонент функций возбуждения и функций выходов, записанных в одних и тех же строч­ках структурной   таблицы.   Так,   конъюнкция   из третьей   строчки

 

Таблица 6-5 Структурная  таблица автомата Мили, построенная по рис. 6-1

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнла

Выходной сигнал

Обязательные функции возбуждения

a1

a1

a2

a2

a3

a3

a4

a4

a4

a4

a5

a5

000

000

001

001

011

011

101

101

101

101

010

010

a1

000

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

a1

a1

a2

a2

a3

a4

a4

a5

a7

000

000

001

001

011

101

101

010

110

a2

001

y1y2

y1y3

y1y4

y1y4

y1y4

y1y4

y1y4

y1y4

y1y4

a2

001

a3

011

y3

a2

a2

001

001

a4

101

y5y6

y5y6

a1

a1

a2

a4

a7

000

000

001

101

110

a5

010

y7y8

y7y8

y7y8

y7y8

y8

a2

a4

001

101

a6

100

y9

y9

a6

100

a7

110

1

y1

табл. 6-5  может быть использована при построе­нии функций  из четвертой строчки  – при построении  и т.д.

Аналогично в схеме на рис. 2-8 выражение  входило в функ­ции . Учет только этого обстоятельства позволяет сократить

Рис. 6-2. Схема для переходов в состояние a5:

a – без исполь­зования преддешифратора; б – с преддешифратором

схему по сравнению с непосредственным построением по выражениям вида (6-1) примерно во столько раз, сколько компонент функций воз­буждения и функций выходов встречается в среднем в одной строке структурной таблицы. В качестве критерия минимальности схемы будем использовать на протяжении всей работы минимум суммарного числа входов в логические элементы схемы.

Синтез схемы будем вести раздельно для переходов в каждое со­стояние. В структурной таблице эти переходы отделены друг от друга горизонтальной чертой. В пределах переходов в одно состояние по­следовательно строим схему для каждой микрокоманды. Так, среди переходов в состояние а5 есть две микрокоманды: {у7, у8} и {у8}. Конъюнкции, соответствующие каждой строчке для одной микро­команды, заводим на схему «ИЛИ», с которой и снимаем соответствующие этой микрокоманде выходные сигналы – микрооперации (рис. 6-2, а) (Для микрокоманды {y8} схема «ИЛИ» не строится, так кай ей соответствует одна строчка таблицы на переходе в состояние а5). Если пересечение микрокоманд не пусто, можно по­строить еще одну схему «ИЛИ», с которой снимаются входящие в пе­ресечение выходные сигналы (у8 снимается с «ИЛИ» 2, так как ). Цена схемы на рис. 6-2, а равна 48 [39 входов в схемы «И», «ИЛИ» плюс девять отметок функций возбуждения и вы­ходов (кроме y7), встречающихся на переходах в другие состояния и, следовательно, требующих построения схем «ИЛИ», на которые и бу­дут поданы эти сигналы].

6-3. Преддешифратор обратной связи

Из формул (6-1) видно, что каждая компонента функций возбужде­ния и выходных сигналов, соответствующая некоторому пути пере­хода, получается как конъюнкция переменных, которыми закодиро­ваны состояния, тактирующего сигнала р и входного сигнала, входя­щего в путь перехода. С кодом каждого состояния автомата можно соотнести клетку карты Карно на соответствующее число перемен­ных и тем самым представить состояние в виде конъюнкции наборов значений триггеров столбца и строки, на пересечении которых нахо­дится рассматриваемое состояние.

Предположим для определенности, что длина кода равна 5. Как видно из карты Карно на 5 переменных (табл. 6-6), конъюнкция Т (am), соответствующая коду К (am) состояния am, разделяется на две ча­сти:

Таблица 6-6. Карта Карно на 5 переменных

000

001

011

010

110

111

101

100

00

01

11

10

Положим  (i = 0, 1, 2, 3), где p – тактирующий импульс. Очевидно, что если построить схемы, на выходах которых опреде­ляются значения  (у = 0, 1, …, 7) и  (i = 0, 1, 2, 3),  где ; ; ; ; ;  (k = 1, 2, 3; r = 4, 5),   то  для  am из табл. 6-6 .

Схему, реализующую  и  назовем преддешифратором обратной связи. Нижние индексы j и i при  и  есть восьмеричные эквиваленты двоичных чисел, приписанных соответствующим столбцу и строке карты Карно, что позво­ляет по этим индексам легко восстановить код состояния. В тех же случаях, когда кон­кретный код состояния ат не важен, а необходимо лишь под­черкнуть, что речь идет о коде именно этого состояния, мы будем использовать обозначения вида , где верхние индексы при  и  означают, что  и отмечают столбец и строку карты Карно, на пересечении которых стоит состоя­ние ат.

Рис. 6-3. Преддешифратор для че­тырех триггеров

Рис. 6-4. Схемы для одного обобщенного пути:

а – с ис­пользованием преддешифратора, б –
без использования преддешифратора

На рис. 6-2, б приведена схема, эквивалентная рис. 6-2, а, но по­строенная с учетом преддешифратора: ; ; ; ; . Преддешифратор для четырех тригге­ров с раздельными входами изображен на рис. 6-3.

Пусть в автомате имеется переход из состояния ат в состояние as под действием входного сигнала X (ат, as), что соответствует пути перехода в граф-схеме алгоритма атХ (ат, as)
Y (am, as) as. Тогда схема для этого перехода будет иметь вид рис. 6-4, а, где – множество компонент обязательных функций возбуждения, выдаваемых на переходе (am, as), а  и  снимаются с выходов преддешифра­тора.

            Может показаться более целесообразной полная расшифровка ко­дов состояний (построение полного дешифратора). В этом случае схема для того же перехода будет иметь вид рис. 6-4, б, где «И»m – второй (последний) каскад дешифратора. Подсчитаем V1
оборудование, идущее на построение сигналов обратной связи при таком способе построения (без учета входных сигналов вида X(ат, as)). Количество схем «И»m, очевидно, равно М – числу состояний автомата, а коли­чество схем «И»k – числу переходов N (точнее, обобщенных путей) в автомате. Тогда V1 = 2М + N.

            При использовании преддешифратора каждому обобщенному пути перехода из состояния в состояние соответствует 2 входа (без учета X(ат, as)) в схему «И»k (рис. 6-4, а), поэтому оборудование при этом способе V2 = 2N. Метод преддешифратора с точки зрения оборудо­вания выгоднее, если V2<V1, т.е. если N<2M. Сточки зрения бы­стродействия использование преддешифратора всегда лучше, так как при построении полного дешифратора число каскадов в схеме увели­чивается на единицу (для построения схемы «И»m на рис. 6-4, б).

            6-4. Доопределение функций возбуждения

            Рассмотрим подграф графа автомата, изображенный на рис. 6-5. На переходе (ai, ak) второй триггер меняет свое состояние с нуля на единицу, состояние остальных триггеров не меняется, т.е. множество обязательных функций возбуждения на этом переходе . Точно так же на пе­реходе . Ясно, что функционирование автомата не нарушается, если на переходе (ai, ak) выдавать те же ком­поненты функций возбуждения, что и на пере­ходе i, ak). Действительно, если на переходе (ai, аk) на нулевой вход первого триггера, установленного в состояние нуль, придет сиг­нал единица (), то этот сигнал не изменит его состояния.

Рис. 6-5. Подграф ав­томата, иллюстриру­ющий доопределение функций возбужде­ния

            Обобщим приведенные рассуждения. Пусть G(as) = {ат1, …, amr , …, атR} подмножество множества состояний, из которых есть переходы в состояние as. Обязательными для этих переходов бу­дут функции возбуждения . Под доопределе­нием функций возбуждения на переходах из состояний ат1, …, amR в as будем понимать выдачу на всех этих переходах одного и того же множества компонент функций возбуждения

,

т.е. на этих переходах, кроме обязательных, можно вырабатывать функции возбуждения, подтверждающие состояния элементов памя­ти, не меняющиеся на данном переходе.

            Функции возбуждения, вырабатываемые на некотором переходе (ат, as), в одних случаях рассматриваются как множество сигналов, поступающих на единичные и нулевые входы триггеров памяти, а в других – как булевы функции входных сигналов автомата и сигна­лов обратной связи. В связи с этим для функций возбуждения в пер­вом случае будет использоваться обозначение F(am, as), а во втором – F(am, as).

            Доопределяя, например, функции возбуждения на всех переходах в состояние а5 (табл. 6-5), получим:

            Эти функции после доопределения можно снять со схемы «ИЛИ»2, в результате чего цена схемы уменьшится на 5 единиц и появится до­полнительная возможность для минимизации (см. ниже «Задача фак­торизации»).

            6-5. Узлы на граф-схеме алгоритма. Сокращение структурной таблицы

            Рассмотрим подграф ГСА, приведенный на рис. 6-6, а. Вход услов­ной вершины хр1, отмеченный символом Q, соединяется с выходом двух условных вершин: xmR и xnL. Из состояний ат и аn в as есть пути пе­рехода

 и

соответственно . Входной сигнал на переходе (am, as)конъюнк­цию X(ат, as) разобьем на две конъюнкции: . Аналогично Х(ап, as) = X(an, Q) X(Q, as), где

;

.

            Условное изображение подграфа рис. 6-6, а приведено на рис. 66, б. Логическая схема для переходов (ат, as) и (ап, as) изображена на рис. 6-7, а.

            Доопределим функции возбуждения на переходах из ат и ап в as: , где G (Q)множество состоя­ний, из которых есть пути перехода в as, проходящие через точку Q. После доопределения множество функций возбуждения F(G(Q), as)
можно снять вместе с Yg, что позволяет вынести за скобки общий член X(Q, as)
(рис. 6-7, б). Со схемы «ИЛИ» снимается функция

.

            Увеличим число путей в точку Q и из точки Q в другие состояния (рис. 6-8, а). Доопределяя функции возбуждения на переходах из мно­жества состояний G(Q) = {а1, …, ат, …, аM} в каждое состоя­ние аr (r = М + 1, …, R), получим:

    (6-2)

            Схема, реализующая формулы (6-2), приведена на рис. 6-8, б. После этих примеров, кроме рассмотренных ранее отметок-состояний на граф-схеме, введем понятие отметки-узла (или просто узла). Вход условной вершины ГСА будем отмечать символом Qk, который будем называть отметкой-узлом, если имеется не менее двух путей из отме­ток-состояний в эту отметку-узел вида , где ;  (r = 1, …, R), проходящих через различные условные вершины.

            Один из путей может не содержать ни одной условной вершины (R = 0), т. е. иметь вид amQk. Тогда вход некоторой условной вер­шины имеет две отметки – состояния и узла, причем отметку-узел нужно помещать под отметкой-состоянием (ближе ко входу вершины), чтобы не пропустить путь из этого состояния в узел.

Рис. 6-7. Логическая схема для подграфа ГСА на рис. 6-6:

а – без доопределения функций возбуждения, б – с доопределением

функций возбуждения

Рис. 6-8. Подграф ГСА с большим числом путей из узла в состояния (а)

и соответствующая логическая схема (б)

            В общем случае могут быть пути в узел не только из состояний, но и из других узлов. Будем считать, что существует путь из узла Qp в узел Qk, если на граф-схеме есть путь вида . На рис. 6-9, а в узел Qk есть пути из ат и ап
и узла Qp.  – множество состояний, из которых есть пути в узел Qk, в том числе проходящие через другие узлы. Логическая схема для рис. 6-9, а приведена на рис. 6-9, б, где

;

;

.

            ГСА на рис. 6-1 имеет три узла: Q1, Q2, Q3.

            Введенная в §6-1 структурная таблица автомата предусматривает представление микропрограммного автомата в виде списка. В каждой строке структурной таблицы записывается путь перехода вместе с ко­дами состояний и вырабатываемыми на этом переходе обязательными функциями возбуждения. Расширим теперь понятие структурной таблицы, введя туда пути «состояние – узел», «узел – состояние» и «узел – узел». Таким образом, всевозможных различных комбина­ций путей на графе алгоритма будет четыре. Общий вид структурной таблицы иллюстрируется табл. 6-7.

Рис. 6-9. Подграф ГСА с путем «узел—узел» (а)

 и соответствую­щая логическая схема (б)

 

Таблица 6-7. Общий вид структурной таблицы с узлами

Исходное состояние, узел

Код исходного состояния

Состояние, узел перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательнеы функции возбуждения

am

am

Qk

Qp

K(am)

K(am)

as

Qk

as

Qk

K(as)

K(as)

X(am, as)

X(am, Qk)

X(Qk, as)

X(Qp, Qk)

Y(am, as)

Y(Qk, as)

            Необходимо подчеркнуть, что узел не является состоянием авто­мата и введен лишь для облегчения построения и упрощения схемы микропрограммного автомата. На самом деле никаких переходов в узел и из узла в обычном понимании слов «переход автомата» не суще­ствует. Таким образом, расширение понятия структурной таблицы привело к тому, что она уже не представляет граф автомата в виде списка. В то же время в этой таблице уже учтены некоторые структур­ные особенности будущей схемы автомата.

            В обратной структурной таблице с узлами сначала необходимо записывать все пути (из узлов и состояний) в узлы Q1, Q2, … затем – в состояния a1, а2, … Такая таблица для ГСА на рис. 6-1 приведена в табл. 6-8. Сравнение этой и структурной таблицы без узлов для той же граф-схемы (табл. 6-5) показывает, что введение узлов позволяет существенно сократить длину структурных таблиц.

            6-6. Задача факторизации

            Пусть задана функция

             (6-3)

            где

            Очевидно, что возможна минимизация схемы, реализующей эту функцию, если предварительно вынести общий множитель из всех или нескольких конъюнкций. Так, например, формулу (6-3) можно преобразовать:

.   (6-4)

            Схема для формулы (6-4) требует на 4 входа в логические элементы меньше, чем схема для формулы (6-3).

            В общем случае, если имеется дизъюнкция п конъюнкций

      (6-5)

            где каждая конъюнкция , т.е. у всех конъюнкций есть общий множитель х1 … хт1, он может быть вынесен за скобки, и тогда соответствующая схема реализуется так, как показано на рис. 6-10, а. Очевидно, что выигрыш в числе входов в логические элементы в этой схеме по сравнению с непосредст­венным построением по формуле (6-5) будет

,

            где т – число общих букв во всех конъюнкциях, п – число конъ­юнкций.

            Может случиться, что вынесение возможно не из всех конъюнкций. Так, если

,      (6-6)

            причем только первые п конъюнкций содержат общий член x1…xm:

            а остальные tn членов имеют вид

то функция f может быть реализована так, как показано на рис. 6-10, 6. В этом случае

.

            Если к тому же у r из первых п конъюнкций (предположим для про­стоты, что это X1, …, Хr) после вынесения общего члена х1…хт остается по одной букве: Хр = х1xmzp(р = 1, …, r), то имеет место наиболее общий случай, при котором первые r конъюнкций на рис. 6-10, б исчезают, схема принимает вид рис. 6-10, в, а выигрыш при таком построении по сравнению с непосредственной реализацией формулы (6-6) составит

.

 

Таблица 6-8. Структурная таблица автомата Мили (с узлами), построенного по рис. 6-1

Исходное состояние, узел

Код исходного состояния

Состояние, узел перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательные функции возбуждения

a2

a4

001

101

Q1

Q1

a4

a5

101

010

Q2

1

Q2

a1

a3

000

011

Q3

Q3

Q3

a1

000

y4y9

y4y8

Q2

a1

a1

a2

a3

a7

000

000

001

011

110

a2

001

y1y4

y1y2

y1y3

y1y4

y1y4

y1y4

a2

001

a3

011

y3

a2

a2

001

001

a4

101

y5y6

y5y6

Q1

a1

a1

a7

000

000

110

a5

010

y7y8

y7y8

y7y8

y8

Q1

a6

100

y9

a6

100

a7

110

1

y1

            Задачу вынесения общего множителя за скобки, в отличие от за­дачи в следующем параграфе, будем называть вынесением вверх по аналогии с тем, что общий множитель выносится над схемой «ИЛИ». Рассмотрим один из возможных алгоритмов вынесения вверх на при­мере формулы (6-3). Пересечения множеств букв, входящих в конъюнк­ции Х1, …, Х5, дают всевозможные наибольшие общие части, по­лученные попарным сравнением. Эти общие части могут быть выне­сены вверх
(в изложенной ниже процедуре переменные (xi) заменены их индексами (i). Кроме того, конъюнкции Х1, …, Х5 будем иногда называть словами, со­стоящими из соответствующих букв):

            В нашем примере это будут общие части:

            В скобках после общей части указаны конъюнкции, в которые она входит.

            По приведенным выше формулам легко подсчитать цену каждой из общих частей Z1, …, Z6 как выигрыш, который дает вынесение этой общей части:

            На первом шаге для вынесения выбирается общая часть, имеющая наибольшую цену: W(Z4) = max (W (Z1), … , W (Z6)) = 6. В ре­зультате вынесения общей части Z4 из исходного множества слов A1
=
{X1, …, X5} образуются два множества: A2 = {Х6, Х7, X8} – конъюнкции, из которых удалены буквы, входящие в Z4 (X6 = Х1 Z4; X7 = Х3 Z4; X8 = Х5
Z4), и В2 = {Х2, Х4, Z4} – конъюнкции, из которых не делалось вынесение, плюс общая часть Z4. Это разбиение иллюстрируется рис. 6-11, а, а полученная в резуль­тате вынесения Z4 схема приведена на рис. 6-11, б. На рис. 6-11, а под общей частью Z4 стоит W (Z4) = 6.

            Из рис. 6-11, б видно, что дальнейшее вынесение возможно только раздельно для множеств А2
и В2. Продолжая аналогично отдельно для А2
и В2 до тех пор, пока не найдется ни одной общей части, имею­щей цену больше нуля, получим процедуру вынесения вверх, в кото­рой на каждом шаге выбирается общая часть, определяемая по наи­большей цене. Такой алгоритм необязательно приведет к оптимальной схеме, так же как и алгоритм, изложенный в [17], где на каждом шаге предлагается выносить общую часть, имеющую наибольшую длину. Эксперименты над комбинационными схемами микропрограммных автоматов показали, что вынесение по наибольшей цене в большинстве случаев дает решение, близкое к оптимальному. Процедура вынесения по этому алгоритму для рассмотренного примера приведена на рис. 6-12, а. Дадим краткие пояснения к этому ри­сунку. Ищем пересечения слов в множестве A2:

            Вынесение Z8 порождает два множества A3, B3:

A3={X9, X10};  X9=X7Z8; X10=X8Z8; B3={X6, Z8}.

Рис. 6-11. Вынесение Z4:

а – условное изображение процесса вынесения,

б – логическая схема

            В каждом из множеств А3, В3 слова не пересекаются. Дальнейшие вынесения невозможны.

            Переходим к множеству В2:

            Вынесение Z10 порождает два множества, A4, B4:

A4={X11, X12};  X11=X4Z10;  X12=Z4Z10;  B4={X2, Z10}.

            В каждом из множеств A4, B4, слова не пересекаются, дальнейшие вынесения невозможны.

Рис. 6-12. Пример вынесения вверх: а – условное изображение процесса,

б – логическая схема

            Схема, соответствующая процедуре на рис. 6-12, а, приведена на рис. 6-12, б. Выигрыш в результате вынесений общих частей

W=W(Z4)+W(Z8)+W(Z10)=9.

            6-7. Декомпозиция схемы из однотипных элементов

            Пусть задана система функций:

        (6-7)

            Очевидно, что возможна минимизация схемы, реализующей эту систему функций, если предварительно построить какую-либо общую для некоторых из этих функций конъюнкцию, например х1х2, в виде отдельного логического элемента, выход которого подать на входы схем, реализующих f1, f2, f3, f5; при этом число входов в логические элементы уменьшится на два (рис. 6-13).

            В общем случае пусть задано множество функций f1, …, ft, …, fT от множества двоичных переменных X = {х1, …, xl, …, xL}:

ft = xt1Θ … Θxtr… Θ; t = 1, …, T;

            Операция Θ есть некоторая логическая функция, например дизъюнкция или конъюнкция, но обязательно только одна из них.

Рис. 6-13. Вынесение вниз х1х2

            Эти функции можно реализовать с помощью Т логических элементов, каждый из которых имеет Rt входов. Обозначим через Xt (t = 1, …, Т) множество переменных, поступающих на входы t-го элемента. Может случиться, что пересечение некоторых множеств из системы множеств Х1, …, ХT не пусто. Пусть, например, это будут первые п множеств Х1, …, Хп: . Тогда мно­жество функций можно пред­ставить в виде декомпозиции (рис. 6-14), такой, что , где ; t = 1, …,  п. Ясно, что если , то полученная в результате декомпозиции схема имеет меньшую цену. В последней формуле , P (Z) и Р(Xt)число элементов в множествах , Z и Xt соответственно. Ставится задача нахождения среди множества экви­валентных схем, реализующих функции f1, …, fT, схемы с минималь­ной ценой, выполненной в виде декомпозиции однотипных элементов (т.е. реализующих одинаковые логические функции). В отличие от задачи в предыдущем параграфе (вынесение вверх), назовем эту задачу вынесением вниз. Из рис. 6-14 видно, что выигрыш от вынесения вниз из п слов общей части Z, состоящей из m букв, равен

 (6-8)

где r –
число множеств из Х1, …, ХT, полностью совпадающих с Z, поскольку соответствующие им функции можно снять прямо с вы­хода схемы для общей части Z.

            Вернемся к функциям (6-7). Пересечения множеств букв, входящих в Х1, …, Х5, дают всевозможные наибольшие общие части, полу­ченные попарным сравнением. Они могут быть вынесены вниз:

Рис. 6-14. Общий вид вынесения вниз

Рис. 6-15. Пример вынесения вниз:

а – условное изобра­жение процесса, б – логическая схема

            В нашем примере это будут общие части:

            В скобках после общей части указаны слова, в которые она входит. По формуле (6-8) легко подсчитать цену каждой из общих частей Z1, …, Z6 как выигрыш, который дает вынесение вниз этой общей части:

            В результате вынесения из множества слов Х1, …, ХT некото­рой общей части Z, входящей в первые п слов Х1, …, Хп, образуется новое множество слов по следующим правилам:

            1. Если некоторое слово из Х1, …, ХT совпадает с Z, то оно исключается из множества слов:

            2. В Х1, …, Хп
множество букв, входящих в Z, заменяется новой буквой хр, не принадлежащей алфавиту X = {х1, …, xL}.

            3. В множестве слов Х1, …, ХT слова Xi (i = 1, …, n) заме­няются словами .

            4. К полученным в пп. 1–3 словам добавляется слово Z.

            Построение нового множества слов иллюстрируется рис. 6-15. По­сле вынесения общей части Z4 = 1, 2, 5, 6 из слов Х1, Х3
и Х5 эти слова заменяются словами Х6, Х7 и Х8 соответственно, в которых вместо букв 1, 2, 5, 6 появляется новая буква 13. Из полученного множества слов возможны дальнейшие вынесения. Найдем всевозможные общие части в этих словах. Так как вынесение вниз одной буквы смысла не имеет, ищем пересечения слов, имеющие не менее двух букв:

            После вынесения общей части Z10 = 10, 12, 13 получаем новое множество слов, у. которых нет пересечений, содержащих более одной буквы. Логическая схема, соответствующая процедуре на рис. 6-15, а, приведена на рис. 6-15, б.

            При синтезе микропрограммного автомата по ГСА после построе­ния всех переходов в узлы и состояния схема может быть проминими-зирована за счет операций вынесения вверх (для каждой отдельной функции) и вынесения вниз общих частей у схем «И» для различных функций. В качестве примера на рис. 6-16, а приведена схема, построенная по табл. 6-9, представляющей собой фрагмент некоторой структурной таблицы (цена схемы равна 70), а на рис. 6-16, б – та же схема после доопределения всех функций возбуждения и минимиза­ции с помощью указанных операций (цена схемы – 50).

Рис. 6-16. Логическая схема, построенная по табл. 6-9:

а – без вынесений общих множителей, б – с вынесениями общих множителей

            Кроме вынесения вниз длясхем «И», эта операция может быть ис­пользована при построении схем «ИЛИ», например, для выходных сиг­налов. После построения всех переходов в каждое состояние часто бывает, что одни и те же микрооперации выдаются на различных переходах, т.е. снимаются с различных схем. Ясно, что все одинаковые микрооперации должны быть поданы на схему «ИЛИ», с которой и снимается соответствующий выходной сигнал.

            Рассмотрим пример. Пусть выходной сигнал у1
снимается со схем «И» 1, «И» 7, «ИЛИ» 12, «ИЛИ» 14, «И» 15, «ИЛИ» 18, выходной сиг­нал у2 – со схем «И» 1, «И» 7, «И» 15 и выходной сигнал y3со схем «И» 1, «ИЛИ» 2, «И» 3, «И» 7, «ИЛИ» 12, «ИЛИ» 14, «И» 15. Для полу чения каждого из этих сигналов необходимо построить, три схемы «ИЛИ», после чего схема примет вид рис. 6-17, а (Цена схемы равна 16).

            Представим y1, y2
и у3
в виде слов, составленных из индексов схем, с которых они снимаются, после чего применим процедуру вынесения вниз, используя на каждом шаге общую часть с наибольшей ценой:

            Выносим Z1. Выход схемы для Z1 обозначим буквой 19.

Таблица 6-9. Часть обратной структурной таблицы

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательные функции возбуждения

a1

a1

a1

a1

a1

a1

a1

11101

11101

11111

00111

00101

00101

11110

a7

00100

y1, y2

y1, y3

y1, y2

y1, y6, y7

y1, y4, y5

y1, y4, y5

y1, y2

            Выносим Z3. Выход схемы для Z3 обозначим буквой 20. Дальней­шие вынесения невозможны. Схема для y1, y2 и у3 после вынесения вниз приведена на рис. 6-17, б. Цена схемы сократилась на 5 входов в логические эле­менты.

            Процедура вынесения вниз может быть использована при минимизации схем «ИЛИ» для выходных сигналов и функций возбуждения с одновременным до­определением функций возбуждения. Проиллюстрируем это на примере построе­ния схемы для переходов в состояние а33
в табл. 6-10, являющейся частью об­ратной структурной таблицы некоторого автомата. Так как в данном случае конкретный вид входных сигналов безразличен, они представлены в этой таблице в общем виде.

Таблица 6-10. Часть структурной таблицы для иллюстрации вынесения вниз

Исходное состояние

Код исходного состояния

Состояние перехода

Код состояния перехода

Входной сигнал

Выходной сигнал

Обязательные функции возбуждения

a50

a50

a64

a75

a19

a19

a21

1010010

1010010

0010011

1010011

0111111

0111111

0110110

a33

1010000

X1(a50, a33)

X2(a50, a50)

X(a64, a33)

X(a75, a33)

X1(a19, a33)

X2(a19, a33)

X(a21, a33)

y61, y62

y15, y55

y61

y61, y62

y61, y62

y15, y55

            Очевидно, что при построении схем, соответствующих каждой строчке, табл. 6-10, получим семь схем «И», с которых снимаются записанные в этих строч­ках выходные сигналы и функции возбуждения:

            Для получения каждого выходного сигнала или функции возбуждения не­обходимо построить схему «ИЛИ», на которую подать выходы тех схем из «И» 1,  …, «И» 7, с которых снимается этот выходной сигнал или эта функция возбуждения (рис. 6-18, а). Схему на рис. 6-18, а можно проминимизировать с по­мощью вынесения вниз, как это было сделано выше для выходных сигналов. Но так как эта схема соответствует переходам в одно состояние, можно попытаться для ее минимизации доопределить функции возбуждения.

            Как и в рассмотренном выше примере вынесения вниз для выходных сигна­лов, выпишем для каждого выходного сигнала и функции возбуждения номера схем «И», с которых они снимаются. Кроме того, для каждой функции возбужде­ния в скобках запишем номера схем, с которых можно снять эту функцию воз­буждения, если доопределить функции возбуждения на рассматриваемом пере­ходе. Таким образом, каждой функции возбуждения соответствует слово из двух частей: обязательной (без скобок) и необязательной (в скобках).

            Находим пересечения всех выписанных слов, не делая различия между бук­вами в обязательной и необязательной частях. Так, например, пересечение между  и  равно 1, 4, 5, 6 и т. д. Находим, таким образом, все общие части:

                В скобках после общей части, как и выше, записываем номера слов, в ко­торые она входит, но только в том случае, если хотя бы одна буква из общей части’входит в обязательную часть слова. Именно поэтому после общей части Z4 в скобках нет  и , так как все буквы Z4 входят в необязательную часть  и . Кроме того, в верхнем индексе при функции возбуждения ставится число букв из общей части, входящих в необязательную часть функции возбуждения. Например, после общей части Z2 = 1, 4, 5, 6 в скобках стоят. Действительно, две буквы общей части Z2 (1 и 4) стоят в скобках в слове  . Верхний индекс у  равен единице, так как только одна буква из  (1) входит в необязательную часть слова .

Рис. 6-18. Вынесение вниз с доопределением функций возбуждения:

а – схема без вынесения,

б – схема после вынесения с доопределением,

в – схема после вынесения без доопределения

                Цена общей части при вынесении вниз c учетом доопределения подсчитывается по формуле:

                 (6-9)

            где т – число букв в общей части; п – число слов, из которых выносится об­щая часть; r – число слов, полностью совпадающих с общей частью; t – сум­марное число верхних индексов у слов, стоящих в скобках после общей части. Включение t со знаком минус в выражение для W(Z) объясняется тем, что уменьшение цены схемы в результате вынесения вниз учитывается только для обязательной части. По формуле (6-9) найдем цену каждой из общих частей:

W(Z1) = max W(Zi) = 16 (i = 1, 2, 3, 4) – максимальная цена у общей ча­сти Z1
которую и выносим вниз из слов . После вынесения общей части Z1 например, из слова   буквы 1, 2, 4, входя­щие в необязательную часть  становятся обязательными, т.е. происходит доопределение , что равносильно тому, что со схем «И»1, «И»2 и «И»4 снимается функция возбуждения . То же самое справедливо и для других функций, из которых выносится Z1.

            После вынесения вниз Z1 слова  удаляются из исход­ного множества слов, так как все они совпадают с общей частью. Выход схемы, реализующей  Z1, обозначим новой буквой, 8.

            Находим пересечения в новом множестве слов:

            Выносим Z5. Выход схемы «ИЛИ», реализующей Z5, обозначим буквой 9.

            Выносим Z9. Выход схемы «ИЛИ», реализующей Z9, обозначим буквой 10.

            Процедура заканчивается вынесением Z10. Соответствующая схема приве­дена на рис. 6-18, б. Число входов в логические элементы по сравнению с рис. 6-18, а сократилось на 24 входа (W(Z1) + W(Z5) + W(Z9) + W(Z10) =  24). Если проделать вынесения вниз только для обязательных частей слов, соответствующих функциям возбуждения, т.е. без учета доопределения, то придем к схеме на рис. 6-18, в, в которой на девять входов в логические элементы больше, чем в схеме на рис. 6-18, б.

Загрузка...