Синтез цифровых автоматов. Захаров Н.Г - 23 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

22
δ : Q x X → Q* λ : Q x X → Y*
q
1
q
2
q
3
q
1
q
2
q
3
x
1
q
2
q
3
q
2
x
1
y
1
y
3
y
3
x
2
q
3
q
2
q
1
x
2
y
2
y
1
y
1
а) б)
Рис. 1.5. Таблицы переходов (а) и выходов (б) автомата А1
Автомат, имея один вход и один выход, работает в дискретном времени, при-
нимающем значения t = 1, 2, 3, ... На вход автомата поступают входные сигналы x
f
(например, сигналы x
1
и x
2
). В каждый момент t автомат находится в некотором со-
стоянии q(t), начиная с начального состояния q
1
.
На пересечении столбца q
m
и строки x
f
в таблице переходов ставится состояние
q
s
= δ (q
m
, x
f
), в которое автомат переходит из состояния q
m
под действием сигнала x
f
,
а в таблице выходов – соответствующий этому переходу выходной сигнал
y
g
= λ (q
m
, x
f
).
Иногда при задании автоматов Мили используют одну совмещенную таблицу
переходов и выходов, в которой на пересечении столбца q
m
и строки x
f
записываются
в виде q
s
/ y
g
следующее состояние и выдаваемый выходной сигнал. На рис. 1.6 пред-
ставлена совмещенная таблица автомата А1.
δ : Q x X → Q ; λ : Q x X → Y
q
1
q
2
q
3
x
1
q
2
/ y
1
q
3
/ y
3
q
2
/ y
3
x
2
q
3
/ y
2
q
2
/ y
1
q
1
/ y
1
Рис. 1.6. Совмещенная таблица автомата А1
Так как в автомате Мура выходной сигнал зависит только от внутреннего со-
стояния и не зависит от входного сигнала, то он задается одной отмеченной таблицей
переходов, в которой каждому ее столбцу приписан, кроме состояния q
m
еще и вы-
ходной сигнал y
g
= λ (q
m
), соответствующий этому состоянию. Пример табличного
описания автомата Мура А2 (рис. 1.7).
Для частичных автоматов, у которых функции δ или λ определены не для всех
пар (q
m
, x
f
)∈Q x X, на месте неопределенных состояний и выходных сигналов ставит-
ся прочерк.
δ : Q x X → Q; λ : Q x X → Y
y
1
y
1
y
3
y
2
y
3
q
1
q
2
q
3
q
4
q
5
x
1
q
2
q
5
q
5
q
3
q
3
x
2
q
4
q
2
q
2
q
1
q
1
Рис. 1.7. Таблица переходов автомата Мура
Часто автомат задают с помощью графа автомата. Граф автомата – ориентиро-
ванный граф, вершины которого соответствуют состояниям, а дуги – переходам меж-

Страницы