12.4 Минимизация абстрактных автоматов
На первом этапе синтеза АА определяют входные/выходные каналы, общее число внутренних состояний, составляют таблицы переходов и выходов АА или строят граф автомата. Определенный таким образом АА может иметь больше внутренних состояний, чем это необходимо для выполнения его функций. При минимизации количества состояний автомата используют принцип эквивалентности. Два эквивалентных автомата могут отличаться только числом внутренних состояний, т. е. избыточной памятью. Из всех рассмотренных вариантов эквивалентных автоматов, выбирают схему с меньшим числом состояний, т. е. с меньшим количеством элементов памяти (триггеров).
Алгоритм минимизации, предложенный Ауфенкампом и Хоном 2 основан на идеи разбиения состояний А на попарно непересекающиеся классы эквивалентности и замене их одним состоянием.
Два состояния А относят к 1-классу эквивалентности (по таблице выходов), если находясь в любом из них, при подаче любого входного сигнала, получаем одинаковые выходы.
Пример. Пусть автомат Мили задан таблицей переходов и выходов (таблица 12.5). Необходимо минимизировать А по числу состояний.
Таблица 12.5-Таблица переходов и выходов А
По таблице выходов, объединяя ее одинаковые столбцы, находим 1-класс эквивалентности U1={B1,B2}, где B1={Z1, Z2, Z5, Z6}, B2={Z3, Z4}.
Строим новую таблицу переходов, где состояния заменяем соответствующими подклассами B1,B2 объединения U1 1-класса эквивалентности (таблица 12.6).
Таблица12.6-Класс эквивалентности 1-й
По таблице 12.6 находим 2-класс эквивалентности U2={С1,С2,С3}, где С1={Z1, Z2}, C2={Z5, Z6}, C3={Z3, Z4}.В том же порядке строим таблицу 12.7.
Таблица12.7-Класс эквивалентности 2-й
Определив по этой таблице 3- класс эквивалентности, видим, что он одинаков со вторым. Поэтому, останавливаемся на 2-классе эквивалентности.
Выбирая произвольно из каждого полученного подкласса С1,С2,С3 по одному состоянию, получим минимизированное множество, например, V={Z1, Z4, Z5} состояний абстрактного автомата. Оставив в таблице 12.5 только эти состояния, и заменяя в таблице 12.7 подклассы С1,С2,С3 на Z1, Z4, Z5, получим таблицу переходов и выходов минимального автомата Мили (МАМ,таблица 12.8).
Таблица 12.8-Таблица переходов и выходов
МАМ
13 Методы структурного синтеза автоматов
После этапа абстрактного синтеза следует этап структурного синтеза, целью которого является проектирование логической схемы цифрового автомата из элементов выбранного базиса.
Структурный синтез автомата базируется на основе композиции элементарных автоматов, например, логического базиса булевых функций. При проектировании, элементарные автоматы А1,А2,…,Ак объединяются во взаимосвязанную систему совместно работающую по выполнению заданных функций и алгоритмов ЦА.
Структурный синтез конкретизирует абстрактные входные/выходные каналы, превращая их в определенные связи, двоичные сигналы, коды адресов, коды данных и другие переменные.
13.1 Канонический метод синтеза автомата
Теоретическим обоснованием структурного синтеза автоматов является теорема о структурной полноте [6].
Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-либо функционально полную систему элементов логических функций, является структурно полной.
Канонический метод структурного синтеза предполагает представление структурной и логической схемы автомата в виде двух частей: памяти и комбинационной схемы (рисунок 13.1).
Память автомата состоит из элементарных, полных автоматов Мура П1,...,Пi…Пt.
Любой автомат Мура должен иметь полную систему переходов и полную систему выходов. Это означает, что для любой пары состояний автомата памяти найдется входной сигнал, переключающий его во второе состояние. Полнота системы выходов автомата Мура состоит в том, что каждому состоянию соответствует свой кодированный сигнал на его выходе. Другими словами, в полном автомате Мура отождествляется его состояние с выходом, т.е. по выходу можно определить в каком состоянии он находится.
Общее количество элементов памяти Мура Т в синтезируемом автомате А определяется необходимой совокупностью всех его состояний М 2Т, где 2 основание двоичной системы счисления. Так, например, автомат имеющий пять элементов памяти может иметь 25 состояний, коды которых определяются простой последовательностью двоичных пятиразрядных чисел.
Так как, после выбора элементов памяти, каждое состояние синтезируемого автомата А определяется кодом состояний элементов Мура, то, например, чтобы перевести его из состояния Zm=00101 в состояние Zs=00001, необходимо переключить триггер третьего разряда из 1 в 0. Эти переключения происходят под действием сигналов, поступающих из комбинационной части автомата.
Результатом канонического метода структурного синтеза является система логических уравнений математического описания автомата А. Эта модель отражает зависимость выходных сигналов автомата (в том числе и для переключения памяти) от сигналов входных переменных (в том числе и сигналов, снимаемых с выхода элементов памяти).
Для правильной работы схемы, сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы.
Таким образом, при каноническом методе синтез автомата сводится к выбору элементов памяти и синтезу комбинационной части схемы, входами которой являются сигналы входных переменных структурного автомата (х1, х2, ..., хn} и сигналы обратной связи от элементов памяти {v1, v2,...,vt}, a выходами - сигналы на выходных каналах (у1 у2, ...,уm} и функций переключения памяти {u1, u2,..., ut}. Автомат А можно задать следующей системой уравнений:
Для практики проектирования цифровых автоматов, рассмотрим пример применения канонического метода структурного синтеза логической схемы.