Минимальная таблица переходов и выходов

	в0	в1	в2
U0
U1
U2
U3
U4
U5
U6
U7

5.1.2. Структурный синтез конечного автомата Мили

Кодирование входов и выходов осуществляется путем перевода индексов входных воздействий U и выходных сигналов V в двоичные числа. В результате получим:

Для кодирования внутренних состояний необходимо по полученной минимальной таблице переходов и выходов 5.3. построить граф автомата. Граф состоит из вершин (кружков) и ребер (линий), которыми соединяются вершины между собой. Вершины представляют собой все внутренние состояния автомата, а ребра переходы автомата из одного состояния в другое при подаче входных воздействий. Каждое ребро на графе обозначается входом и через дробь соответствующим ему выходом. Если под воздействием какого-либо входа автомат не меняет своего внутреннего состояния, то данное ребро проводится в виде полукольца около данной вершины.

На основе минимальной таблицы переходов и выходов получается граф автомата (рис. 5.2.).

В графе различают вершины смежные 1-го ранга, вершины смежные 2-го ранга и т.д. Вершинами смежными 1-го ранга являются те вершины, переход автомата, в которые происходит из другой вершины только с помощью одного ребра. Например, из вершины в₀ в вершину в₁ с помощью ребра или с вершиныв₂ в вершину в₀ с помощью ребра .

Рис. 5.2. Граф автомата

В графе все вершины смежные 1-го ранга должны кодироваться соседними двоичными числами, которые отличаются между собой только в одном разряде. Количество разрядов двоичных чисел, которыми кодируются вершины графа, зависит от количества вершин в графе, т.е. от количества внутренних состояний автомата. Следовательно, каждый разряд двоичного числа, которым закодирована вершина графа, соответствует одному элементу памяти. Если все смежные вершины 1-го ранга в графе автомата закодированы соседними двоичными числами, то переход автомата из одного состояния в другое при подаче одного входного воздействия U будет происходить за счет изменения состояния только одного элемента памяти. В этом случае сбоев в работе автомата не будет. В случае, если смежные первого ранга (внутренние состояния) будут закодированы не соседними двоичными числами (например в₁ – 01, в₂ – 10), то при переходе автомата из состояния в₁ в состояние в₂ необходимо изменить состояние обоих элементов памяти. Так как совершенно одинакового быстродействия элементов автоматики не бывает, то автомат из состояния 01 (6) может перейти или в состояние 00, или в состояние 11, а, следовательно, будет появляться ложный выходной сигнал. Это и будет являться сбоем в работе автомата.

в₀ в₁

в₃ в₂

Рис. 5.3. Граф автомата с четным числом вершин

После построения графа автомата определяется возможность кодирования вершин графа смежных первого ранга соседними двоичными числами. Одним из условий такой возможности является четное число вершин во всех замкнутых контурах графа. Если имеют место контуры с нечетным числом вершин, то необходимо в эти контуры добавить вершину, которая будет соответствовать неустойчивому внутреннему состоянию автомата. В рассматриваемом автомате граф (рис. 5.2) состоит из контура с тремя вершинами, которые закодировать соседними двоичными числами не представляется возможным, поэтому в граф вводим дополнительную вершину в₃ (рис. 5.3).

Вершина в₃ будет неустойчивой, т.е. автомат из вершины в₂ под воздействием ребра сигнала перейдет в состояниев₃ и, не останавливаясь в этом состоянии, перейдет в состояние в₀.

Так как в граф введена дополнительная вершина в₃, то минимальная, абстрактная таблица будет иметь вид (табл. 5.4), где добавлен столбец, соответствующий в₃ и показано, что по сигналу U₄ автомат переходит из состояния в₂ в неустойчивое состояние в₃, а затем в состояние в₀ без изменения входного сигнала.

Таблица 5.4.