Канонический метод структурного синтеза

 

 

Основной задачей структурной теории является задача построения композиций автоматов. Из элементарных автоматов (ЭА) строят более сложные автоматы.

 

Композиции могут быть последователь- ными, паралельными и смешаными.

Число состояний автомата, получен-

ного в результате композиции несколь-

ких, равно произведению чисел состоя-

ний этих автоматов.

 

 

Если из некоторого набора ЭА можно построить любой автомат, то набор структурно полон.

Для произвольных структурно полных систем нет алгоритма построения ком- позиций (кроме перебора и проверки всех схем).

 

 

Для определенного класса ЭА есть канонический метод структурного синтеза.

Метод оперирует с ЭА Мура, облада- ющими полнотой системы переходов и выходов, и комбинационными логичес- кими элементами.

 

Полнота переходов - возможность пере-

хода от любого S_i(t) к любому S_i(t+1).

Полнота выходов - взаимная однозначность Y = F(S). ( Любое S(t) можно «опознать» по Y(t). )

Обычно берутся ЭА Мура с двумя сос- тояниями.

 

 

Поведение ЭА Мура удобно описывать матрицами переходов.

ЭА типа Д.

 

 

(t) (t+1)

ЭА типа T.

 

K(t) J(t) Q(t+1) 0 0 Q(t) 0 1 1 1 0 0 1 1 Q(t)

K(t)

0-0 ~ 0 0-1 ~ 1 1-0 1 ~ 1-1 0 ~

J(t)

Q(t) Q(t+1)

KJQ Q 000 0 001 1 010 1 011 1 100 0 101 0 110 1 111 0

(t+1)

(t)

ЭА типа RS.

 

 

Неопределенность в таблице переходов означает непредсказуемость поведения ЭА.

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

 

 

ЭА типа JK.

 

K(t)

J(t)

155

 

 

Матрицы переходов описывают функции возбуждения ЭА, задающие значения входов ЭА в такте t, которые обеспечивают переход ЭА к такту (t+1)

из текущего состояния к требуемому.

 

 

Основная идея канонического метода структурного синтеза автоматов в сведении задачи к синтезу КС.

 

Этапы алгоритма

1. Кодирование входного, выходного и афавита состояний символами структур- ного алфавита.

 

 

Пример

 

 

 

2.Построение кодированных

таблиц (функций) переходов и выходов.

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

 

159

. . .

. . .

. . .

. . .

x0 x1 Q0 Q1 J0 J1 Q0 Q1 Д0 J1 K1 0 0 0 0 0 1 0 0 0 0 ~ . 0 1 . 1 0 1 ~ 1 . 1 0 . 1 0 1 0 ~ . 1 1 . ~ ~ ~ ~ ~

. . .

. . .

S(t+1)

S(t)

Пример (продолжение).

 

3. Построение функций возбуждения для ЭА.

Полагаем, что тип каждого ЭА задан.

Выбор типов ЭА, как и вариантов коди-

рования алфавитов, здесь не рассматри-

ваем.

 

 

Пример (продолжение).

Предположим, что ЭА₀ - типа Д, а ЭА₁ - типа JK.

 

4. Построение схемы.

 

Имея функции выходов и возбужде-

ния, можно построить реализующие

их КС. Методы синтеза КС нам изве-

стны. ЛЭ должны образовывать функ-

ционально полный набор.

 

Пример (окончание).

 

 

 

Сложность построенной схемы в основ- ном определяется сложностью КС j и КС f. Оценить сложность этих КС мож- но по числу реализуемых функций и по числу их аргументов. (Для конкретных бф оценка может уточняться.)

 

 

 

Каноническая реализация автоматов Мили и Мура подобна и в общем случае имеет такой вид:

 

Автомат Мили:

 

 

Автомат Мура :