Изменения
→Псевдокод
{{Определение
|definition=
'''Код антигрея ''' (англ. ''Anti-Gray Code)''' ) {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
}}
== Двоичный код антигрея ==
{{Определение
|definition=
'''Двоичный код антигрея''' (англ. ''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)
v = getMirrorGray(i, n)
print(v)
inverseBits(v)
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>.
=== Пример Примеры работы алгоритма ===
{| class="wikitable"
!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 ||
|}
=== Доказательство корректности алгоритма ===
== См. также ==
*[[Цепные коды]]
== Источники информации == *[http://en.wikipedia.org/wiki/Gray_code Wikipedia {{---}} Gray code] [[Категория: Дискретная математика и алгоритмы]]