Коды антигрея — различия между версиями
(→Псевдокод) |
(→Псевдокод) |
||
| Строка 56: | Строка 56: | ||
genTernAntiGray(n) | genTernAntiGray(n) | ||
| − | + | for v = <000..0> to <022..2> | |
| + | digitCircleShift(v) | ||
| + | while(v[0] != 0) | ||
| + | print(v) | ||
| + | digitCircleShift(v) | ||
=== Доказательство корректности алгоритма === | === Доказательство корректности алгоритма === | ||
Версия 15:08, 19 декабря 2012
Содержание
Определение
| Определение: |
| Код антигрея (Anti-Gray Code) — такое упорядочивание -ичных векторов, что расстояние Хэмминга между двумя соседними векторами максимально. |
Здесь должно быть написано о том нафига вообще все это нужно.
Двоичный код антигрея
| Определение: |
| Двоичный код антигрея — такое упорядочивание двоичных векторов длины , что соседние отличаются не менее, чем в битах. |
Объяснение, почему невозможен код, где соседние отличаются во всех битах.
Пример
Пример двоичного кода антигрея.
Алгоритм генерации
Описание алгоритма генерации
Псевдокод
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)
Доказательство корректности алгоритма
Здесь идет доказательство корректности приведенного выше алгоритма
