Коды антигрея

Определение:

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

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

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

Определение:

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

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

Пример

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. Печатать его инверсию

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

Псевдокод

 function genBinAntiGray(n: int):
   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]\overline G_i[/math] — его инверсию. Тогда вектора будут располагаться в таком порядке:

[math]\dots[/math]

[math]G_i[/math]

[math]\overline G_i[/math]

[math]G_{i+1}[/math]

[math]\overline G_{i+1}[/math]

[math]G_{i+2}[/math]

[math]\dots[/math]

[math]G_i[/math] и [math]\overline 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]\overline G_i[/math] и [math]G_{i+1}[/math] отличаются во всех позициях, кроме [math]k[/math]-ой.

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

Определение:

Троичный код антигрея (англ. Trinary Anti-Gray Code) — такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.

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

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

Упорядочим все троичные вектора лексикографически. Тогда для первых [math]3^{n-1}[/math] векторов будем выводить сначала сам этот вектор, потом [math]2[/math] его поразрядных циклических сдвига (каждый отдельный бит увеличиваем на [math]1[/math]).
Например, если мы имеем вектор [math]021[/math], то вы выведем: [math]021[/math], [math]102[/math], [math]210[/math].

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

Псевдокод

 function genTernAntiGray(n: int):
   for v = <000..0> to <022..2> // троичные вектора длины [math]n[/math] 
     fori = 0 to 2
       print(v)
       digitCircleShift(v)

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

Примеры работы алгоритма

n = 1		n = 2		n = 3
Первые [math]3^{n-1}[/math] векторов	Коды антигрея	Первые [math]3^{n-1}[/math] векторов	Коды антигрея	Первые [math]3^{n-1}[/math] векторов	Коды антигрея
0	0	00	00	000	000	200
	1	01	11	001	111	012
	2	02	22	002	222	120
			01	010	001	201
			12	011	112	020
			20	012	220	101
			02	020	002	212
			10	021	110	021
			21	022	221	102
					010	210
					121	022
					202	100
					011	211
					122

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

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

[math]\dots[/math]

[math]G_i^0[/math]

[math]G_i^1[/math]

[math]G_i^2[/math]

[math]G_{i+1}^0[/math]

[math]\dots[/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] несколько разрядов справа на единицу больше (по модулю [math]3[/math]), чем у [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]-ичного кода антигрея, где [math]k \geqslant 3[/math].

См. также

• Коды Грея
• Коды Грея для перестановок
• Цепные коды

Источники информации

• Wikipedia — Gray code