Синтез автомата Мура по граф-схеме — различия между версиями
| Строка 41: | Строка 41: | ||
=== Разметка состояний === | === Разметка состояний === | ||
В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния '''b<sub>m</sub>''' в состояние '''b<sub>s</sub>''' — это переход из одной операторной вершины в другую при выполнении логический условий '''X(b<sub>m</sub>,b<sub>s</sub>)''' на пути из '''b<sub>m</sub>''' в '''b<sub>s</sub>'''. | В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния '''b<sub>m</sub>''' в состояние '''b<sub>s</sub>''' — это переход из одной операторной вершины в другую при выполнении логический условий '''X(b<sub>m</sub>,b<sub>s</sub>)''' на пути из '''b<sub>m</sub>''' в '''b<sub>s</sub>'''. | ||
| − | Т.к. начальное и конечное состояние автомата совпадают, на '''ГСА''' искусственно добавлена еще одна операторная вершина, соответствующая состоянию | + | Т.к. начальное и конечное состояние автомата совпадают, на '''ГСА''' искусственно добавлена еще одна операторная вершина, соответствующая состоянию '''b<sub>0</sub>'''. |
Узлы ө используются для упрощения формул переходов и ставятся на '''ГСА''' в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | Узлы ө используются для упрощения формул переходов и ставятся на '''ГСА''' в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | ||
| Строка 48: | Строка 48: | ||
'''Рис.2. Размеченная ГСА автомата Мура с узлами.''' | '''Рис.2. Размеченная ГСА автомата Мура с узлами.''' | ||
=== Построение прямой таблицы переходов 1 === | === Построение прямой таблицы переходов 1 === | ||
| − | Отличительная особенность: в данном примере в '''ГСА''' введены узлы ө. В '''ГСА''' с узлами возможны переходы четырех видов: | + | Отличительная особенность: в данном примере в '''ГСА''' введены узлы '''ө'''. В '''ГСА''' с узлами возможны переходы четырех видов: |
'''b<sub>m</sub>→b<sub>s</sub>''', '''b<sub>m</sub>→ө<sub>s</sub>''', '''ө<sub>m</sub>→b<sub>s</sub>''', '''ө<sub>m</sub>→ө<sub>s</sub>'''. | '''b<sub>m</sub>→b<sub>s</sub>''', '''b<sub>m</sub>→ө<sub>s</sub>''', '''ө<sub>m</sub>→b<sub>s</sub>''', '''ө<sub>m</sub>→ө<sub>s</sub>'''. | ||
Все эти переходы описываются в прямой таблице переходов. | Все эти переходы описываются в прямой таблице переходов. | ||
| Строка 84: | Строка 84: | ||
'''Рис.4. ФСА автомата Мура на жёсткой логике.''' | '''Рис.4. ФСА автомата Мура на жёсткой логике.''' | ||
== Пример 2 == | == Пример 2 == | ||
| − | Синтез автомата Мура по ГСА (рис.5). | + | Синтез автомата Мура по '''ГСА''' (рис.5). |
[[файл:ГСА021.png]] | [[файл:ГСА021.png]] | ||
Версия 05:38, 9 июля 2022
Синтез автомата Мура по граф-схеме — это метод построения функциональной схемы автомата.
Содержание
Описание
Определение 1
Автомат Мура — абстрактный автомат второго рода — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и, не зависит напрямую, в, отличие от автомата Мили, от входных значений. Автомат Мура назван в честь описавшего его свойства Эдварда Ф. Мура, опубликовавшего исследования в 1956 году в издании «Gedanken-experiments on Sequential Machines.».
Определение 2
Автомат Мура — кортеж из 6 элементов, включающий: множество внутренних состояний S (внутренний алфавит); начальное состояние S0; множество входных сигналов X (входной алфавит); множество выходных сигналов Y (выходной алфавит); функция переходов.
Обозначения
ГСА — граф-схема автомата;
ФСА — функциональная схема автомата;
b0 — операторная вершина — начальное и конечное состояние автомата;
bm — операторная вершина — исходное состояние перехода;
bs — операторная вершина — конечное состояние перехода;
өs — узел — дополнительная операторная вершина для упрощения ГСА;
bm→bs — переход из одной операторной вершины в другую;
bm→өs, өm→bs, өm→өs — дополнительные переходы;
X(bm, bs) — логическое условие перехода;
Si — значение на S-триггере;
Ri — значение на R-триггере.
Примеры:
Пример 1
Синтез автомата Мура по ГСА (рис.1).
Рис.1. ГСА автомата Мура с узлами.
Разметка состояний
В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния bm в состояние bs — это переход из одной операторной вершины в другую при выполнении логический условий X(bm,bs) на пути из bm в bs. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.
Рис.2. Размеченная ГСА автомата Мура с узлами.
Построение прямой таблицы переходов 1
Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: bm→bs, bm→өs, өm→bs, өm→өs. Все эти переходы описываются в прямой таблице переходов.
Таблица 1.
В столбце X(bm,bs) единица записывается тогда, когда bm в bs переход осуществляется всегда.
Кодирование состояний
Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b0)=000; k(b1)=001; k(b2)=010; k(b3)=011; k(b4)=100.
Построение обратной структурной таблицы 2
Вначале описываем переходы в узлы, затем остальные переходы автомата.
Таблица 2.
Если переход в некоторое состояние bs происходит из узла ө, то в автомате с памятью на RS триггерах значения Ri и Si в обратной структурной таблице записываются с учетом кодов состояний bm из которых был переход в узел ө.
Рис.3. Схема определения значений Ri и Si.
Запись функции выходов и переходов автомата
По обратной структурной таблице запишем функции для ө, Yi, Ri и Si.
Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.
Построение ФСА автомата Мура
Рис.4. ФСА автомата Мура на жёсткой логике.
Пример 2
Синтез автомата Мура по ГСА (рис.5).
Рис.5. ГСА автомата Мура с узлами.
Разметка состояний
В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния bm в состояние bs — это переход из одной операторной вершины в другую при выполнении логический условий X(bm,bs) на пути из bm в bs. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.
Рис.6. Размеченная ГСА автомата Мура с узлами.
Построение прямой таблицы переходов 3
Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: bm→bs, bm→өs, өm→bs, өm→өs. Все эти переходы описываются в прямой таблице переходов.
Таблица 3.
В столбце X(bm,bs) единица записывается тогда, когда bm в bs переход осуществляется всегда.
Кодирование состояний
Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b0)=00; k(b1)=01; k(b2)=01; k(b3)=11.
Построение обратной структурной таблицы 4
Вначале описываем переходы в узлы, затем остальные переходы автомата.
Таблица 4.
Если переход в некоторое состояние bs происходит из узла ө, то в автомате с памятью на RS триггерах значения Ri и Si в обратной структурной таблице записываются с учётом кодов состояний bm из которых был переход в узел ө.
Рис.7. Схема определения значений Ri и Si.
Запись функции выходов и переходов автомата
По обратной структурной таблице запишем функции для ө, Yi, Ri и Si.
Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.
Построение ФСА автомата Мура
Рис.8. ФСА автомата Мура на жёсткой логике.
Ссылки
- Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
- Участник:Logic-samara
