Другие предметы \ Проектирование цифровых устройств

Устройство синхронизации сигналов. Проект конечного автомата, осуществляющего синхронизацию информационных импульсов, поступающих в произвольные моменты времени, страница 5

Для проверки правильности кодирования составим таблицу соседства состояний автомата (табл. 12).

Таблица 12. Таблица соседства состояний автомата А

Состояние	Код состояния	Соседние состояния	Коды соседних состояний
q₀	000	q₁	001
		q₄	100
		q₅	010
q₁	001	q₀	000
q₁	001	q₆	101
q₂	111	q₃	110
q₂	111	q₆	101
q₃	110	q₂	111
		q₄	100
		q₅	010
q₄	100	q₀	000
q₄	100	q₃	110
q₅	010	q₀	000
q₅	010	q₃	110
q₆	101	q₁	001
q₆	101	q₂	111

По табл. 12 видно, что противогоночное кодирование выполнено верно.

Кодирование состояний автомата с устранением критических состязаний

Данный вид кодирования основывается на следующей теореме: в автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (q_α, q_β) и (q_γ, q_δ), где q_β≠ q_δ, происходящим под действием одного и того же входного сигнала, соответствующие пары кодов состояний развязаны.

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

Таблица 13. Множество переходов автомата А

M₀ (по X₀)

M₁ (по X₁)

M₂ (по X₂)

(q₀, q₀)

(q₁, q₁)

(q₂, q₃)

(q₃, q₃)

(q₄, q₀)

(q₅, q₃)

(q₀, q₀)

(q₁, q₂)

(q₂, q₂)

(q₃, q₀)

(q₄, q₀)

(q₅, q₅)

(q₀, q₁)

(q₁, q₁)

(q₂, q₃)

(q₃, q₃)

(q₄, q₄)

(q₅, q₃)

(q₀, q₅)

(q₁, q₂)

(q₂, q₂)

(q₃, q₄)

(q₄, q₄)

(q₅, q₅)

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

Таблица 14. Пары переходов автомата А, подлежащие развязыванию

M₀ (по X₀)

M₁ (по X₁)

M₂ (по X₂)

(q₀, q₀), (q₁, q₁)

(q₀, q₀), (q₂, q₃)

(q₀, q₀), (q₃, q₃)

(q₀, q₀), (q₅, q₃)

(q₁, q₁), (q₂, q₃)

(q₁, q₁), (q₃, q₃)

(q₁, q₁), (q₄, q₀)

(q₁, q₁), (q₅, q₃)

(q₂, q₃), (q₄, q₀)

(q₃, q₃), (q₄, q₀)

(q₄, q₀), (q₅, q₃)

(q₀, q₀), (q₁, q₂)

(q₀, q₀), (q₂, q₂)

(q₀, q₀), (q₅, q₅)

(q₁, q₂), (q₃, q₀)

(q₁, q₂), (q₄, q₀)

(q₁, q₂), (q₅, q₅)

(q₂, q₂), (q₃, q₀)

(q₂, q₂), (q₄, q₀)

(q₂, q₂), (q₅, q₅)

(q₃, q₀), (q₅, q₅)

(q₄, q₀), (q₅, q₅)

(q₀, q₁), (q₂, q₃)

(q₀, q₁), (q₃, q₃)

(q₀, q₁), (q₄, q₄)

(q₀, q₁), (q₅, q₃)

(q₁, q₁), (q₂, q₃)

(q₁, q₁), (q₃, q₃)

(q₁, q₁), (q₄, q₄)

(q₁, q₁), (q₅, q₃)

(q₂, q₃), (q₄, q₄)

(q₃, q₃), (q₄, q₄)

(q₄, q₄), (q₅, q₃)

(q₀, q₅), (q₁, q₂)

(q₀, q₅), (q₂, q₂)

(q₀, q₅), (q₃, q₄)

(q₀, q₅), (q₄, q₄)

(q₁, q₂), (q₃, q₄)

(q₁, q₂), (q₄, q₄)

(q₁, q₂), (q₅, q₅)

(q₂, q₂), (q₃, q₄)

(q₂, q₂), (q₄, q₄)

(q₂, q₂), (q₅, q₅)

(q₃, q₄), (q₅, q₅)

(q₄, q₄), (q₅, q₅)

Проведем сокращение таблицы пар переходов, исключив пары переходов, которые автоматически развязываются при развязывании пары (q_α, q_β), (q_γ, q_δ). При этот получим сокращенную таблицу пар переходов автомата А, подлежащих развязыванию (табл. 15).

Таблица 15. Пары переходов автомата А, подлежащие развязыванию

M₀ (по X₀)

M₁ (по X₁)

M₂ (по X₂)

(q₂, q₃), (q₄, q₀)

(q₄, q₀), (q₅, q₃)

(q₁, q₂), (q₃, q₀)

(q₁, q₂), (q₄, q₀)

(q₃, q₀), (q₅, q₅)

(q₀, q₁), (q₂, q₃)

(q₀, q₁), (q₄, q₄)

(q₀, q₁), (q₅, q₃)

(q₀, q₅), (q₁, q₂)

(q₀, q₅), (q₃, q₄)

(q₁, q₂), (q₃, q₄)

1 2 3 4 5 6 7 8 9 10

Скачать файл