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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство корректности алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 5 участников)
Строка 1: Строка 1:
== Определение ==
 
 
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Код антигрея (Anti-Gray Code)''' {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.  
+
'''Код антигрея''' (англ. ''Anti-Gray Code'') {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.  
 
}}
 
}}
 
 
Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.
 
Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.
  
Строка 11: Строка 8:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
+
'''Двоичный код антигрея''' (англ. ''Binary Anti-Gray Code'') {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
 
}}
 
}}
 
+
Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для <tex>n = 1</tex>. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где <tex>n > 1</tex>, таких векторов должно быть два.
Заметим, что для <tex>n > 2</tex> невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2.
 
  
 
=== Пример ===
 
=== Пример ===
Строка 48: Строка 44:
  
 
=== Псевдокод ===
 
=== Псевдокод ===
 
+
   '''function''' genBinAntiGray(n: '''int'''):
   genBinAntiGray(n)
+
     '''for''' i = 1 '''to''' 2 ** (n - 1)
     for i = 1 to 2^(n-1)
 
 
       v = getMirrorGray(i, n)
 
       v = getMirrorGray(i, n)
 
       print(v)
 
       print(v)
Строка 58: Строка 53:
 
=== Доказательство корректности алгоритма ===
 
=== Доказательство корректности алгоритма ===
  
Обозначим за <tex dpi = "140">G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex dpi = "140">\bar G_i</tex> — его инверсию.  
+
Обозначим за <tex>G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex>\overline G_i</tex> — его инверсию.  
 
Тогда вектора будут располагаться в таком порядке:
 
Тогда вектора будут располагаться в таком порядке:
  ... <br>
+
:<tex>\dots</tex> <br>
  <tex dpi="120">G_i</tex> <br>
+
:<tex>G_i</tex> <br>
  <tex dpi="120">\bar G_i</tex> <br>
+
:<tex>\overline G_i</tex> <br>
  <tex dpi="120">G_{i+1}</tex> <br>
+
:<tex>G_{i+1}</tex> <br>
  <tex dpi="120">\bar G_{i+1}</tex> <br>
+
:<tex>\overline G_{i+1}</tex> <br>
  <tex dpi="120">G_{i+2}</tex> <br>
+
:<tex>G_{i+2}</tex> <br>
  ...
+
:<tex>\dots</tex>
* <tex dpi = "140">G_i</tex> и <tex dpi = "140">\bar G_i</tex> отличаются во всех битах.
+
<tex>G_i</tex> и <tex>\overline G_i</tex> отличаются во всех битах. <br>
* Если <tex dpi = "140">G_i</tex> и <tex dpi = "140">G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex dpi = "140">G_i</tex> совпадает с <tex dpi = "140">G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex dpi = "140">\bar G_i</tex> и <tex dpi = "140">G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
+
Если <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=
 
|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>.
 +
 +
Утверждается, что выполняя эти действия мы получим троичный код антигрея.
  
В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
+
=== Псевдокод ===
 +
<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>-ичного кода антигрея.
  
=== Пример ===
+
=== Примеры работы алгоритма ===
  
 
{| class="wikitable"
 
{| class="wikitable"
!style="width:45px"| n = 1  
+
!colspan="2" align="center"| n = 1  
!style="width:45px"| n = 2  
+
!colspan="2" align="center"| n = 2  
!colspan="3" align="center" style="width:135px"| n = 3
+
!colspan="3" align="center"| n = 3
 +
|-
 +
!align="center"|Первые <tex>3^{n-1}</tex><br>векторов
 +
!align="center"|Коды антигрея
 +
!align="center"|Первые <tex>3^{n-1}</tex><br>векторов
 +
!align="center"|Коды антигрея
 +
!align="center"|Первые <tex>3^{n-1}</tex><br>векторов
 +
!colspan="2" align="center"|Коды антигрея
 +
|-
 +
| '''0''' || '''0''' || '''00''' || '''00''' || '''000''' || '''000''' || 200
 +
|-
 +
| || 1 || '''01''' || 11 || '''001''' || 111 || '''012'''
 
|-
 
|-
| 0 || 00 || 000 || 010 || 020
+
| || 2 || '''02''' || 22 || '''002''' || 222 || 120
 
|-
 
|-
| 1 || 11 || 111 || 121 || 101
+
| || || || '''01''' || '''010''' || '''001''' || 201
 
|-
 
|-
| 2 || 22 || 222 || 202 || 212
+
| || || || 12 || '''011''' || 112 || '''020'''
 
|-
 
|-
| || 01 || 001 || 011 || 021
+
| || || || 20 || '''012''' || 220 || 101
 
|-
 
|-
| || 12 || 112 || 122 || 102
+
| || || || '''02''' || '''020''' || '''002''' || 212
 
|-
 
|-
| || 20 || 220 || 200 || 210
+
| || || || 10 || '''021''' || 110 || '''021'''
 
|-
 
|-
| || 02 || 002 || 012 || 022
+
| || || || 21 || '''022''' || 221 || 102
 
|-
 
|-
| || 10 || 110 || 120 || 100
+
| || || || || || '''010''' || 210
 
|-
 
|-
| || 21 || 221 || 201 || 211
+
| || || || || || 121 || '''022'''
 +
|-
 +
| || || || || || 202 || 100
 +
|-
 +
| || || || || || '''011''' || 211
 +
|-
 +
| || || || || || 122 ||
 
|}
 
|}
 
=== Алгоритм генерации ===
 
 
Упорядочим все троичные вектора лексикографически. Тогда для первых <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>-ичного кода антигрея.
 
  
 
=== Доказательство корректности алгоритма ===
 
=== Доказательство корректности алгоритма ===
  
Обозначим <tex>i</tex>-ый троичный вектор как <tex dpi="140">G_i^0</tex>, его первый и второй циклический сдвиги как <tex dpi="140" >G_i^1</tex> и <tex dpi="140">G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
+
Обозначим <tex>i</tex>-ый троичный вектор как <tex>G_i^0</tex>, его первый и второй циклический сдвиги как <tex>G_i^1</tex> и <tex>G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
  ... <br>
+
:<tex>\dots</tex> <br>
  <tex dpi="120">G_i^0</tex> <br>
+
:<tex>G_i^0</tex> <br>
  <tex dpi="120">G_i^1</tex> <br>
+
:<tex>G_i^1</tex> <br>
  <tex dpi="120">G_i^2</tex> <br>
+
:<tex>G_i^2</tex> <br>
  <tex dpi="120">G_{i+1}^0</tex> <br>
+
:<tex>G_{i+1}^0</tex> <br>
  ...
+
:<tex>\dots</tex>
* <tex dpi = "140">G_i^0</tex> и <tex dpi = "140">G_i^1</tex>, равно как <tex dpi = "140">G_i^1</tex> и <tex dpi = "140">G_i^2</tex>, отличаются во всех битах.
+
<tex >G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах. <br>
* Если говорить о векторах как о троичных числах, то <tex dpi = "140">G_{i+1}^0</tex> получено из <tex dpi = "140">G_i^0</tex> прибавлением единицы, это значит, что у <tex dpi = "140">G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex dpi = "140">G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex dpi = "140">G_{i}^2</tex> получено из <tex dpi = "140">G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex dpi = "140">G_{i+1}^0</tex> некоторые биты такие же, как в <tex dpi = "140">G_{i}^0</tex>, остальные на единицу больше; в числе <tex dpi = "140">G_{i}^2</tex> все биты на один меньше по сравнению с <tex dpi = "140">G_{i}^0</tex>, значит <tex dpi = "140">G_{i}^2</tex> и <tex dpi = "140">G_{i+1}^0</tex> различны во всех битах.
+
Если говорить о векторах как о троичных числах, то <tex>G_{i+1}^0</tex> получено из <tex>G_i^0</tex> прибавлением единицы, это значит, что у <tex>G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex>G_i^0</tex> (по правилам сложения в столбик). С другой стороны <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 \ge 3</tex>.
+
Подобные рассуждения можно провести для любого <tex>k</tex>-ичного кода антигрея, где <tex>k \geqslant 3</tex>.
  
 
== См. также ==
 
== См. также ==
Строка 140: Строка 151:
 
*[[Цепные коды]]
 
*[[Цепные коды]]
  
== Источники ==
+
== Источники информации ==
 +
 
 +
*[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]
+
[[Категория: Комбинаторика]]

Текущая версия на 19:03, 4 сентября 2022

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

Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.

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

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

Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для [math]n = 1[/math]. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где [math]n \gt 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. Печатать двоичный вектор
  2. Печатать его инверсию

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

Псевдокод

 function genBinAntiGray(n: int):
   for i = 1 to 2 ** (n - 1)
     v = getMirrorGray(i, n)
     print(v)
     inverseBits(v)
     print(v)

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

Обозначим за [math]G_i[/math][math]i[/math]-ый вектор в зеркальном коде Грея, [math]\overline G_i[/math] — его инверсию. Тогда вектора будут располагаться в таком порядке:

[math]\dots[/math]
[math]G_i[/math]
[math]\overline G_i[/math]
[math]G_{i+1}[/math]
[math]\overline G_{i+1}[/math]
[math]G_{i+2}[/math]
[math]\dots[/math]

[math]G_i[/math] и [math]\overline G_i[/math] отличаются во всех битах.
Если [math]G_i[/math] и [math]G_{i+1}[/math] отличаются в [math]k[/math]-ом бите, то инверсия [math]G_i[/math] совпадает с [math]G_{i+1}[/math] только в [math]k[/math]-ом бите. То есть [math]\overline G_i[/math] и [math]G_{i+1}[/math] отличаются во всех позициях, кроме [math]k[/math]-ой.

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

Определение:
Троичный код антигрея (англ. Ternary Anti-Gray Code) — такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.

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

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

Упорядочим все троичные вектора лексикографически. Тогда для первых [math]3^{n-1}[/math] векторов будем выводить сначала сам этот вектор, потом [math]2[/math] его поразрядных циклических сдвига (каждый отдельный бит увеличиваем на [math]1[/math]).
Например, если мы имеем вектор [math]021[/math], то вы выведем: [math]021[/math], [math]102[/math], [math]210[/math].

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

Псевдокод

 function genTernAntiGray(n: int):
   for v = <000..0> to <022..2> // троичные вектора длины [math]n[/math] 
     for i = 0 to 2
       print(v)
       digitCircleShift(v)

Заметим, что данный алгоритм можно обобщить на случай [math]k[/math]-ичного кода антигрея.

Примеры работы алгоритма

n = 1 n = 2 n = 3
Первые [math]3^{n-1}[/math]
векторов
Коды антигрея Первые [math]3^{n-1}[/math]
векторов
Коды антигрея Первые [math]3^{n-1}[/math]
векторов
Коды антигрея
0 0 00 00 000 000 200
1 01 11 001 111 012
2 02 22 002 222 120
01 010 001 201
12 011 112 020
20 012 220 101
02 020 002 212
10 021 110 021
21 022 221 102
010 210
121 022
202 100
011 211
122

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

Обозначим [math]i[/math]-ый троичный вектор как [math]G_i^0[/math], его первый и второй циклический сдвиги как [math]G_i^1[/math] и [math]G_i^2[/math] соответственно. Получаем вектора в следующем порядке:

[math]\dots[/math]
[math]G_i^0[/math]
[math]G_i^1[/math]
[math]G_i^2[/math]
[math]G_{i+1}^0[/math]
[math]\dots[/math]

[math]G_i^0[/math] и [math]G_i^1[/math], равно как [math]G_i^1[/math] и [math]G_i^2[/math], отличаются во всех битах.
Если говорить о векторах как о троичных числах, то [math]G_{i+1}^0[/math] получено из [math]G_i^0[/math] прибавлением единицы, это значит, что у [math]G_{i+1}^0[/math] несколько разрядов справа на единицу больше (по модулю [math]3[/math]), чем у [math]G_i^0[/math] (по правилам сложения в столбик). С другой стороны [math]G_{i}^2[/math] получено из [math]G_{i}^0[/math] двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе [math]G_{i+1}^0[/math] некоторые биты такие же, как в [math]G_{i}^0[/math], остальные на единицу больше; в числе [math]G_{i}^2[/math] все биты на один меньше по сравнению с [math]G_{i}^0[/math], значит [math]G_{i}^2[/math] и [math]G_{i+1}^0[/math] различны во всех битах. Подобные рассуждения можно провести для любого [math]k[/math]-ичного кода антигрея, где [math]k \geqslant 3[/math].

См. также

Источники информации