Синтез автомата Мура по граф-схеме — различия между версиями
Строка 29: | Строка 29: | ||
'''X(b<sub>m</sub>, b<sub>s</sub>)''' — логическое условие перехода; | '''X(b<sub>m</sub>, b<sub>s</sub>)''' — логическое условие перехода; | ||
− | '''S<sub>i</sub>''' — значение на S-триггере; | + | '''S<sub>i</sub>''' — значение на '''S'''-триггере; |
− | '''R<sub>i</sub>''' — значение на R-триггере. | + | '''R<sub>i</sub>''' — значение на '''R'''-триггере. |
= Примеры: = | = Примеры: = | ||
== Пример 1 == | == Пример 1 == | ||
Строка 38: | Строка 38: | ||
[[файл:ГСА011.png]] | [[файл:ГСА011.png]] | ||
− | Рис.1. ГСА автомата Мура с узлами. | + | '''Рис.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>'''. | В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния '''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. | + | Т.к. начальное и конечное состояние автомата совпадают, на '''ГСА''' искусственно добавлена еще одна операторная вершина, соответствующая состоянию b0. |
− | Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | + | Узлы ө используются для упрощения формул переходов и ставятся на '''ГСА''' в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. |
[[файл:ГСА012.png]] | [[файл:ГСА012.png]] | ||
− | Рис.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>'''. | ||
Все эти переходы описываются в прямой таблице переходов. | Все эти переходы описываются в прямой таблице переходов. | ||
Строка 58: | Строка 58: | ||
В столбце '''X(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>''' переход осуществляется всегда. | ||
=== Кодирование состояний === | === Кодирование состояний === | ||
− | Произведём кодирование узлов (узлы ө не кодируются). | + | Произведём кодирование узлов (узлы '''ө''' не кодируются). |
В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на '''RS''' триггерах. | В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на '''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'''. | ||
Строка 68: | Строка 68: | ||
[[файл:ГСА014.png]] | [[файл:ГСА014.png]] | ||
− | Если переход в некоторое состояние '''b<sub>s</sub>''' происходит из узла ө, то в автомате с памятью на '''RS''' триггерах значения '''R<sub>i</sub>''' и '''S<sub>i</sub>''' в обратной структурной таблице записываются с учетом кодов состояний '''b<sub>m</sub>''' из которых был переход в узел ө. | + | Если переход в некоторое состояние '''b<sub>s</sub>''' происходит из узла ө, то в автомате с памятью на '''RS''' триггерах значения '''R<sub>i</sub>''' и '''S<sub>i</sub>''' в обратной структурной таблице записываются с учетом кодов состояний '''b<sub>m</sub>''' из которых был переход в узел '''ө'''. |
[[файл:ГСА015.png]] | [[файл:ГСА015.png]] | ||
− | Рис.3. Схема определения значений | + | '''Рис.3. Схема определения значений R<sub>i</sub> и S<sub>i</sub>'''. |
=== Запись функции выходов и переходов автомата === | === Запись функции выходов и переходов автомата === | ||
По обратной структурной таблице запишем функции для '''ө, Y<sub>i</sub>, R<sub>i</sub>''' и '''S<sub>i</sub>'''. | По обратной структурной таблице запишем функции для '''ө, Y<sub>i</sub>, R<sub>i</sub>''' и '''S<sub>i</sub>'''. | ||
Строка 78: | Строка 78: | ||
[[файл:ГСА016.png]] | [[файл:ГСА016.png]] | ||
− | Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов. | + | Легко заметить, что использование узлов в '''ГСА''' автомата Мура позволило значительно упростить функции выходов и переходов. |
=== Построение ФСА автомата Мура === | === Построение ФСА автомата Мура === | ||
[[файл:ГСА017.png]] | [[файл:ГСА017.png]] | ||
− | Рис.4. ФСА автомата Мура на жёсткой логике. | + | '''Рис.4. ФСА автомата Мура на жёсткой логике.''' |
== Пример 2 == | == Пример 2 == | ||
Синтез автомата Мура по ГСА (рис.5). | Синтез автомата Мура по ГСА (рис.5). | ||
Строка 88: | Строка 88: | ||
[[файл:ГСА021.png]] | [[файл:ГСА021.png]] | ||
− | Рис.5. ГСА автомата Мура с узлами. | + | '''Рис.5. ГСА автомата Мура с узлами.''' |
=== Разметка состояний === | === Разметка состояний === | ||
В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния '''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>'''. | + | Т.к. начальное и конечное состояние автомата совпадают, на '''ГСА''' искусственно добавлена еще одна операторная вершина, соответствующая состоянию '''b<sub>0</sub>'''. |
− | Узлы '''ө''' используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. | + | Узлы '''ө''' используются для упрощения формул переходов и ставятся на '''ГСА''' в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются. |
[[файл:ГСА022.png]] | [[файл:ГСА022.png]] | ||
− | Рис.6. Размеченная ГСА автомата Мура с узлами. | + | '''Рис.6. Размеченная ГСА автомата Мура с узлами.''' |
=== Построение прямой таблицы переходов 3 === | === Построение прямой таблицы переходов 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>'''. | '''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>'''. | ||
Все эти переходы описываются в прямой таблице переходов. | Все эти переходы описываются в прямой таблице переходов. | ||
Строка 108: | Строка 108: | ||
В столбце '''X(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>''' переход осуществляется всегда. | ||
=== Кодирование состояний === | === Кодирование состояний === | ||
− | Произведём кодирование узлов (узлы ө не кодируются). | + | Произведём кодирование узлов (узлы '''ө''' не кодируются). |
− | В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на RS триггерах. | + | В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на '''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'''. | Коды состояний: '''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 === | ||
Строка 122: | Строка 122: | ||
[[файл:ГСА025.png]] | [[файл:ГСА025.png]] | ||
− | Рис.7. Схема определения значений | + | '''Рис.7. Схема определения значений R<sub>i</sub> и S<sub>i</sub>.''' |
=== Запись функции выходов и переходов автомата === | === Запись функции выходов и переходов автомата === | ||
− | По обратной структурной таблице запишем функции для '''ө, Y<sub>i</sub>, R<sub>i</sub> и S<sub>i</sub>'''. | + | По обратной структурной таблице запишем функции для '''ө, Y<sub>i</sub>, R<sub>i</sub>''' и '''S<sub>i</sub>'''. |
[[файл:ГСА026.png]] | [[файл:ГСА026.png]] | ||
− | Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов. | + | Легко заметить, что использование узлов в '''ГСА''' автомата Мура позволило значительно упростить функции выходов и переходов. |
=== Построение ФСА автомата Мура === | === Построение ФСА автомата Мура === | ||
[[файл:ГСА027.png]] | [[файл:ГСА027.png]] | ||
− | Рис.8. ФСА автомата Мура на жёсткой логике. | + | '''Рис.8. ФСА автомата Мура на жёсткой логике.''' |
= Ссылки = | = Ссылки = | ||
*Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г. | *Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г. | ||
*[[Участник:Logic-samara]] | *[[Участник:Logic-samara]] | ||
[[Категория:Дискретная математика]][[Категория:Автоматы]] | [[Категория:Дискретная математика]][[Категория:Автоматы]] |
Версия 05:35, 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