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