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

 Введение.

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

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

Далее производят разбиения состояний в пределах каждого класса двухэквиволентных состояний на классы трехэквиволентных  т.д., пока этот процес допустим.

Структурный синтез:  

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

Используем в качестве элементарных автоматов J-K-тригеры,

Определяем колличество входов структурного автомата :

L=log₂2=1.

Кодируем выходные сигналы:

Z1 соответствует X=0 и Z2 - X=1.

Определяем клличество выходов:

N>log₂2=1.

Кодируем выходные сигналы:

w1 соответствует y=0, w2 - y=1.       

Определяем колличество тригеров:

R>log₂12=4

Кодируем состояния автомата.

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

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

     Абстрактным автоматом  называют дискретный преоброзователь информации с конечным    входным алфовитом Z = {z1..., z_f,...,z_F}, конечным выходным алфовитом W = {w1,...,w_g,...,w_G} , конечным         множеством внутренних состояний  А = {a1,...,а_m,...,а_м} и двумя характеристическими  функциями: функцией переходов и функций выходов.

Абстрактный автомат имеет один входной и один выходной канал. функционирование автомата происходит в дискретные моменты автоматного времени, t = 0,1,2,3,... . В каждыймомент дискретного времени t автомат находится в определенном состоянии, воспринимает на входном конале некоторую  букву  входного алфовита, выдаетна выходном  канале некоторую букву выходного алфавита.

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

Древовидный граф:

Движение по графу  всегдабудет начинаться из состояния а1.Из него можно попасть в состояние а2,если подоется сигнал Z2 , или в состояние а3,если подоется  сигнал Z1. Из состояния а2 и а3 ведут два пути: один путь связан сигналом  Z1, а другой с сигналом  Z2. таким оброзом всего имеются четыри пути , которые приводят к состояниям  а4, а5, а6, а7. для каждого из этих четырех состояний существыет два выходных пути, которые приведут к последующим восьми выходным состояниям, которые в свою очередь лриведут к конечным шеснадцати выходным состояниям. но так как следующий переход является конечным то все выходные пути должны привести в начальное состояние а1. На выходах которые не соответствуют задоному коду выходной сигнал будет равен 0, на выходах которые сответствуют коду выходной сигнал равен 1.

 Таблицы переходов выходов:

Так как и по графу по таблицам можно проследить последовательность работы автомата. Вначальный момент t=0 автомат находится в состоянии а(0)=а1. если на входе в момент t=0 будет действовать к примеру z(0)=z2, то автома сформирует на выходе букву  w1=w(0)  и в следующий момент времени  t=1 автомат переключится в новое состояние а2. таким оброзом автомат будет последовотельно переключаться в состояния а(1), а(2), ... .

Минимизация абстрактного автомата:

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