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

Определение

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

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

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

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

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

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

Объяснение, почему невозможен код, где соседние отличаются во всех битах.

Пример

Пример двоичного кода антигрея.

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

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

1. Печатать его

1. Печатать его инверсию

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

Псевдокод

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

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

Здесь приведено доказательство корректности алгоритма выше

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

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

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

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

Пример

Пример троичного кода антигрея

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

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

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

Псевдокод

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

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

Здесь идет доказательство корректности приведенного выше алгоритма

См. также

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

Источники

• Talk:Gray Code - Wikipedia, the free encyclopedia