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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
ду ними. Две вершины графа автомата q
m
и q
s
(исходное состояние и состояние пере-
хода) соединяются дугой, направленной от q
m
к q
s
, если в автомате имеется переход
из q
m
в q
s
, т. е. если q
s
= δ (q
m
, x
f
) при некотором x
f
∈Х. Данной дуге (q
m
, q
s
) припи-
сывается входной сигнал x
f
и выходной сигнал y
g
= λ (q
m
, x
f
). При этом выходной
сигнал y
g
записывается внутри вершины q
m
или рядом с ней. На рис. 1.8 и 1.9 приве-
дены графы автоматов А1 и А2, описанных ранее табличным способом.
Рис. 1.8. Граф автомата А1 Рис. 1.9. Граф автомата А2
Любой автомат может быть задан с помощью графа, но не всякий граф в алфа-
витах Q, X, Y задает автомат. В графе автомата не должно существовать двух дуг с
одинаковыми входными сигналами, выходящих из одной и той же вершины (условие
однозначности).
Иногда применяется способ задания автомата с помощью матрицы переходов и
выходов, которая представляет собой таблицу с двумя входами. Строки и столбцы
таблицы отмечены состояниями. Если существует переход из состояния q
m
под дей-
ствием входного сигнала x
f
в состояние q
s
, с выдачей выходного сигнала y
i,
то на пе-
ресечении строки q
m
и столбца q
s
записывается пара x
f
/ y
i
.
Для автомата Мура используется матрица, столбцы которой отмечены выход-
ными сигналами y
i
, а на пересечении ее строк и столбцов указываются только вход-
ные сигналы x
f
.
Ниже приведены матрицы переходов и выходов для рассмотренных ранее ав-
томатов S1 и S2 (рис. 1.10).
q
1
q
2
q
3
y
1
y
1
y
3
y
2
y
3
q
1
x
1
/y
1
x
2
/y
2
q
1
q
2
q
3
q
4
q
5
q
2
x
2
/y
1
x
1
/y
3
q
1
x
1
x
2
q
3
x
2
/y
1
x
1
/y
3
q
2
x
2
x
1
q
3
x
2
x
1
q
4
x
2
x
1
q
5
x
2
x
1
а б
Рис. 1.10. Матрицы переходов и выходов автоматов А1 (а) и А2 (б)
Рассмотрим пример составления графа автомата. Пусть задано некоторое уст-
ройство в виде таблицы (табл. 1) и граф переходов к ней (рис. 1.11).
q
3
q
1
q
2
x
1
y
1
x
2
y
1
x
2
y
2
x
1
x
1
x
2
y
1
y
3
y
3
q
1
q
3
q
5
q
4
q
2
y
1
y
1
x
1
x
2
x
1
x
2
x
2
x
2
x
1
x
1
x
1
x
2
y
3
y
2
y
3

Страницы