Изменения

'''Код антигрея ''' (англ. ''Anti-Gray Code)''' ) {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.

 Здесь должно быть написано о том нафига вообще все это нужноКод антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.

'''Двоичный код антигрея''' (англ. ''Binary Anti-Gray Code'') {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.

 Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для <tex>n > 2= 1</tex> невозможно такое упорядочивание двоичных векторов. Это объясняется тем, что соседние отличаются для двоичного вектора существует ровно один вектор, отличающийся во всех битах. Это объясняется однозначностью "соседа" для каждого вектора. Так как количество "соседей" может быть равно , а в последовательности, где <tex>2n > 1</tex> и все вектора различны, то мы приходим к противоречиютаких векторов должно быть два.

  '''function''' genBinAntiGray(n: '''int'''): '''for ''' i = 1 '''to ''' 2^** (n-1)

'''Троичный код антигрея''' (англ. ''Ternary Anti-Gray Code'') {{---}} такое упорядочивание троичных векторомвекторов, что соседние отличаются во всех разрядах.

В отличие от двоичного кода антигреяУтверждается, здесь что выполняя эти действия мы не сталкиваемся с проблемой однозначности получим троичный код антигрея. === Псевдокод ===<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>-ичного кода антигрея.

=== Пример Примеры работы алгоритма ===

!stylecolspan="2" align="width:45pxcenter"| n = 1 !stylecolspan="width:45px2" align="center"| n = 2 !colspan="3" align="center" style| n = 3|-!align="width:135pxcenter"| Первые <tex>3^{n -1}</tex><br>векторов !align= "center"|Коды антигрея !align="center"|Первые <tex>3^{n-1}</tex><br>векторов !align="center"|Коды антигрея !align="center"|Первые <tex>3^{n-1}</tex><br>векторов !colspan="2" align="center"|Коды антигрея

| '''0 ''' || '''0''' || '''00 ''' || '''00''' || '''000 ''' || 010 '''000''' || 020200

| || 1 || '''01''' || 11 || 111 '''001''' || 121 111 || 101'''012'''

| || 2 || '''02''' || 22 || 222 '''002''' || 202 222 || 212120

| || || || '''01 ''' || 001 '''010''' || 011 '''001''' || 021201

| || || || 12 || 112 '''011''' || 122 112 || 102'''020'''

| || || || 20 || 220 '''012''' || 200 220 || 210101

| || || || '''02 ''' || 002 '''020''' || 012 '''002''' || 022212

| || || || 10 || 110 '''021''' || 120 110 || 100'''021'''

| || || || 21 || '''022''' || 221 || 201 102|-| || || || || || '''010''' || 210|-| || || || || || 121 || '''022'''|-| || || || || || 202 || 100|-| || || || || || '''011''' || 211|-| || || || || || 122 ||

=== Алгоритм генерации Доказательство корректности алгоритма === Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</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> genTernAntiGray(n):<tex>\dots</tex> for v = <tex >G_i^000..0</tex> to и <022tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах..2<br> digitCircleShift(v) while(v[Если говорить о векторах как о троичных числах, то <tex>G_{i+1}^0</tex> получено из <tex>G_i^0] != </tex> прибавлением единицы, это значит, что у <tex>G_{i+1}^0) print</tex> несколько разрядов справа на единицу больше (vпо модулю <tex>3</tex>) digitCircleShift, чем у <tex>G_i^0</tex> (vпо правилам сложения в столбик) Заметим. С другой стороны <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Комбинаторика]]