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

Материал из Викиконспекты
Перейти к: навигация, поиск

Определение

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


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

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

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


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

Пример

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

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

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

Псевдокод

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

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

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

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

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


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

Пример

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

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

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

Псевдокод

 genTernAntiGray(n)
   doSomething

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

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

См. также

Источники