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

UptoLike

ВУЗ: 

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

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

Рубрика: 

66
Четвертый случай – операция суперпозиции автоматов. Рассматриваются два
автомата А и В, при этом у автомата А имеется m входных и n выходных узлов, а у
автомата В – n входных и р выходных узлов. Суперпозиция этих автоматов заключа-
ется в построении системы, состоящей из автоматов А и В, m внешних входных и р
внешних выходных узлов посредством соединения i-го внешнего входного узла с i-м
входным узлом автомата А (i = 1, ..., m), j-го выходного узла автомата А с j-м вход-
ным узлом автомата В (j = 1, ..., n) и k-го выходного узла автомата В с k-м внешним
выходным узлом (k = 1, ..., p).
Пятый случай – операция объединения автоматов. Пусть имеется любое ко-
нечное множество автоматов А
1
, ..., А
р
. Каждый автомат А
i
имеет m
i
входных и n
i
вы-
ходных узлов (i = 1, ..., p). Строится система, состоящая из данных автоматов, у кото-
рых m
1
+ m
2
+ ... + m
p
внешних входных узлов и n
1
+ n
2
+ ... + n
p
внешних выходных
узлов. При этом каждый из внешних входных узлов соединяется в точности с одним
из входных узлов автоматов А
1
, ..., А
р
. Точно такое же отождествление, по принципу
взаимно однозначного соответствия, осуществляется между выходными узлами дан-
ных автоматов и внешними выходными узлами.
В дальнейшем будут рассматриваться в основном правильные схемы. Однако
правильные схемы не всегда исчерпывают всех корректно построенных схем и это
позволяет в ряде случаев пользоваться схемами, не принадлежащими к числу пра-
вильных. Отсюда следуют два важнейших случая.
Во-первых, очевидно, что в случае наличия в структурном алфавите естествен-
ного нулевого сигнала можно не соблюдать условие правильности 1.1 и, тем не менее,
получать корректно построенные схемы. Условие 1.1 в таких схемах будет выполнен-
ным после введения так называемого нулевого автомата.
Нулевым автоматом называют автомат Мили с одним входным и одним вы-
ходным узлом, отличающийся тем, что на его выходном узле при любом сигнале на
входном узле появляется нулевой сигнал.
При наличии в схеме узлов, для которых условие 1.1 не выполняется, можно,
не изменяя условий работы схемы, вставить в нее добавочные цепи из нулевых авто-
матов, соединяющие задающие узлы со всеми такими узлами. После такой операции
условие 1.1 будет выполнено.
Во-вторых, в случае, когда имеется естественное разделение элементарных
сигналов, можно не соблюдать условие правильности 1.2 и, тем не менее, получать
корректно построенные схемы. Однако в этом случае необходимо интерпретировать
указанные схемы, чтобы выполнялось условие 1.2.
Этой цели можно достичь, введением понятия разделяющего автомата Мили,
или просто разделения. В разделяющем автомате Мили на единственный выходной
узел автомата передается всегда самый большой элементарный сигнал из числа вход-
ных сигналов, поданных в то же самое время на его входные узлы. Если в схеме с ес-
тественным разделением сигналов имеется соединение какого-нибудь узла с несколь-
кими внешними входными или внутренними выходными узлами α
1
, ..., α
k
, то можно
считать этот узел соединенным с выходным узлом разделяющего автомата, входные
узлы которого соединены с узлами α
1
, ..., α
k
. При таком дополнении схемы ее работа
не изменится, но условие 1.2 будет уже соблюдаться.
Прежде чем сформулировать условие 1.5 рассмотрим состояния автомата А,
которые могут быть получены в результате композиции некоторых автоматов
А
1
,...,А
k
. Состояниями такого автомата А можно считать упорядоченные наборы

Страницы