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

Структурный синтез автомата

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

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

Под композицией элементарных автоматов будем понимать следующее. Пусть заданы элементарные автоматы S1,S2,……..Sk. Произведем объединение элементарных автоматов в систему совместно работающих устройств. Для этого введём некоторое конечное множество узлов. Узлы разделяются на внешние и внутренние.

Композиция автомата состоит в том, что совместная работа всех элементарных автоматов от сигнала, поданного на один из внешних входных узлов, начинается одновременно. Входной сигнал запускает работу всей системы в целом, отождествляя внутренние узлы композиции автомата. После проведённых отождествлений всех узлов система автомата превращается так в называемую в схему автоматов или сеть автоматов. На внешние входные узлы подаётся набор входных сигналов (структурный входной сигнал схемы) и со всех внешних выходных узлов снимается набор выходных сигналов (структурный выходной сигнал).

При построении схемы автоматов должно выполняться условие корректности. Т.е. все входящие в композицию элементарные автоматы должны иметь одинаковые структурные входные и выходные алфавиты и должны работать в одном и том же автоматном времени.

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

При построении структурного автомата предварительно выбираются элементарные автоматы, из которых путем их композиции строится структурная схема автомата (Мили, Мура или С-автомата).

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

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

1. Автоматы с памятью, имеющие более одного внутреннего состояния – нетривиальные автоматы.

2. Автомат без памяти – логические элементы.

Автоматы первого типа называются элементарными автоматами памяти. Автоматы второго типа называются комбинационной схемой или логическими элементами. Теоретическим обоснованием канонического метода структурного синтеза автомата является теорема о структурной полноте.

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

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

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

Полнота системы переходов автомата Мура означает, что для любой пары состояний найдётся входной сигнал, переводящий автомат из состояния b_m в состояние b_s. Полнота системы выходов автомата Мура состоит в том, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний. В связи с тем, что выходные сигналы ля полного автомата Мура эквивалентны его внутренним состояниям, можно использовать одни и те же обозначения, как для внутреннего состояния автомата, так и для состояния выхода.