9.7. Синтез автомата – распознавателя последовательности

Дано: кодовая последовательность 0-1-3-2 двоичного двухразрядного сигнала (в десятичном коде).

Получить ПФ, описывающие соответствующий конечный автомат-распознаватель последовательности (рис. 75).

Рис. 75. Распознаватель последовательности на входах а, b

Последовательность поступает на входы a,b конечного автомата (КА):

Это правильная последовательность изменения входов a,b в соответствии с заданием.

Возможны и неправильные последовательности из алфавита А={0,1,2,3}.

Ограничим возможные неправильные коды изменением только одного двоичного разряда.

Рассмотрим соответствующий квадрат соседних чисел (рис. 76, т.к. всего два входа).

Рис. 76. Иллюстрация изменения входов

Направление изменения входных кодов показано стрелками. Видно, что в начале из 00 (0) имеем переход в 01 (1). Это если последовательность правильная. А если не правильная?

Тогда возможен лишь один вариант (рис. 77).

Рис. 77. Иллюстрация возможного нарушения последовательности:

из 00(0) в 10(2)

На втором шаге правильно: 01 (1) в 11 (3), а неправильно (рис. 78)?

Рис. 78. Иллюстрация возможного нарушения последовательности:

из 01(1) в 00(0)

Т.е. возможен возврат, в 00.

Аналогично на третьем шаге неправильным будет переход (рис. 79) из 11 (3) в 01 (1).

Рис. 79. Иллюстрация возможного нарушения последовательности:

из 11(3) в 01(1)

Таким образом, можно построить граф возможных последовательностей (рис. 80).

Рис. 80. Граф последовательностей распознавателя 0-1-3-2

Таким образом, имеем всего 4 последовательности:

1. 0-1-3-2 (правильная);

2. 0-2 (неправильная);

3. 0-1-0 (неправильная);

4. 0-1-3-1 (неправильная).

Строим первичную таблицу переходов (ПТП) соответствующего конечного автомата – распознавателя последовательности 0-1-3-2 (табл. 62).

Таблица 62

Первичная таблица переходов-выходов распознавателя 0-1-3-2

Здесь (см. табл. 62) кружком обведены устойчивые такты работы автомата-распознавателя. Переход от одного устойчивого такта в соответствующей строке таблицы переходов-выходов к другому осуществляется через неустойчивый такт. В каждой строке ПТП только один устойчивый такт, номер которого соответствует номеру строки.

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

Это удобно делать путем построения графа объединения строк. В таком графе число вершин равно числу строк ПТП. В нашем случае – 7. Ребром соединяются вершины, соответствующие двум строкам, которые можно слить в одну строку, т.е. в этих строках клетки не противоречат друг другу. Такими клетками будут:

1) пустые клетки и клетки с цифрами, и наоборот;

2) клетки с цифрой i и клетки с цифрой в кружке, и наоборот, т.е. соответствующие неустойчивый и устойчивый такты сливаются в один устойчивый такт.

Граф объединения строк показан на 81.

Рис. 81. Граф объединения строк

Теперь в графе объединения строк необходимо выделить минимальное количество максимальных полных подграфов. В нашем случае это подграфы 3,4,6,7; 1,5 и одна вершина 2.

Возможны другие варианты объединения. Но ни при одном варианте мы не получим две строки (это идеал – к нему надо стремиться).

Получим минимизированную таблицу переходов (табл. 63).

Таблица 63

Минимизированная таблица переходов

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

Кодирование может иметь вид:

I: 00

II: 01

III: 11

Т.е. необходимо два двоичных разряда, которые обозначим y₁y₂. Это не что иное, как текущее состояние автомата, которое принято обозначать у₂(t) y₁(t) или сокращенно у₂ y₁(t).

Теперь получим таблицу переходов-выходов (ТПВ, табл. 64), в которой указывается, как автомат переходит из текущего состояния (коды строки) в последующее (у₂y₁(t+1) – код в некоторой клетке) при различных комбинациях входов ab.

Таблица 64

Таблица переходов-выходов

Код клетки – это соединение (конкатенация) двоичного кода строки и столбца, представленные в виде десятичного числа. Очевидно, что кружки в МТП и ТПВ располагаются в одинаковых клетках. Если такт устойчивый, то в кружке ТПВ в числителе указывается номер соответствующей строки. Если такт неустойчивый – то указывается код той строки, в которую осуществляется переход. В знаменателе указываются выходные сигналы z₂z₁. Они берутся из первичной таблицы переходов-выходов. Так, если в клетке МТП находится цифра 5 (пятый такт), то из пятой строки ПТП берется код 10 (нарушение последовательности). Указываем это число в клетке 2 ТПВ ().

Теперь получаем все четыре ПФ, описывающие наш автомат в символической форме:

По этим ПФ можно построить схему автомата, предварительно проведя минимизацию. Получим структурную схему автомата (рис. 82).

Рис. 82. Структурная схема автомата-распознавателя