ПТЦА - Прикладная теория цифровых автоматов (стр. 7 из 20)

Как следует из рис. 15 для автомата Sa при попадании в состояние а₁ вырабатываются выходные сигналы W₂, W₄, W₅, при попадании в а₂ – W₁, W₂, a₃ – W₂, a₄ – W₃. Каждой паре состояние a_i - выходной сигнал Wj, который вырабатывается при попадании в это состояние, поставим в соответствие состояние b_k эквивалентного автомата Мура S_b с тем же выходным сигналом Wj : b₁ = (a₁, W₂), b₂ = (a₁, W₄), b₃ = (a₁, W₅), b₄ = (a₂, W₁), b₅ = (a₂, W₂), b₆ = (a₃, W₂), b₇ = (a₄, W₃), т.е. каждое состояние a_i автомата Мили порождает некоторое множество A_i состояний эквивалентного автомата Мура: A₁ = { b₁, b₂, b₃ }, A₂ = { b₄, b₅ }, A₃ = { b₆ }, A₄ = { b₇ }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа S_b поступаем следующим образом. Т.к. в автомате S_a есть переход из состояния а₁ в состояние а₂ под действием сигнала z₁ с выдачей W₁, то из множества состояний A₁ = {b₁, b₂, b₃}, порождаемых состоянием а₁ автомата S_a в автомате S_b должен быть переход в состояние (a₃, W₂) = b₆ под действием сигнала Z₂ и т.д. Граф эквивалентного автомата Мура представлен на рис.19.

Если от автомата Мура S_b, эквивалентного автомату Мили Sa (рис. 19) вновь перейти к автомату Мили, то получим автомат Мили S₁ (рис. 20)

Вследствие транзитивности отношения эквивалентности два автомата Мили S₁ и Sa также будут эквивалентными, но у последнего будут на 3 состояния больше. Т.о., эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (т.е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.

МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.

Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.

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

Для пользования методом введем несколько определений.

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

Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения состояний автомата на ( i +1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на ¥ - классы эквивалентности.

Разбиение множества внутренних состояний автомата на ¥ - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.

Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.

Рассмотрим пример минимизации автомата Мили, заданного таблицами переходов и выходов :

Из таблицы выходов получаем разбиение на 1-классы эквивалентности p₁, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами:

p₁ = {B₁, B₂}; B₂ = {a₁, a₂, a₅, a₆}; B₂ = {a₃, a₄}

Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.17), заменяя в таблице переходов состояния a₁ соответствующими классами эквивалентности B1 или B2.

Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности C_i и разбиение p₂ = {C₁, C₂, C₃}, где С₁ = {a₁, a₁}, C₂ = {a₅, a₆}, C₃ = {a₃, a₄}. Сравнивая p₂ и p₁, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 18), опять заменяя в таблице переходов состояния a_i соответствующими классами эквивалентности C_i.

Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности D_i и разбиение p₃ ={ D₁, D₂, D₃}, где D₁ = {a₁, a₂}, D₂ = {a₅, a₆}, D₃ = {a₃, a₄}.

Сравнивая p₃ и p₂, замечаем, что D₁ = C₁, D₂ = C₂, D₃ = C₃, p₃ = p₃. Следовательно получили разбиение на ¥- эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса D_i по одному состоянию и получаем множество состояний A' минимального автомата. Пусть, например, A'={a₁, a₄, a₅}. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 16) вычеркиваем столбцы, соответствующие "лишним состояниям" a₂, a₃, a₆. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 19).

Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.

Структурный синтез ЦА.

Задачи синтеза ЦА.

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

Элементарные цифровые автоматы с памятью

(триггерные устройства) и их свойства.

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

В отличие от абстрактного автомата, имеющего один вход и один выход, на которые поступают сигналы во входном и выходят в выходном W={W₁,..,W_G} алфавитах, структурный автомат имеет L входных каналов х₁,х₂,..,х_L и N выходных y₁,y₂,…,y_N на каждом из которых присутствует сигнал структурного алфавита.

Обычно в качестве структурного используется двоичный алфавит.

В этом случае каждому входному сигналу Z_F абстрактного автомата соответствует некоторый двоичный вектор (l_f1,l_f2,..,l_fL), где l_fLÎ{0,1}.

Очевидно, что для представления (кодирования) входных сигналов Z₁,..,Z_F абстрактного автомата различными двоичными векторами должно быть выполнено условие

L

] log₂F [,

аналогично

N

] log₂G [

Например , Z={Z₁,Z₂,Z₃,Z₄} W={W₁,W₂,W₃}.

Тогда L

log₂4=2 N

log₂3=2

Закодировать входные и выходные сигналы можно ,например, так:

Z₁ = 00 W₁ = 00

Z₂ = 01 W₂ = 01

Z₃ = 10 W₃ = 11

Z₄ = 11