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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 6 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Код Грея (Gray code)''' {{---}} такое упорядочение <tex>k</tex>-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.
+
'''Код Грея''' (англ. ''Gray code'') {{---}} такое упорядочение <tex>k</tex>-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.
 
}}
 
}}
  
Строка 8: Строка 8:
 
== Алгоритм построения ==  
 
== Алгоритм построения ==  
  
[[Файл:Gray_Code.png|360px|thumb|right|Иллюстрация получения зеркального двоичного кода Грея.]]
+
[[Файл:Gray_Code_Building.png|300px|thumb|right|Получение зеркального двоичного кода Грея.]]
  
Существует несколько видов Кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный Код Грея. Строится он так:
 
  
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй  "1". С каждым шагом длина векторов увеличивается на 1, а их количество {{---}} вдвое.  
+
Существует несколько видов кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный код Грея. Строится он так:
 +
 
 +
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину <tex>1</tex> и состоит из двух векторов <tex>0</tex> и <tex>1</tex>. На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается <tex>0</tex>, а ко второй  <tex>1</tex>. С каждым шагом длина векторов увеличивается на <tex>1</tex>, а их количество {{---}} вдвое.  
 
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
 
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
  
Строка 18: Строка 19:
 
{| border="0"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
GrayCode {{---}} двумерный массив, в котором GrayCode[a, b] {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея.
+
*<tex>\mathtt{GrayCode}</tex> {{---}} двумерный массив типа '''boolean''', в котором <tex>\mathtt{GrayCode[a, b]}</tex> {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея,
<font size=3>
+
*<tex>\mathtt{p}</tex> {{---}} Счетчик количества уже имеющихся кодов,
 +
*<tex>\mathtt{t}</tex> {{---}} Показывает количество кодов в <tex>(a-1)</tex>-м коде Грея.
 +
<code>
 
  buildCode(n):
 
  buildCode(n):
  GrayCode[1, n] = 0
+
    GrayCode[1, n] = ''false''
  GrayCode[2, n] = 1 {построение кода длины 1}
+
    GrayCode[2, n] = ''true''                <font color=green> // Построение кода длины 1 </font>
  p = 2 {p {{---}} количество уже имеющихся кодов}
+
    p = 2
  for (i = 2, i <= n, i++):
+
    '''for''' i = 2 '''to''' n
    p = p * 2
+
      t = p
    for (k = i + 1, k <= 2 * i, k++):
+
      p = p * 2
      GrayCode[k] = GrayCode[p + 1 - k] {отражение имеющихся кодов}
+
      '''for''' k = (p / 2 + 1) '''to''' p
      GrayCode[k - i, n + 1 - i] = 0
+
          GrayCode[k] = GrayCode[t]       <font color=green> // Отражение имеющихся кодов </font>
      GrayCode[k, n + 1 - i] = 1 {добавление 0 и 1 в начало}
+
          GrayCode[t, n + 1 - i] = ''false''
</font>
+
          GrayCode[k, n + 1 - i] = ''true''  <font color=green> // Добавление 0 и 1 в начало </font>
 +
          t--
 +
    '''return''' GrayCode
 +
</code>
 
|}
 
|}
  
Строка 38: Строка 44:
  
 
* на первом шаге код отвечает условиям  
 
* на первом шаге код отвечает условиям  
* предположим, что код, получившийся на <tex>i</tex>-ом шаге, является Кодом Грея
+
* предположим, что код, получившийся на <tex>i</tex>-ом шаге, является кодом Грея
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.  
+
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита <tex>0</tex>. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит <tex>1</tex>. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.  
Таким образом, этот код {{---}} Код Грея. Индукционное предположение доказано, алгоритм работает верно.  
+
Таким образом, этот код {{---}} код Грея. Индукционное предположение доказано, алгоритм работает верно.  
  
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.  
+
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в код Грея.  
  
Существует ещё несколько видов Кода Грея {{---}} сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
+
Существует ещё несколько видов кода Грея {{---}} сбалансированный код Грея, код Баркера-Грея, одноколейный код Грея.<ref>[http://en.wikipedia.org/wiki/Gray_code#Special_types_of_Gray_codes Wikipedia {{---}} Special types of Gray codes]</ref> Кроме того, коды Грея используются для [[:Коды_Грея_для_перестановок|упорядочения перестановок.]]
  
 
== Явная формула для получения зеркального двоичного кода Грея ==
 
== Явная формула для получения зеркального двоичного кода Грея ==
Строка 53: Строка 59:
 
В двоичном зеркальном коде Грея <tex>i</tex>-ый код может быть получен по формуле <tex>G_i = i \oplus (\lfloor i / 2 \rfloor)</tex> при нумерации кодов с нуля.
 
В двоичном зеркальном коде Грея <tex>i</tex>-ый код может быть получен по формуле <tex>G_i = i \oplus (\lfloor i / 2 \rfloor)</tex> при нумерации кодов с нуля.
 
|proof =
 
|proof =
Для кода длиной 1 бит утверждение проверяется непосредственно.
+
Для кода длиной <tex>1</tex> бит утверждение проверяется непосредственно.
  
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i \enskip M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>
+
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i</tex> выполняется <tex>\enspace M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>
  
 
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
 
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
  
Для любого <tex>x < 2^n \enskip L_x = 0M_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) =</tex>
+
Для любого <tex>x < 2^n</tex> выполняется <tex>\enspace L_x = 0M_x</tex> и, по условию, равно
<tex> 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (\lfloor x / 2 \rfloor)</tex>
 
  
Для любого <tex>x \geq 2^n \enskip L_x = 1M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть
+
<tex>L_x = 0(x_{n-1}x_{n-2}  \dots x_{0} \oplus 0x_{n-1}x_{n-2\dots x_{1})</tex> раскрыв скобки, получим новое выражение <tex>L_x</tex>:
  
<tex>L_x = 1(\overline {x_{n-1} x_{n-2}... x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}... x_{1}}) =</tex>
+
<tex>= 0x_{n-1}x_{n-2} \dots x_{0} \oplus 00x_{n-1}x_{n-2} \dots x_{1}</tex> что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)
<tex> 1(\overline {x_{n-1}}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) =</tex>
 
  
<tex>= 1(x_{n-1}x_{n-2}...x_{0} \oplus 1x_{n-1}x_{n-2}...x_{1}) = 1x_{n-1}x_{n-2}...x_{0}</tex>
+
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex>
<tex> \oplus 01x_{n-1}x_{n-2}...x_{1} = x_{n}x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}...x_{1} =</tex>
+
 
<tex> x \oplus (\lfloor x / 2 \rfloor)</tex>
+
Для любого <tex>x \geqslant 2^n</tex> выполняется  <tex>\enspace L_x = 1</tex><tex>M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть
 +
 
 +
<tex>L_x = 1(\overline {x_{n-1} x_{n-2} \dots x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}  \dots x_{1}})</tex> что по свойству '''xor''' (<tex>\neg x \oplus \neg y = x \oplus y</tex>) равно
 +
 
 +
<tex>= 1(\overline {x_{n-1}}x_{n-2}  \dots x_{0} \oplus 0x_{n-1}x_{n-2} \dots x_{1})</tex> или (все по тому же свойству)
 +
 
 +
<tex>= 1(x_{n-1}x_{n-2}  \dots x_{0} \oplus 1x_{n-1}x_{n-2} \dots x_{1})</tex> раскрыв скобки, получим
 +
 
 +
<tex>= 1x_{n-1}x_{n-2}  \dots x_{0} \oplus 01x_{n-1}x_{n-2} \dots x_{1}</tex> откуда получаем, зная из условия, что старший разряд <tex>L_x</tex> равен <tex>1</tex>
 +
 
 +
<tex>= x_{n}x_{n-1}x_{n-2} \dots x_{0} \oplus 0x_{n}x_{n-1}x_{n-2} \dots x_{1}</tex> что, аналогично первому пункту, равно
 +
 
 +
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex>
  
 
Таким образом, шаг индукции доказан, следовательно, теорема верна.
 
Таким образом, шаг индукции доказан, следовательно, теорема верна.
 
}}
 
}}
  
== Специальные типы кодов Грея ==
+
[[Файл:single_track.png|50px|thumb|right|Пример однодорожечного кода грея.]]
 +
 
 
=== Сбалансированный код Грея ===
 
=== Сбалансированный код Грея ===
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно. Чтобы показать это точнее, пусть G - это R-ичный полный цикл Грея, имеющий последовательность перехода <math> (\delta_k)</math>; отсчёты переходов(спектры) G являются наборами целых чисел, определенных как <math>\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \, , \text { for } k \in \mathbb{Z}_R</math>.
+
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно.  
Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть <math>\lambda_k = R^n / n</math> для всех <math>k</math>. Ясно, что при R = 2, такие коды существуют только при n = 2. В противном случае, если <math>R^n</math> не делится на n равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо <math>\lfloor R^n / n \rfloor </math> либо <math> \lceil R^n / n \rceil</math>. Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.
+
 
 +
Чтобы показать это точнее, пусть <tex>G</tex> {{---}} это <tex>R</tex>-ичный полный цикл Грея, имеющий последовательность перехода <tex>(\delta_k)</tex>, <tex>\delta_k = i</tex>, для <tex>k = 0 \dots n</tex> если в коде Грея <tex>i</tex>-й и <tex>(i+1)</tex> биты различны и <tex>n</tex> {{---}} кол-во таких различий; отсчёты переходов (спектры) <tex>G</tex> являются наборами целых чисел, определенных как <tex>\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \,</tex> для <tex> k \in \mathbb{Z}_R</tex>.
 +
 
 +
Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть <tex>\lambda_k = R^n / n</tex> для всех <tex>k</tex>. Ясно, что при <tex>R = 2</tex>, такие коды существуют только при <tex>n = 2</tex>. В противном случае, если <tex>R^n</tex> не делится на <tex>n</tex> равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо <tex>\lfloor R^n / n \rfloor </tex> либо <tex> \lceil R^n / n \rceil</tex>.  
 +
 
 +
Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.
 +
 
 
=== Однодорожечный код Грея ===
 
=== Однодорожечный код Грея ===
Еще один вид кода Грея - это однодорожечный код Грея. Разработан Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини. Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины n так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как <math>P_{xn}</math> матрица, каждая колонка - это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся 0 или 1. Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в 1 градус нужно, по крайней мере, 360 различных позиций на оборот, который требует минимум 9 бит данных, и тем самым такое же количество контактов.
+
Еще один вид кода Грея {{---}} это однодорожечный код Грея, разработанный Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини.  
 +
 
 +
Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины <tex>n</tex> так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как <tex>P_{xn}</tex> матрица, каждая колонка {{---}} это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся <tex>0</tex> или <tex>1</tex>.  
 +
 
 +
Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в <tex>1</tex> градус нужно, по крайней мере, <tex>360</tex> различных позиций на оборот, который требует минимум <tex>9</tex> бит данных, и тем самым такое же количество контактов.
 +
 
 +
'''Не путать''' с [[:Цепные_коды|цепными кодами]], получаемых циклическим сдвигом.
 +
 
 
== Применение ==
 
== Применение ==
Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. "PCM трубка" - аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из Bell Labs, работая с Греем и Уильямом М. Гудоллом.
+
 
[[Файл:PCM_Tube.png|500px|thumb|center|Часть первой страницы патента Грея, показывающая PCM трубку с отраженным двоичным кодом в тарелке.]]
+
Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. "PCM трубка" {{---}} аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из (англ.) Bell Labs, работая с Греем и Уильямом М. Гудоллом.
* В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в [http://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%BA%D0%BE%D0%B4%D0%B5%D1%80 датчиках-энкодерах]). В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в M-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в M-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея. Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из <math>k = log_2 M</math> переданных битов.)  
+
 
 +
* В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках-энкодерах <ref>[http://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%BA%D0%BE%D0%B4%D0%B5%D1%80 Википедия {{---}} Датчик угла поворота]</ref>).  
 +
 
 +
В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в <tex>M</tex>-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в <tex>M</tex>-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея.  
 +
 
 +
Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из <tex>k = \log_2 M</tex> переданных битов.)  
 +
 
 
* Коды Грея используются для кодирования номера дорожек в жёстких дисках.
 
* Коды Грея используются для кодирования номера дорожек в жёстких дисках.
* Код Грея можно использовать также и для решения задачи о [http://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B8%D0%B5_%D0%B1%D0%B0%D1%88%D0%BD%D0%B8 Ханойских башнях]:
+
 
 +
* Коды Грея широко применяются в теории генетических алгоритмов <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC Википедия {{---}} Генетический алгоритм]</ref> для кодирования генетических признаков, представленных целыми числами.
 +
 
 +
* Коды Грея используются в Картах Карно<ref>[http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D1%8B_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Википедия {{---}} Карта Карно]</ref> (при передаче в карту переменные сортируются в код Грея).
 +
 
 +
* Алгоритм модуляции 2B1Q (англ. ''2 Binary 1 Quandary'') <ref>[http://en.wikipedia.org/wiki/2B1Q Wikipedia {{---}} 2B1Q]</ref>
 +
 
 +
* Код Грея можно использовать также и для решения следующей задачи<ref>[http://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B8%D0%B5_%D0%B1%D0%B0%D1%88%D0%BD%D0%B8 Википедия {{---}} Ханойская Башня]</ref>:
 +
=== Задача о Ханойских башнях ===
 +
 
 
{{задача
 
{{задача
 
|definition =
 
|definition =
Пусть n — количество дисков. Начнём с кода Грея длины n, состоящего из одних нулей (т.е. G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому i-ому биту текущего кода Грея i-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита i как перемещение i-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если n нечётно, то последовательность перемещений наименьшего диска имеет вид <math>f \rightarrow t \rightarrow r \rightarrow f \rightarrow t \rightarrow r \rightarrow \ldots .</math>(где f — стартовый стержень, t — финальный стержень, r — оставшийся стержень), а если n чётно, то <math>f \rightarrow r \rightarrow t \rightarrow f \rightarrow r \rightarrow t \rightarrow \ldots.</math>
+
Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
 
}}
 
}}
* Коды Грея широко применяются в теории [http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC генетических алгоритмов] для кодирования генетических признаков, представленных целыми числами.
+
'''Решение:'''
* Коды Грея используются в [http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D1%8B_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Картах Карно] (при передаче в карту переменные сортируются в Код Грея).
+
 
 +
Пусть <tex>n</tex> — количество дисков. Начнём с кода Грея длины <tex>n</tex>, состоящего из одних нулей (т.е. <tex>G(0)</tex>), и будем двигаться по кодам Грея (от <tex>G(i)</tex> переходить к <tex>G(i+1)</tex>).
 +
 
 +
Поставим в соответствие каждому <tex>i</tex>-ому биту текущего кода Грея <tex>i</tex>-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита <tex>i</tex> как перемещение <tex>i</tex>-го диска. То есть, будем понимать переход от последовательности <tex>101</tex> к <tex>100</tex> как перемещение <tex>0</tex>-го диска на свободное место, а от <tex>010</tex> к <tex>110</tex> {{---}} как перемещение <tex>2</tex>-го диска на свободное место.
 +
 
 +
Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для самого маленького диска всегда есть две свободные позиции, потому что он самый маленький, его можно положить сверху на любой диск. Если диск не самый маленький, то для него может быть не более одной свободной позиции. Допустим, что для него свободные две позиции. Это означает, что на двух других стержнях расположены диски размером больше, чем рассматриваемый. А так как рассматриваемый диск не самый маленький, то где-то расположен наименьший. Либо он расположен на рассматриваемом диске, тогда мы не можем переместить рассматриваемый, либо на каком-то другом, но тогда у нашего диска остаётся не более одной свободной позиции. Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <tex>n</tex> нечётно, то последовательность перемещений наименьшего диска имеет вид <tex>r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow \ldots .</tex>(где <tex>r_{1}</tex> — стартовый стержень, <tex>r_{3}</tex> — финальный стержень, <tex>r_{2}</tex> — оставшийся стержень), а если <tex>n</tex> чётно, то <tex>r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow \ldots.</tex>
 +
 
 +
Выбор обусловлен тем, на каком стержне окажется в конце пирамидка, решение с помощью кода Грея является следствием классического нерекурсивного решения<ref>[https://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution Wikipedia {{---}} Tower of Hanoi Non-recursive solution]</ref>.
 +
 
 +
==См. Также==
 +
 
 +
*[[:Коды_антигрея|Коды антигрея]]
 +
 
 +
==Примечания==
 +
 
 +
<references />
  
== Источники ==
+
== Источники информации ==
  
* [http://en.wikipedia.org/wiki/Gray_code Gray code, From Wikipedia, the free encyclopedia]
+
* [http://en.wikipedia.org/wiki/Gray_code Wikipedia {{---}} Gray code]
  
* [http://ru.wikipedia.org/wiki/Код_Грея Код Грея, Материал из Википедии — свободной энциклопедии]
+
* [http://ru.wikipedia.org/wiki/код_Грея Википедия {{---}} Код Грея]
  
 +
* [http://www.jucs.org/jucs_13_11/the_gray_code/jucs_13_11_1573_1597_doran.pdf Robert W. Doran The Gray Code, Journal of Universal Computer Science, vol. 13, no. 11 (2007).]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

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

Определение:
Код Грея (англ. Gray code) — такое упорядочение [math]k[/math]-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.


Код назван в честь Фрэнка Грея, который в 1947-ом году получил патент на "отражённый двоичный код".

Алгоритм построения

Получение зеркального двоичного кода Грея.


Существует несколько видов кода Грея, самый простой из них — так называемый зеркальный двоичный код Грея. Строится он так:

Для получения кода длины [math]n[/math] производится [math]n[/math] шагов. На первом шаге код имеет длину [math]1[/math] и состоит из двух векторов [math]0[/math] и [math]1[/math]. На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается [math]0[/math], а ко второй [math]1[/math]. С каждым шагом длина векторов увеличивается на [math]1[/math], а их количество — вдвое. Таким образом, количество векторов длины [math]n[/math] равно [math]2^n.[/math]

Псевдокод

  • [math]\mathtt{GrayCode}[/math] — двумерный массив типа boolean, в котором [math]\mathtt{GrayCode[a, b]}[/math][math]b[/math]-ый бит в [math]a[/math]-ом коде Грея,
  • [math]\mathtt{p}[/math] — Счетчик количества уже имеющихся кодов,
  • [math]\mathtt{t}[/math] — Показывает количество кодов в [math](a-1)[/math]-м коде Грея.

buildCode(n):
   GrayCode[1, n] = false
   GrayCode[2, n] = true                  // Построение кода длины 1 
   p = 2
   for i = 2 to n
      t = p
      p = p * 2
      for k = (p / 2 + 1) to p
         GrayCode[k] = GrayCode[t]        // Отражение имеющихся кодов 
         GrayCode[t, n + 1 - i] = false
         GrayCode[k, n + 1 - i] = true    // Добавление 0 и 1 в начало 
         t--
   return GrayCode 

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

По индукции:

  • на первом шаге код отвечает условиям
  • предположим, что код, получившийся на [math]i[/math]-ом шаге, является кодом Грея
  • тогда на шаге [math]i + 1[/math]: первая половина кода будет корректна, так как она совпадает с кодом с шага [math]i[/math] за исключением добавленного последнего бита [math]0[/math]. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит [math]1[/math]. На стыке: первые [math]i[/math] бит совпадают в силу зеркальности, последние различны по построению.

Таким образом, этот код — код Грея. Индукционное предположение доказано, алгоритм работает верно.

Этот алгоритм можно обобщить и для [math]k[/math]-ичных векторов. Также известен алгоритм преобразования двоичного кода в код Грея.

Существует ещё несколько видов кода Грея — сбалансированный код Грея, код Баркера-Грея, одноколейный код Грея.[1] Кроме того, коды Грея используются для упорядочения перестановок.

Явная формула для получения зеркального двоичного кода Грея

Теорема:
В двоичном зеркальном коде Грея [math]i[/math]-ый код может быть получен по формуле [math]G_i = i \oplus (\lfloor i / 2 \rfloor)[/math] при нумерации кодов с нуля.
Доказательство:
[math]\triangleright[/math]

Для кода длиной [math]1[/math] бит утверждение проверяется непосредственно.

Пусть существует зеркальный двоичный код Грея [math]M[/math] длины [math]n[/math], для которого выполнено, что для любого [math]i[/math] выполняется [math]\enspace M_i = i \oplus (\lfloor i / 2 \rfloor)[/math]

Обозначим за [math]L[/math] код длины [math]n + 1[/math], полученный из [math]M[/math] описанным выше алгоритмом. Тогда:

Для любого [math]x \lt 2^n[/math] выполняется [math]\enspace L_x = 0M_x[/math] и, по условию, равно

[math]L_x = 0(x_{n-1}x_{n-2} \dots x_{0} \oplus 0x_{n-1}x_{n-2} \dots x_{1})[/math] раскрыв скобки, получим новое выражение [math]L_x[/math]:

[math]= 0x_{n-1}x_{n-2} \dots x_{0} \oplus 00x_{n-1}x_{n-2} \dots x_{1}[/math] что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)

[math]= x \oplus (\lfloor x / 2 \rfloor)[/math]

Для любого [math]x \geqslant 2^n[/math] выполняется [math]\enspace L_x = 1[/math][math]M_y[/math], где [math]y = 2^{n+1} - 1 - x = \neg x[/math], то есть

[math]L_x = 1(\overline {x_{n-1} x_{n-2} \dots x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2} \dots x_{1}})[/math] что по свойству xor ([math]\neg x \oplus \neg y = x \oplus y[/math]) равно

[math]= 1(\overline {x_{n-1}}x_{n-2} \dots x_{0} \oplus 0x_{n-1}x_{n-2} \dots x_{1})[/math] или (все по тому же свойству)

[math]= 1(x_{n-1}x_{n-2} \dots x_{0} \oplus 1x_{n-1}x_{n-2} \dots x_{1})[/math] раскрыв скобки, получим

[math]= 1x_{n-1}x_{n-2} \dots x_{0} \oplus 01x_{n-1}x_{n-2} \dots x_{1}[/math] откуда получаем, зная из условия, что старший разряд [math]L_x[/math] равен [math]1[/math]

[math]= x_{n}x_{n-1}x_{n-2} \dots x_{0} \oplus 0x_{n}x_{n-1}x_{n-2} \dots x_{1}[/math] что, аналогично первому пункту, равно

[math]= x \oplus (\lfloor x / 2 \rfloor)[/math]

Таким образом, шаг индукции доказан, следовательно, теорема верна.
[math]\triangleleft[/math]
Пример однодорожечного кода грея.

Сбалансированный код Грея

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

Чтобы показать это точнее, пусть [math]G[/math] — это [math]R[/math]-ичный полный цикл Грея, имеющий последовательность перехода [math](\delta_k)[/math], [math]\delta_k = i[/math], для [math]k = 0 \dots n[/math] если в коде Грея [math]i[/math]-й и [math](i+1)[/math] биты различны и [math]n[/math] — кол-во таких различий; отсчёты переходов (спектры) [math]G[/math] являются наборами целых чисел, определенных как [math]\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \,[/math] для [math] k \in \mathbb{Z}_R[/math].

Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть [math]\lambda_k = R^n / n[/math] для всех [math]k[/math]. Ясно, что при [math]R = 2[/math], такие коды существуют только при [math]n = 2[/math]. В противном случае, если [math]R^n[/math] не делится на [math]n[/math] равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо [math]\lfloor R^n / n \rfloor [/math] либо [math] \lceil R^n / n \rceil[/math].

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

Однодорожечный код Грея

Еще один вид кода Грея — это однодорожечный код Грея, разработанный Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини.

Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины [math]n[/math] так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как [math]P_{xn}[/math] матрица, каждая колонка — это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся [math]0[/math] или [math]1[/math].

Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в [math]1[/math] градус нужно, по крайней мере, [math]360[/math] различных позиций на оборот, который требует минимум [math]9[/math] бит данных, и тем самым такое же количество контактов.

Не путать с цепными кодами, получаемых циклическим сдвигом.

Применение

Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. "PCM трубка" — аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из (англ.) Bell Labs, работая с Греем и Уильямом М. Гудоллом.

  • В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках-энкодерах [2]).

В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в [math]M[/math]-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в [math]M[/math]-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея.

Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из [math]k = \log_2 M[/math] переданных битов.)

  • Коды Грея используются для кодирования номера дорожек в жёстких дисках.
  • Коды Грея широко применяются в теории генетических алгоритмов [3] для кодирования генетических признаков, представленных целыми числами.
  • Коды Грея используются в Картах Карно[4] (при передаче в карту переменные сортируются в код Грея).
  • Алгоритм модуляции 2B1Q (англ. 2 Binary 1 Quandary) [5]
  • Код Грея можно использовать также и для решения следующей задачи[6]:

Задача о Ханойских башнях

Задача:
Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Решение:

Пусть [math]n[/math] — количество дисков. Начнём с кода Грея длины [math]n[/math], состоящего из одних нулей (т.е. [math]G(0)[/math]), и будем двигаться по кодам Грея (от [math]G(i)[/math] переходить к [math]G(i+1)[/math]).

Поставим в соответствие каждому [math]i[/math]-ому биту текущего кода Грея [math]i[/math]-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита [math]i[/math] как перемещение [math]i[/math]-го диска. То есть, будем понимать переход от последовательности [math]101[/math] к [math]100[/math] как перемещение [math]0[/math]-го диска на свободное место, а от [math]010[/math] к [math]110[/math] — как перемещение [math]2[/math]-го диска на свободное место.

Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для самого маленького диска всегда есть две свободные позиции, потому что он самый маленький, его можно положить сверху на любой диск. Если диск не самый маленький, то для него может быть не более одной свободной позиции. Допустим, что для него свободные две позиции. Это означает, что на двух других стержнях расположены диски размером больше, чем рассматриваемый. А так как рассматриваемый диск не самый маленький, то где-то расположен наименьший. Либо он расположен на рассматриваемом диске, тогда мы не можем переместить рассматриваемый, либо на каком-то другом, но тогда у нашего диска остаётся не более одной свободной позиции. Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если [math]n[/math] нечётно, то последовательность перемещений наименьшего диска имеет вид [math]r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow \ldots .[/math](где [math]r_{1}[/math] — стартовый стержень, [math]r_{3}[/math] — финальный стержень, [math]r_{2}[/math] — оставшийся стержень), а если [math]n[/math] чётно, то [math]r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow \ldots.[/math]

Выбор обусловлен тем, на каком стержне окажется в конце пирамидка, решение с помощью кода Грея является следствием классического нерекурсивного решения[7].

См. Также

Примечания

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