Редактирование: Синтез автомата Мили по граф-схеме

'''Синтез автомата Мили по граф-схеме''' — это метод построения функциональной схемы автомата.
= Описание =
'''Автомат Мили (Mealy machine)'''  —  кортеж из 6 элементов, включающий:
множество внутренних состояний '''S''' (внутренний алфавит);
начальное состояние '''S<sub>0</sub>''';
множество входных сигналов '''X''' (входной алфавит);
множество выходных сигналов '''Y''' (выходной алфавит);
функция переходов '''X''';
функция выходов '''Y'''.
== Определение  ==
'''Автомат Мили''' — конечный автомат, выходная последовательность которого зависит от состояния автомата и входных сигналов, в отличие от [[Синтез автомата Мура по граф-схеме|автомата Мура]]. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). 
В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы. 
Назван именем Джорджа Мили, учёного в области математики и компьютерных наук, придумавшего этот автомат. 
== Обозначения ==
'''ГСА''' — граф-схема автомата;

'''ФСА''' — функциональная схема автомата;

'''a<sub>0</sub>''' — вход вершины следующей за оператором — начальное и конечное состояние автомата;

'''a<sub>m</sub>''' — вход вершины следующей за оператором — исходное состояние перехода;

'''a<sub>s</sub>''' — вход вершины следующей за оператором — конечное состояние перехода;

'''a<sub>m</sub>→a<sub>s</sub>''' — переход из одного состояния в другое;

'''X(a<sub>m</sub>,a<sub>s</sub>)''' — логическое условие перехода;

'''Y(a<sub>m</sub>,a<sub>s</sub>)''' — функция выходов (микрокоманда);

'''Z<sub>i</sub>''' — промежуточные функции;

'''DC''' — дешифратор состояний автомата; 

'''D<sub>i</sub>''' — значение на '''D'''-триггере.
= Примеры: =
== Пример 1 ==
Синтез автомата Мили по '''ГСА''' (рис.1).
                                       
[[файл:ГСА031.png]]

'''Рис.1. ГСА автомата Мили с узлами. '''
=== Разметка состояний ===
В автомате Мили входу каждой операторной вершины соответствует состояние автомата.
Микрокоманда 
'''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>'''.

[[файл:ГСА032.png]]
                                   
'''Рис.2. Размеченная ГСА автомата Мили'''.
=== Построение прямой таблицы переходов 1 ===
Прямая таблица переходов строится по размеченной '''ГСА''' (рис.1). В ней указываются все возможные пути переходов из состояния '''а<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>''' переход осуществляется всегда.

'''Таблица 1.'''

[[файл:ГСА033.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'''.
=== Построение обратной структурной таблицы 2 ===
Обратная структурная таблицы автомата строится из прямой таблицы переходов упорядочиванием строк по полю '''а<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'''-триггера.

'''Таблица 2.'''

[[файл:ГСА034.png]]

Построим по таблице 2 граф переходов (см.рис.3).

[[файл:ГСА035.png]]

'''Рис.3. Граф переходов.'''
=== Запись функции выходов и переходов автомата ===
В функциях выходов '''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>'''.

[[файл:ГСА036.png]]
=== Построение ФСА автомата Мили ===
В качестве элементов памяти использованы '''D'''-триггера '''T<sub>1</sub>''' и '''T<sub>0</sub>'''. '''DC''' — дешифратор состояний автомата. '''Z<sub>i</sub>''' — промежуточные функции — термы из функций. Их введение позволило упростить схему автомата.

[[файл:ГСА037.png]]

'''Рис.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).

[[файл:ГСА045.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/Автомат_Мили 
*Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
*[[Участник:Logic-samara]]
[[Категория:Дискретная математика]][[Категория:Алгоритмы]][[Категория:Автоматы]]