Коды антигрея

2013-01-01T07:35:46Z

46.233.201.233: /* Двоичный код антигрея */

== Определение ==

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

Здесь должно быть написано о том нафига вообще все это нужно.

== Двоичный код антигрея ==
{{Определение
|definition=
'''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
}}

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

=== Пример ===

{| class="wikitable"
! n = 1 || n = 2 || n = 3
|-
| 0 || 00 || 000
|-
| 1 || 11 || 111
|-
| || 01 || 001
|-
| || 10 || 110
|-
| || || 011
|-
| || || 100
|-
| || || 010
|-
| || || 101
|}

=== Алгоритм генерации ===

Возьмем двоичный зеркальный [[Коды Грея | код Грея]] размером <tex>n</tex>. Тогда для первых <tex>2^{n-1}</tex> двоичных векторов будем:

# Печатать двоичный вектор
# Печатать его инверсию

Утверждается, что с помощью данного алгоритма мы напечатаем двоичный код антигрея.

=== Псевдокод ===

genBinAntiGray(n)
for i = 1 to 2^(n-1)
v = getMirrorGray(i, n)
print(v)
inverseBits(v)
print(v)

=== Доказательство корректности алгоритма ===

Здесь приведено доказательство корректности алгоритма выше

== Троичный код антигрея ==
{{Определение
|definition=
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.
}}

В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.

=== Пример ===

{| class="wikitable"
!style="width:45px"| n = 1
!style="width:45px"| n = 2
!colspan="3" align="center" style="width:135px"| n = 3
|-
| 0 || 00 || 000 || 010 || 020
|-
| 1 || 11 || 111 || 121 || 101
|-
| 2 || 22 || 222 || 202 || 212
|-
| || 01 || 001 || 011 || 021
|-
| || 12 || 112 || 122 || 102
|-
| || 20 || 220 || 200 || 210
|-
| || 02 || 002 || 012 || 022
|-
| || 10 || 110 || 120 || 100
|-
| || 21 || 221 || 201 || 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>-ичного кода антигрея.

=== Доказательство корректности алгоритма ===

Здесь идет доказательство корректности приведенного выше алгоритма

== См. также ==

*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]

== Источники ==

*[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk:Gray Code - Wikipedia, the free encyclopedia]

Коды антигрея

2013-01-01T07:14:50Z

46.233.201.233: /* Пример */

== Определение ==

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

Здесь должно быть написано о том нафига вообще все это нужно.

== Двоичный код антигрея ==
{{Определение
|definition=
'''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
}}

Объяснение, почему невозможен код, где соседние отличаются во всех битах.

=== Пример ===

{| class="wikitable"
! n = 1 || n = 2 || n = 3
|-
| 0 || 00 || 000
|-
| 1 || 11 || 111
|-
| || 01 || 001
|-
| || 10 || 110
|-
| || || 011
|-
| || || 100
|-
| || || 010
|-
| || || 101
|}

=== Алгоритм генерации ===

Возьмем двоичный зеркальный [[Коды Грея | код Грея]] размером <tex>n</tex>. Тогда для первых <tex>2^{n-1}</tex> двоичных векторов будем:

# Печатать двоичный вектор
# Печатать его инверсию

Утверждается, что с помощью данного алгоритма мы напечатаем двоичный код антигрея.

=== Псевдокод ===

genBinAntiGray(n)
for i = 1 to 2^(n-1)
v = getMirrorGray(i, n)
print(v)
inverseBits(v)
print(v)

=== Доказательство корректности алгоритма ===

Здесь приведено доказательство корректности алгоритма выше

== Троичный код антигрея ==
{{Определение
|definition=
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.
}}

В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.

=== Пример ===

{| class="wikitable"
!style="width:45px"| n = 1
!style="width:45px"| n = 2
!colspan="3" align="center" style="width:135px"| n = 3
|-
| 0 || 00 || 000 || 010 || 020
|-
| 1 || 11 || 111 || 121 || 101
|-
| 2 || 22 || 222 || 202 || 212
|-
| || 01 || 001 || 011 || 021
|-
| || 12 || 112 || 122 || 102
|-
| || 20 || 220 || 200 || 210
|-
| || 02 || 002 || 012 || 022
|-
| || 10 || 110 || 120 || 100
|-
| || 21 || 221 || 201 || 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>-ичного кода антигрея.

=== Доказательство корректности алгоритма ===

Здесь идет доказательство корректности приведенного выше алгоритма

== См. также ==

*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]

== Источники ==

*[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk:Gray Code - Wikipedia, the free encyclopedia]

Викиконспекты - Вклад участника [ru]

Коды антигрея

Коды антигрея