Коды антигрея — различия между версиями
Oxygen3 (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 44: | Строка 44: | ||
=== Псевдокод === | === Псевдокод === | ||
− | |||
'''function''' genBinAntiGray(n: '''int'''): | '''function''' genBinAntiGray(n: '''int'''): | ||
'''for''' i = 1 '''to''' 2 ** (n - 1) | '''for''' i = 1 '''to''' 2 ** (n - 1) | ||
Строка 51: | Строка 50: | ||
inverseBits(v) | inverseBits(v) | ||
print(v) | print(v) | ||
− | + | ||
=== Доказательство корректности алгоритма === | === Доказательство корректности алгоритма === | ||
Текущая версия на 19:03, 4 сентября 2022
Определение: |
Код антигрея (англ. Anti-Gray Code) — такое упорядочивание расстояние Хэмминга между двумя соседними векторами максимально. | -ичных векторов, что
Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.
Двоичный код антигрея
Определение: |
Двоичный код антигрея (англ. Binary Anti-Gray Code) — такое упорядочивание двоичных векторов длины | , что соседние отличаются не менее, чем в битах.
Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для
. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где , таких векторов должно быть два.Пример
n = 1 | n = 2 | n = 3 |
---|---|---|
0 | 00 | 000 |
1 | 11 | 111 |
01 | 001 | |
10 | 110 | |
011 | ||
100 | ||
010 | ||
101 |
Алгоритм генерации
Возьмем двоичный зеркальный код Грея размером . Тогда для первых двоичных векторов будем:
- Печатать двоичный вектор
- Печатать его инверсию
Утверждается, что с помощью данного алгоритма мы напечатаем двоичный код антигрея.
Псевдокод
function genBinAntiGray(n: int): for i = 1 to 2 ** (n - 1) v = getMirrorGray(i, n) print(v) inverseBits(v) print(v)
Доказательство корректности алгоритма
Обозначим за
— -ый вектор в зеркальном коде Грея, — его инверсию. Тогда вектора будут располагаться в таком порядке:
Если и отличаются в -ом бите, то инверсия совпадает с только в -ом бите. То есть и отличаются во всех позициях, кроме -ой.
Троичный код антигрея
Определение: |
Троичный код антигрея (англ. Ternary Anti-Gray Code) — такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах. |
В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
Алгоритм генерации
Упорядочим все троичные вектора лексикографически. Тогда для первых
Например, если мы имеем вектор , то вы выведем: , , .
Утверждается, что выполняя эти действия мы получим троичный код антигрея.
Псевдокод
function genTernAntiGray(n: int):
for v = <000..0> to <022..2> // троичные вектора длины
for i = 0 to 2
print(v)
digitCircleShift(v)
Заметим, что данный алгоритм можно обобщить на случай
-ичного кода антигрея.Примеры работы алгоритма
n = 1 | n = 2 | n = 3 | ||||
---|---|---|---|---|---|---|
Первые векторов |
Коды антигрея | Первые векторов |
Коды антигрея | Первые векторов |
Коды антигрея | |
0 | 0 | 00 | 00 | 000 | 000 | 200 |
1 | 01 | 11 | 001 | 111 | 012 | |
2 | 02 | 22 | 002 | 222 | 120 | |
01 | 010 | 001 | 201 | |||
12 | 011 | 112 | 020 | |||
20 | 012 | 220 | 101 | |||
02 | 020 | 002 | 212 | |||
10 | 021 | 110 | 021 | |||
21 | 022 | 221 | 102 | |||
010 | 210 | |||||
121 | 022 | |||||
202 | 100 | |||||
011 | 211 | |||||
122 |
Доказательство корректности алгоритма
Обозначим
-ый троичный вектор как , его первый и второй циклический сдвиги как и соответственно. Получаем вектора в следующем порядке:
Если говорить о векторах как о троичных числах, то получено из прибавлением единицы, это значит, что у несколько разрядов справа на единицу больше (по модулю ), чем у (по правилам сложения в столбик). С другой стороны получено из двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе некоторые биты такие же, как в , остальные на единицу больше; в числе все биты на один меньше по сравнению с , значит и различны во всех битах.
Подобные рассуждения можно провести для любого -ичного кода антигрея, где .