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

Определение

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

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

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

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

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

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

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

Пример

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

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

Описание алгоритма генерации

Псевдокод

 genBinAntiGray(n)
   doSomething

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

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

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

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

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

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

Пример

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

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

Здесь идет описание алгоритма генерации троичного кода антигрея

Псевдокод

 genTernAntiGray(n)
   doSomething

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

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

См. также

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

Источники

• Talk:Gray Code - Wikipedia, the free encyclopedia