55
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Код антигрея ''' (англ. ''Anti-Gray Code)''' ) {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
}}
Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.
'''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
}}
Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для <tex>n = 1</tex>. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где <tex>n > 1</tex>, таких векторов должно быть два.
=== Псевдокод ===
function genBinAntiGray(n: '''int''') '''for ''' i = 1 to 2^**(n-1)
v = getMirrorGray(i, n)
print(v)
=== Доказательство корректности алгоритма ===
Обозначим за <tex dpi = "140">G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex dpi = "140">\overline G_i</tex> — его инверсию. Тогда вектора будут располагаться в таком порядке:<br> *... <br> *<tex dpi="120">G_i</tex> <br> *<tex dpi="120">\overline G_i</tex> <br> *<tex dpi="120">G_{i+1}</tex> <br> *<tex dpi="120">\overline G_{i+1}</tex> <br> *<tex dpi="120">G_{i+2}</tex> <br> *...<br>* <tex dpi = "140">G_i</tex> и <tex dpi = "140">\overline G_i</tex> отличаются во всех битах.<br>* Если <tex dpi = "140">G_i</tex> и <tex dpi = "140">G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex dpi = "140">G_i</tex> совпадает с <tex dpi = "140">G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex dpi = "140">\overline G_i</tex> и <tex dpi = "140">G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
== Троичный код антигрея ==
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
}}
В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
=== Алгоритм генерации ===
Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить все сначала сам этот вектор, потом 2 его поразрядные циклические сдвигипоразрядных циклических сдвига. <br>Например, если мы имеем вектор <tex>021</tex>, то вы выведем: <tex>021</tex>, <tex>102</tex>, <tex>210</tex>.
Утверждается, что выполняя эти действия мы получим троичный код антигрея.
=== Псевдокод ===
function genTernAntiGray(n: '''int''') '''for ''' v = <000..0> to <022..2>
digitCircleShift(v)
'''while'''(v[0] != 0)
print(v)
digitCircleShift(v)
=== Доказательство корректности алгоритма ===
Обозначим <tex>i</tex>-ый троичный вектор как <tex dpi="140">G_i^0</tex>, его первый и второй циклический сдвиги как <tex dpi="140" >G_i^1</tex> и <tex dpi="140">G_i^2</tex> соответственно. Получаем вектора в следующем порядке: *... <br> *<tex dpi="120">G_i^0</tex> <br> *<tex dpi="120">G_i^1</tex> <br> *<tex dpi="120">G_i^2</tex> <br> *<tex dpi="120">G_{i+1}^0</tex> <br> *...* <tex dpi = "140">G_i^0</tex> и <tex dpi = "140">G_i^1</tex>, равно как <tex dpi = "140">G_i^1</tex> и <tex dpi = "140">G_i^2</tex>, отличаются во всех битах.<br>* Если говорить о векторах как о троичных числах, то <tex dpi = "140">G_{i+1}^0</tex> получено из <tex dpi = "140">G_i^0</tex> прибавлением единицы, это значит, что у <tex dpi = "140">G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex dpi = "140">G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex dpi = "140">G_{i}^2</tex> получено из <tex dpi = "140">G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex dpi = "140">G_{i+1}^0</tex> некоторые биты такие же, как в <tex dpi = "140">G_{i}^0</tex>, остальные на единицу больше; в числе <tex dpi = "140">G_{i}^2</tex> все биты на один меньше по сравнению с <tex dpi = "140">G_{i}^0</tex>, значит <tex dpi = "140">G_{i}^2</tex> и <tex dpi = "140">G_{i+1}^0</tex> различны во всех битах.
Подобные рассуждения можно провести для любого <tex>k</tex>-ичного кода антигрея, где <tex>k \ge 3</tex>.
*[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk:Gray Code - Wikipedia, the free encyclopedia]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
