По таблице переходов 5.10 составлена таблица выходов 5.11, в которую перенесены значения выходных сигналов для каждого устойчивого состояния автомата. Первая цифра в клетках табл. 5.11 указывает на состояние выхода Z1, а вторая-на состояние выхода z2.

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

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

Изменение входных сигналов происходит быстрее, если с неустойчивым состоянием автомата сопоставлять такое состояние выхода, которое имеется у соответствующего устойчивого состояния. Для нашего примера при переходе из состояния (1), в котором выходные сигналы имеют значение 00, в состояние (2) с выходными сигналами 01 необходимо, чтобы в неустойчивом состоящий 2 выходные сигналы имели значение 01. Аналогичным способом заполнены остальные клетки таблицы выходов 5.12,а.

Если требуется, чтобы выходные сигналы появлялись как можно позже, во всех клетках таблицы выходов, соответствующих неустойчивым состояниям таблицы переходов, проставляются состояния выходов, от которых производится переход. Например, при переходе от состояния (1) к состоянию (3) выходные сигналы изменяют свое состояние с 00 на 10. Поэтому в клетке, соответствующей состоянию 3, проставляются 00. Однако в этом случае имеются некоторые ограничения. Если в одной строке находится несколько устойчивых состояний автомата с различными состояниями выходов, то во избежание состязаний на месте неустойчивого состояния ставится состояние выхода, к которому производится переход. Например, при переходе от (3), 10 или от (5), 00 к (6), 01 на месте состояния 6 следует записать 01. Если состязания выходов не учитывать, то на месте неустойчивого состояния ставится значение выходов одного из устойчивых состояний данной строки ( в рассматриваемом случае 00 или 10). Аналогичное положение будет при переходе от (6) и (7) к (2). Состояние выходов с учетом состязаний показано в табл. 5.12,6.

Таблица 5.12

*1*2

Если основным требованием является устранение состязаний выходов и время их появления не учитывается, то при переходе от одного состояния выходов к другому в ряде случаев нет необходимости задавать на переходах состояние всех выходов, можно записывать только значение выхода, которое не изменяется. Состояние же второго выхода будет безразличным. Например, при переходе от (2) или (4) к (5) состояние выходов изменяется с 01 к 00. Единственный выход, который изменяет свое состояние, - это z<t. Поэтому в клетке, соответствующей переходу 5, можно записать 01 или 00, т. е. состояние выхода Zi должно быть равно О, а состояние г-г. безразлично. Аналогично заполняются остальные клетки табл. 5.12,в.

Исключение составляют переходы в табл. 5.2 через неустойчивое состояние 6 и через состояние 2 второй строки, при котором изменяются состояния обоих входов. В этих случаях в неустойчивых состояниях ставится такое значение выходов, которое соответствует устойчивому состоянию. Так, при переходе от (3), 10 и от (5),00 ко (6),01 для неустойчивого состояния 6 указывается состояние выхода 01.

5.3. Минимизация функций

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

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

(склеивания) соседних конституентов.

Такая таблица, используемая для минимизации четырех переменных, содержит четыре строки и четыре столбца. Если столбцам придать значение переменных, имеющих вес 1 и 2, а строкам - значения переменных с весом 4 и 8, то расположение но меров десятичных эквивалентов конституентов будет таким, как показано в табл. 5.13,а.

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

Если функция содержит только три переменные, то табл. 5.13,6 будет содержать две строки, соответствующие переменной y1, имеющей вес 4. Для минимизации функцийс пятью переменными используются две таблицы для четырех переменных (табл. 5.13,в), в одной из которых переменная уз с весом 16 имеет значение 0, а в другой- 1. Каждая клетка одной таблицы является соседней с клеткой другой таблицы. Например, клетка, где записан 0, будет соседней с 16, 1 с 17, 8 с 24 и т. д.

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

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

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

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

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

4.При объединении 16 номеров устраняются четыре переменные и вся функция будет равна 1.

Для иллюстрации рассмотрим минимизацию функции Y1 табл. 5.3, заданной следующим набором обязательных номеров конституентов, при которых функция равна 1, и безразличных номеров (заключены в круглые скобки):

fYl={h 5, 7, 8, 12, 13, 15(2, 9, 14)}.

В соответствии с расположением номеров табл.5.13,а запишем номера конституентов в таблицу, обозначив обязательные номера цифрами в кружках и безразличные-цифрами без кружков; запрещенные номера, при которых функция равна 0, будут соответствовать пустым клеткам (табл. 5.14).

таблица 5.14 Минимизацию начинаем с номеров, имеющих наименьшее число соседних гптномеров конституентов. Такими номерами являются 1, 7, 8 и 12, так как каждый

из них имеет два соседних номера. Номер 1 соседний с номерами 5 и 9, номер 7- с 5 и 15, номер - 8 - с 12 и 9 и номер 12 - с 13 и 8. Если начать объединение с номера 7, то его можно объединить с номером 5 или 15. Объедияя номера 5 и 7, видим, что соседней с ними будет пара номеров 13 и 15. Следовательно, максимальной группой, образующей квадрат, является объединение, состоящее из fi/fномеров 5, 7, 13, 15. Номер 1 объединяется с номерами 5, 13, 9, образующими

группу, расположенную в одном столбце; номера 12, 13, 8, 9 образуют квадрат. У первого объединения пара номеров 5 и 7 расположена в одной строке, где у 1=1 и у2=0, но каждый из номеров находится в разных столбцах. Номер 7 находится в столбце, где х1==1, x2=1, а номер 5-в столбце, где xi=1 и Х2=0. Следовательно, при сложении 5 и 7 исчезнет переменная X2, имеющая разное значение.

Пара номеров 13 и 15 расположена в строке, где у1=1 и у2=1, и в тех же столбцах, что и номера 5 и 7 Следовательно, при объединении номеров 13 и 15 также исчезнет переменная x2.

Эти пары, расположенные в разных строках, отличаются значением Y2. Поэтому эта переменная не войдет в общую конъюнкцию. Последняя будет состоять из переменных, общих для обеих пар. Такими переменными являются X1 и у1. Общая конъюнкция представляет собой логическое произведение X1Y1.

Проделаем операцию объединения номеров в алгебраическом виде. Для этого запишем каждый из номеров конституентов в совершенной нормальной форме. Номер 5 расположен во втором столбце и второй строке, где X1==1, X2=0, у1=1 и Y2=0. Поэтому конъюнкция, соответствующая этому номеру, будетравнаx1x2y1y2.

Аналогичным образом запишем остальные конституенты.

Объединение номеров 5, 7, 13, 15 запишем как логическую сумму конъюнкций отдельных номеров. Используя законы алгебры Буля, произведем упрощение (минимизацию) функции

/V, = Ух У г V хх хг Ух ~Уг V хх хъ Ух Уг V хх хг Ух Уг = = Хх Ух ~Уч. (XzVxz) V*i Ух Уг (х2\/х2)=х1 yt y2V*i Ух У* =

= *1 #1 (#2 V

Объединяя номера 8, 9, 12, 13, получим хлуг; объединение номеров 1, 5, 9, 13 даст - XiXz. Следовательно, минимизированная функция будет иметь следующий вид:

fy 1 == х1 xl V x2Y2 V x1x2(151)

Аналогичным образом по табл. 5.4 получим функцию элемента памяти Уд

fYl = x1xi\/x2y1 V xayt\/xiy2=x1{xi\/tf\/x2Q1\/yi).(5.2)j

Порядок расположения номеров в таблице зависит от принятого расположения столбцов, строк и весов элементов. Например, свойства таблицы не изменятся, если поменять местами первый и третий столбцы или строки, или второй и четвертый столбцы и такие же строки, или изменить веса элементов. Поэтому может существовать ряд таблиц, имеющих разное расположение номеров, но обладающих одинаковыми свойствами. Чтобы не зависеть от принятых весов элементов и расположения строк и столбцов, в таблицу заносят не номера конституентов, а их значения, т. е. 1, О или -.

При использовании в качестве ЭП триггеров типа RS для минимизации функций составляют таблицы для каждого из входов R и 5, как показано в табл. 5.15, составленной на основе табл. 5.5 и 5.6.

Таблица 5.15

В табл. 5.15 штрихом показаны объединения номеров состояний каждой из таблиц, приводящие к наиболее простой форме функций:

Fsxxxy; FRl=~x1~y<i;(5.3)

Fs, = хУхV*i х.г; FHl = хг х2.(5.4)

Минимальная .форма функции /"л, получена за счет объединения двух пар номеров, расположенных в крайних столбцах, а функция FS2- при объединении двух пар номеров крайних строк и столбца.