Алгоритм состоит из следующих шагов.
1.Строим матрицу 
, состоящую из всех пар номеров (i, j), для которых р(i, j) ¹ 0 (т.е. в автомате есть переход из аi в аj или наоборот) и i<j. Для каждой пары в матрице указываем ее вес р(i, j), совпадающий с весом ребра соединяющего аi и аj.
| i | j | p(i,j) | ||
| T | = | |||
2.Упорядочим строки матрицы , для чего построим матрицу 
следующим образом. В первую строку матрицы поместим пару (a,b) с наибольшим весом р(a,b). В нашем случае (a,b) = (2,3), р(2,3) = 3. Из всех пар, имеющих общий компонент с парой (a,b) выбирается пара (g,d) с наибольшим весом и заносится во вторую строку матрицы . Ясно, что {a,b}×{g,d}¹0. Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с наибольшим весом и заносится в матрицу и т.д.. В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р(a) компонента a называется число появлений a в матрице ) и в матрицу заносится пара с наибольшей суммой весов. В рассматриваемом автомате на второе место вслед за парой (2,3) претендуют пары: (1,2) с р(1,2) = 2; (3,4) с р(3,4) = 2, (3,5) с р(3,5) = 2.
Для определения того, какая пара займет второе место в матрице находим веса компонентов пар:
р(1) = 3 р(2) = 3 р(1) + р(2) = 6
р(3) = 4 р(4) = 2 р(3) + р(4) = 6
р(3) = 4 р(5) = 2 р(3) + р(5) = 6
В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всех пар, получим матрицу в виде:
| i | j | p(i,j) | ||
| M | = | |||
3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда
R = ]log2M[ = ]log25[ =3.
Закодируем состояния из первой строки матрицы следующим образом: K2 = K(а2) = 000; K3 = K(а3) = 001.
Для удобства кодирования будем иллюстрировать этот процесс картой Карно:
|
4.Вычеркнем из матрицы первую строку, соответствующую закодированным состояниям а2 и а3. Получим матрицу .
| i | j | p(i,j) | ||
| M’ | = | |||
5.В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его g. (В нашем случае g = 1).
6.Строим матрицу 
, выбрав из 
строчки, содержащие g.
| i | j | p(i,j) | ||||
| Mg | = | M’ | = | |||
Пусть Bg = {g1,...,gF} – множество элементов из матрицы , которые уже закодированы. Их коды Кg1,..., KgF соответственно. В нашем случае:
Bg = B3 = {2,3} K2 = 000 K3 = 001.
7.Для каждого Kgf (f=1, ..., F) найдем 
– множество кодов, соседних с 
и еще не занятых для кодирования состояний автомата. (Для соседних кодов кодовое расстояние d=1).
K2 = 000 
= {100, 010}
K3 = 001 
= {011, 101}.
Построим множество 
Если оказывается, что 
, то строим новое множество 
, где 
– множество кодов, у которых кодовое расстояние до кода равно 2 и т.д..
8.Для каждого кода из множества Dg находим кодовое расстояние до кода .
K2 = 000 K3 = 001
d(100, 000) = 1 d(100, 001) = 2
d(010, 000) = 1 d(010, 001) = 2
d(011, 000) = 2 d(011, 001) = 1
d(101, 000) = 2 d(100, 001) = 1
9.Находим значение функции w для каждого кода из множества Dg.
10.Из множества Dg выбираем код Kg, у которого получилось минимальное значение w в п.9. Выбираем код для состояния a1 К1 =100.
|
11.Из матрицы вычеркиваем строки, в которых оба элемента уже закодированы, в результате чего получим новую матрицу . Если в новой матрице не осталось ни одной строки, то кодирование закончено. В противном случае возвращаемся к п.5. В нашем случае имеем:
| i | j | p(i,j) | ||
| M’ | = | |||
К2 = 000 = {010}
K3 = 001 
= {011, 101}
K2 = 000 K3 = 001
d(010, 000) = 1 d(010, 001) = 2
d(011, 000) = 2 d(011, 001) = 1
d(101, 000) = 2 d(101, 001) = 1
Выбираем К4 = 101.
|
К1 = 100 
= {110}
K2 = 000 
= {010}
К3 = 001 = {011}
К1 = 100 K2 = 000 K3 = 001
d(110, 100) = 1 d(110, 000) = 2 d(110, 001) = 3
d(010, 100) = 2 d(010, 000) = 1 d(010, 001) = 2
d(011, 100) = 3 d(011, 000) = 2 d(011, 001) = 1
Выбираем К5 = 011.
|
Т.к. все состояния автомата закодированы, то работа алгоритма заканчивается. Общее количество переключений триггеров:
Минимально возможное количество переключений (если бы состояния были закодированы соседним кодированием)
Коэффициент эффективности кодирования:
Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм.
Необходимо отметить в заключении, что использование алгоритма кодирования обеспечивает наиболее простую с точки зрения реализации схему, но при этом возможны гонки. Для радикального устранения последних используют аппаратные методы – триггеры с двойной памятью: триггеры, управляемые фронтом и т.д..