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

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

Кодирование любого объекта из общего числа объектов, равному 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₃). Возможны два случая:

  Рис. 3.19. а) гонки не критические, б) гонки критические.  

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

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

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

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

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

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

Осуществим кодирование символов алфавитов абстрактных автоматов S₁ и S₂ из раздела 3.2.2. Они заданы на входном x={x₁,x₂,x₃,x₄} и выходном y={y₁,y₂,y₃} алфавитах. Кроме того автомат Мура S₁ определён на алфавите состояний A₁={a₁,a₂,a₃,a₄}, а автомат Мили S₂ на алфавите A₂={a₁,a₂,a₃}.

Определим разрядность кодов символов:

1. Алфавита состояний для S₁: n_Q= ] log₂n_a [ =log₂4=2 (автомат Мура).

Возможно n_a!=4!=24 способов кодирования

Для S₂: n_Q= ] log₂n_a [ = ] log₂3 [ =2 (автомат Мили).

Возможно =4*3*2=24 способов кодирования.

2. Входного алфавита

n_C= ] log₂n_X [ =log₂4=2

Возможно n_X!=4!=24 вариантов кодирования.

3. Выходного алфавита

n_Z= ] log2n_Y [ = ] log₂3 [ =2

Возможно =4*3*2=24 вариантов кодирования.

  Рис.3.20 Рис.3.21 Рис.3.22

Рис. 3.20. - таблица кодирования символов входного алфавита, рис. 3.21. - таблица кодирования символов выходного алфавита, рис. 3.22. - таблица кодирования символов алфавита состояний.

Для автомата S₂ таблица кодирования символов алфавита состояний A₂ включает только первые три строки таблицы на рис. 3.22. Структурные автоматы имеют n_C=2 входов, n_Z=2 выходов и реализуются на n_Q=2 элементарных автоматах.

Дата добавления: 2014-10-15