Синтез автомата Мили по граф-схеме — различия между версиями

Материал из Мегапедии
Перейти к: навигация, поиск
 
(не показано 15 промежуточных версий этого же участника)
Строка 9: Строка 9:
 
функция выходов '''Y'''.
 
функция выходов '''Y'''.
 
== Определение  ==
 
== Определение  ==
−
'''Автомат Мили''' — конечный автомат, выходная последовательность которого зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ).  
+
'''Автомат Мили''' — конечный автомат, выходная последовательность которого зависит от состояния автомата и входных сигналов, в отличие от [[Синтез автомата Мура по граф-схеме|автомата Мура]]. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ).  
 
В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.  
 
В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.  
 
Назван именем Джорджа Мили, учёного в области математики и компьютерных наук, придумавшего этот автомат.  
 
Назван именем Джорджа Мили, учёного в области математики и компьютерных наук, придумавшего этот автомат.  
Строка 17: Строка 17:
 
'''ФСА''' — функциональная схема автомата;
 
'''ФСА''' — функциональная схема автомата;
  
−
'''a<sub>0</sub>''' — операторная вершина — начальное и конечное состояние автомата;
+
'''a<sub>0</sub>''' — вход вершины следующей за оператором — начальное и конечное состояние автомата;
  
−
'''a<sub>m</sub>''' — операторная вершина — исходное состояние перехода;
+
'''a<sub>m</sub>''' — вход вершины следующей за оператором — исходное состояние перехода;
  
−
'''a<sub>s</sub>''' — операторная вершина — конечное состояние перехода;
+
'''a<sub>s</sub>''' — вход вершины следующей за оператором — конечное состояние перехода;
  
−
'''a<sub>m</sub>→a<sub>s</sub>''' — переход из одной операторной вершины в другую;
+
'''a<sub>m</sub>→a<sub>s</sub>''' — переход из одного состояния в другое;
  
−
'''X(b<sub>m</sub>, b<sub>s</sub>)''' — логическое условие перехода;
+
'''X(a<sub>m</sub>,a<sub>s</sub>)''' — логическое условие перехода;
  
−
'''Y(b<sub>m</sub>, b<sub>s</sub>)''' — функция выходов (микрокоманда);
+
'''Y(a<sub>m</sub>,a<sub>s</sub>)''' — функция выходов (микрокоманда);
  
 
'''Z<sub>i</sub>''' — промежуточные функции;
 
'''Z<sub>i</sub>''' — промежуточные функции;
Строка 33: Строка 33:
 
'''DC''' — дешифратор состояний автомата;  
 
'''DC''' — дешифратор состояний автомата;  
  
−
'''D<sub>i</sub>''' — значение на '''D'''-триггере;
+
'''D<sub>i</sub>''' — значение на '''D'''-триггере.
−
 
 
−
'''S<sub>i</sub>''' — значение на '''S'''-триггере;
 
−
 
 
−
'''R<sub>i</sub>''' — значение на '''R'''-триггере.
 
 
= Примеры: =
 
= Примеры: =
 
== Пример 1 ==
 
== Пример 1 ==
Строка 46: Строка 42:
 
'''Рис.1. ГСА автомата Мили с узлами. '''
 
'''Рис.1. ГСА автомата Мили с узлами. '''
 
=== Разметка состояний ===
 
=== Разметка состояний ===
−
В автомате Мили каждой операторной вершине соответствует состояние автомата.
+
В автомате Мили входу каждой операторной вершины соответствует состояние автомата.
−
Микрокоманда y1y2 вырабатывается '''УА''' при завершении его работы по '''ГСА'''.  
+
Микрокоманда  
 +
'''y<sub>1</sub>y<sub>2</sub>''' вырабатывается '''УА''' при завершении его работы по '''ГСА'''.  
 
'''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>'''.
 
Искусственно введём '''y<sub>1</sub>y<sub>2</sub>''' при любых переходах в начальное (конечное) состояние '''а<sub>0</sub>'''.
Строка 82: Строка 79:
 
'''Рис.3. Граф переходов.'''
 
'''Рис.3. Граф переходов.'''
 
=== Запись функции выходов и переходов автомата ===
 
=== Запись функции выходов и переходов автомата ===
−
В функциях выходов '''y<sub>i</sub>= fa<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>'''.
+
В функциях выходов '''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>= fa<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>'''.
 
По обратной структурной таблице запишем функции для  '''Y<sub>i</sub>''' и '''D<sub>i</sub>'''.
Строка 94: Строка 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 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 4, поэтому число элементов памяти = 2.
 +
Коды состояний: '''k(a<sub>0</sub>)=11; k(a<sub>1</sub>)=10; k(a<sub>2</sub>)=01; k(a<sub>3</sub>)=00'''.
 +
=== Построение обратной структурной таблицы 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/Автомат_Мили  
 
*https://ru.wikipedia.org/wiki/Автомат_Мили  
 
*Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
 
*Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
 
*[[Участник:Logic-samara]]
 
*[[Участник:Logic-samara]]
−
[[Категория:Дискретная математика]][[Категория:Автоматы]]
+
[[Категория:Математика]][[Категория:Дискретная математика]][[Категория:Алгоритмы]][[Категория:Автоматы]]

Текущая версия на 15:23, 6 апреля 2023

Синтез автомата Мили по граф-схеме — это метод построения функциональной схемы автомата.

Описание

Автомат Мили (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 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 4, поэтому число элементов памяти = 2. Коды состояний: k(a0)=11; k(a1)=10; k(a2)=01; k(a3)=00.

Построение обратной структурной таблицы 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. ФСА автомата Мили на жёсткой логике.

Другие алгоритмы:

Другие разделы

Ссылки

Источник — «http://megapedia.wiki/w/index.php?title=Синтез_автомата_Мили_по_граф-схеме&oldid=114321»