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

Кодирование любого объекта из общего числа объектов, равному 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 – триггерах и им подобных.

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

Пример 3.2.

Осуществим кодирование символов алфавитов абстрактных автоматов 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 элементарных автоматах.

Получение кодированной таблицы переходов и выходов.

Исходными данными для построения кодированной таблицы переходов и выходов являются:

1) Таблицы переходов и выходов абстрактного автомата.

2) Таблицы кодирования символов алфавита абстрактного автомата.

Таблица кодирования получается путём подстановки двоичных кодов символов в таблицу переходов и выходов абстрактного автомата.

Пример 3.3

Для описанных выше автоматов S₁ и S₂ кодированные таблицы переходов и выходов изображены на рис.3.23,3.24. Они получаются путём кодирования таблиц на рис. 3.8 и 3.9. с использованием таблиц на рис. 3.20.,3.21. и 3.22.

Кодированная таблица автомата Мура. Кодированная таблица автомата Мили. Рис. 3.23. Рис. 3.24.

Таблицы задают переходы элементарных автоматов. По кодированной таблице переходов находят функции внешних переходов элементарных автоматов, а по кодированной таблице выходов - функции выходов.