Основные этапы проектирования автоматов

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

При проектировании управляющих автоматов будем различать два основных этапа: построение автоматного оператора и структурного синтеза автомата.

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

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

Этап построения автоматного оператора состоит из трех подэтапов: алгоритмического, абстрактного и этапа кодирования внутренних состояний автомата.

Абстрактный этап проектирования автоматов

При проектировании автоматов могут появиться эквивалентные состояния, которые на практике приводят к перерасходу материальных средств.

Понятие состояния возникло в связи с реализацией автоматов на конкретных устройствах – триггерах, которые могут находиться в одном из двух состояний – 0 или 1. Автомат с большим числом состояний имеет множество триггеров и их состояние тесным образом связаны с поступающими на вход и снимаемыми с выхода сигналами.

Введенный на этапе алгоритмического проектирования объем памяти автомата может быть избыточным. Эта избыточность устраняется склеиванием эквивалентных состояний. Данное преобразование относится к этапу абстрактного проектирования.

Определение. Состояния, находясь в которых автомат вырабатывает для любой входной последовательности одну и ту же выходную последовательность называются эквивалентными.

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

Метод абстрактной минимизации автомата, основанный на склеивании эквивалентных состояний, был предложен Хафменом и состоит в последовательном выделении классов эквивалентных состояний с помощью таблиц выходов и переходов. Рассмотрим метод Хафмена на примере.

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

1) Строим таблицу выходов, представляющую собой двумерную таблицу (таблица 1), каждой строке которой взаимно однозначно соответствует значение входного вектора , столбцу – внутреннее состояние автомата и на пересечении -й строки с -м столбцом находится значение выходного вектора , который вырабатывается на выходе, когда автомат находится в -м внутреннем состоянии и на входе подан -й вектор.

Таблица 1

0	1	1	0	0	1	0	0
1	0	0	1	1	0	1	1

Если двум внутренним состояниям автомата соответствуют различные значения столбцов в таблице выходов, то состояния не эквивалентны, так как в этих состояниях отображения различные. Предварительно Разобьем все множество состояний на классы условно эквивалентных состояний, а именно: в один и тот же класс попадают те состояния, которым соответствуют одинаковые значения столбцов в таблице выходов: ; .

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

Для проверки этого условия:

2) Строим таблицы переходов (таблица 2.1 и таблица 2.2). Каждой строке, столбцу в этой таблице соответствуют те же значения, что в таблице выходов, и на пересечении -й строки с -м столбцом находится класс условно эквивалентных состояний, в который переходит автомат из состояния под воздействием .

Таблица 2.1

0
1

Таблица 2.2

0
1

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

Каждый класс разбивается на новые классы условно эквивалентных состояний, т.е. разбиваем далее на два класса и , причем в один и тот же класс входят все состояния класса с одинаковыми значениями столбцов: ; ; .