Коды антигрея
Содержание
Определение
| Определение: |
| Код антигрея (Anti-Gray Code) — такое упорядочивание -ичных векторов, что расстояние Хэмминга между двумя соседними векторами максимально. |
Здесь должно быть написано о том нафига вообще все это нужно.
Двоичный код антигрея
| Определение: |
| Двоичный код антигрея — такое упорядочивание двоичных векторов длины , что соседние отличаются не менее, чем в битах. |
Объяснение, почему невозможен код, где соседние отличаются во всех битах.
Пример
| n = 1 | n = 2 | n = 3 |
|---|---|---|
| 0 | 00 | 000 |
| 1 | 11 | 111 |
| 01 | 001 | |
| 10 | 110 | |
| 011 | ||
| 100 | ||
| 010 | ||
| 101 |
Алгоритм генерации
Возьмем двоичный зеркальный код Грея размером . Тогда для первых двоичных вектором будем:
- Печатать его
- Печатать его инверсию
Утверждается, что с помощью данного алгоритма мы получим двоичный код антигрея.
Псевдокод
genBinAntiGray(n)
for i = 1 to 2^(n-1)
v = getMirrorGray(i, n)
print(v)
inverseBits(v)
print(v)
Доказательство корректности алгоритма
Здесь приведено доказательство корректности алгоритма выше
Троичный код антигрея
| Определение: |
| Троичный код антигрея — такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах. |
В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
Пример
Пример троичного кода антигрея
Алгоритм генерации
Упорядочим все троичные вектора лексикографически. Тогда для первых векторов будем выводить все его поразрядные циклические сдвиги.
Утверждается, что выполняя эти действия мы получим троичный код антигрея.
Псевдокод
genTernAntiGray(n)
for v = <000..0> to <022..2>
digitCircleShift(v)
while(v[0] != 0)
print(v)
digitCircleShift(v)
Доказательство корректности алгоритма
Здесь идет доказательство корректности приведенного выше алгоритма
