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

Глава третья

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

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. Таблица переходов частичного автомата

–

Очевидно, что пары должны быть развязаны в каждом из массивов переходов М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)

–

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

–

Из табл. 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)

–

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

–

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

–

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

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

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

–

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

–

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

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

–

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

Все остальные пары развязаны. Далее исключаем переменную и получаем табл. 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 = 23 – 8, и они разбиваются на 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

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

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

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

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

x1x4

x4x3

x1x4

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

Класс эквивалентности	Исходное состояние	Класс перехода	Входной сигнал	Выходной сигнал
B1	a1	B2 B2 B2 B1		Y1 Y3 Y2 Y6
B1	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
B3	a7	B2 B4		Y3 Y5
B4	a8	B1	1	Y1
B4	a9	B1	1	Y1

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

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

Класс эквивалентности	Исходное состояние	Класс перехода	Входной сигнал	Выходной сигнал
C1	a1	C2 C3 C2 C1		Y1 Y3 Y2 Y6
C1	a5	C2 C3 C2 C1		Y1 Y3 Y2 Y6
C2	a2	C4 C5 C4 C5		Y5 Y4 Y5 Y4
C2	a4	C4 C5		Y5 Y4
C3	a3	C4 C4		Y5 Y4
C4	a6	C2 C5		Y3 Y5
C4	a7	C2 C5		Y3 Y5
C5	a8	C1	1	Y1
C5	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. Обратная структурная таблица автомата Мура

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

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

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

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

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

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

0111

1001

a1 (–)

0001

a7 (y2)

0010

0001

0010

(y2, y3, y4, y5)

0011

1000

a4 (y7)

0100

0011

1000

a5 (y6)

0101

0100

0101

a6 (y8)

0110

0100

0101

0110

a7 (y9)

0111

a8 (y10, y11)

1000

0100

0101

a9 (y12)

1001

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

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

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

(6-1)

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

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

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

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

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

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

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

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

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

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

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

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

000

001

011

101

010

000

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

y4y8

y4y9

–

000

001

011

101

010

110

001

y1y2

y1y3

y1y4

–

001

011

001

101

y5y6

000

001

101

110

010

y7y8

001

101

100

110

табл. 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, а приведено на рис. 6—6, б. Логическая схема для переходов (ат, 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. Общий вид структурной таблицы с узлами

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

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

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

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

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

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

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

K(am)

–

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:

а остальные t–n членов имеют вид

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

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

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

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

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

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

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

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

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

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

001

101

–

101

010

–

000

011

–

000

y4y9

y4y8

–

000

001

011

110

001

y1y4

y1y2

y1y3

y1y4

–

001

011

001

101

y5y6

–

000

110

010

y7y8

–

100

110

Задачу вынесения общего множителя за скобки, в отличие от задачи в следующем параграфе, будем называть вынесением вверх по аналогии с тем, что общий множитель выносится над схемой «ИЛИ». Рассмотрим один из возможных алгоритмов вынесения вверх на примере формулы (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. Часть обратной структурной таблицы

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

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

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

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

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

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

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

11101

11111

00111

00101

11110

00100

y1, y2

y1, y3

y1, y2

y1, y6, y7

y1, y4, y5

y1, y2

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

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

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

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

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

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

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

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

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

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

a50

a64

a75

a19

a21

1010010

0010011

1010011

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

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, б.

В помощь студентам ПМР