Автомат мура как построить

Автоматы Мура и Мили

Выходные сигналы АА зависят от того, что поступало на его вход раньше.

В каждый момент времени АА, будучи в состоянии [math]a_^[/math] , способен воспринимать одну из букв входного алфавита [math]z_^[/math] . В соответствии с функцией [math]\delta[/math] , АА перейдет в состояние [math]a_^[/math] с выдачей выходного сигнала, который вырабатывается в соответствии с функцией выходов [math]\lambda[/math] .

Рассмотрим функционирование автоматов Мура и Мили.

Автомат Мили

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t), z(t))[/math]

Автомат Мура

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t))[/math]

В автоматах Мура выходные воздействия записаны на состояниях, а в автомате Мили — на переходах.

Применение автоматов Мура и Мили

Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС).

Основное преимущество использования автомата Мили заключается в возможности реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной комбинации от текущей входной комбинации [math]a_[/math] .

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

Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании (например, для решения задачи об «Умном муравье» [1] ).

Автомат, регулирующий пешеходный переход

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

Выход автомата в каждом состоянии определяется парой [math]\langle[/math] Светофор транспорта; светофор пешехода [math]\rangle[/math] . Например, в состоянии [math]S_1[/math] управляющий автомат устанавливает [math]\langle[/math] З; К [math]\rangle[/math] , то есть включёнными зеленый свет транспорту и красный — пешеходам. В состоянии [math]S_6[/math] установлен [math]\langle[/math] Ж, К; К [math]\rangle[/math] , то есть желтый и красный свет транспорту (приготовиться) и красный — пешеходам. В начальном состоянии [math]S_0[/math] разрешен проезд транспорту, а пешеходам движение запрещено.

В состояниях [math]S_4[/math] , [math]S_5[/math] при запрещающем сигнале транспорту зеленый сигнал пешеходам мигает каждые [math]t_0[/math] секунд в течение [math]t_2[/math] секунд. Запрос на переход принимается только в состоянии [math]S_0[/math] , в остальных состояниях он игнорируется. Задержки (тайм-ауты [math]t_0[/math] — [math]t_3[/math] ) устанавливаются в момент перехода автомата в данное состояние, по исчерпании тайм-аута автомат переходит в следующее состояние. В гиперсостоянии [math]Q[/math] , объединяющему пару состояний [math]S_4[/math] и [math]S_5[/math] , автомат находится ровно [math]t_2[/math] секунд: внутренние переходы не срывают тайм-аута.

Именно для этого удобно использовать гиперсостояние [math]Q[/math] .

Торговый автомат

В качестве примера применения автомата Мили рассмотрим автомат по продаже шоколадок стоимостью [math]20[/math] рублей, принимающий монеты номиналом в [math]5[/math] и [math]10[/math] рублей и возвращающий сдачу, если это необходимо.

Состояний автомата всего четыре: [math]0[/math] , [math]5[/math] , [math]10[/math] и [math]15[/math] рублей.

Входных сигналов [math]Z[/math] два: [math]Z_5[/math] — [math]5[/math] рублей и [math]Z_[/math] — [math]10[/math] рублей.

Выходных сигналов [math]W[/math] три: [math]W_[/math] — ничего не выдавать, [math]W_[/math] — выдать шоколадку и [math]0[/math] рублей сдачи, [math]W_[/math] — выдать шоколадку и [math]5[/math] рублей сдачи.

Например, если у человека есть одна монета номиналом в [math]10[/math] рублей и две монеты номиналом в [math]5[/math] рублей и монеты забрасываются в порядке [math]10[/math] , [math]5[/math] и [math]5[/math] рублей, то происходит следующее:

1. Автомат переходит в состояние [math]10[/math] р. и ничего не выдает;
2. Автомат переходит в состояние [math]15[/math] р. и ничего не выдает;
3. Автомат переходит в состояние [math]0[/math] р., выдает шоколадку и не возвращает сдачу.

Способы задания автоматов

Табличный способ задания автомата Мили

Автомат Мили может быть задан таблицей переходов и таблицей выходов.

В таблице переходов АА Мили на пересечении столбца [math]a_[/math] и строки [math]z_[/math] записывается состояние [math]a_[/math] , которое есть функция [math]\delta[/math] от [math]a_[/math] и [math]z_[/math]

[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]=\delta (a_, z_)[/math]

В таблице выходов на пересечении столбца [math]a_[/math] и строки [math]z_[/math] записывается выходной сигнал, который есть функция [math]\lambda[/math] от [math]a_[/math] и [math]z_[/math] .

[math]a_[/math]
[math]z_[/math]	[math]w_[/math]	[math]=\lambda (a_, z_)[/math]

Пример: Задание автомата Мили табличным способом (автомат имеет два входных сигнала, два выходных сигнала и три состояния).

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

[math]\delta[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]

Таблица выходов

[math]\lambda[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]
[math]z_[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]

Графический способ задания автомата Мили

На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример).

Табличный способ задания автомата Мура

В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала.

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

[math]\lambda[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]
[math]\delta[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]

Графический способ задания автомата Мура

На рисунке приведен граф автомата Мура на 5 состояний, имеющий 2 входных сигнала и 2 выходных сигнала.

Реакция автоматов на входное слово

Автомат Мили

Допустим, входное слово [math]\xi[/math] поступает на вход автомата буква за буквой.

Выходное слово [math]\omega[/math] называется реакцией автомата Мили на входное слово [math]\xi[/math] в состоянии [math]a_[/math] строится по таблице переходов и выходов).

Реакцию автомата на входное слово [math]\xi[/math] можно заменить обходом графа.

Автомат Мура

Выходное слово [math]\omega[/math] называется реакцией автомата Мура на входное слово [math]\xi[/math] в состоянии [math]a_[/math] .

В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.

Эквивалентность автоматов Мили и Мура

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

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

Далее будет приведено формальное доказательство факта эквивалентности с явным предъявлением конструкции.

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

Переход от автомата Мура к автомату Мили

Шестикомпонентным набором с индексом А будем обозначать автомат Мура, а с индексом В — автомат Мили.

Пусть задан автомат Мура.

Требуется перейти к автомату Мили

[math]S_ = (A_, Z_, W_, \delta _, \lambda _, a_[/math] ),

При переходе от автомата Мура к автомату Мили алфавиты состояний также совпадают, т.е. [math]A_ = A_[/math] .

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

Мура	Мили
[math]\delta _ (a_, z_) = a_[/math]	[math]\delta _ (a_, z_) = a_[/math]
[math]\lambda _(a_) = w_[/math]	[math]\lambda _ (a_, z_) = w_[/math]

При переходе от автомата Мура к автомату Мили функции переходов также совпадают, а для определения функции выходов выходные сигналы с вершин опускается на входные дуги.

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

При таком переходе (Мура к Мили) число состояний совпадает.

Полученный автомат эквивалентен исходному

Переход от автомата Мили к автомату Мура

Пусть задан автомат Мили [math]S_ = (A_, Z_, W_, \delta _, \lambda _, a_)[/math] .

Требуется перейти к автомату Мура

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

В данном случае [math]A_ \neq A_[/math] .

При таком переходе (Мили к Мура) каждому состоянию автомата Мили [math]a_[/math] ставится в соответствие множество всевозможных пар [math]a_ \rightarrow A_ = \<( a_, w_) | a_ = \delta(a_, z_), w_ = \lambda(a_, z_)\>[/math] , где [math]a_[/math] есть функция [math]\delta[/math] от состояния и входного сигнала, [math]w_[/math] функция [math]\lambda[/math] от состояния и входного сигнала.

Мура	Мили
	[math]A_ = \<(a_, w_), (a_, w_), (a_, w_)\>[/math]

[math]a_: A_ = \left \ < \begin (a_, w_) = b_ \\ (a_, w_) = b_ \\ \end \right.[/math]

[math]a_: A_ = \left \ < \begin (a_, w_) = b_ \\ (a_, w_) = b_ \\ \end \right.[/math]

[math]a_: A_ = \< (a_, w_) \> = b_[/math]

В качестве начального состояния результирующего автомата может быть выбрано любое состояние Мура, порожденное начальным состоянием автомата Мили, т.е. состояния [math]b_[/math] или [math]b_[/math] .

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

Поскольку в автомате Мура выходной сигнал зависит только от состояния автомата, то в примере рядом с состояниями проставим соответствующие выходные сигналы.

И так если осуществить следующие преобразования, то получим:

Мили	Мура	Мили
[math]S_ \rightarrow[/math]	[math]S_ \rightarrow[/math]	[math]S_[/math]
3 состояния	5 состояний	5 состояний

Можно утверждать, что если [math]S_[/math] эквивалентно [math]S_[/math] , а [math]S_[/math] эквивалентно [math]S_[/math] , то [math]S_[/math] эквивалентно [math]S_[/math] (т.е. эквивалентность обладает свойством транзитивности).

Полученный автомат эквивалентен исходному

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

См. также

• Локальные автоматы
• Двусторонний детерминированный конечный автомат
• Квантовый конечный автомат

Примечания

Источники информации

• Ожиганов А.А. Теория автоматов: Учебное пособие. СПб.: НИУ ИТМО, 2013 — С. 84.
• Богаченко Н.Ф., Файзуллин Р.Т. Синтез дискретных автоматов: Учебное пособие. Омск: Издательство Наследие. Диалог-Сибирь, 2006.
• Википедия — Автомат Мура
• Ofap.ulstu.ru — Абстрактные автоматы
• Николай Борисенко — Технические аспекты построения управляющих автоматов при проектировании цифровых устройств на основе современных ПЛИС

Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2

Статья написана, собрана и сверстана Brotherofken. Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.

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

• Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
• Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

Абстрактный автомат

Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.
В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом:

Или, если перейти от иллюстрации к математическому описанию:
A =

1. Множество – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
2. Множество – представляет собой множество значений на физических выходах автомата.
3. Множество – а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата.
4. δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
5. λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

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

1. Автоматы Мили. Описывается системой уравнений:
   c(t) = δ( a(t), c(t-1) );
   b(t) = λ( a(t), c(t-1) ).
2. Автоматы Мура. Описывается уравнениями:
   c(t) = δ( a(t), c(t-1) );
   b(t) = λ( a(t), c(t) ).

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

Способы задания автоматов

Как мы выяснили в первой части — автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.

1. При помощи графов.
2. При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.

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

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

Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным, а автомат Мура – частичным.
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.

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

Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

ТПВ графа Мили

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

ТПВ графа Мура

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

Пример синтеза автомата

При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?
Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:

Кодируем входной и выходной алфавиты:
A = , где a0 – логическая 1 на входе R, a1 – логическая единица на входе S.
B = , где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.
Строим граф автомата Мили:

Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов:

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

Нанесём полученную функцию на карту Вейча и минимизируем:

Выпишем, что получилось:

Строим по функции схему (Выполняли домашнее задание?):

Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:

А на схеме асинхронный RS триггер обозначается вот так:

Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.

• Схемотехника
• теория автоматов
• абстрактный автомат
• триггер

С чем едят конечный автомат

Машина Тьюринга и машина состояний, детерминированный и недетерминированный конечный автомат, конечный автомат Мура и конечный автомат Мили. Голова кругом от всех этих понятий. Как во всем этом разобраться новичку? Тем более, что и у бывалых спецов бывает такая каша в голове из этих понятий. Чего только стоит вебинар от Яндекс Практикум на тему «Конечные автоматы в реальной жизни». Именно случайный просмотр этого вебинара сподвиг меня написать статью. Я обратил внимание, что даже более опытные лекторы ловко жонглируют всеми этими понятиями или подменяют одни другими в своих лекциях. С этим можно просто смириться, или дойти до безумия, разбираясь что к чему. И как со всем этим жить начинающему ардуинщику, если про конечные автоматы в программировании трубят из каждого утюга, а добраться до истины самостоятельно непросто?

Не гарантирую, что после прочтения статьи все сразу станет на свои места, но, как минимум, постараемся выудить из всей этой «каши» что-то полезное для себя. Так что усаживайтесь по удобнее, тема не простая, под катом будет много текста.

❯ Во всем виноваты математики

Да, именно так. Математика — это наука с долгой историей. Наука очень увлекательная, и поэтому она затягивает все большее количество умов. И каждому математику в душе хочется стать новым Пифагором, Евклидом, Лобачевским. А для этого необходимо постоянно расширять поле деятельности. Как только появляется какое-то новое научное направления, математики тут же жадно накидываются на него и изобретают свои новые теории.

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

Такая же участь ждала и электронику на заре ее развития. На ранних парах электроника была нераздельно связана со словом «радио» (радиоэлектроника), и ориентирована на радиосвязь. Новое прикладное применение обрела для себя тригонометрия, подтянулась теория сигналов, преобразования Фурье и еще много чего интересного.

❯ Комбинационные логические схемы

С развитием электроники от нее стали откалываться новые направления. Одно из таких — вычислительная техника. И тут математики тоже не остались в стороне. Хорошим подспорьем стала дискретная математика, от которой перешли к математической теории вычислительной техники.

К компьютерам вычислительная техника пришла далеко не сразу. Сперва появились комбинационные логические схемы. К таким схема можно отнести знакомые всем базовые логические вентили НЕ, И, ИЛИ, Исключающее ИЛИ и другие их комбинации. Шифраторы и дешифраторы можно считать более сложным вариантом комбинационных схем.

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

❯ Последовательностные логические схемы

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

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

Примером последовательностных логических схем могут служить защелки или различные типы триггеров. Они способны запоминать всего один бит информации. Объединение нескольких триггеров позволяет получить более сложные схемы параллельных, параллельно-последовательных, последовательно-параллельных и прочих регистров, которые способны хранить уже несколько бит.

❯ Конечный автомат Мура и Мили

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

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

Частным случаем этой теории являются автоматы Мура и Мили, позволяющие описать функционирование цифровых систем, которые нашла широкое применение для синтеза сложных последовательностных схем на основе ПЛИС. А математические «иероглифы», которыми обильно сдобрена теория, стали хорошим подспорьем для языков описания аппаратуры подобных SystemVerilog или VHDL.

Автоматы Мура и Мили названы в честь своих изобретателей, ученых, разработавших теорию автоматов и математическую базу для них в фирме Bell Labs.

Эдвард Форест Мур (1925–2003) опубликовал свою первую статью «Gedankenexperiments on Sequential Machines» («Мысленные эксперименты с последовательностными автоматами») в 1956 году.

Джордж Мили (1927–2010) опубликовал «Method of Synthesizing Sequential Circuits» («Метод синтеза последовательностных схем») в 1955 году. Впоследствии он написал первую операционную систему для компьютера IBM 704. Позже он перешел на работу в Гарвардский Университет.

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

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

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

Основная разница между конечными автоматами Мура и Мили в том, что у автомата Мура обычно больше (Moore – more) состояний, чем у автомата Мили, решающего ту же задачу.

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

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

❯ Машина Тьюринга

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

Машина Тьюринга была предложена для формализации понятия алгоритма, и является расширением или частным случаем конечного автомата. Сам Алан Тьюринг использовал понятие «вычислительная машина» («computing machine»).

Отдельно останавливаться на самом Тьюринге нет смысла, личность его достаточно известна. Чего стоит только один фильм «Игра в имитацию» с великолепным Бенедиктом Камбербэдчем. Кто не смотрел — крайне рекомендую.

Машина Тьюринга разрабатывалась для того, чтобы ответить на вопрос: «есть ли конкретный метод или механический процесс, который можно применить к математическому утверждению и он ответит, доказуемо ли это утверждение» — которым задавался известный математик Макс Ньюман на своих лекциях в Кембридже.

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

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

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

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

❯ Конечные автоматы в программировании

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

Идея рассматривать программу в терминах конечного автомата сама по себе не новая. Но наиболее активно свое развитие она получила в начале 90-х годов прошлого века. Одним из основоположников данной идеи является профессор Университета ИТМО Анатолий Абрамович Шалыто. Идея заключается в том, чтобы программировать с использованием понятия «состояние». Сперва для названия этого подхода появился термин «Switch-технологии«, так как операторы множественного выбора в традиционных языках подходили для смены состояний программы больше всего. Позже, в конце 90-х термин «Switch-технологии» был заменен на «автоматное программирование«.

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

Автоматное программирование можно рассматривать как самостоятельную парадигму. Есть мнение, что оно должно исправить недостатки ООП, и может использоваться как дополнение к нему.

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

Хочу заметить, что в англоязычном интернете упоминаний о работе Шалыто я не нашел. А Finite State Machine рассматривается как модель для разработки и электрических схем и программных алгоритмов. Каких-то отдельных названий для программирования конечных автоматов я тоже не встречал, обычно так и пишут: «программирование конечного автомата«. Хотя, мне лично такое название, как «автоматное программирование«, кажется удобным для обращения. На Хабре есть интересная статья, посвященная работе Анатолия Абрамовича, советую почитать.

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

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

Хорошим примером языка программирования, специализированного на автоматном стиле, является язык последовательных функциональных схем SFC (Sequential Function Chart).

SFC — язык программирования стандарта IEC61131-3, предназначенный для программирования промышленных контроллеров. Широко используется в SCADA/HMI пакетах для программирования промышленных логических контроллеров PLC. Является графическим языком, программа описывается в виде схематической последовательности шагов, объединенных переходами, подобно диаграмме состояний.

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

❯ Заключение

И все-таки, почему же с конечными автоматами получается такая каша? Мне кажется, что это связано с большим объемом знаний по данной тематике. Не все они имеют прямое отношение к программированию. Да и такая высокая формализация в программировании, как в синтезе электрических схем, скорее всего не нужна. Или все-таки нужна, но программисты обычно не уделяют этому вопросу достаточного внимания?

В общем, можно говорить о том, что такие понятия как: конечный автомат или конечный автомат состояний, и машина состояний или State Mashine, или Finite State Machine (FSM)- являются синонимами. Это связанно с особенностями терминологии на русском и английском языках.

Надеюсь, что дальнейшее изучение теории цифровых автоматов станет для вас значительно проще.

• timeweb_статьи
• конечный автомат
• автомат Мура и Мили
• finite state machine
• FSM
• математика
• логические схемы
• радиоэлектроника
• Тьюринг
• scada разработка программирование

Функционирование и синтез цифровых устройств. Часть 3

Управляющие автоматы. Принцип микропрограммного управления

Введение

1. Скорость переключения задаётся частотой генератора.
2. Порядок переключения входов определяется алгоритмами работы счётчика и дешифратора.

Недостатки тоже очевидны:

1. Невозможность какого-либо внешнего управления работой УУ. Управлять можно только частотой генератора и параметрами импульсов (если взять генератор «получше»). Алгоритмы работы счётчика и дешифратора вообще жёстко фиксированы, т.к. это стандартные узлы со стандартным «поведением» и т.д.

2. Если мы захотим включать лампочки как-то иначе, например в порядке 0, 2, 1, 3, (или вообще «на лету» менять каким-либо образом эту очерёдность) либо включать их парами (например, 0-1, 2-3), то окажется, что этого в принципе сделать нельзя, т.к. счётчик/дешифратор или какие-то другие стандартные элементы «не умеют» так работать.

Для преодоления этих недостатков разрабатывают специальные УА.

Раздел 1. Управляющие автоматы с жёсткой логикой

Теория управляющих абстрактных и конечных автоматов – очень обширная наука, описывающая понятие автоматов, их поведение, формализацию, различные модели и пр. Здесь не будут рассматриваться все эти теоретические аспекты, рассмотрим лишь две практических варианта УА с жёсткой логикой.

Название «автомат с жёсткой логикой» проистекает из того, что алгоритм функционирования такого автомата жёстко задан его схемой. Для внесения даже незначительных изменений в алгоритм необходимо полностью (или почти полностью) пересинтезировать всю схему автомата. «Отделаться» какими-то мелкими изменениями возможно далеко не всегда.

Обобщённая структурная схема УА с жёсткой логикой имеет вид – рис. 2.

Рис. 2. Обобщённая структурная схема УА с жёсткой логикой

На рис. 2: X – множество входных сигналов автомата, Y – множество выходных сигналов, D – сигналы управления памятью, T – сигналы состояния.

УА состоит из 2-х функциональных блоков:

1. КС – комбинационная схема, формирующая выходные сигналы автомата и сигналы управления памятью.

2. Память автомата – просто набор триггеров (регистр). Кол-во триггеров n определяется кол-вом k требуемых состояний автомата. k определяется по-разному для разных автоматов. k равно ближайшему целому (в большую сторону) числу из значений выражения 2 n . Т.е. n=]log₂k[. Например, если у нас 5 состояний, то мы должны поставить 3 триггера (2 3 =8>5), а если 8, то 4 (2 4 =16>8).

Функционирование УА может задаваться графом переходов либо таблицами истинности. Можно описать его поведение и формулами: Y=ƒ1(X,T), D=ƒ2(X,T).

Очевидно, что при использовании одновходовых триггеров (D и Т) КС получается проще (для каждого триггера формировать надо только один сигнал вместо 2, как для RS или JK триггеров). На практике, если, например, в наличии есть только RS-триггеры, то можно несколько «схитрить», сделав D-триггеры из RS и синтезировать КС в расчёте на D.

Следует также отметить, что всегда следует применять триггеры с синхронизацией. Если использовать триггеры без синхронизации, например, асинхронные RS-триггеры, то полученный автомат будет «перещёлкивать» все свои состояния очень быстро, со скоростью, определяемой скоростью работы элементов, входящих в КС и самих триггеров. Кроме того, на выходе могут появляться какие-то другие, случайные и «незапланированные» комбинации состояний выходов.

Если применяются D-триггеры, то можно использовать обычные регистры хранения вместо раздельных триггеров. Это может существенно упростить конечную схему.

УА с жёсткой логикой бывают 2-х видов – Мили и Мура.

1.1 Управляющий автомат Мили

Автомат Мили имеет структуру, на 100% совпадающую с рис. 2. И поведение его описывается теми же общими формулами – Y=ƒ1(X,T), D=ƒ2(X,T). Поэтому иногда говорят, что этот автомат генерирует (в смысле изменяет) выходные сигналы при переходах из одного состояния в другое. Здесь подчёркивается тот факт, что Y непосредственно зависит от X.

Рассмотрим синтез автомата Мили на примере.

Допустим, нам необходимо построить автомат, имеющий 2 входных сигнала (x1, x2) и 4 выходных (y1-y4):

Т.к. мы имеем 6 состояний, то нам понадобится 3 триггера. Используем для простоты D-триггеры. Построим теперь полную таблицу истинности автомата:

1. Пронумеровали все состояния автомата.
2. Закодировали все 6 состояний автомата сигналами текущего состояния триггеров Tx. Кодировать можно как угодно, единственное требование – все коды состояний д.б. уникальны. Т.е. не должно быть 2-х и более состояний с одинаковыми кодами.
3. Дополнили исходную таблицу сигналами Tx и сигналами Dx управления триггерами для того, чтобы автомат мог переходить из одного состояния в другое.

Также подразумевается, что состояния меняются по кругу. В разделе 1.2 показано, как реализовывается переход их одного состояния в 2 других в зависимости от разных входных сигналов.

По этой таблице уже можно синтезировать КС автомата. Но перед тем, как перейти непосредственно к синтезу, отметим небольшую особенность использованного кодирования состояний: сигнал T1 повторяет x1 со сдвигом на один такт. Это позволяет не строить какие-то формулы и схемы для сигнала D1, а сразу пустить x1 на D1. Подобные «уловки» в ряде случаев позволяют упростить схему и ускорить её быстродействие.

КС должна формировать 7 сигналов: y1-y4 и D1-D3. Составим формулы для каждого сигнала:

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

Следует отметить, что у автомата Мили теоретически возможна ситуация, при которой окажется, что какой-то yi зависит только от xj и не зависит от Tn. Т.е. автомат изменяет выходные сигналы, не изменяя своего состояния. Учесть это при синтезе сложно, гораздо проще после него ввести какие-то «ненужные» зависимости yi от каких-то Tn.

1.2 Управляющий автомат Мура

Автомат Мура отличается от Мили тем, что он описывается формулами Y=ƒ1(T), D=ƒ2(X,T). Т.е. его выходные сигналы зависят только от состояния триггеров. Поэтому его КС фактически распадается на 2 независимые КС – рис. 3.

Рис. 3 Структура автомата Мура

КС1 реализует функцию D=ƒ2(X,T), а КС2 — Y=ƒ1(T).

Построим автомат Мура для того же примера:

Сразу отметим, что состояния 2 и 5 для Мура полностью эквивалентны, т.к. они генерируют идентичные наборы выходных сигналов. Поэтому состояние 5 можно выбросить и добавить дополнительный переход из состояния 2 по сигналам x1x2=01 в состояние 0. Это действие заменит выброшенное 5-е состояние в плане переходов.

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

ТИ для КС1 (таблица переходов автомата):

Правила кодирования состояний те же, что и автомате Мили.

Коды состояний 001, 100, 101 и сочетание входных сигналов x1x2=10 не используются, это можно учитывать при минимизации.

Обратите внимание, что в таблице 2 строки, соответствующие состоянию 2. Строка 2b соответствует выброшенному состоянию 5. Видно, что из неё автомат переходит в состояние 0.

Получим минимальные формулы сигналов D1, D2 и D3 КС1:

Карта Карно для сигнала X1 – рис 4.

Рис 4. Карта Карно для сигнала X1.

Из карты следует, что D1 = x1. Это же видно из ТИ.

Аналогично:
D2 = x1 + T2 + T1 T2 T3 x2
D3 = T1 T2 T3 x2 + T2 + T1 T2 T3 x1

ТИ для КС2 автомата:

Рис.5 Карты Карно для сигналов y1-y4

Из анализа формул видно, что y3 и y4 можно формировать, используя уже готовые y1 и y2. Это может дополнительно упростить КС2, но на практике такое решение снижает нагрузочную способность схемы на выходах y1 и y2.

Также, можно упростить реальную схему, если в каком-то смысле объединять схемы КС1 и КС2, формируя общие для них внутренние сигналы (например, T1 T3 ) и использовать их одновременно в обоих схемах. Конечно, обращая внимание на длину получаемых цепочек элементов и на их быстродействие (при увеличении длины цепочки падает её быстродействие).

Даже несмотря на то, что при рассмотрении автомата Мили мы не минимизировали его формулы, можно заметить, что автомат Мура проще уже потому, что для формирования Y не нужны сигналы X.

Раздел 2. Микропрограммное управление.

Основное достоинство рассмотренных УА с жёсткой логикой – их высокое быстродействие, определяемой быстродействием используемой элементной базы.

Однако есть и большие недостатки:

1. при необходимости внесения любых, даже небольших изменений алгоритма работы схему автомата надо полностью пересинтезировать.

2. при большом числе входных и выходных сигналов схема автомата сильно разрастается, а синтез становится сложным и тяжёлым занятием. Так, карты Карно уже при 5 аргументах (см. рис. 4) становятся трудночитаемыми и труднопонимаемыми, т.к. не все клетки, которые можно склеить и минимизировать, являются физически соседними. Неизбежным итогом этого может стать неполная минимизация и, как следствие излишне сложная и избыточная схема полученного автомата. На работоспособность схемы это, правда, не повлияет.

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

В таких случаях используют принципиально другие УА – УА с микропрограммным управлением.

Структура такого УА изображена на рис. 6.

Рис. 6. Структура УА с микропрограммным управлением

Основа такого управляющего аппарата – ROM – ПЗУ. Каждая ячейка ПЗУ хранит микрокоманду (МК) – набор выходных сигналов Y для каждого состояния автомата и набор управляющих сигналов T для своего сугубо внутреннего устройства управления УУ.

В плане генерации выходных сигналов все микропрограммные автоматы идентичны автомату Мура – Y зависят только от состояния памяти автомата.

УА с микропрограммным управлением бывают 2-х типов – с естественной адресацией микрокоманд и с принудительной. В каждом случае структура УУ разная.

Рассмотрим эти 2 варианта.

2.1. Микропрограммный УА с принудительной адресацией

Структура УА с принудительной адресацией приведена на рис. 7.

Рис. 7. Структура УА с принудительной адресацией

На рис.7: MS1 – мультиплексор входных сигналов, MS2 – мультиплексор адреса микрокоманды, РАМК – регистр адреса микрокоманды, МПЗУ – ROM микропрограмм из рис. 6, РМК – регистр микрокоманд.

Разрядность MS2 и РАМК равна адресности ROM n=]log₂k[, где k – кол-во микрокоманд автомата. Например, если у нас 13 микрокоманд, то для них надо 13 ячеек ПЗУ, для адресации которых требуется n=]log₂13[=4 разряда адреса.

Разрядность ПЗУ и РМК равна кол-ву всех сигналов, которое должна выдавать ROM

Формат РМК идентичен формату микрокоманды: A0 и A1 – адрес следующей МК в ПЗУ, по которому перейдёт автомат, если выбранный управляющий сигнал равен 0 или 1 соответственно. Nx – код входного сигнала, проверяемого в текущей МК, ОЧ – операционная часть, содержит все выходные сигналы автомата.

ДШМО – дешифратор микрооперации. Его назначение – уменьшить разрядность ПЗУ и РАМК, в том случае, если все или часть входных сигналов Y являются унитарными и их можно закодировать таким образом, чтобы разрядность поля ОЧ была меньше кол-ва выходных сигналов. В общем случае он не нужен.

В реальности регистр РМК можно исключить, т.к. ПЗУ не меняют состояния своих выходов при неизменности адреса. Т.е., пока содержимое РАМК неизменно, то и на выходах ПЗУ будет неизменная информация.

Целесообразность использования ДШМО на практике зависит и от разрядности реальных ПЗУ, из которых будет строиться МПЗУ автомата.

Так, например, если мы будем использовать 8-разрядные ПЗУ, то, понятно, что конечная разрядность МПЗУ будет кратна 8 битам. Поэтому, если, допустим, на все поля в сумме без доп. кодирования Y понадобится 15 разрядов, а с кодированием 12, то доп. кодирование каких-то Yi и введение дешифратора не приведёт к уменьшению конечного МПЗУ (и на 15 и на 12 сигналов надо 2 8-битных микросхемы ПЗУ), а дополнительный дешифратор только усложнит схему и, возможно, снизит её быстродействие. Но, если в распоряжении есть и 8 и 4-разрядные ПЗУ (8+4=12), то в случае с 12-разрядной МК мы можем применить не две 8-битные микросхемы, а одну 8 и одну 4 битную, то вариант с ДШ может оказаться выгоднее.

Также, следует отметить, что промышленность не выпускает регистров с двумя входными шинами (РАМК на рис. 7). Поэтому, при необходимости такой узел м.б. заменён многоразрядным мультиплексором с двух направлений и обычным одновходовым регистром.

Рассмотрим подробно работу микропрограммного автомата с принудительной адресацией.

Работа автомата начинается с занесения в регистр адреса микрокоманд (РАМК) кода операции (по сути стартового адреса микрокоманды). В простейшем случае вместо занесения адреса можно использовать вход сброса регистра.

На время исполнения микрокоманда из RAM копируется в регистр микрокоманд РМК.

Далее мультиплексор MS1 передаёт на свой выход значение входного сигнала Xi, указанного полем Nx микрокоманды.

По сигналу с MS1 мультиплексор MS2 выбирает один из двух адресов A0/А1 и передаёт его на вход РАМК.

После этого всё повторяется.

Отметим, что на первый (с номером 0) вход мультиплексора MS1 заведен постоянный лог. 0. Это даёт возможность реализации МК с безусловным переходом по адресу A0 в тех МК, где не нужно проверять никакие входные сигналы. Вместо лог. 0 можно использовать лог. 1. Это повлияет только на то, что адресом перехода будет считаться содержимое поля A1, а не A0.

Наличие MS1 обусловливает следующую особенность автомата – любая МК может проверять (учитывать) только один сигнал Xi. Это обстоятельство относится к любым автоматам с микропрограммным управлением (не только с принудительной адресацией). Поэтому, если в какой-либо МК необходимо проверять несколько Xi, то такая МК разбивается на несколько, проверяющих требуемые Xi в произвольном порядке.

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

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