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

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

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

Теоретическим обоснованием канонического метода структурного синтеза автоматов является теорема В.М. Глушковао структурной полноте.

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

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

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

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

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

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

Таким образом, в соответствии с теоремой В.М. Глушкова цифровой автомат должен состоять из двух функционально законченных блоков: комбинационной схемы и конечного автомата.

Комбинационной схемой называют устройство, совокупность выходных символов которого (выходное слово) U в каждый дискретный момент времени t_i однозначно определяетсясовокупностью входныхсигналов (входным словом) Q, поступившей на вход устройства в тот же момент времени t_i.

Конечным автоматом называют устройство, выходное слово которого в дискретный момент времени t_i определяется не только входным словом, поступившем в тот же момент времени t_i, но и внутренним состоянием устройства, обусловленным его предшествующей работой. Поэтому кроме входного и выходного алфавита необходимо задать еще один конечный алфавит состояний S = { s₁, s₂, s₃,..., s_m }, который называют алфавитом внутренних состояний, а символы s_i - внутренними состояниями.

В общем случае конечный автомат определяется как система с конечным входным алфавитом Х, конечным выходным алфавитом Y, конечным множеством внутренних состояний S и двумя характеристическими функциями:

функцией переходов S(t+1)=d(x(t), S(t)),

функцией выходов Y(t) = l(x(t), S(t)). Блок-схема конечного автомата в общем виде состоит из комбинационной схемы, реализующей характеристические функции d, l, и памяти, сохраняющей на один такт предыдущее состояние автомата.

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

рисунке 7.

 

 

Рисунок 7 Структурная схем цифрового автомата

 

На вход комбинационной схемы подается множество входных сигналов Х, а с выхода снимается множество выходных сигналов Y. Память состоит из элементарных автоматов Мура (триггеров) Т₁ … Т_n. Переходы автоматов памяти, соответствующие переходам в синтезируемом автомате, происходят под действием функций возбуждения автоматов памяти u₁ … u_n, поступающих с выхода комбинационной схемы на вход автоматов памяти. Функции возбуждения автоматов памяти определяют переход автомата в следующее состояние.

Выходы автоматов памяти связаны со входом комбинационной схемы через сигналы обратной связи q₁ … q_n, определяющие текущее состояние автомата. Количество входных сигналов Х и выходных сигналов Y зависит от задач, решаемых цифровым автоматом. Количество автоматов памяти (триггеров) определяется количеством состояний цифрового автомата

,

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

.