Изменения

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

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

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

  '''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="width:45px2" align="center"| n = 1 !stylecolspan="width:45px2" align="center"| n = 2 !colspan="3" align="center" style="width:135px"| n = 3

!align="center"| 0 Первые <tex>3^{n-1}</tex><br>векторов !align="center"|Коды антигрея !align="center"| 00 Первые <tex>3^{n-1}</tex><br>векторов !align="center"|Коды антигрея !align="center"| 000 Первые <tex>3^{n-1}</tex><br>векторов !colspan="2" align="center"|| 010 || 020Коды антигрея

| 1 '''0''' || 11 '''0''' || 111 '''00''' || 121 '''00''' || 101'''000''' || '''000''' || 200

| 2 || 22 1 || 222 '''01''' || 202 11 || 212'''001''' || 111 || '''012'''

| || 01 2 || 001 '''02''' || 011 22 || 021'''002''' || 222 || 120

| || 12 || 112 || 122 '''01''' || 102'''010''' || '''001''' || 201

| || 20 || 220 || 200 12 || 210'''011''' || 112 || '''020'''

| || 02 || 002 || 20 || '''012 ''' || 220 || 022101

| || 10 || 110 || 120 '''02''' || 100'''020''' || '''002''' || 212

| || || || 10 || '''021''' || 110 || '''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Комбинаторика]]