Структурный синтез автомата

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

Рис. 6

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

Триггерный регистр 2, запись информации в который осуществляется вторым синхросигналом t₂, необходим для того, чтобы сделать все состояния автомата устойчивыми и исключить влияние состязаний. Триггеры регистра 1 называются вспомогательными, а триггеры регистра 2 – основными. Сигнал z₅ является сигналом «Ошибка», а сигнал z₆ - сигналом принадлежности входной цепочки символов языку с грамматикой G”. Сигналы Р₁, Р₂, Р₃ – закодированные сигналы входных символов, Р₄ – сигнал признака конца цепочки. Сигналом НУ (начальная установка) триггеры автомата устанавливаются в начальное состояние.

В общем случае сложность реализации автомата, точнее дешифратора и комбинационной схемы, зависит от способа кодирования входных символов. Предположим, что входные сигналы закодированы двоичным кодом, тогда входные символы x₀ ÷ x₇ могут быть представлены тремя кодирующими переменными p₁, p₂, и p₃. В качестве символа окончания входной цепочки может быть использован любой свободный входной символ из x₀ ÷ x₇. Если таких нет, то необходимо ввести дополнительный, обозначив его через переменную p₄.

Выделив в структурной схеме автомата дешифратор, можно упростить комбинационную схему и тем самым облегчить синтез автомата. С помощью дешифратора входные символы, закодированные двоичными переменными p₁, p₂, и p₃, преобразуются в унитарный код, в котором только одна из переменных принимает значение 1, в то время как все другие равны нулю. Поэтому выходы дешифратора можно обозначить x₀ ÷ x₇. В свою очередь символ окончания входной цепочки р₄ принимает значение 1 по окончании любой входной цепочки.

Пусть входные символы закодированы так, что их номера являются десятичными эквивалентами двоичных кодов (N=p₁×2⁰+ p₂×2¹+p₃×2²), тогда, составив таблицу кодов (табл.1), получим, например:

Таблица 1

Символ	р3	р2	р1
х0
х1
х2
х3
х4
х5
х6
х7

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

Выберем для реализации схемы автомата микросхемы серии КР555.

Реализация дешифратора на микросхеме данной серии приводится на рис.7.

Четыре инвертора на входе используются для снижения нагрузок на источники сигналов p₁, p₂, p₃ и p₄. Логическую функцию ЗИ – НЕ выполняют 8 логических элементов. 8 инверторов на выходе позволяют получить сигналы унитарного кода x₀ ÷ x₇, инверсии этих сигналов (x₀ ÷ x₇) получаются непосредственно с входов элементов ЗИ – НЕ.

Для реализации дешифратора в указанном виде необходимо 16 инверторов и 8 логических элементов ЗИ – НЕ.

В принципиальной схеме инверторы реализуются на микросхеме КР555ЛН1, содержащей в одном корпусе 6 инверторов, логические элементы ЗИ – НЕ на микросхеме КР555ЛА4.

Так как для работы комбинационной схемы при фиксации конца цепочки могут быть необходимы сигналы p₄ и `р₄, то для их формирования используются два инвертора 15, 16.

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

Рис. 7

Построить функцию переходов – это значит найти переключательную функцию кодирующих (внутренних) z₁ ÷ z₄ переменных. В соответствии со структурной схемой автомата каждая внутренняя переменная представляет состояние элемента памяти – триггера. По переключательным функциям внутренних переменных могут быть найдены функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата.

Сложность функции возбуждения, а значит и сложность комбинационной схемы, в общем случае зависит от типа триггера. Известны основные три типа триггера, используемые в элементах памяти – D-триггер, RS-триггер и Т-триггер. В принципе, можно использовать любой из типов триггеров, однако мы остановим свой выбор на триггере типа D. D-триггер лишь задерживает входной сигнал, поэтому его функция возбуждения D совпадает с функцией переключения внутренней переменной z_i.

Запишем функции возбуждения D-триггеров для рассматриваемого примера и результаты занесем в таблицу 2.

Таблица 2

Символ состояния	Код состояния	Функции возбуждения
z4 z3 z2 z1	D4	D3	D2	D1
r4
r2
r11
r5
r3
r1
*		*	*	*	*
r0
*		*	*	*	*
r8
r9
r10
*		*	*	*	*
r7
*		*	*	*	*
r6

В графе «Код состояния» таблицы представлены все возможные наборы значений внутренних переменных z₁, z₂, z₃ и z₄ в порядке возрастания их двоичных эквивалентов. В графе «Символ состояния» эти наборы помечаются условными обозначениями (r₀ ÷ r₁₁) в соответствии с выбранным вариантом размещения состояний автомата (рис. 5).

Четыре набора, которые не соответствуют никаким состояниям автомата, помечены звездочками.

Принцип составления функций возбуждения заключается в следующем.

Рассмотрим заполнение, например, строки r₀ табл. 2. Из состояния r₀ (код 0111) возможны три перехода: в состоянии r₁ (код 0101) при поступлении на вход символа x₃, в состоянии r₄ (код 0000) при воздействии x₂ и в состояние r₆ (код 1111) при воздействии x₅. В первом переходе (0111 – 0101) изменяет свое значение внутренняя переменная z₂ из 1 в 0, поэтому в столбце D₂ должен быть записан символ `x<sub>3</sub>. Во втором переходе (0111 – 0000) изменяют свои значения сразу три переменных z<sub>1</sub>, z<sub>2</sub>, z<sub>3</sub>, причем из 1 в 0, значит, в столбцах D<sub>1</sub>, D<sub>2</sub>, и D<sub>3</sub> должны быть записаны символы `x₂. Но так как в столбце D₂ уже записан символ `x<sub>3</sub>, а изменение z<sub>2</sub> в обоих случаях происходит из 1 в 0, то в столбце D<sub>2</sub> должно быть записано выражение `x₃`n`x₂. Последнее означает, что переход из 1 в 0 переменной z₂ происходит при поступлении на вход схемы символа x₂ или символа x₃. Наконец в третьем переходе (0111 – 1111) при поступлении символа x₅ изменяется только переменная z₄ из 0 в 1, поэтому в столбце D₄ записывается символ x₅.

Аналогично заполняются остальные строки в таблице, причем при отсутствии изменений любой из переменных z₁, z₂, z₃, z₄, в каком – либо состоянии в соответствующий столбец D_i записывается значение переменой z_i, определяемое данным состоянием.

Значение D_i в четырех строках, отмеченных звездочками, могут быть заданы произвольно.

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

Для нахождения минимальной ДНФ функции возбуждения удобно воспользоваться ее геометрическим представлением на вершинах 4-мерного куба, которое для функции Д₁ представлено на рис.8. На этом рисунке вершины, в которых значение функции равно 1, помечены зачерненными кружками, вершины, на которых значение функции равно 0, не имеют отметки, вершины, на которых функция не определена, помечены звездочками. Вершины, помеченные входными переменными или логическими выражениями из них, обозначаются полузачеркнутыми кружками. Этим отражается тот факт, что в этой вершине значение функции равно 1, если соответствующая переменная (или выражение) равна 1, и 0 – в противном случае. Причем инверсные и неинверсные значения переменных помечаются противоположным полузачеркиванием кружка (рис 8). При выполнении минимизации сначала выписываются импликанты (коньюкции), покрывающие зачерненные вершины (и, возможно, некоторые вершины, помеченные звездочками).

Рис. 8

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

На рис.8 для функции D₁ мы имеем две зачерненные вершины с координатами 1100 и 1110 (иначе, доопределив функцию D₁) запишем импликанту, покрывающую эти вершины. Она будет иметь вид z₃, z₄, так как эти переменные однозначно определяют данные вершины, (переменные z₃ и z₄ не меняют своих значений на этих вершинах, соответственно z₁ и z₂ меняют значения). Выделим рассмотренное жирными линиями на рисунке.

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

Например, для вершины `x<sub>1</sub> (координата 0001) наилучшим будет покрытие: вершина `x₇ (0101), зачерненная вершина (1101) и вершина `x<sub>0</sub> (1001). Тогда импликанта будет иметь вид: `x₁. z₁. `z<sub>2</sub>. `z₃. `z<sub>4</sub>. В то же время, для вершины `x₂ (0111) наилучшим будет покрытие с вершинами, помеченными звездочками (координаты 0110 и 1110), и зачерненной вершиной (1111), а импликанта будет иметь вид: `x<sub>2</sub>z<sub>2</sub>z<sub>3</sub>. Для вершины `x₇ (0101) – вершины с координатами 0111,1111 и 1101 (две последние зачернены), а импликанта имеет вид `x<sub>7</sub> z<sub>1</sub>`z₂ z₃. Здесь переменная `z<sub>2</sub> в импликанте показывает отличие в вершине `x₇ от вершины`x₂. Проделав аналогичные операции для остальных вершин, получим минимальную ДНФ функции D₁:

Упрощая выражение, окончательно получим минимальную ДНФ:

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

Теперь рассмотрим переключательные функции z₅ и z₆, представляющие выходные сигналы автомата. Сигнал z₆, свидетельствующий о принадлежности цепочки входных символов языку с грамматикой G“, принимает значение 1, если автомат находится в заключительном состоянии (в нашем случае – r₁₁) и на его вход поступает сигнал признака конца цепочки символов x₈=1, в противном случае z₆=0. Следовательно, z₆= x₈`z<sub>1</sub> z<sub>2</sub> `z₃`z₄.

Функция сигнала ошибки z₅ может быть построена точно так же, как функции D₁ ÷ D₄, но для уменьшения сложности ее реализации можно воспользоваться следующим условием.

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

,

где

С целью исключения возможного влияния функциональных состязаний и фиксации ошибки до момента принятия решения сигнал z₅ удобно представить состоянием триггера, стробируемого синхросигналом t₂. В качестве триггера, реализующего сигнал z₅, может быть выбран любой тип триггера, в том числе и RS – триггер. Сигнал z₆ тоже необходимо стробировать, но синхросигналом t₁. При этом необязательно представлять этот сигнал состоянием триггера.

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

При этом минимальная ДНФ функции находится не инверсией выражения для прямого значения, а по ее геометрическому представлению. Для этого необходимо проинвертировать выражения, помечающие вершины с полузачеркнутыми кружками и провести минимизацию, считая, что вершины с зачеркнутыми кружками представляют нули функции, а неотмеченные вершины – единицы функции. Получив ДНФ для инверсной функции `D<sub>i</sub>, необходимо проверить ее сложность, и если она меньше сложности прямого значения D<sub>i</sub>, то использовать схему получения инверсной функции. Для получения прямого значения от инверсной функции`D_i, необходимого для подачи на информационный вход, нужно проинвертировать результирующий сигнал.

Так, рассмотрим прямую и инверсную функции возбуждения для информационного входа D₃. Геометрическое представление для D₃. дано на рис. 9.

Функция возбуждения D₃. будет иметь вид

Сложность функции – 15.

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

.

Сложность функции – 17. Необходимо реализовать функцию D₃.

Рис. 9

Дата добавления: 2014-12-08