На этапе структурного синтеза предварительно выбираются элементарные автоматы, путем композиции которых строят логические схемы полученных на этапе абстрактного синтеза автоматов Мили и Мура. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.
Рассмотрим канонический метод структурного синтеза при котором используются элементарные автоматы некоторого специального вида – автоматы с памятью, имеющие более одного состояния, и автоматы без памяти – с одним состоянием. Первые автоматы называются элементамипамяти, вторые – комбинационные или логические элементы.
Теоретическим обоснованием канонического метода структурного синтеза автоматов служит теорема о структурной полноте:
Для правильной работы схем сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. Поэтому запоминающими элементами должны быть не автоматы Мили, а автоматы Мура. Таким образом, структурно полная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то же время, для синтеза автоматов с минимальным числом элементов памяти, необходимо в качестве таких элементов выбирать автоматы Мура, имеющие полную систему переходов и полную систему выходов – полные автоматы.
Полнота системы переходов означает, что для любой упорядоченной пары состояний автомата найдётся входной сигнал, переводящий первый элемент этой пары во второй, т.е в таком автомате в каждом столбце таблицы переходов должны встречаться все состояния автомата.
Полнота системы выходов автомата Мура состоит в том, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний. Т.о. в таком автомате число выходных сигналов равно числу состояний автомата. В связи с этим, в автоматах памяти будем использовать одни и те же обозначения и для состояний, и для выходных сигналов.
Канонический метод структурного синтеза предполагает представление структурной схемы автомата в виде двух частей: памяти и комбинационной схемы.
Память состоит из элементарных автоматов Мура П1,....,ПZ,....,ПR. После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П1...,ПR одинаковы, что в общем случае необязательно, то их число
где M – число состояний синтезируемого автомата А, а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b=2, тогда .
Например, переход автомата А, имеющего 5 элементов памяти, алфавит состояний которых – двоичный, из одного состояния (Am)=01011 в другое (A3)= 11000, заключается в изменении состояний соответствующих автоматов памяти: первый элемент памяти переходит из 0 в 1, второй – из 1 в 1, третий из 0 в 0, четвёртый – из 1 в 0, пятый - из 1 в 0.
Переходы автоматов памяти, соответствующие переходам в автомате А, происходят под действием сигналов возбуждения памяти, поступающих с выхода комбинационной схемы на вход памяти автомата. Так на рисунке X=(X1,X2,..,XL) и Y=(Y1,Y2,...,YN) – векторные структурные входной и выходной сигналы автомата, U=(U1,U2,...,UT) – векторная функция возбуждения памяти и Q=(Q1,...,QT) – вектор выходного сигнала обратной связи от элементов памяти автомата.
Рассмотрим отдельно элемент памяти Пz, таблица переходов которого дана в таблице. Множество выходных сигналов элементов памяти совпадает с множеством внутренних состояний.
Полнота переходов очевидна из таблицы (в каждом столбце все состояния встречаются). При рассмотрении автомата на абстрактном уровне его можно представить в виде рис.22 а.
При переходе от абстрактного автомата к структурному, входные и выходные сигналы должны быть закодированы наборами сигналов структурного алфавита (входного или выходного соответственно). При двоичном структурном алфавите автомат Пz будет иметь два входных и два выходных канала.
Итак, сами компоненты Uz и Qz при Z = 1,...,R векторов сигналов возбуждения памяти U и сигналов обратной связи от памяти Q также могут быть представлены в виде векторов:
Uz = (UZ1,UZ2,...,UZK) и QZ = (QZ1,QZ2,...,QZR).
Если не оговорено особо, то используется двоичный структурный алфавит как для входных и выходных каналов синтезируемого автомата, так и для входных и выходных каналов автоматов памяти. Алфавит состояний автоматов памяти также обычно двоичный.
При построении функций возбуждения памяти автомата используют функцию входов элемента памяти m(bi,bj), ставящую в соответствие каждой паре состояний (bi,bj) сигнал, который должен быть подан на вход этого автомата для перевода его из состояния bi в состояние bj. Функцию входов удобно задавать в виде таблицы. Для элемента памяти (функция переходов которого приведена ранее) функция входов имеет вид:
Если входные сигналы элемента памяти q1,...,qp закодированы наборами (UZ1,...,UZK) сигналов на его входных каналах, то элементами таблицы, задающей функцию входов вместо qi будут соответствующие наборы. Так, если q1 = 00, q2 = 01, q3 = 10, то соответствующая f входов будет иметь вид рис.23a.
.
и два выходных 