Канонический метод структурного синтеза
Основной задачей структурной теории является задача построения композиций автоматов. Из элементарных автоматов (ЭА) строят более сложные автоматы.
Композиции могут быть последователь- ными, паралельными и смешаными.
Число состояний автомата, получен-
ного в результате композиции несколь-
ких, равно произведению чисел состоя-
ний этих автоматов.
Если из некоторого набора ЭА можно построить любой автомат, то набор структурно полон.
Для произвольных структурно полных систем нет алгоритма построения ком- позиций (кроме перебора и проверки всех схем).
Для определенного класса ЭА есть канонический метод структурного синтеза.
Метод оперирует с ЭА Мура, облада- ющими полнотой системы переходов и выходов, и комбинационными логичес- кими элементами.
Полнота переходов - возможность пере-
хода от любого Si(t) к любому Si(t+1).
Полнота выходов - взаимная однозначность Y = F(S). ( Любое S(t) можно «опознать» по Y(t). )
Обычно берутся ЭА Мура с двумя сос- тояниями.
Поведение ЭА Мура удобно описывать матрицами переходов.
ЭА типа Д.
|
|
|
|
|
|
|
|
|
Неопределенность в таблице переходов означает непредсказуемость поведения ЭА.
Неопределенность в матрице переходов означает возможность фиксации любого значения.
ЭА типа JK.
|
|
Матрицы переходов описывают функции возбуждения ЭА, задающие значения входов ЭА в такте t, которые обеспечивают переход ЭА к такту (t+1)
из текущего состояния к требуемому.
Основная идея канонического метода структурного синтеза автоматов в сведении задачи к синтезу КС.
Этапы алгоритма
1. Кодирование входного, выходного и афавита состояний символами структур- ного алфавита.
Пример
2.Построение кодированных
таблиц (функций) переходов и выходов.
Представление кодированных функций таблицами, а не в другой форме, не обязательно, но удобно.
159
|
|
|
|
|
|
|
|
|
3. Построение функций возбуждения для ЭА.
Полагаем, что тип каждого ЭА задан.
Выбор типов ЭА, как и вариантов коди-
рования алфавитов, здесь не рассматри-
ваем.
Пример (продолжение).
Предположим, что ЭА0 - типа Д, а ЭА1 - типа JK.
4. Построение схемы.
Имея функции выходов и возбужде-
ния, можно построить реализующие
их КС. Методы синтеза КС нам изве-
стны. ЛЭ должны образовывать функ-
ционально полный набор.
Пример (окончание).
Сложность построенной схемы в основ- ном определяется сложностью КС j и КС f. Оценить сложность этих КС мож- но по числу реализуемых функций и по числу их аргументов. (Для конкретных бф оценка может уточняться.)
Каноническая реализация автоматов Мили и Мура подобна и в общем случае имеет такой вид:
Автомат Мили:
Автомат Мура :