Соседнее кодирование состояний автомата

Соседними состояниями первого порядка называются состояния, которые можно соединить ребром.

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

Два состояния, в которые переходят под действием одного и того же входного сигнала состояния, являющиеся соседями первого рода, называются соседями второго рода.

Соседними кодами называются наборы значений, имеющие противоположные значения только в одном разряде, т.е. коды с кодовым расстоянием 1.

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

Существуют ограничения соседнего кодирования:

1. В графе автомата не должно быть циклов с нечётным числом вершин.

2. Два соседних состояния второго порядка не должны иметь более двух состояний, лежащих между ними.

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

Соседями первого рода в обратной таблице переходов оказываются попарно состояния, находящиеся в одной ячейке таблицы:

(a2,a6), (a1,a4), (a1,a3), (a3,a4), (a2,a5), (a5,a6).

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

Часто для кодирования состояний, близких к соседним, используются диаграммы Вейча–Карно. В этом случае первым кодируется состояние, которое в списке соседей встречается наибольшее число раз.

Диаграмма :