Синтез автомата Мили по граф-схеме — различия между версиями
Строка 91: | Строка 91: | ||
'''Рис.4. ФСА автомата Мили на жёсткой логике.''' | '''Рис.4. ФСА автомата Мили на жёсткой логике.''' | ||
+ | == Пример 2 == | ||
+ | Синтез автомата Мили по '''ГСА''' (рис.5). | ||
+ | |||
+ | [[файл:ГСА041.png]] | ||
+ | |||
+ | '''Рис.5. ГСА автомата Мили с узлами. ''' | ||
+ | === Разметка состояний === | ||
+ | В автомате Мили входу каждой операторной вершины соответствует состояние автомата. | ||
+ | Микрокоманда | ||
+ | '''y<sub>1</sub>y<sub>2</sub>''' вырабатывается '''УА''' при завершении его работы по '''ГСА'''. | ||
+ | '''y<sub>1</sub>y<sub>2</sub>''' — соответствует событию «операция выполнена». | ||
+ | Искусственно введём '''y<sub>1</sub>y<sub>2</sub>''' при любых переходах в начальное (конечное) состояние '''а<sub>0</sub>'''. | ||
+ | Переход из состояния '''a<sub>m</sub>''' в состояние '''a<sub>s</sub>''' — это переход из одной операторной вершины в другую при выполнении логический условий '''X(a<sub>m</sub>,a<sub>s</sub>)''' на пути из '''a<sub>m</sub>''' в '''a<sub>s</sub>'''. | ||
+ | Т.к. начальное и конечное состояние автомата совпадают, на '''ГСА''' искусственно добавлена еще одна операторная вершина, соответствующая состоянию '''a<sub>0</sub>'''. | ||
+ | |||
+ | [[файл:ГСА042.png]] | ||
+ | |||
+ | '''Рис.6. Размеченная ГСА автомата Мили'''. | ||
+ | === Построение прямой таблицы переходов 3 === | ||
+ | Прямая таблица переходов строится по размеченной '''ГСА''' (рис.5). В ней указываются все возможные пути переходов из состояния '''а<sub>m</sub>''' в состояние '''а<sub>s</sub>''', условия при которых переход из '''а<sub>m</sub>''' в '''а<sub>s</sub>''', происходит по данному пути '''(X(a<sub>m</sub>,a<sub>s</sub>))''', микрокоманда '''(Y(a<sub>m</sub>,a<sub>s</sub>))''', вырабатывается автоматом на данном переходе. | ||
+ | Все эти переходы описываются в прямой таблице переходов. | ||
+ | В столбце '''X(a<sub>m</sub>,a<sub>s</sub>)''' единица записывается тогда, когда '''a<sub>m</sub>''' в '''a<sub>s</sub>''' переход осуществляется всегда. | ||
+ | |||
+ | '''Таблица 3.''' | ||
+ | |||
+ | [[файл:ГСА043.png]] | ||
+ | === Кодирование состояний === | ||
+ | Произведём кодирование узлов. | ||
+ | '''УА''' с жесткой логикой имеет память состояний, которая обычно выполнена на '''D'''- или '''RS'''- триггерах, синхронизируемых фронтом. Каждое состояние кодируется двоичным числом. Минимальное количество триггеров для памяти состояний должно быть больше или равно log2 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 5, поэтому число элементов памяти = 3. | ||
+ | Коды состояний: '''k(a<sub>0</sub>)=100; k(a<sub>1</sub>)=011; k(a<sub>2</sub>)=010; k(a<sub>3</sub>)=001; k(a<sub>4</sub>)=000'''. | ||
+ | === Построение обратной структурной таблицы 4 === | ||
+ | Обратная структурная таблицы автомата строится из прямой таблицы переходов упорядочиванием строк по полю '''а<sub>s</sub>''' и добавлением столбцов '''k(a<sub>m</sub>), k(a<sub>s</sub>), F(a<sub>m</sub>,a<sub>s</sub>)'''. | ||
+ | В столбце '''F(a<sub>m</sub>,a<sub>s</sub>)''' — записываются значения сигналов управления элементами памяти. В данном примере в качестве элементов памяти выбраны '''D'''-триггера. Их состояние зависит от значения управляющего сигнала '''D''' на входе '''D'''-триггера. | ||
+ | |||
+ | '''Таблица 4.''' | ||
+ | |||
+ | [[файл:ГСА044.png]] | ||
+ | |||
+ | Построим по таблице 4 граф переходов (см.рис.7). | ||
+ | |||
+ | [[файл:ГСА035.png]] | ||
+ | |||
+ | '''Рис.7. Граф переходов.''' | ||
+ | === Запись функции выходов и переходов автомата === | ||
+ | В функциях выходов '''y<sub>i</sub>= f<sub>i</sub>(a<sub>m</sub>,X(a<sub>m</sub>,a<sub>s</sub>))''', записанных в виде '''ДНФ''', описываются условия формирования автоматом микрокоманды '''y<sub>i</sub>'''; '''a<sub>m</sub>''' — исходное состояние, '''X(a<sub>m</sub>,a<sub>s</sub>)''' — условия перехода из '''a<sub>m</sub>''' в '''a<sub>s</sub>'''. | ||
+ | В функциях переходов '''D<sub>i</sub>= f<sub>i</sub>(a<sub>m</sub>,X(a<sub>m</sub>,a<sub>s</sub>))''', также записанных в виде '''ДНФ''', описываются значения сигналов управления элементами памяти, обеспечивающих переход из состояния '''a<sub>m</sub>''' в '''a<sub>s</sub>'''. | ||
+ | Функции выходов и переходов могут быть минимизированы с использованием карт Карно или законов булевой алгебры. | ||
+ | По обратной структурной таблице запишем функции для '''Y<sub>i</sub>''' и '''D<sub>i</sub>'''. | ||
+ | |||
+ | [[файл:ГСА046.png]] | ||
+ | === Построение ФСА автомата Мили === | ||
+ | В качестве элементов памяти использованы '''D'''-триггера '''T<sub>1</sub>''' и '''T<sub>0</sub>'''. '''DC''' — дешифратор состояний автомата. '''Z<sub>i</sub>''' — промежуточные функции — термы из функций. Их введение позволило упростить схему автомата. | ||
+ | |||
+ | [[файл:ГСА047.png]] | ||
+ | |||
+ | '''Рис.8. ФСА автомата Мили на жёсткой логике.''' | ||
= Ссылки = | = Ссылки = | ||
*https://ru.wikipedia.org/wiki/Автомат_Мили | *https://ru.wikipedia.org/wiki/Автомат_Мили |
Версия 14:39, 10 июля 2022
Синтез автомата Мили по граф-схеме — это метод построения функциональной схемы автомата.
Содержание
Описание
Автомат Мили (Mealy machine) — кортеж из 6 элементов, включающий: множество внутренних состояний S (внутренний алфавит); начальное состояние S0; множество входных сигналов X (входной алфавит); множество выходных сигналов Y (выходной алфавит); функция переходов X; функция выходов Y.
Определение
Автомат Мили — конечный автомат, выходная последовательность которого зависит от состояния автомата и входных сигналов, в отличие от автомата Мура. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы. Назван именем Джорджа Мили, учёного в области математики и компьютерных наук, придумавшего этот автомат.
Обозначения
ГСА — граф-схема автомата;
ФСА — функциональная схема автомата;
a0 — вход вершины следующей за оператором — начальное и конечное состояние автомата;
am — вход вершины следующей за оператором — исходное состояние перехода;
as — вход вершины следующей за оператором — конечное состояние перехода;
am→as — переход из одного состояния в другое;
X(am,as) — логическое условие перехода;
Y(am,as) — функция выходов (микрокоманда);
Zi — промежуточные функции;
DC — дешифратор состояний автомата;
Di — значение на D-триггере.
Примеры:
Пример 1
Синтез автомата Мили по ГСА (рис.1).
Рис.1. ГСА автомата Мили с узлами.
Разметка состояний
В автомате Мили входу каждой операторной вершины соответствует состояние автомата. Микрокоманда y1y2 вырабатывается УА при завершении его работы по ГСА. y1y2 — соответствует событию «операция выполнена». Искусственно введём y1y2 при любых переходах в начальное (конечное) состояние а0. Переход из состояния am в состояние as — это переход из одной операторной вершины в другую при выполнении логический условий X(am,as) на пути из am в as. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию a0.
Рис.2. Размеченная ГСА автомата Мили.
Построение прямой таблицы переходов 1
Прямая таблица переходов строится по размеченной ГСА (рис.1). В ней указываются все возможные пути переходов из состояния аm в состояние аs, условия при которых переход из аm в аs, происходит по данному пути (X(am,as)), микрокоманда (Y(am,as)), вырабатывается автоматом на данном переходе. Все эти переходы описываются в прямой таблице переходов. В столбце X(am,as) единица записывается тогда, когда am в as переход осуществляется всегда.
Таблица 1.
Кодирование состояний
Произведём кодирование узлов. УА с жесткой логикой имеет память состояний, которая обычно выполнена на D- или RS- триггерах, синхронизируемых фронтом. Каждое состояние кодируется двоичным числом. Минимальное количество триггеров для памяти состояний должно быть больше или равно log2 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 5, поэтому число элементов памяти = 3. Коды состояний: k(a0)=100; k(a1)=011; k(a2)=010; k(a3)=001; k(a4)=000.
Построение обратной структурной таблицы 2
Обратная структурная таблицы автомата строится из прямой таблицы переходов упорядочиванием строк по полю аs и добавлением столбцов k(am), k(as), F(am,as). В столбце F(am,as) — записываются значения сигналов управления элементами памяти. В данном примере в качестве элементов памяти выбраны D-триггера. Их состояние зависит от значения управляющего сигнала D на входе D-триггера.
Таблица 2.
Построим по таблице 2 граф переходов (см.рис.3).
Рис.3. Граф переходов.
Запись функции выходов и переходов автомата
В функциях выходов yi= fi(am,X(am,as)), записанных в виде ДНФ, описываются условия формирования автоматом микрокоманды yi; am — исходное состояние, X(am,as) — условия перехода из am в as. В функциях переходов Di= fi(am,X(am,as)), также записанных в виде ДНФ, описываются значения сигналов управления элементами памяти, обеспечивающих переход из состояния am в as. Функции выходов и переходов могут быть минимизированы с использованием карт Карно или законов булевой алгебры. По обратной структурной таблице запишем функции для Yi и Di.
Построение ФСА автомата Мили
В качестве элементов памяти использованы D-триггера T1 и T0. DC — дешифратор состояний автомата. Zi — промежуточные функции — термы из функций. Их введение позволило упростить схему автомата.
Рис.4. ФСА автомата Мили на жёсткой логике.
Пример 2
Синтез автомата Мили по ГСА (рис.5).
Рис.5. ГСА автомата Мили с узлами.
Разметка состояний
В автомате Мили входу каждой операторной вершины соответствует состояние автомата. Микрокоманда y1y2 вырабатывается УА при завершении его работы по ГСА. y1y2 — соответствует событию «операция выполнена». Искусственно введём y1y2 при любых переходах в начальное (конечное) состояние а0. Переход из состояния am в состояние as — это переход из одной операторной вершины в другую при выполнении логический условий X(am,as) на пути из am в as. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию a0.
Рис.6. Размеченная ГСА автомата Мили.
Построение прямой таблицы переходов 3
Прямая таблица переходов строится по размеченной ГСА (рис.5). В ней указываются все возможные пути переходов из состояния аm в состояние аs, условия при которых переход из аm в аs, происходит по данному пути (X(am,as)), микрокоманда (Y(am,as)), вырабатывается автоматом на данном переходе. Все эти переходы описываются в прямой таблице переходов. В столбце X(am,as) единица записывается тогда, когда am в as переход осуществляется всегда.
Таблица 3.
Кодирование состояний
Произведём кодирование узлов. УА с жесткой логикой имеет память состояний, которая обычно выполнена на D- или RS- триггерах, синхронизируемых фронтом. Каждое состояние кодируется двоичным числом. Минимальное количество триггеров для памяти состояний должно быть больше или равно log2 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 5, поэтому число элементов памяти = 3. Коды состояний: k(a0)=100; k(a1)=011; k(a2)=010; k(a3)=001; k(a4)=000.
Построение обратной структурной таблицы 4
Обратная структурная таблицы автомата строится из прямой таблицы переходов упорядочиванием строк по полю аs и добавлением столбцов k(am), k(as), F(am,as). В столбце F(am,as) — записываются значения сигналов управления элементами памяти. В данном примере в качестве элементов памяти выбраны D-триггера. Их состояние зависит от значения управляющего сигнала D на входе D-триггера.
Таблица 4.
Построим по таблице 4 граф переходов (см.рис.7).
Рис.7. Граф переходов.
Запись функции выходов и переходов автомата
В функциях выходов yi= fi(am,X(am,as)), записанных в виде ДНФ, описываются условия формирования автоматом микрокоманды yi; am — исходное состояние, X(am,as) — условия перехода из am в as. В функциях переходов Di= fi(am,X(am,as)), также записанных в виде ДНФ, описываются значения сигналов управления элементами памяти, обеспечивающих переход из состояния am в as. Функции выходов и переходов могут быть минимизированы с использованием карт Карно или законов булевой алгебры. По обратной структурной таблице запишем функции для Yi и Di.
Построение ФСА автомата Мили
В качестве элементов памяти использованы D-триггера T1 и T0. DC — дешифратор состояний автомата. Zi — промежуточные функции — термы из функций. Их введение позволило упростить схему автомата.
Рис.8. ФСА автомата Мили на жёсткой логике.
Ссылки
- https://ru.wikipedia.org/wiki/Автомат_Мили
- Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
- Участник:Logic-samara