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

Определение

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

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

Здесь должно быть написано о том нафига вообще все это нужно.

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

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

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

Заметим, что для [math]n \gt 2[/math] невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Это объясняется однозначностью "соседа" для каждого вектора. Так как количество "соседей" может быть равно [math]2[/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. Печатать его инверсию

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

Псевдокод

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

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

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

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

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

Пример

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]-ичного кода антигрея.

См. также

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

Источники

• Talk:Gray Code - Wikipedia, the free encyclopedia