Задача синтеза структуры автомата.

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

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

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

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

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

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

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

Память состоит из элементарных автоматов Мура П₁,....,П_Z,....,П_R. После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П₁...,П_R одинаковы, что в общем случае необязательно, то их число

где M – число состояний синтезируемого автомата А, а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b=2, тогда .

Например, переход автомата А, имеющего 5 элементов памяти, алфавит состояний которых – двоичный, из одного состояния (A_m)=01011 в другое (A₃)= 11000, заключается в изменении состояний соответствующих автоматов памяти: первый элемент памяти переходит из 0 в 1, второй – из 1 в 1, третий из 0 в 0, четвёртый – из 1 в 0, пятый - из 1 в 0.

Переходы автоматов памяти, соответствующие переходам в автомате А, происходят под действием сигналов возбуждения памяти, поступающих с выхода комбинационной схемы на вход памяти автомата. Так на рисунке X=(X₁,X₂,..,X_L) и Y=(Y₁,Y₂,...,Y_N) – векторные структурные входной и выходной сигналы автомата, U=(U₁,U₂,...,U_T) – векторная функция возбуждения памяти и Q=(Q₁,...,Q_T) – вектор выходного сигнала обратной связи от элементов памяти автомата.

Рассмотрим отдельно элемент памяти П_z, таблица переходов которого дана в таблице. Множество выходных сигналов элементов памяти совпадает с множеством внутренних состояний.

Полнота переходов очевидна из таблицы (в каждом столбце все состояния встречаются). При рассмотрении автомата на абстрактном уровне его можно представить в виде рис.22 а.

При переходе от абстрактного автомата к структурному, входные и выходные сигналы должны быть закодированы наборами сигналов структурного алфавита (входного или выходного соответственно). При двоичном структурном алфавите автомат П_z будет иметь два входных и два выходных канала.

Итак, сами компоненты U_z и Q_z при Z = 1,...,R векторов сигналов возбуждения памяти U и сигналов обратной связи от памяти Q также могут быть представлены в виде векторов:

U_z = (U_Z1,U_Z2,...,U_ZK) и Q_Z = (Q_Z1,Q_Z2,...,Q_ZR).

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

При построении функций возбуждения памяти автомата используют функцию входов элемента памяти m(b_i,b_j), ставящую в соответствие каждой паре состояний (b_i,b_j) сигнал, который должен быть подан на вход этого автомата для перевода его из состояния b_i в состояние b_j. Функцию входов удобно задавать в виде таблицы. Для элемента памяти (функция переходов которого приведена ранее) функция входов имеет вид:

Если входные сигналы элемента памяти q₁,...,q_p закодированы наборами (U_Z1,...,U_ZK) сигналов на его входных каналах, то элементами таблицы, задающей функцию входов вместо q_i будут соответствующие наборы. Так, если q₁ = 00, q₂ = 01, q₃ = 10, то соответствующая f входов будет иметь вид рис.23a.