Автоматы мура и мили кратко

Обновлено: 02.07.2024

Конечные автоматы могут иметь выходные данные, соответствующие каждому переходу. Существует два типа конечных автоматов, которые генерируют вывод:

Мили Машина

Мили-машина — это FSM, выход которого зависит от текущего состояния, а также от текущего ввода.

Он может быть описан набором 6 (Q, ∑, O, δ, X, q ₀ ), где —

Q — конечное множество состояний.

∑ — это конечный набор символов, называемый входным алфавитом.

O — это конечный набор символов, называемый выходным алфавитом.

δ — функция входного перехода, где δ: Q × ∑ → Q

X — функция выходного перехода, где X: Q × ∑ → O

q ₀ — начальное состояние, из которого обрабатывается любой вход (q ₀ ∈ Q).

Q — конечное множество состояний.

∑ — это конечный набор символов, называемый входным алфавитом.

O — это конечный набор символов, называемый выходным алфавитом.

δ — функция входного перехода, где δ: Q × ∑ → Q

X — функция выходного перехода, где X: Q × ∑ → O

q ₀ — начальное состояние, из которого обрабатывается любой вход (q ₀ ∈ Q).

Таблица состояний Мили-машины показана ниже —

Современное состояние	Следующее состояние
	вход = 0		вход = 1
	государственный	Выход	государственный	Выход
→ а	б	х ₁	с	х ₁
б	б	х ₂	d	х ₃
с	d	х ₃	с	х ₁
d	d	х ₃	d	х ₂

Диаграмма состояния вышеупомянутого Мили Машины —

Мур машина

Машина Мура является автоматом, выход которого зависит только от текущего состояния.

Машина Мура может быть описана набором из 6 (Q, ∑, O, δ, X, q ₀ ), где —

Q — конечное множество состояний.

∑ — это конечный набор символов, называемый входным алфавитом.

O — это конечный набор символов, называемый выходным алфавитом.

δ — функция входного перехода, где δ: Q × ∑ → Q

X — функция выходного перехода, где X: Q → O

q ₀ — начальное состояние, из которого обрабатывается любой вход (q ₀ ∈ Q).

Q — конечное множество состояний.

∑ — это конечный набор символов, называемый входным алфавитом.

O — это конечный набор символов, называемый выходным алфавитом.

Диаграмма состояний вышеуказанной машины Мура —

Мили машина против Мура машины

В следующей таблице выделены точки, которые отличают машину Мили от машины Мура.

Мили Машина	Мур машина
Выход зависит как от текущего состояния, так и от текущего ввода	Выход зависит только от текущего состояния.
Как правило, в нем меньше состояний, чем в Moore Machine.	Как правило, он имеет больше состояний, чем Мили Машина.
Значение функции выхода является функцией переходов и изменений, когда логика ввода в текущем состоянии выполнена.	Значение выходной функции является функцией текущего состояния и изменений по краям часов, когда бы ни происходили изменения состояния.
Мили машины реагируют быстрее на входы. Они обычно реагируют в одном и том же тактовом цикле.	В машинах Мура для декодирования выходов требуется больше логики, что приводит к большим задержкам в цепи. Обычно они реагируют на один такт позже.

Мур машина в Мили машина

Алгоритм 4

Выход — Мили Машина

Шаг 1 — Возьмите пустой формат таблицы переходов Mealy Machine.

Шаг 2 — Скопируйте все переходные состояния машины Мура в этот формат таблицы.

Шаг 3 — Проверьте текущие состояния и их соответствующие выходы в таблице состояний машины Мура; если для состояния Q _i вывод равен m, скопируйте его в выходные столбцы таблицы состояний Mealy Machine везде, где Q _i появляется в следующем состоянии.

пример

Давайте рассмотрим следующую машину Мура —

Современное состояние	Следующее состояние		Выход
Современное состояние	а = 0	а = 1	Выход
→ а	d	б	1
б	d	0
с	с	с	0
d	б	1

Теперь мы применяем алгоритм 4, чтобы преобразовать его в Mealy Machine.

Современное состояние	Следующее состояние
	а = 0		а = 1
	государственный	Выход	государственный	Выход
→ а	d		б
б		d
с	с		с
d	б

Современное состояние	Следующее состояние
	а = 0		а = 1
	государственный	Выход	государственный	Выход
=> а	d	1	б	0
б	1	d	1
с	с	0	с	0
d	б	0	1

Мили машина для машины Мура

Алгоритм 5

Ввод — Мили Машина

Выход — машина Мура

Шаг 1 — Рассчитайте количество различных выходов для каждого состояния (Q _i ), которые доступны в таблице состояний машины Мили.

Шаг 2 — Если все выходы Qi одинаковы, скопируйте состояние Q _i . Если он имеет n различных выходов, разбейте Q _i на n состояний как Q, где n = 0, 1, 2 …….

Шаг 3 — Если выходные данные начального состояния равны 1, вставьте новое начальное состояние в начале, которое дает 0 выходных данных.

пример

Давайте рассмотрим следующую машину Мили —

Современное состояние	Следующее состояние
	а = 0		а = 1
	Следующее состояние	Выход	Следующее состояние	Выход
→ а	d	0	б	1
б	1	d	0
с	с	1	с	0
d	б	0	1

Выходные сигналы АА зависят от того, что поступало на его вход раньше.

В каждый момент времени АА, будучи в состоянии [math]a_^[/math] , способен воспринимать одну из букв входного алфавита [math]z_^[/math] . В соответствии с функцией [math]\delta[/math] , АА перейдет в состояние [math]a_^[/math] с выдачей выходного сигнала, который вырабатывается в соответствии с функцией выходов [math]\lambda[/math] .

Рассмотрим функционирование автоматов Мура и Мили.

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t), z(t))[/math]

[math]a(t+1) = \delta (a(t), z(t))[/math]

[math]w(t) = \lambda (a(t))[/math]

В автоматах Мура выходные воздействия записаны на состояниях, а в автомате Мили — на переходах.

Содержание

Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС).

Основное преимущество использования автомата Мили заключается в возможности реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной комбинации от текущей входной комбинации [math]a_[/math] .

Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата, простота описания на языках описания аппаратуры HDL делает автомат Мура практически незаменимым.

Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании (например, для решения задачи об "Умном муравье" [1] ).

Рассмотрим автомат, регулирующий пешеходный переход по запросу пешеходов. Внешние события автомата — это события нажатия пешеходами кнопки-запроса на тротуаре и исчерпание тайм-аута. Автомат строится как автомат Мура, в котором выход — регулирование светофора и разрешающий сигнал на переход — это потенциальные сигналы, являющиеся функциями состояния.

Выход автомата в каждом состоянии определяется парой [math]\langle[/math] Светофор транспорта; светофор пешехода [math]\rangle[/math] . Например, в состоянии [math]S_1[/math] управляющий автомат устанавливает [math]\langle[/math] З; К [math]\rangle[/math] , то есть включёнными зеленый свет транспорту и красный — пешеходам. В состоянии [math]S_6[/math] установлен [math]\langle[/math] Ж, К; К [math]\rangle[/math] , то есть желтый и красный свет транспорту (приготовиться) и красный — пешеходам. В начальном состоянии [math]S_0[/math] разрешен проезд транспорту, а пешеходам движение запрещено.

В состояниях [math]S_4[/math] , [math]S_5[/math] при запрещающем сигнале транспорту зеленый сигнал пешеходам мигает каждые [math]t_0[/math] секунд в течение [math]t_2[/math] секунд. Запрос на переход принимается только в состоянии [math]S_0[/math] , в остальных состояниях он игнорируется. Задержки (тайм-ауты [math]t_0[/math] — [math]t_3[/math] ) устанавливаются в момент перехода автомата в данное состояние, по исчерпании тайм-аута автомат переходит в следующее состояние. В гиперсостоянии [math]Q[/math] , объединяющему пару состояний [math]S_4[/math] и [math]S_5[/math] , автомат находится ровно [math]t_2[/math] секунд: внутренние переходы не срывают тайм-аута.

Именно для этого удобно использовать гиперсостояние [math]Q[/math] .

В качестве примера применения автомата Мили рассмотрим автомат по продаже шоколадок стоимостью [math]20[/math] рублей, принимающий монеты номиналом в [math]5[/math] и [math]10[/math] рублей и возвращающий сдачу, если это необходимо.

Состояний автомата всего четыре: [math]0[/math] , [math]5[/math] , [math]10[/math] и [math]15[/math] рублей.

Выходных сигналов [math]W[/math] три: [math]W_[/math] — ничего не выдавать, [math]W_[/math] — выдать шоколадку и [math]0[/math] рублей сдачи, [math]W_[/math] — выдать шоколадку и [math]5[/math] рублей сдачи.

Например, если у человека есть одна монета номиналом в [math]10[/math] рублей и две монеты номиналом в [math]5[/math] рублей и монеты забрасываются в порядке [math]10[/math] , [math]5[/math] и [math]5[/math] рублей, то происходит следующее:

Автомат переходит в состояние [math]10[/math] р. и ничего не выдает;
Автомат переходит в состояние [math]15[/math] р. и ничего не выдает;
Автомат переходит в состояние [math]0[/math] р., выдает шоколадку и не возвращает сдачу.

Автомат Мили может быть задан таблицей переходов и таблицей выходов.

В таблице переходов АА Мили на пересечении столбца [math]a_[/math] и строки [math]z_[/math] записывается состояние [math]a_[/math] , которое есть функция [math]\delta[/math] от [math]a_[/math] и [math]z_[/math]

[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]=\delta (a_, z_)[/math]

В таблице выходов на пересечении столбца [math]a_[/math] и строки [math]z_[/math] записывается выходной сигнал, который есть функция [math]\lambda[/math] от [math]a_[/math] и [math]z_[/math] .

[math]a_[/math]
[math]z_[/math]	[math]w_[/math]	[math]=\lambda (a_, z_)[/math]

Пример: Задание автомата Мили табличным способом (автомат имеет два входных сигнала, два выходных сигнала и три состояния).

На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример).

В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала.

Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.

[math]\lambda[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]	[math]w_[/math]
[math]\delta[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]
[math]z_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]	[math]a_[/math]

На рисунке приведен граф автомата Мура на 5 состояний, имеющий 2 входных сигнала и 2 выходных сигнала.

Допустим, входное слово [math]\xi[/math] поступает на вход автомата буква за буквой.

Выходное слово [math]\omega[/math] называется реакцией автомата Мили на входное слово [math]\xi[/math] в состоянии [math]a_[/math] строится по таблице переходов и выходов).

Реакцию автомата на входное слово [math]\xi[/math] можно заменить обходом графа.

Выходное слово [math]\omega[/math] называется реакцией автомата Мура на входное слово [math]\xi[/math] в состоянии [math]a_[/math] .

В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.

Автомат Мура переходит в автомат Мили, если всем переходам в состояние поставить выходные воздействия этого состояния. После таких преобразований получим эквивалентный автомат Мили.

Однако, чтобы преобразовать автомат Мили в автомат Мура такой алгоритм не подходит, т.к. в одно состояние могут вести разные переходы. Но можно просто добавить новых состояний, устанавливая необходимые соответствия.

Далее будет приведено формальное доказательство факта эквивалентности с явным предъявлением конструкции.

Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура, и обратно — для каждого автомата Мура может быть построен эквивалентный ему автомат Мили.

Шестикомпонентным набором с индексом А будем обозначать автомат Мура, а с индексом В — автомат Мили.

Пусть задан автомат Мура.

Требуется перейти к автомату Мили

[math]S_ = (A_, Z_, W_, \delta _, \lambda _, a_[/math] ),

При переходе от автомата Мура к автомату Мили алфавиты состояний также совпадают, т.е. [math]A_ = A_[/math] .

Для определения соответствия между функциями переходов выходов автоматов Мура и Мили воспользуемся следующей вспомогательной таблицей.

Мура	Мили
[math]\delta _ (a_, z_) = a_[/math]	[math]\delta _ (a_, z_) = a_[/math]
[math]\lambda _(a_) = w_[/math]	[math]\lambda _ (a_, z_) = w_[/math]

При переходе от автомата Мура к автомату Мили функции переходов также совпадают, а для определения функции выходов выходные сигналы с вершин опускается на входные дуги.

Проделав такие преобразования мы должны доказать, что получили автомат Мили, эквивалентный автомату Мура, т.е. что реакции автоматов на одинаковые входные воздействия совпадают.

При таком переходе (Мура к Мили) число состояний совпадает.

Пусть задан автомат Мили [math]S_ = (A_, Z_, W_, \delta _, \lambda _, a_)[/math] .

Требуется перейти к автомату Мура

Для определения алфавита состояний, функций переходов и выходов автомата Мура воспользуемся следующей вспомогательной таблицей.

В данном случае [math]A_ \neq A_[/math] .

При таком переходе (Мили к Мура) каждому состоянию автомата Мили [math]a_[/math] ставится в соответствие множество всевозможных пар [math]a_ \rightarrow A_ = \<( a_, w_) | a_ = \delta(a_, z_), w_ = \lambda(a_, z_)\>[/math] , где [math]a_[/math] есть функция [math]\delta[/math] от состояния и входного сигнала, [math]w_[/math] функция [math]\lambda[/math] от состояния и входного сигнала.

Мура	Мили
	[math]A_ = \<(a_, w_), (a_, w_), (a_, w_)\>[/math]

[math]a_: A_ = \left \ < \begin (a_, w_) = b_ \\ (a_, w_) = b_ \\ \end \right.[/math]

[math]a_: A_ = \< (a_, w_) \> = b_[/math]

В качестве начального состояния результирующего автомата может быть выбрано любое состояние Мура, порожденное начальным состоянием автомата Мили, т.е. состояния [math]b_[/math] или [math]b_[/math] .

При определении функции переходов результирующего автомата Мура из всех состояний, порожденных одним состоянием автомата Мили, должны быть переходы под воздействием одинаковых входных сигналов.

Поскольку в автомате Мура выходной сигнал зависит только от состояния автомата, то в примере рядом с состояниями проставим соответствующие выходные сигналы.

И так если осуществить следующие преобразования, то получим:

Мили	Мура	Мили
[math]S_ \rightarrow[/math]	[math]S_ \rightarrow[/math]	[math]S_[/math]
3 состояния	5 состояний	5 состояний

Можно утверждать, что если [math]S_[/math] эквивалентно [math]S_[/math] , а [math]S_[/math] эквивалентно [math]S_[/math] , то [math]S_[/math] эквивалентно [math]S_[/math] (т.е. эквивалентность обладает свойством транзитивности).

Методы взаимной транспозиции автоматов Мили и Мура показывают, что при переходе от автомата Мили к автомату Мура число состояний принципиально не меняется. В то время как при обратном переходе в автомат Мура число состояний, как правило, увеличивается. Вследствие транзитивности отношения эквивалентности два автомата Мили, первый из которых получен из автомата Мура, так же будут эквивалентны, но у второго автомата число состояний будет больше. Таким образом эквивалентные между собой автоматы могут иметь различное число состояний. В связи с чем и возникает задача нахождения минимального автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.

Управляющие автоматы. Принцип микропрограммного управления

Введение

Любое устройство можно структурно разделить на управляющую часть и исполнительную. Управляющая часть (управляющий автомат, УА) отвечает за взаимодействие с внешней средой, а исполнительная (операционный автомат, ОА) – за выполнение каких-то действий.

На примере простой ёлочной гирлянды – лампочки – исполнительная часть, а микросхему, которая ими управляет – управляющая.

В простейшем случае, УА может представлять собой соединённые последовательно генератор низкой частоты (0.5-2 Гц), двоичный счётчик и дешифратор – рис. 1.

Рис. 1. Простейший УА

В этом случае, на выходе дешифратора будет появляться бегущая единица. Можно также подключить лампы непосредственно к выходам счётчика и т.д.

Из схемы понятны аспекты работы этого УУ:

Скорость переключения задаётся частотой генератора.
Порядок переключения входов определяется алгоритмами работы счётчика и дешифратора.

Недостатки тоже очевидны:

Для преодоления этих недостатков разрабатывают специальные УА.

Раздел 1. Управляющие автоматы с жёсткой логикой

Теория управляющих абстрактных и конечных автоматов – очень обширная наука, описывающая понятие автоматов, их поведение, формализацию, различные модели и пр. Здесь не будут рассматриваться все эти теоретические аспекты, рассмотрим лишь две практических варианта УА с жёсткой логикой.

Обобщённая структурная схема УА с жёсткой логикой имеет вид – рис. 2.

Рис. 2. Обобщённая структурная схема УА с жёсткой логикой

На рис. 2: X – множество входных сигналов автомата, Y – множество выходных сигналов, D – сигналы управления памятью, T – сигналы состояния.

УА состоит из 2-х функциональных блоков:

1. КС – комбинационная схема, формирующая выходные сигналы автомата и сигналы управления памятью.

2. Память автомата – просто набор триггеров (регистр). Кол-во триггеров n определяется кол-вом k требуемых состояний автомата. k определяется по-разному для разных автоматов. k равно ближайшему целому (в большую сторону) числу из значений выражения 2 n . Т.е. n=]log₂k[. Например, если у нас 5 состояний, то мы должны поставить 3 триггера (2 3 =8>5), а если 8, то 4 (2 4 =16>8).

Функционирование УА может задаваться графом переходов либо таблицами истинности. Можно описать его поведение и формулами: Y=ƒ1(X,T), D=ƒ2(X,T).

Если применяются D-триггеры, то можно использовать обычные регистры хранения вместо раздельных триггеров. Это может существенно упростить конечную схему.

УА с жёсткой логикой бывают 2-х видов – Мили и Мура.

1.1 Управляющий автомат Мили

Автомат Мили имеет структуру, на 100% совпадающую с рис. 2. И поведение его описывается теми же общими формулами – Y=ƒ1(X,T), D=ƒ2(X,T). Поэтому иногда говорят, что этот автомат генерирует (в смысле изменяет) выходные сигналы при переходах из одного состояния в другое. Здесь подчёркивается тот факт, что Y непосредственно зависит от X.

Рассмотрим синтез автомата Мили на примере.

Допустим, нам необходимо построить автомат, имеющий 2 входных сигнала (x1, x2) и 4 выходных (y1-y4):

Т.к. мы имеем 6 состояний, то нам понадобится 3 триггера. Используем для простоты D-триггеры. Построим теперь полную таблицу истинности автомата:

Пронумеровали все состояния автомата.
Закодировали все 6 состояний автомата сигналами текущего состояния триггеров Tx. Кодировать можно как угодно, единственное требование – все коды состояний д.б. уникальны. Т.е. не должно быть 2-х и более состояний с одинаковыми кодами.
Дополнили исходную таблицу сигналами Tx и сигналами Dx управления триггерами для того, чтобы автомат мог переходить из одного состояния в другое.

Также подразумевается, что состояния меняются по кругу. В разделе 1.2 показано, как реализовывается переход их одного состояния в 2 других в зависимости от разных входных сигналов.

КС должна формировать 7 сигналов: y1-y4 и D1-D3. Составим формулы для каждого сигнала:

По формулам можно нарисовать схему автомата. Мы этого делать не будем, здесь и так всё понятно.

1.2 Управляющий автомат Мура

Автомат Мура отличается от Мили тем, что он описывается формулами Y=ƒ1(T), D=ƒ2(X,T). Т.е. его выходные сигналы зависят только от состояния триггеров. Поэтому его КС фактически распадается на 2 независимые КС – рис. 3.

Рис. 3 Структура автомата Мура

КС1 реализует функцию D=ƒ2(X,T), а КС2 - Y=ƒ1(T).

Построим автомат Мура для того же примера:

Сразу отметим, что состояния 2 и 5 для Мура полностью эквивалентны, т.к. они генерируют идентичные наборы выходных сигналов. Поэтому состояние 5 можно выбросить и добавить дополнительный переход из состояния 2 по сигналам x1x2=01 в состояние 0. Это действие заменит выброшенное 5-е состояние в плане переходов.

Исключение эквивалентных состояний в общем случае может сократить число триггеров автомата.

ТИ для КС1 (таблица переходов автомата):

Правила кодирования состояний те же, что и автомате Мили.

Коды состояний 001, 100, 101 и сочетание входных сигналов x1x2=10 не используются, это можно учитывать при минимизации.

Обратите внимание, что в таблице 2 строки, соответствующие состоянию 2. Строка 2b соответствует выброшенному состоянию 5. Видно, что из неё автомат переходит в состояние 0.

Получим минимальные формулы сигналов D1, D2 и D3 КС1:

Карта Карно для сигнала X1 – рис 4.

Рис 4. Карта Карно для сигнала X1.

Из карты следует, что D1 = x1. Это же видно из ТИ.

Аналогично:
D2 = x1 + T2 + T1 T2 T3 x2
D3 = T1 T2 T3 x2 + T2 + T1 T2 T3 x1

ТИ для КС2 автомата:

Рис.5 Карты Карно для сигналов y1-y4

Из анализа формул видно, что y3 и y4 можно формировать, используя уже готовые y1 и y2. Это может дополнительно упростить КС2, но на практике такое решение снижает нагрузочную способность схемы на выходах y1 и y2.

Также, можно упростить реальную схему, если в каком-то смысле объединять схемы КС1 и КС2, формируя общие для них внутренние сигналы (например, T1 T3 ) и использовать их одновременно в обоих схемах. Конечно, обращая внимание на длину получаемых цепочек элементов и на их быстродействие (при увеличении длины цепочки падает её быстродействие).

Даже несмотря на то, что при рассмотрении автомата Мили мы не минимизировали его формулы, можно заметить, что автомат Мура проще уже потому, что для формирования Y не нужны сигналы X.

Раздел 2. Микропрограммное управление.

Основное достоинство рассмотренных УА с жёсткой логикой – их высокое быстродействие, определяемой быстродействием используемой элементной базы.

Однако есть и большие недостатки:

1. при необходимости внесения любых, даже небольших изменений алгоритма работы схему автомата надо полностью пересинтезировать.

2. при большом числе входных и выходных сигналов схема автомата сильно разрастается, а синтез становится сложным и тяжёлым занятием. Так, карты Карно уже при 5 аргументах (см. рис. 4) становятся трудночитаемыми и труднопонимаемыми, т.к. не все клетки, которые можно склеить и минимизировать, являются физически соседними. Неизбежным итогом этого может стать неполная минимизация и, как следствие излишне сложная и избыточная схема полученного автомата. На работоспособность схемы это, правда, не повлияет.

Второй недостаток особенно ярко проявляется при разработке различных вычислительных структур (часть 4), где есть много операционных узлов, для которых требуется очень много выходных сигналов и много состояний управляющего автомата.

В таких случаях используют принципиально другие УА – УА с микропрограммным управлением.

Структура такого УА изображена на рис. 6.

Рис. 6. Структура УА с микропрограммным управлением

Основа такого управляющего аппарата – ROM – ПЗУ. Каждая ячейка ПЗУ хранит микрокоманду (МК) – набор выходных сигналов Y для каждого состояния автомата и набор управляющих сигналов T для своего сугубо внутреннего устройства управления УУ.

В плане генерации выходных сигналов все микропрограммные автоматы идентичны автомату Мура – Y зависят только от состояния памяти автомата.

УА с микропрограммным управлением бывают 2-х типов – с естественной адресацией микрокоманд и с принудительной. В каждом случае структура УУ разная.

Рассмотрим эти 2 варианта.

2.1. Микропрограммный УА с принудительной адресацией

Структура УА с принудительной адресацией приведена на рис. 7.

Рис. 7. Структура УА с принудительной адресацией

На рис.7: MS1 – мультиплексор входных сигналов, MS2 – мультиплексор адреса микрокоманды, РАМК – регистр адреса микрокоманды, МПЗУ – ROM микропрограмм из рис. 6, РМК – регистр микрокоманд.

Разрядность MS2 и РАМК равна адресности ROM n=]log₂k[, где k – кол-во микрокоманд автомата. Например, если у нас 13 микрокоманд, то для них надо 13 ячеек ПЗУ, для адресации которых требуется n=]log₂13[=4 разряда адреса.

Разрядность ПЗУ и РМК равна кол-ву всех сигналов, которое должна выдавать ROM

Формат РМК идентичен формату микрокоманды: A0 и A1 – адрес следующей МК в ПЗУ, по которому перейдёт автомат, если выбранный управляющий сигнал равен 0 или 1 соответственно. Nx – код входного сигнала, проверяемого в текущей МК, ОЧ – операционная часть, содержит все выходные сигналы автомата.

ДШМО – дешифратор микрооперации. Его назначение – уменьшить разрядность ПЗУ и РАМК, в том случае, если все или часть входных сигналов Y являются унитарными и их можно закодировать таким образом, чтобы разрядность поля ОЧ была меньше кол-ва выходных сигналов. В общем случае он не нужен.

В реальности регистр РМК можно исключить, т.к. ПЗУ не меняют состояния своих выходов при неизменности адреса. Т.е., пока содержимое РАМК неизменно, то и на выходах ПЗУ будет неизменная информация.

Целесообразность использования ДШМО на практике зависит и от разрядности реальных ПЗУ, из которых будет строиться МПЗУ автомата.

Также, следует отметить, что промышленность не выпускает регистров с двумя входными шинами (РАМК на рис. 7). Поэтому, при необходимости такой узел м.б. заменён многоразрядным мультиплексором с двух направлений и обычным одновходовым регистром.

Рассмотрим подробно работу микропрограммного автомата с принудительной адресацией.

Работа автомата начинается с занесения в регистр адреса микрокоманд (РАМК) кода операции (по сути стартового адреса микрокоманды). В простейшем случае вместо занесения адреса можно использовать вход сброса регистра.

На время исполнения микрокоманда из RAM копируется в регистр микрокоманд РМК.

Далее мультиплексор MS1 передаёт на свой выход значение входного сигнала Xi, указанного полем Nx микрокоманды.

По сигналу с MS1 мультиплексор MS2 выбирает один из двух адресов A0/А1 и передаёт его на вход РАМК.

После этого всё повторяется.

Отметим, что на первый (с номером 0) вход мультиплексора MS1 заведен постоянный лог. 0. Это даёт возможность реализации МК с безусловным переходом по адресу A0 в тех МК, где не нужно проверять никакие входные сигналы. Вместо лог. 0 можно использовать лог. 1. Это повлияет только на то, что адресом перехода будет считаться содержимое поля A1, а не A0.

Наличие MS1 обусловливает следующую особенность автомата – любая МК может проверять (учитывать) только один сигнал Xi. Это обстоятельство относится к любым автоматам с микропрограммным управлением (не только с принудительной адресацией). Поэтому, если в какой-либо МК необходимо проверять несколько Xi, то такая МК разбивается на несколько, проверяющих требуемые Xi в произвольном порядке.

В ряде случаев, если входных сигналов не очень много, то, в принципе, можно заменить мультиплексор MS1 простой схемой совпадения кодов, а в МК вместо Nx записывать требуемое сочетание Xi.

В качестве примера рассмотрим микропрограммную реализацию того же автомата, который мы рассматривали для моделей Мили и Мура.

Функция переходов устанавливает зависимость внутреннего состояния автомата в следующий момент времени от состояния входа и внутреннего состояния в настоящий момент времени.

Функция выходов устанавливает зависимость состояния выхода автомата от состояния входа и внутреннего состояния автомата.

Различный характер этих зависимостей для различных автоматов позволяет выделить отдельные типы автоматов в классе синхронных конечных детерминированных автоматов.

Основными являются две модели: Мили и Мура.

Автомат Мили описывается следующими формулами:

1. внутреннее состояние автомата в следующий момент времени зависит от внутреннего состояния автомата в настоящий момент времени и входного сигнала в настоящий момент времени.

2. выходной сигнал автомата в настоящий момент времени зависит от входного сигнала в настоящий момент времени и внутреннего состояния автомата в настоящий момент времени.

Понятие состояния автомата в момент времени t определяется внутренним состоянием автомата и состоянием входа автомата в тот же момент времени.

Автоматы, для которых функции переходов и функции выходов определены на всех парах , называются полностью определенными или полными автоматами. Соответственно, автоматы, для которых функции переходов или функции выходов определены не на всех парах , называются недоопределенными (не полностью определенными) автоматами. Состояние М(t) автомата недоопределенного на соответствующей паре , называется неиспользованным состоянием автомата. Если на каком-либо определенном состоянии автомата не определена только функция выходов, то говорят, что ему соответствует безразличное состояние выхода.

Автомат Мура

Для автомата Мура функции переходов и выходов выглядят следующим образом:

Функция выходов для автомата Мура определяется внутренним состоянием автомата.

Для асинхронного автомата.

Поведение определяется следующим уравнением:

В асинхронном автомате изменение состояния входа вызывает переход в следующее внутреннее состояние, т.е. внутреннее состояние автомата зависит от состояния входа в этот же момент времени, соответственно состояние выхода автомата зависит от состояния его входа.

Функционирование или поведение автомата при заданных множествах () и начальном внутреннем состоянии x₀ полностью детерминировано, и определяется функциями переходов и выходов -

Основными являются две модели: Мили и Мура.

Автомат Мили описывается следующими формулами:

Автомат Мура

Для автомата Мура функции переходов и выходов выглядят следующим образом:

Функция выходов для автомата Мура определяется внутренним состоянием автомата.

Для асинхронного автомата.

Поведение определяется следующим уравнением:

Читайте также: