Табличный метод структурного синтеза конечных автоматов

Лекция 15 Табличный метод структурного синтеза конечных автоматов Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении возбуждения каждого элементарно автомата и функций кодированных выходов заданного автомата. На этапе структурного синтеза выбираем также способ кодирования состояний и выходных сигналов заданного автомата через состояния и выходные сигналы элем1ентарных автоматов, в результате чего составляют кодированные таблицы переходов и выходов. Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов. Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов. xj\ai a0 a1 a2 x1 a1/y1 a1/y2 a1/y2 x2 a2y3 a2/y3 a0/y1 В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ. Итак, имеем A={a0, a1, a2}; X={x1, x2}; Y={y1, y2, y3}. Здесь n=2, n+1=3; m=2, k=3. 1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов. R = ]log (n+1)[ = ] log 3[ = 2 L = ]log m[ = ] log 2[ = 1 R = ]log k[ = ] log 3[ = 2. Таким образом, необходимо иметь два элементарных автомата Q1 и Q2 (т.к. R=2), один входной канал b1 и два выходных канала Z1 и Z2. 2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов. Сост.элем.авт. Сост.задан.абстрактн.авт. Q1 Q2 a0 a1 1 a2 1 Таблица кодирования состояний автомата. Вх.сигн.структ.авт Вх.сигн.задан.авт b1 X1 X2 1 Таблица кодирования входных сигналов. Вых.сигн.структ.авт Вых.сигн.задан.авт Z1 Z2 Y1 Y2 1 Y3 1 Таблица кодирования выходных сигналов. Поэтому автомат имеет три состояния, то комбинация состояний элементарных автоматов 11 не используется и является запрещенной (автомат в это состояние никогда не попадет). Здесь и в дальнейшем будем использовать естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата. Xj\ai 00 01 10 01/00 01/01 01/01 1 10/10 10/10 00/00 В таблицах кодирования выходные каналы Z1 и Z2 называются физическими выходами автомата. 3. Пользуясь таблицами кодирования можно на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов. Кодированная таблица переходов определяет зависимость состояний Qi(t+1) элементарных автоматов в момент времени (t+1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t. Т.е. Qi(t+1) = fi[(Q1(t), Q2(t), …, Qr(t), В кодированной таблице выходов – выходные сигналы Zl(t) определяются в зависимости от значения входных сигналов и внутренних состояний в момент времени t. b1(t) Q1(t) Q2(t) Q1(t+1) Q2(t+1) Z1(t) Z2(t) 1 1 1 1 1 1 1 1 1 - - - - 1 1 1 1 1 1 1 1 1 1 1 1 - - - - Эти функции являются переключательными, поскольку значения функции и ее аргументов определены в один и тот же момент времени t. 4. Основная задача, решаемая в процессе структурного синтеза – построение синтеза функций возбуждения элементарных автоматов, которая определяет значения сигналов на входах элементарных автоматов, необходимые для обеспечения переходов автомата из одного состояния в другое. При построение этой таблицы используется матрица переходов выбранных элементарных автоматов, в нашем случае JK-триггеров. С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках этой таблицы записываются значения Ji и Ki, обеспечивающие нужный переход. J K Q(t) Q(t+1) b1 1 b2 1 b3 1 1 b4 1 1 1(t) Q1(t) Q2(t) Q1(t+1) Q2(t+1) J1(t) K1(t) J2(t) K2(t) 1 b 1 b 1 1 b b 1 1 b 1 1 b 1 1 - - - - - - 1 1 1 b b 1 1 1 1 b b 1 1 1 b 1 b 1 1 1 - - - - - - Например, переход Q1(t) из 0 в 0 обеспечивается подачей на вход J сигнала 0, а значение сигнала на входе K – безразлично. Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала так и от состояния автомата в тот же момент времени, что и Qi и B (т.е. в t). Поскольку функции возбуждения J(t) и K(е) определенны в тот же момент времени, что и их аргументы Q1(t), Q2(t) и B1(t), то эти функции являются переключательными. В результате мы получим систему переключательных функций Z1(t), Z2(t), J1(t), K1(t), J2(t) и K2(t) заданных в виде таблиц их истинности. 5. Следующий этап – комбинационный синтез конечных автоматов. На этом этапе по полученным переключательным функциям синтезируются комбинационные схемы. Очевидно, задача комбинационного синтеза конечных автоматов полностью совпадает с задачей синтеза логических схем, которую мы уже рассматривали. Обычно полученные переключательные функции минимизируют и представляют в булевом базисе, для каждой из которых построим диаграмму Вейча. J1 b B J2 1 B B 1 1 1 b b b b Z1 B 1 1 b K1 B B B 1 K2 B B B B B b 1 b 1 b B Z2 1 B 1 b Обычно полученную систему ПФ минимизируют совместно. Однако совместная минимизация всех ПФ представляет собой достаточно трудоемкую и длительную операцию, применимую, в общем случае, при использовании машины. В результате минимизации мы получим следующую схему конечного автомата. Функциональные схемы, получаемые в результате структурного синтеза, в дальнейшем на этапе инженерной доработки подвергаются изменениям. Эти изменения связаны с тем, что добавляются специальные цепи, необходимые для работы разработанной схемы в составе других схем ЦВМ. Например, в схеме регистра сдвига информации добавляется цепь «установка в 0». Другие изменения связаны с особенностью физического представления информации в ЦВМ, с особенностями логических элементов и с техническими особенностями логических элементов и с техническими особенностями конечных автоматов.