== Определение ==
{{Определение
|definition=
'''Код антигрея ''' (англ. ''Anti-Gray Code)''' ) {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
}}
Здесь должно быть написано о том нафига вообще все это нужноКод антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.
== Двоичный код антигрея ==
{{Определение
|definition=
'''Двоичный код антигрея''' (англ. ''Binary Anti-Gray Code'') {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
}}
ОбъяснениеЗаметим: упорядочивание векторов такое, почему невозможен код, где что соседние отличаются во всех битах, возможно только для <tex>n = 1</tex>. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где <tex>n > 1</tex>, таких векторов должно быть два.
=== Пример ===
=== Алгоритм генерации ===
Возьмем двоичный зеркальный [[Коды Грея | код Грея]] размером <tex>n</tex>. Тогда для первых <tex>2^{n-1}</tex> двоичных вектором векторов будем: # Печатать его
# Печатать двоичный вектор
# Печатать его инверсию
Утверждается, что с помощью данного алгоритма мы получим напечатаем двоичный код антигрея.
=== Псевдокод ===
'''function''' genBinAntiGray(n: '''int'''): '''for ''' i = 1 '''to ''' 2^** (n-1)
v = getMirrorGray(i, n)
print(v)
=== Доказательство корректности алгоритма ===
Здесь приведено доказательство корректности алгоритма вышеОбозначим за <tex>G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex>\overline G_i</tex> — его инверсию. Тогда вектора будут располагаться в таком порядке::<tex>\dots</tex> <br>:<tex>G_i</tex> <br>:<tex>\overline G_i</tex> <br>:<tex>G_{i+1}</tex> <br>:<tex>\overline G_{i+1}</tex> <br>:<tex>G_{i+2}</tex> <br>:<tex>\dots</tex><tex>G_i</tex> и <tex>\overline G_i</tex> отличаются во всех битах. <br>Если <tex>G_i</tex> и <tex>G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex>G_i</tex> совпадает с <tex>G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex>\overline G_i</tex> и <tex>G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
== Троичный код антигрея ==
{{Определение
|definition=
'''Троичный код антигрея''' (англ. ''Ternary Anti-Gray Code'') {{---}} такое упорядочивание троичных векторомвекторов, что соседние отличаются во всех разрядах.
}}
В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
В отличие от двоичного кода антигрея=== Алгоритм генерации === Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить сначала сам этот вектор, потом <tex>2</tex> его поразрядных циклических сдвига (каждый отдельный бит увеличиваем на <tex>1</tex>). <br>Например, если мы имеем вектор <tex>021</tex>, то вы выведем: <tex>021</tex>, <tex>102</tex>, <tex>210</tex>. Утверждается, здесь что выполняя эти действия мы не сталкиваемся с проблемой однозначности получим троичный код антигрея. === Псевдокод ===<code> '''function''' genTernAntiGray(n: '''int'''): '''for''' v = <000..0> '''to''' <022..2> <span style="соседаcolor:Green" и можем привести такой код>// троичные вектора длины <tex>n</tex> </span> '''for''' i = 0 '''to''' 2 print(v) digitCircleShift(v)</code>Заметим, соседние элементы которого будут отличаться во всех разрядахчто данный алгоритм можно обобщить на случай <tex>k</tex>-ичного кода антигрея.
=== Пример Примеры работы алгоритма ===
{| class="wikitable"
! colspan="2" align="center"| n = 1 |!colspan="2" align="center"| n = 2 |!colspan="3" align="center"| n = 3|-| 0 || 00 || 000|-| 1 || 11 || 111|-| 2 || 22 || 222|-| || 01 || 001|-| || 12 || 112
|-
!align="center"| Первые <tex>3^{n-1}</tex><br>векторов !align="center"|Коды антигрея !align="center"| 20 Первые <tex>3^{n-1}</tex><br>векторов !align="center"|Коды антигрея !align="center"| 220Первые <tex>3^{n-1}</tex><br>векторов !colspan="2" align="center"|Коды антигрея
|-
| '''0''' || 02 '''0''' || 002'''00''' || '''00''' || '''000''' || '''000''' || 200
|-
| || 10 1 || 110'''01''' || 11 || '''001''' || 111 || '''012'''
|-
| || 21 2 || 221'''02''' || 22 || '''002''' || 222 || 120
|-
| || || || '''01''' || '''010''' || '''001''' || 201
|-
| || || 121|| 12 || '''011''' || 112 || '''020'''
|-
| || || 202|| 20 || '''012''' || 220 || 101
|-
| || || 011|| '''02''' || '''020''' || '''002''' || 212
|-
| || || 122|| 10 || '''021''' || 110 || '''021'''
|-
| || || 200|| 21 || '''022''' || 221 || 102
|-
| || || 012|| || || '''010''' || 210
|-
| || || 120|| || || 121 || '''022'''
|-
| || || 201|| || || 202 || 100
|-
| || || 020|| || || '''011''' || 211
|-
| || || 101|-| || || 212122 |-| || || 021|-| || || 102|-| || || 210|-| || || 022|-| || || 100|-| || || 211
|}
=== Алгоритм генерации ===
Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить все его поразрядные циклические сдвиги.
Утверждается, что выполняя эти действия мы получим троичный код антигрея.
=== Псевдокод ===
genTernAntiGray(n)
for v = <000..0> to <022..2>
digitCircleShift(v)
while(v[0] != 0)
print(v)
digitCircleShift(v)
Заметим, что данный алгоритм можно обобщить на случай <tex>k</tex>-ичного кода антигрея.
=== Доказательство корректности алгоритма ===
Здесь идет доказательство корректности приведенного выше алгоритмаОбозначим <tex>i</tex>-ый троичный вектор как <tex>G_i^0</tex>, его первый и второй циклический сдвиги как <tex>G_i^1</tex> и <tex>G_i^2</tex> соответственно. Получаем вектора в следующем порядке::<tex>\dots</tex> <br>:<tex>G_i^0</tex> <br>:<tex>G_i^1</tex> <br>:<tex>G_i^2</tex> <br>:<tex>G_{i+1}^0</tex> <br>:<tex>\dots</tex><tex >G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах. <br>Если говорить о векторах как о троичных числах, то <tex>G_{i+1}^0</tex> получено из <tex>G_i^0</tex> прибавлением единицы, это значит, что у <tex>G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex>G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex>G_{i}^2</tex> получено из <tex>G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex>G_{i+1}^0</tex> некоторые биты такие же, как в <tex>G_{i}^0</tex>, остальные на единицу больше; в числе <tex>G_{i}^2</tex> все биты на один меньше по сравнению с <tex>G_{i}^0</tex>, значит <tex>G_{i}^2</tex> и <tex>G_{i+1}^0</tex> различны во всех битах.Подобные рассуждения можно провести для любого <tex>k</tex>-ичного кода антигрея, где <tex>k \geqslant 3</tex>.
== См. также ==
*[[Цепные коды]]
== Источники информации == *[http://en.wikipedia.org/wiki/Gray_code Wikipedia {{---}} Gray code] [[Категория: Дискретная математика и алгоритмы]]
*[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk[Категория:Gray Code - Wikipedia, the free encyclopediaКомбинаторика]]
