Коды антигрея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (вектором -> векторов)
м (Доказательство корректности алгоритма)
Строка 124: Строка 124:
 
=== Доказательство корректности алгоритма ===
 
=== Доказательство корректности алгоритма ===
  
Обозначим <tex>i</tex>-ый троичный вектор как <tex>G_i^0</tex>, его первый и второй циклический сдвиги как <tex>G_i^1</tex> и <tex>G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
+
Обозначим <tex>i</tex>-ый троичный вектор как <tex dpi="140">G_i^0</tex>, его первый и второй циклический сдвиги как <tex dpi="140" >G_i^1</tex> и <tex dpi="140">G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
   ...
+
   ... <br>
   <tex>G_i^0</tex>
+
   <tex dpi="120">G_i^0</tex> <br>
   <tex>G_i^1</tex>
+
   <tex dpi="120">G_i^1</tex> <br>
   <tex>G_i^2</tex>
+
   <tex dpi="120">G_i^2</tex> <br>
   <tex>G_{i+1}^0</tex>
+
   <tex dpi="120">G_{i+1}^0</tex> <br>
 
   ...
 
   ...
 
* <tex>G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах.
 
* <tex>G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах.

Версия 14:45, 13 января 2013

Определение

Определение:
Код антигрея (Anti-Gray Code) — такое упорядочивание [math]k[/math]-ичных векторов, что расстояние Хэмминга между двумя соседними векторами максимально.


Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.

Двоичный код антигрея

Определение:
Двоичный код антигрея — такое упорядочивание двоичных векторов длины [math]n[/math], что соседние отличаются не менее, чем в [math]n-1[/math] битах.


Заметим, что для [math]n \gt 2[/math] невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2.

Пример

n = 1 n = 2 n = 3
0 00 000
1 11 111
01 001
10 110
011
100
010
101

Алгоритм генерации

Возьмем двоичный зеркальный код Грея размером [math]n[/math]. Тогда для первых [math]2^{n-1}[/math] двоичных векторов будем:

  1. Печатать двоичный вектор
  2. Печатать его инверсию

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

Псевдокод

 genBinAntiGray(n)
   for i = 1 to 2^(n-1)
     v = getMirrorGray(i, n)
     print(v)
     inverseBits(v)
     print(v)

Доказательство корректности алгоритма

Обозначим за [math]G_i[/math][math]i[/math]-ый вектор в зеркальном коде Грея, [math]\bar G_i[/math] — его инверсию. Тогда вектора будут располагаться в таком порядке:

 ...
 [math]G_i[/math]
 [math]\bar G_i[/math]
 [math]G_{i+1}[/math]
 [math]\bar G_{i+1}[/math]
 [math]G_{i+2}[/math]
 ...
  • [math]G_i[/math] и [math]\bar G_i[/math] отличаются во всех битах.
  • Если [math]G_i[/math] и [math]G_{i+1}[/math] отличаются в [math]k[/math]-ом бите, то инверсия [math]G_i[/math] совпадает с [math]G_{i+1}[/math] только в [math]k[/math]-ом бите. То есть [math]\bar G_i[/math] и [math]G_{i+1}[/math] отличаются во всех позициях, кроме [math]k[/math]-ой.


Троичный код антигрея

Определение:
Троичный код антигрея — такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.


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

Пример

n = 1 n = 2 n = 3
0 00 000 010 020
1 11 111 121 101
2 22 222 202 212
01 001 011 021
12 112 122 102
20 220 200 210
02 002 012 022
10 110 120 100
21 221 201 211

Алгоритм генерации

Упорядочим все троичные вектора лексикографически. Тогда для первых [math]3^{n-1}[/math] векторов будем выводить все его поразрядные циклические сдвиги.

Утверждается, что выполняя эти действия мы получим троичный код антигрея.

Псевдокод

 genTernAntiGray(n)
   for v = <000..0> to <022..2>
     digitCircleShift(v)
     while(v[0] != 0)
       print(v)
       digitCircleShift(v)

Заметим, что данный алгоритм можно обобщить на случай [math]k[/math]-ичного кода антигрея.

Доказательство корректности алгоритма

Обозначим [math]i[/math]-ый троичный вектор как [math]G_i^0[/math], его первый и второй циклический сдвиги как [math]G_i^1[/math] и [math]G_i^2[/math] соответственно. Получаем вектора в следующем порядке:

 ... 
[math]G_i^0[/math]
[math]G_i^1[/math]
[math]G_i^2[/math]
[math]G_{i+1}^0[/math]
...
  • [math]G_i^0[/math] и [math]G_i^1[/math], равно как [math]G_i^1[/math] и [math]G_i^2[/math], отличаются во всех битах.
  • Если говорить о векторах как о троичных числах, то [math]G_{i+1}^0[/math] получено из [math]G_i^0[/math] прибавлением единицы, это значит, что у [math]G_{i+1}^0[/math] несколько разрядов справа на единицу больше (по модулю 3), чем у [math]G_i^0[/math] (по правилам сложения в столбик). С другой стороны [math]G_{i}^2[/math] получено из [math]G_{i}^0[/math] двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе [math]G_{i+1}^0[/math] некоторые биты такие же, как в [math]G_{i}^0[/math], остальные на единицу больше; в числе [math]G_{i}^2[/math] все биты на один меньше по сравнению с [math]G_{i}^0[/math], значит [math]G_{i}^2[/math] и [math]G_{i+1}^0[/math] различны во всех битах.

Для [math]k[/math]-ичного кода антигрея рассуждения будут аналогичными.

См. также

Источники