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

UptoLike

ВУЗ: 

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

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

Рубрика: 

64
нается любым из узлов а или b и кончается другим из этих узлов. Во втором случае
цепь начинается и кончается узлом а. Циклические цепи, состоящие из пустого мно-
жества автоматов, называются тривиальными и в дальнейшем не рассматриваются.
Покажем на примере, каким образом может возникнуть неоднозначность в пет-
ле. Предположим, что каждый из трех автоматов Мили, входящих в цепь (рис. 4.2),
обладает следующим свойством: структурный алфавит состоит из двух элементарных
сигналов 0 и 1, и каждый автомат цепи переводит входной сигнал 0 в выходной сиг-
нал 1, а входной сигнал 1 – в выходной сигнал 0; при этом входной и соответствую-
щий ему выходной сигналы возникают в один и тот же момент времени.
оо
о3
12
Рис. 4.2. Некорректно построенная цепь
Легко видеть, что при таком определении сигналов во всех входящих в цепь
узлах будут возникать противоречия. Действительно, полагая, что если в какой-то
момент времени в узле 1 сигнал 0, то в узле 2 в тот же самый момент времени будет
сигнал 1, а в узле 3 – сигнал 0, следовательно, в узле 1 должен быть сигнал 1, хотя
был сигнал 0, что и приводит к противоречию.
Петли, подобные только что рассмотренной, считают некорректно построен-
ными. Некорректность такого рода не будет иметь места, если хотя бы один из вхо-
дящих в петлю автоматов Мили заменить автоматом Мура. Действительно, автомат
Мура реагирует на тот или иной входной сигнал выходным сигналом, возникающим
на один элементарный промежуток времени позже, чем вызвавший его появление
входной сигнал. Поэтому в данном примере сигнал 0, переданный в момент времени
t в узел 1, вызвал бы в результате передачи его вдоль петли появление в этом узле
сигнала 1 не в момент времени t, а в момент времени t + 1.
Рассмотрим, как построить схемы с соблюдением первого условия корректности.
Условие соблюдается автоматически, если в структурный алфавит включить
естественный нулевой сигнал. В противном случае для соблюдения этого условия не-
обходимо при проведении операции отождествления узлов выполнить определенные
требования.
Прежде всего заметим, что все внешние входные узлы и все внутренние узлы,
являющиеся выходными узлами автоматов Мура, по определению, получают элемен-
тарные сигналы во все моменты автоматного времени. Назовем все эти узлы задаю-
щими узлами. Сформулируем условие, обеспечивающее передачу элементарных сиг-
налов от задающих узлов во все узлы автомата в каждый момент автоматного време-
ни. Для этой цели учтем, что выходные сигналы у автоматов Мили, по определению,
возникают одновременно с воздействием сигналов на все его входные узлы. Соответ-
ствующие условия можно сформулируем следующим образом:
1.1. Для любого узла схемы должна иметься цепь, состоящая из некоторого
множества (может быть пустого) автоматов Мили, начинающаяся каким-либо за-
дающим узлом и кончающаяся данным узлом. Назовем это условие первым условием
правильности построения схемы.

Страницы