Структурный и логический синтез распознающего автомата.

Переходя к синтезу распознающего автомата, необходимо условиться о способе его реализации. Уже выбрана синхронная модель. Теперь примем соответствующую структурную схему, которая изображена на рис.7. Она состоит из комбинационной схемы, реализующей функции возбуждения элементов памяти; памяти, построенной из триггеров по двухрегистровой схеме; дешифратора входных сигналов. При синхронной реализации автомата нет необходимости бороться с функциональными и логическими состояниями в комбинационной схеме и дешифраторе, так как предполагается, что все переходные процессы в этих схемах успевают закончиться к моменту прихода синхросигнала t₁, стробирующего прием информации с выходов комбинационной схемы в триггеры регистра 1. Второй триггерный регистр, прием информации в который стробируется синхросигналом t₂, необходим для того, чтобы сделать все состояния автомата устойчивыми и исключить влияние гонок. Триггеры регистра 1 будем называть вспомогательными, а регистра 2 - основными. Сигнал z₅ является сигналом ОШИБКА, а сигнал z₆ - сигналом принадлежности входной цепочки символов языку с грамматикой G’’. С помощью сигнала НУ осуществляется начальная установка основных триггеров автомата.

Рисунок 7

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

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

 

 

Рисунок 8 Таблица 8

Символ	p1	p2	p3
x0 x1 x2 x3 x4 x5 x6 x7

Реализация дешифратора показана на рис. 8. Она содержит 8 элементов типа 3 И-НЕ и 14 входных инверторов, причем 3 входных инвертора используются лишь с целью уменьшения нагрузки на входные сигналы. Комбинационная схема автомата реализует функцию его переходов. Исходным заданием для ее построения является граф переходов (рис.3) или таблица переходов (табл.7) и выбранный вариант кодирования состояний. Построить функцию переходов - значит найти переключательную функцию кодирующих (внутренних) переменных. В соответствии со структурной схемой автомата каждая внутренняя переменная представляется состоянием элемента памяти - триггера. По переключательным функциям внутренних переменных могут быть найдены функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата. Сложность функций возбуждения и, соответственно, сложность комбинационной схемы существенно зависит от выбора тира триггера. Известны три основных типа триггеров - это D-триггер, RS-триггер и Т-триггер. Поскольку заранее невозможно отдать предпочтение ни одному из этих типов, необходимо построить функции возбуждения для всех указанных типов триггеров. Для нашего примера результаты выполнения этапа представлены в табл. 9.

В графе «Код состояния» таблицы приведены все возможные наборы значений внутренних переменных z₁z₂z₃z₄.В графе «Символ состояния» в соответствии с рис.8 эти наборы помечены условными обозначениями состояний. Четыре набора, которые не соответствуют никаким состояниям, помечены прочерками. Столбцы третьей, четвертой и пятой граф определяют функции возбуждения D, RS, и Т-триггеров соответственно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Построим теперь переключательные функции z₅, z₆, представляющие выходные сигналы автомата. Сигнал z₆ принадлежности цепочки входных символов языку с грамматикой G’’ принимает значение 1, если автомат находится в заключительном состоянии r₁₁ или r₁ и на его вход поступает сигнал конца цепочки символов х₃ = 1; в противном случае z₆ = 0. Следовательно, z₆ = x₃z₂z₃z₄. Функция сигнала ошибки может быть построена точно так же, как функция z₁ - z₄, но для уменьшения сложности её реализации воспользуемся следующим соображением. Сигнал ошибки вырабатывается тогда, когда при поступлении очередного входного символа внутреннее состояние автомата не изменяется (кроме случая, когда автомат находится в заключительном состоянии и на его вход подаётся символ конца цепочки). Поэтому для нашего случая z₅ = f₁vf₂vf₃vf₄vz₆, где f_i - функция, принимающая значение 1, если i - й триггер переключается при переходе автомата из одного состояния в другое. Очевидно, что для Т-триггера f_i =T_i, для D-триггера f_i = Z_iD_i v z_i D_i и для RS-триггера f_i = z_i R_I v z_i S_i;. Каждый D и RS-триггер вносит в функцию переключения z₅ сложность, равную 4, а Т-триггер - сложность 1. Эту оценку следует прибавить к оценкам сложности функций переключения, приведенных в табл. 9, и выбрать минимальные по сложности функции возбуждения (и типы) триггеров.

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

 

Реализация автомата

На рис. 13 приведен набор элементов - интегральных микросхем (ИМС) малой степени интеграции - серии К155 [4], рекомендуемый для построения автомата. Этот набор содержит семь логических элементов и два элемента памяти.

Рис. 13. Рекомендуемый набор элементов ИМС серии К155

 

 

В состав ИМС К155ТМ7 входят 4 D-триггера. Каждая пара триггеров имеет один общий сигнал стробирования. Если прямые выходы одной пары триггеров соединить с D-входами другой пары триггеров, то одним корпусом реализуются два разряда двухрегистровой памяти. К сожалению, эти D-триггеров не имеют отдельного входа для начальной установки. Поэтому установку их следует осуществлять через D-вход, т.е. необходимо ввести переменную начальной установки в функцию возбуждения, что приводит к усложнению этой функции.

ИМС К155ТВ1 представляет собой один JK-триггер, который имеет три конъюнктивных входа J, три конъюнктивных входа К, вход стробирующего сигнала С и два входа начальной установки в 0 (R) и в1 (s). Структура триггера такова, что он состоит из двух вспомогательных и одного основного триггеров, т.е. построен по двухрегистровой схеме с разнополярным управлением [6]. При С=1 осуществляется прием информации в один из вспомогательных триггеров, а при С=0 - перепись информации в основной триггер. Поэтому JK-триггер может быть непосредственно использован в качестве элемента памяти автомата. В этом случае тактирование автомата осуществляется с помощью только одной последовательности синхроимпульсов. При J=S и K=R JK-триггер работает как RS-триггер, а при J=K=T - как Т-триггер. С помощью входных сигналов

R и s основной триггер JK-триггера может быть принудительно установлен в начальное состояние 0, если R=0, S=1, и 1, если S=0, R=1; при нормальной работе JK-триггера входные сигналы s и R должны быть равны 1.

Существенные отличия между D и JK-триггерами в способах управления и осуществлении начальной установки свидетельствует о нежелательности использования триггеров обоих типов в качестве памяти автомата.

Выпишем систему функций, представления которых получены после выполнения этапа минимизации:

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

Сигнал начальной установки НУ реализуется с помощью инвертора, выход которого соединяется с входами R всех триггеров автомата z₁ – z₅. Начальная установка автомата осуществляется сигналом НУ=1 каждый раз с подачей на вход автомата первого символа очередной распознаваемой цепочки (или одновременно с его подачей).