Проблемы возникающие при кодировании

Кодирование любого объекта из общего числа объектов, равному n, может быть выполнено:

способами, где . Если n=2^k, то число вариантов кодирования в точности равно n! Выбирается такой вариант кодирования, который обеспечивал бы минимальные аппаратные затраты. Эффективных алгоритмов выбора оптимальных вариантов кодирования не существует, и задача решается методом перебора.

При кодировании состояний, помимо проблемы оптимального кодирования в указанном выше смысле, необходимо решать задачу борьбы с гонками, или состязаниями. Вследствие разброса времени перехода отдельных ЭА возникают промежуточные состояния, которые могут привести к неправильной работе автомата.

Например, пусть для ЭА Q₁,Q₂,Q₃ имеем переход из a_k=<1,0,0> в a_m=<1,1,1>.

При переходе может возникнуть состояние <1,1,0>, если Q₂ быстрее изменяет своё состояние, чем Q₃ (гонки выигрывает Q₂) или <1,0,1>, если Q₃ быстрее изменяет своё состояние, чем Q₂ (гонки выигрывает Q₃). Возможны два случая:

В случае «а» при воздействии входного сигнала x_i достигается верное состояние a_m, в случае «б» вместо состояния a_m переходим в другое состояние a_l. В первом, случае автомат функционирует правильно, и гонки являются некритическими, во втором неправильно - гонки являются критическими.

Для борьбы с состязаниями используют различные методы:

1) Противогоночное кодирование состояний автомата. Оно приводит к увеличению числа состояний автомата. Частным случаем такого кодирования является соседнее кодирование, при котором на каждом переходе изменяется состояние только одного ЭА: 101à111à110à100à…

2) Тактирование входных сигналов С_i ÞtC_i. В этом случае предъявляются жёсткие условия к длительности тактирующего сигнала t, которая должна быть не больше времени задержки в цепи обратной связи.

3) Использование двойной памяти на MS – триггерах и им подобных.

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

Дата добавления: 2014-01-05