Коды антигрея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Пример)
(→‎Пример)
Строка 71: Строка 71:
 
=== Пример ===
 
=== Пример ===
  
−
Пример троичного кода антигрея
+
{| class="wikitable"
 +
! n = 1 || n = 2 || n = 3
 +
|-
 +
| 0 || 00 || 000
 +
|-
 +
| 1 || 11 || 111
 +
|-
 +
| 2 || 22 || 222
 +
|-
 +
| || 01 || 001
 +
|-
 +
| || 12 || 112
 +
|-
 +
| || 20 || 220
 +
|-
 +
| || 02 || 002
 +
|-
 +
| || 10 || 110
 +
|-
 +
| || 21 || 221
 +
|-
 +
| || || 010
 +
|-
 +
| || || 121
 +
|-
 +
| || || 202
 +
|-
 +
| || || 011
 +
|-
 +
| || || 122
 +
|-
 +
| || || 200
 +
|-
 +
| || || 012
 +
|-
 +
| || || 120
 +
|-
 +
| || || 201
 +
|-
 +
| || || 020
 +
|-
 +
| || || 101
 +
|-
 +
| || || 212
 +
|-
 +
| || || 021
 +
|-
 +
| || || 102
 +
|-
 +
| || || 210
 +
|-
 +
| || || 022
 +
|-
 +
| || || 100
 +
|-
 +
| || || 211
 +
|}
  
 
=== Алгоритм генерации ===
 
=== Алгоритм генерации ===

Версия 17:26, 19 декабря 2012

Определение

Определение:
Код антигрея (Anti-Gray Code) — такое упорядочивание [math]k[/math]-ичных векторов, что расстояние Хэмминга между двумя соседними векторами максимально.


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

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

Определение:
Двоичный код антигрея — такое упорядочивание двоичных векторов длины [math]n[/math], что соседние отличаются не менее, чем в [math]n-1[/math] битах.


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

Пример

n = 1 n = 2 n = 3
0 00 000
1 11 111
01 001
10 110
011
100
010
101

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

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

  1. Печатать его
  1. Печатать его инверсию

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

Псевдокод

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

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

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

Троичный код антигрея

Определение:
Троичный код антигрея — такое упорядочивание троичных вектором, что соседние отличаются во всех разрядах.


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

Пример

n = 1 n = 2 n = 3
0 00 000
1 11 111
2 22 222
01 001
12 112
20 220
02 002
10 110
21 221
010
121
202
011
122
200
012
120
201
020
101
212
021
102
210
022
100
211

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

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

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

Псевдокод

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

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

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

См. также

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Коды_антигрея&oldid=28048»