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

Определение

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

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

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

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

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

Двоичный код антигрея — такое упорядочивание двоичных векторов длины [math]n[/math], что соседние отличаются не менее, чем в [math]n-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. Печатать его инверсию

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

Псевдокод

 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
1	11	111
2	22	222
	01	001
	12	112
	20	220
	02	002
	10	110
	21	221
		010
		121
		202
		011
		122
		200
		012
		120
		201
		020
		101
		212
		021
		102
		210
		022
		100
		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