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

2012-12-19T13:28:25Z

217.66.156.137: /* Алгоритм генерации */

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

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

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

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

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

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

Пример двоичного кода антигрея.

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

Возьмем двоичный зеркальный [[Коды Грея | код Грея]] размером <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=
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.
}}

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

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

Пример троичного кода антигрея

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

Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить все его поразрядные циклические сдвиги.

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

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

genTernAntiGray(n)
for v = <000..0> to <022..2>
digitCircleShift(v)
while(v[0] != 0)
print(v)
digitCircleShift(v)

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

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

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

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

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

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

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

2012-12-19T13:26:13Z

217.66.156.137: /* Алгоритм генерации */

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

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

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

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

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

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

Пример двоичного кода антигрея.

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

Возьмем двоичный зеркальный [[Коды Грея | код Грея]] размером <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=
'''Троичный код антигрея''' {{---}} такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.
}}

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

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

Пример троичного кода антигрея

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

Здесь идет описание алгоритма генерации троичного кода антигрея

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

genTernAntiGray(n)
for v = <000..0> to <022..2>
digitCircleShift(v)
while(v[0] != 0)
print(v)
digitCircleShift(v)

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

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

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

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

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

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

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

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

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