Минимизация числа переключений элементов памяти.

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

Алгоритм кодирования:

1. Определяем множество пар состояний, между которыми существует переход M.

2. Выбирается любая пара состояний, между которыми есть переход, один из них кодируется всеми нулями, а другой нулями и одной единицей.(00…01)

3. Из множества Mудаляются пары состояний, которые уже закодированыM\(S_iS_j), если станет равным 0 , то процесс завершается.

4. Берем любую пару в которой одно состояние уже закодировано, а другое нет (* , S_q)S_q- незакодированное состояние, * - состояние закодировано. Далее кодируем это состояние.

5. Выбираем множество пар из Mкуда входитS_q (M_q)

6. Из M_qвыбираем все закодированные состояния (B_q)

7. Строим множество кодов, имеющих расстояние d, с каждым кодом из состоянияB_q

8. Для каждого кода из всех множеств C^d_qопределяется сумма расстояний по Хеммингу с каждым кодом изB_qВыбирается код, имеющий минимальную сумму и этот код приписываетсяC_qДеле возврат к пункту 3.

Пример:

1. Пары состояний M={(1,2),(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

2. {1,2} => S₁ = 000 S₂ = 001

3. M={(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

4. {2,4}

q=4

5. M_q = {(2,4),(3,4),(4,5)}

6. B_q = {2}

7. C¹₄ = {101,011}

8. 101 + 001 = 100 d =1

011 + 001 = 010 d =1

S₄ = 101

3) M={(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

4) {2,5} q=5

5) M_q = {(2,5),(1,5),(4,5)}

6) B_q = {2,4,1}

7) C¹₅ = {011}

C¹₅ = {(111),(100)}

C¹₅ = {(100),(010)}

8) 011 + 001 = 010

011 + 101 = 110

011 + 000 = 110

111 + 001 = 110

111 + 101 = 010

111 + 000 = 111

100 + 001 = 101

100 + 101 = 001

100 + 000 = 100

010 + 001 = 011

010 + 101 = 111

010 + 000 = 010

S₅ = 100

3) M = {(2,3,(3,4) }

4) {2,3} q=3

5) M_q = {(2,3),(3,4)}

6) B_q = {2,4}

7) C¹₅ = {011}

C¹₅ = {(111)}

C¹₅ = {(100),(010)}

8) 011 + 001 = 010

011 + 101 = 110

111 + 001 = 110

111 + 101 = 010

S₃ = 011

3) M = {0 } – конец цикла.

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