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

Для выбранной синхронной модели автомата применим структурную схему, приведенную на рис.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

Символ	р₃	р₂	р₁
х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

Символ состояния	Код состояния	Функции возбуждения
z₄ z₃ z₂ z₁	D₄	D₃	D₂	D₁
r₄
r₂
r₁₁
r₅
r₃
r₁
*		*	*	*	*
r₀
*		*	*	*	*
r₈
r₉
r₁₀
*		*	*	*	*
r₇
*		*	*	*	*
r₆

В графе «Код состояния» таблицы представлены все возможные наборы значений внутренних переменных 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₃. Во втором переходе (0111 – 0000) изменяют свои значения сразу три переменных z₁, z₂, z₃, причем из 1 в 0, значит, в столбцах D₁, D₂, и D₃ должны быть записаны символы `x₂. Но так как в столбце D₂ уже записан символ `x₃, а изменение z₂ в обоих случаях происходит из 1 в 0, то в столбце D₂ должно быть записано выражение `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₁ (координата 0001) наилучшим будет покрытие: вершина `x₇ (0101), зачерненная вершина (1101) и вершина `x₀ (1001). Тогда импликанта будет иметь вид: `x₁. z₁. `z₂. `z₃. `z₄. В то же время, для вершины `x₂ (0111) наилучшим будет покрытие с вершинами, помеченными звездочками (координаты 0110 и 1110), и зачерненной вершиной (1111), а импликанта будет иметь вид: `x₂z₂z₃. Для вершины `x₇ (0101) – вершины с координатами 0111,1111 и 1101 (две последние зачернены), а импликанта имеет вид `x₇z₁`z₂z₃. Здесь переменная `z₂ в импликанте показывает отличие в вершине `x₇ от вершины`x₂. Проделав аналогичные операции для остальных вершин, получим минимальную ДНФ функции D₁:

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

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

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

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

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

где

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

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

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

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

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

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

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

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

Рис. 9

РЕАЛИЗАЦИЯ АВТОМАТА

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

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

Наибольшее распространение получили микросхемы серий КР555 и КР1533, выполненные по технологии ТТЛШ (транзистор-транзисторная логика с диодами Шоттки), а также серий К561 или КР1561, выполненных по технологии КМДМ (на основе комплементарных полевых транзисторов типа металл-диэлектрик-полупроводник).

Несмотря на различие параметров, схема автомата будет мало завесить от типа микросхем, поэтому выберем для применения в реализации автомата интегральные микросхемы серии КР555. Рекомендуемый набор микросхем приведен на рис.10.

Другие элементы, реализующие более сложные функции, приведены на рис.11. и рис.12. Здесь же приводятся таблицы состояний. Так, микросхема КР555ЛП5 реализует функцию «исключающее ИЛИ», а выходной сигнал соответствует логическому уравнению Q=AÅB=`A`B+`B`A, где Å – символ суммирования по модулю 2.

Микросхема КР555ИД4 – два дешифратора-демультиплексора. Она может выполнять функции двойного дешифратора с 2 на 4; двойного демультиплексора на 4; дешифратора с 3 на 8; демультиплексора 1 на 8. В частности, дешифратор (рис.7) может быть реализован на этой микросхеме.

Микросхема имеет два адресных входа A₀ и A₁, они служат для одновременного управления выходными состояниями DC_A и DC_B. В каждом дешифраторе имеется отдельный стробирующий вход `E_A и `E_B, а также по одному информационному `E_A и `E_B (инверсный).

Для дешифрации трехразрядного кода следует соединить`E_A и `E_B, `E_A и E_B.

Логические элементы

Рис. 10 (начало)

Рис. 10 (окончание)

Рис. 11

Рис. 12

ВХОДЫ	ВЫХОДЫ
Адрес	Разрешен.
_ E_а и Е_в	А₀	А₁	_ _ E_а и Е_в	Y₅	Y₆	Y₇	Y₈	Y₁	Y₂	Y₃	Y₄
Х	Х	Х

Таблица состояний КР555ИД4

В качестве элементов памяти выбраны триггеры D-типа. Поэтому рекомендуется использовать микросхему КР555ТМ8, содержащую четыре триггера D-типа. Структура микросхемы ТМ8 представлена на рис.13

Рис. 13

Режим работы	ВХОДЫ	ВЫХОДЫ
R	D	C	Qⁿ⁺¹	Qⁿ⁺¹
Сброс		Х	Х
Загрузка “1”			↑
Загрузка “0”			↑

Таблица состояний триггера КР555ТМ8

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

Схема реализации дана на рис. 14.

Реализовать функцию – это значит представить ее в базисе собственных функций выбранного набора элементов. Сложность реализации системы может быть уменьшена за счет выделения общих частей, которые могут быть реализованы отдельно, или использования полученных при реализации функции D₁ логических выражений. Цель совместной реализации – формирование функций возбуждения минимальным числом корпусов из набора интегральных микросхем. При этом поиск наилучшей реализации основывается на использовании правил де Моргана.

Реализация дешифратора входных сигналов, помимо приведенной на рис.12, может быть выполнена на микросхеме КР555ИД4.

Реализация функции возбуждения `S₅ RS-триггера сигнала «Ошибка» (`z₅) может быть выполнена с использованием микросхемы КР555ЛП5.

Сигнал начальной установки НУ реализуется путем подачи на входы D триггеров вспомогательного регистра сигналов, соответствующих выбранному начальному состоянию (в рассматриваемом примере это r₀=0111, что соответствует D₁=1, D₂=1, D₃=1, D₄=0).

Эти сигналы объединяются логическим «ИЛИ» с функциями возбуждения D₁, D₂, D₃, D₄.

Сигналом НУ триггеры основного регистра устанавливаются в состояние 0000.

Синхросигналами t₁ и t₂, подаваемыми на вход С, оба регистра устанавливаются в начальное состояние. Если начальное состояние имеет код 0000, установка может производиться путем подачи сигнала начальной установки на вход `R триггеров вспомогательного и основного регистров.

Реализация формирования сигнала начальной установки для триггера 1 регистра 1 рассматриваемого примера приводится на рис.15.

Рис. 14

Рис. 15

Начальная установка автомата осуществляется сигналом НУ=1 каждый раз перед подачей на вход автомата первого символа очередной распознаваемой цепочки. При этом длительность сигнала начальной установки должна быть такой, чтобы синхросигнал t₁ поступал во время действия сигнала НУ. Так как триггеры основного регистра установлены в состоянии 0, и следовательно для установки 4-го триггера вспомогательного регистра в состояние 0 нет необходимости использования объединения D₄ и НУ по «ИЛИ».

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

При составлении принципиальной схемы следует руководствоваться следующими правилами:

- элементы не могут иметь незадействованные входы, они либо соединяются с задействованными, либо на них подаются константы;

- подача на вход элемента константы 0 осуществляется соединением этого входа с общим проводом, подача константы 1 – соединением этого входа с выходом инвертора, вход которого соединен с общим проводом;

- объединение входов одного элемента не увеличивает нагрузку на выход элемента, соединенного с этими входами;

- максимальная нагрузочная способность выхода элемента для микросхем серии КР555 и КР1533 равна 20, для серий КР561 и КР1561 – 100, что означает невозможность соединения его более чем с 20 (или 100) входами различных элементов.