Размещение состояний автомата

При размещении состояний автомата (иначе – кодирование) определяется выбор способа размещения, который зависит от типа реализуемого автомата (асинхронный или синхронный).

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

Длина кода измеряется числом двоичных переменных, набор значений которых образует кодовую комбинацию из нулей и единиц. Наименьшее число переменных, необходимое для кодирования синхронного автомата с N состояниями, определяется как n=]log₂N[, где ]K[ - ближайшее сверху к К целое число. Для рассматриваемого примера N=12(r₀ ÷ r_n) и n=]log₂12[=4.

Один из способов кодирования состояний синхронного автомата состоит в произвольном назначении кодовых наборов. Рассмотрим данное кодирование для нашего случая.

Состоянию r_i необходимо поставить в соответствие одну из вершин 4–мерного куба с десятичным номером i, который определяется по значениям двоичных координат z₁, z₂, z₃ и z₄ этой вершины в соответствии с формулой i= z₁×2⁰+ z₂×2¹+ z₃×2²+ z₄×2³.

В этом случае вершине с координатами 0000 соответствует состояние r₀, вершине с координатами 0001 – r₁ и так далее (рис.4). Всего в рассматриваемом случае 12 состояний, поэтому 4 вершины куба из 16 остаются неиспользованными. При таком варианте кодирования переход автомата из одного состояния в другое в общем случае может сопровождаться изменениями значений нескольких переменных. Так, при переходе r₄- r₁₁ (0100 – 1011), возникающем при входном сигнале x₀, изменяют свои значения все четыре внутренних кодирующих переменных z₁ ÷ z₄.

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

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

Известно, что такой способ кодирования избыточен и может потребовать (2]log₂N[- 1) кодирующих переменных при N состояниях автомата. В рассматриваемом случае используется код минимальной длины, n=]log₂N[, поэтому на некотором шаге кодирования может оказаться, что все соседние коды уже заняты, что потребует увеличения расстояния по Хеммингу на следующем шаге кодирования.

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

На рис.5 приведен один из возможных вариантов размещения, где состояние «Ошибка» (r₁₂) не показано, т.к. оно не удовлетворяет принятому критерию размещения из–за того, что в это состояние производятся переходы из всех других состояний, поэтому кодирование состояния «Ошибка» выполняется позднее.

Размещение начнем с состояния r₄ (как имеющего наибольшее количество входящих и исходящих дуг), которое поместим в вершину 0000 куба. Состояние r₁₁, связанное дугой x₀ с состоянием r₄, поместим в вершину 0010, удаленную от r₄ на расстоянии 1. В вершинах 0001 и 0100 разместим состояния r₂ и r₃, также удаленные от r₄ на расстояние 1. Пометим соответствующие этим переходам дуги символами x₁ и x₄. Естественным будет также размещение состояния r₅ в вершине 0011, это состояние связано дугами x₆ и x₇ с состояниями r₀ и r₁₁, причем эти дуги расположены на ребрах куба и имеют минимальную длину, равную 1.

Расстояния, соответствующие переходам r₀- r₄ (по дуге x₂) и r₄-r₅ (по дуге x₁), имеют соответственно длину 3 и 2.

Рис.4

Рис. 5

Состояние r₀ связано дугой x₅ с состоянием r₆. Разместим состояние r₆ в вершине 1111, отстоящей от r₀ также на расстояние 1. Продолжая операцию размещения состояний исходного орграфа, получим окончательно картинку, представленную на рис.5.

Проанализируем полученное размещение. Из 18 возможных переходов 15 являются соседними и имеют расстояние 1, два перехода имеют расстояние 2 и один – 3. Общее суммарное расстояние – 22. Возможны и другие варианты размещения состояний автомата с той же величиной суммарного расстояния по Хеммингу, однако существенного значения это не имеет.