Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

входным сигналам, а столбцы — состояниям, причем крайний левый столбец состояний обозначен начальным состоянием а х. На пересе­ чении столбца âm и строки zf в таблице переходов ставится состояние а = б (а,п, Zf), в которое автомат переходит из состояния ат под дейст­ вием сигнала zf, а в таблице выходов —соответствующий этому пере­ ходу выходной сигнал wg — А (а„„ zf). Пример табличного способа задания полностью определенного автомата Мили Sj^ с тремя состоя­

или А определены не для всех пар (ат , zf) £ А X Z, на месте неопреде­ ленных состояний и выходных сигналов ставится прочерк (частичный автомат S 2 задан табл. 1-5 и 1-6).

7

Так как в автомате Мура выходной сигнал зависит только от со стояния, автомат Мура задается одной отмеченной таблицей перехо­ дов (табл. 1-7), в которой каждому ее столбцу приписан, кроме со­ стояния ат, еще и выходной сигнал wg — X (аш), соответствующий этому состоянию. Пример табличного описания автомата Мура S 3 иллюстрируется табл. 1-8.

Граф автомата — ориентированный связный граф, вершины ко­ торого соответствуют состояниям, а дуги —■переходам между ними.

Две вершины графа автомата а,„ и as (исходное состояние и состояние перехода) соединяются дугой, направленной от ат к as, если в авто­ мате имеется переход из ат в as, т. е. если as — б (ат , z;) при некото­ ром Zf f Z. Дуге (ат, as) графа автомата приписывается входной сигнал zf и выход­ ной сигнал Wg = X (ат, zf), если он опре­ делен, и ставится прочерк в противном случае. Если переход автомата из состоя­ ния ат в состояние as происходит под дей­ ствием нескольких входных сигналов, то дуге (ат, as) приписываются все эти вход­ ные и соответствующие выходные сигналы.

При описании автомата Мура в виде графа выходной сигнал wg — К (ат) записывается Рис. 1-4. Граф автомата внутри вершины ат или рядом с ней. На

т-й строки и s-ro столбца, в случае автомата Мили соответствует вход­ ному сигналу Zf, вызывающему переход из состояния ат в состояние

8

Если переход из ат в as происходит под действием нескольких сиг­ налов, элемент cms представляет собой множество пар (вход/выход) для этого перехода, соединенных знаком дизъюнкции. Для модели Мура элемент cms равен множеству входных сигналов на переходе (ат, as), а выход описывается вектором выходов

Ч«і) 1

Wn X (ап1)

X (ам)

т-я компонента которого есть выходной сигнал, отмечающий состоя­ ние ат. Для автомата Мура S s

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

В заключение данного параграфа определим синхронные и асин­

as £ А устойчиво. Автомат S называется синхронным, если он не яв­ ляется асинхронным.

Необходимо заметить, что построенные на практике автоматы — всегда асинхронные и устойчивость их состояний всегда обеспечи­

9

вается тем или иным способом, например введением сигналов синхро­ низации (см. ниже, § 3-1). Однако на уровне абстрактной теории, когда автомат есть лишь математическая модель, которая не отражает многих конкретных особенностей его возможной реализации, часто оказывается более удобным оперировать с синхронными автоматами,

символами тех же входных сигналов. Анализ таблиц 1-3, 1-5 и 1-8 или рис. 1-2 — 1-4 показывает, что автоматы 5 Х, S 3 и 5 3 являются синхронными.

1-3. Связь между моделями Мили и Мура

В § 1-1 отмечалось, что абстрактный автомат работает как преоб­ разователь слов входного алфавита в слова в выходном алфавите. Остановимся на этом вопросе более подробно, взяв в качестве примера автомат Мили 5 Хна рис. 1-2 (или табл. 1-3, 1-4). Пусть на вход этого автомата, установленного в начальное состояние, поступает входное слово I = z1z1z2z1z2z2. Так как б (ох, zx) = а3, а к (alt zx) — wlt то под действием первой буквы слова | — входного сигнала zx автомат перейдет в состояние а3 и на выходе его появится сигнал wx. Далее, б (а3, Zj) = а х, к (а3, zx) = w2 и потому при приходе второго сигнала zx автомат окажется в состоянии ах, а на выходе его появится сигнал w2. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову £, вторая — последо­

10

k + 1 и выходное слово длины к. В общем виде поведение автомата Милн, установленного в состояние ат, можно описать следующим образом:

Точно так же можно описать поведение автомата Мура, находя­ щегося в состоянии ат, при приходе входного слова zc , z, , . . .,z,k.

Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (w (t)) зависит лишь от состояния, в котором на­ ходится автомат в момент t (а (/)):

Очевидно, что выходной сигнал wt — %(ат) в момент времени іг не зависит от входного сигнала г.1, а определяется только состоянием

ат. Таким образом, этот сигнал wt никак не связан с входным словом, поступающим на вход автомата, начиная с момента і1. В связи с этим под реакцией автомата Мура, установленного в состояние ат, на вход­ ное слово \ = z(- zfo . . . zik будем понимать выходное слово той же длины (а = %(а„), I) = wt wl3 . . . w,k+i.

В качестве примера рассмотрим автомат Мура 5 6, граф которого изображен на рис. 1-6, и найдем его реакцию в начальном состоянии аг на то же самое входное слово g = z1z 1z2z1z2z2, которое мы исполь­ зовали при анализе поведения автомата Мили S x:

фавитами называются эквивалентными, если после установления их

11