logo
Лекции по теории автоматов

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

  2. {1,2} => S1 = 000 S2 = 001

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

  2. {2,4}

q=4

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

  2. Bq = {2}

  3. C14 = {101,011}

  4. 101 + 001 = 100 d =1

011 + 001 = 010 d =1

S4 = 101

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

4) {2,5} q=5

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

6) Bq = {2,4,1}

7) C15 = {011}

C15 = {(111),(100)}

C15 = {(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

S5 = 100

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

4) {2,3} q=3

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

6) Bq = {2,4}

7) C15 = {011}

C15 = {(111)}

C15 = {(100),(010)}

8) 011 + 001 = 010

011 + 101 = 110

111 + 001 = 110

111 + 101 = 010

S3 = 011

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

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