Теория автоматов. 7.Кодирование состояний и сложность логической схемы

Гонки в ЦА:

Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания, или гонки. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное законом функционирования. Гонки в автомате связаны с разбросом во временных параметрах сигналов, проходящих через логические и запоминающие элементы, и имеют место в любой реальной логической схеме. Для обеспечения заданного закона функционирования автомата необходимо исключить возможность появления критических гонок.

Аппаратные методы устранения гонок:

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

Использование Двойной (двухступенчатой) памяти: Заключается в разделении во времени процессов выработки сигналов возбуждения и процесса переключения состояний.

Логические методы:

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

При соседнем кодировании состояний автомата условие отсутствия гонок (и состязаний вообще) всегда выполнено.

Требования к графу автомата:

1. В графе автомата не существует циклов с нечетным числом вершин.

2. Два соседних состояния второго порядка (путь между ними состоит из двух ребер, независимо от направления) не должны иметь более двух состояний, лежащих между ними.

Развязывание пар переходов:

Две пары (α, β) и (γ, δ) бинарных кодов наз. развязными, если существует координата №j такая, что αi = βi, γi = δi и αi ≠ γi.

В автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (a_m, a_s) и (a_k, a_l) (таких, что a_s ≠ a_l), происходящих под

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

Качество кодирования: k = W/p, где

W = число состояний элементов памяти на всех переходах

p = число переходов (без учета петель)

При соседнем кодировании K=1.

Если I – длина кода, то 1 ≤ k ≤ I (так как 1 ≤ Wms ≤ I и в сумме для расчета W всего p слагаемых).