Этап 3. Кодирование состояний автомата.

1). Определяем разрядность кода L, то есть минимально необходимое количество элементарных автоматов или, иначе говоря, разрядность памяти автомата. Так как система счисления двоичная, то

где |S| – мощность множества состояний, ]…[ – ближайшее целое число сверху.

В данном примере |S| = 5, получаем L = 3. Таким образом, линейка памяти автомата трехразрядная, то есть память строится на трех триггерах.

2). Определяем двоичный код каждого состояния автомата. Существует множество алгоритмов кодирования состояний, например, противогоночное, экономичное, соседнее кодирование и ряд других. В случае противогоночного кодирования стремятся к переключению в каждый дискретный момент времени только одного разряда, чтобы избежать ложных срабатываний элементов памяти из-за гонок (критических состязаний) в комбинационной схеме. Этот способ актуален для асинхронных схем. Обоснование эффективности противогоночного кодирования относится к давним разработкам – периода элементной базы малой степени интеграции. В настоящее время, когда в СБИС время срабатывания триггера мало отличается от времени задержки распространения сигнала в логическом элементе и б о льшее значение имеют задержки в линиях связи (слоях металлизации на кристалле), значительно выгоднее проектировать синхронный автомат, не заботясь о противогоночном кодировании, требующем дополнительных аппаратных затрат.

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

Шаг 1. Для состояния, вершине которого на графе инцидентно наибольшее количество входящих дуг, выбираем нулевой код.

Шаг 2 – итерационный. Находим состояние, наиболее связанное с ранее закодированными. Из всех свободных кодовых комбинаций выбираем ту, для которой сумма кодовых расстояний*) с уже существующими кодами состояний, связанных с рассматриваемым, будет минимальной. Кратность связей учитываем введением поправочного коэффициента k_св. Очевидно, число итераций шага 2 равно |S| – 1.

Рассмотрим применение сформулированного алгоритма к кодированию состояний данного конкретного автомата.

Шаг 1. Наибольшее количество входящих дуг на графе переходов инцидентно вершине s₁. (полустепени захода: p⁺(s₁) = 4, p⁺(s₃) = 3, p⁺(s₂) = p⁺(s₄) = p⁺(s₅) = 1). Состоянию s₁ усваиваем нулевой код:

s₁ = 000.

Шаг 2. Итерация 2.1. Вершины s₂, s₃, s₄, s₅ связаны с вершиной s₁ каждое одной дугой. Не имеет значения, какое из состояний предпочесть. Выбираем s₂. Очевидно, код s₂ должен содержать единицу в любом разряде, обеспечивая d₂₁ = 1. Пусть

s₂ = 001.

Итерация 2.2. С подмножеством вершин {s₁, s₂} наиболее связана вершина s₃ (тремя дугами: s₁®s₃, s₂®s₃, s₃®s₂); вершины s₄ и s₅ связаны с {s₁, s₂} одной дугой каждая. Следовательно, очередным кодируемым состоянием должно быть s₃. Рассчитываем кодовые расстояния:

Свободные комбинации	d31 + 2d32
	1 + 2*2 = 5
	2 + 2*1 = 4
	1 + 2*2 = 5
	2 + 2*1 = 4
	2 + 2*3 = 8
	3 + 2*2 = 7

Поскольку вершины s₂ и s₃ связывают две дуги, d₃₂ входит в сумму с поправочным коэффициентом k_св = 2. Наименьшим значением суммы кодовых расстояний обладают комбинации 011 и 101. Предпочтение можно отдать любой из них. Пусть

s₃ = 011.

Итерация 2.3. Подмножество закодированых вершин: {s₁, s₂, s₃}. Число связей для s₄ – две, для s₅ – две; выбор s₄ или s₅ равновероятный. Кодируем состояние s₄:

Свободные комбинации	d41 + d43
	1 + 1 = 2
	1 + 3 = 4
	2 + 2 = 4
	2 + 2 = 4
	3 + 1 = 4

Наименьшее значение суммы кодовых расстояний соответствует комбинации 010. Итак,

s₄ = 010.

Итерация 2.4. Кодируем последнее оставшееся незакодированным состояние s₅:

Свободные комбинации	d51 + d53+ d54
	1 + 3 + 2 = 6
	2 + 2 + 3 = 7
	2 + 2 + 1 = 5
	3 + 1 +2 = 6

Имеем: s₅ = 110.

Сведем полученные коды состояний автомата в общую таблицу (рис. 9.2). Разряды кода обозначим Q₂Q₁Q₀, где Q₀ – младший разряд.

Рис. 9.2. Результат этапа кодирования состояний КА