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

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

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

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

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

Состоянию ri необходимо поставить в соответствие одну из вершин 4–мерного куба с десятичным номером i, который определяется по значениям двоичных координат z1, z2, z3 и z4 этой вершины в соответствии с формулой i= z1×20+ z2×21+ z3×22+ z4×23.

В этом случае вершине с координатами 0000 соответствует состояние r0, вершине с координатами 0001 – r1 и так далее (рис.4). Всего в рассматриваемом случае 12 состояний, поэтому 4 вершины куба из 16 остаются неиспользованными. При таком варианте кодирования переход автомата из одного состояния в другое в общем случае может сопровождаться изменениями значений нескольких переменных. Так, при переходе r4- r11 (0100 – 1011), возникающем при входном сигнале x0, изменяют свои значения все четыре внутренних кодирующих переменных z1 ÷ z4.

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

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

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

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

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

Размещение начнем с состояния r4 (как имеющего наибольшее количество входящих и исходящих дуг), которое поместим в вершину 0000 куба. Состояние r11, связанное дугой x0 с состоянием r4, поместим в вершину 0010, удаленную от r4 на расстоянии 1. В вершинах 0001 и 0100 разместим состояния r2 и r3, также удаленные от r4 на расстояние 1. Пометим соответствующие этим переходам дуги символами x1 и x4. Естественным будет также размещение состояния r5 в вершине 0011, это состояние связано дугами размещение состояний автомата - student2.ru x6 и x7 с состояниями r0 и r11, причем эти дуги расположены на ребрах куба и имеют минимальную длину, равную 1.

Расстояния, соответствующие переходам r0- r4 (по дуге x2) и r4-r5 (по дуге x1), имеют соответственно длину 3 и 2.

размещение состояний автомата - student2.ru

Рис.4

размещение состояний автомата - student2.ru

Рис. 5

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

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

Наши рекомендации