Редактирование: Коды Грея

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 8: Строка 8:
 
== Алгоритм построения ==  
 
== Алгоритм построения ==  
  
[[Файл:Gray_Code_Building.png|300px|thumb|right|Получение зеркального двоичного кода Грея.]]
+
[[Файл:Gray_Code_Building.png|440px|thumb|right|Получение зеркального двоичного кода Грея.]]
  
  
Строка 19: Строка 19:
 
{| border="0"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
*<tex>\mathtt{GrayCode}</tex> {{---}} двумерный массив типа '''boolean''', в котором <tex>\mathtt{GrayCode[a, b]}</tex> {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея,
+
<tex>GrayCode</tex> {{---}} двумерный массив, в котором <tex>GrayCode[a, b]</tex> {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея.
*<tex>\mathtt{p}</tex> {{---}} Счетчик количества уже имеющихся кодов,
 
*<tex>\mathtt{t}</tex> {{---}} Показывает количество кодов в <tex>(a-1)</tex>-м коде Грея.
 
 
<code>
 
<code>
 
  buildCode(n):
 
  buildCode(n):
     GrayCode[1, n] = ''false''
+
     GrayCode[1, n] = 0
     GrayCode[2, n] = ''true''                <font color=green> // Построение кода длины 1 </font>
+
     GrayCode[2, n] = 1                <font color=green> // Построение кода длины 1 </font>
     p = 2
+
     p = 2                             <font color=green> // Где p {{---}} количество уже имеющихся кодов </font>
 
     '''for''' i = 2 '''to''' n
 
     '''for''' i = 2 '''to''' n
 
       t = p
 
       t = p
 
       p = p * 2
 
       p = p * 2
 
       '''for''' k = (p / 2 + 1) '''to''' p
 
       '''for''' k = (p / 2 + 1) '''to''' p
           GrayCode[k] = GrayCode[t]       <font color=green> // Отражение имеющихся кодов </font>
+
           GrayCode[k] = GrayCode[t]   <font color=green> // Отражение имеющихся кодов </font>
           GrayCode[t, n + 1 - i] = ''false''
+
           GrayCode[t, n + 1 - i] = 0
           GrayCode[k, n + 1 - i] = ''true''  <font color=green> // Добавление 0 и 1 в начало </font>
+
           GrayCode[k, n + 1 - i] = <font color=green> // Добавление 0 и 1 в начало </font>
 
           t--
 
           t--
    '''return''' GrayCode
 
 
</code>
 
</code>
 
|}
 
|}
Строка 61: Строка 58:
 
Для кода длиной <tex>1</tex> бит утверждение проверяется непосредственно.
 
Для кода длиной <tex>1</tex> бит утверждение проверяется непосредственно.
  
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i</tex> выполняется <tex>\enspace M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>
+
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i</tex> выполняется <tex>е\enskip 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</tex> выполняется <tex>\enspace L_x = 0M_x</tex> и, по условию, равно
+
Для любого <tex>x < 2^n</tex> выполняется <tex>\enskip L_x = 0M_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 = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1})</tex> раскрыв скобки, получим новое выражение <tex>L_x</tex>:
  
<tex>= 0x_{n-1}x_{n-2} \dots x_{0} \oplus 00x_{n-1}x_{n-2} \dots x_{1}</tex> что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)
+
<tex>= 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1}</tex> что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)
  
 
<tex>= x \oplus (\lfloor x / 2 \rfloor)</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>x \geq 2^n</tex> выполняется  <tex>\enskip 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>L_x = 1(\overline {x_{n-1} x_{n-2}... x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}... 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(\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} \dots x_{0} \oplus 1x_{n-1}x_{n-2} \dots x_{1})</tex> раскрыв скобки, получим
+
<tex>= 1(x_{n-1}x_{n-2}...x_{0} \oplus 1x_{n-1}x_{n-2}...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>= 1x_{n-1}x_{n-2}...x_{0} \oplus 01x_{n-1}x_{n-2}...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_{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 \oplus (\lfloor x / 2 \rfloor)</tex>
Строка 95: Строка 92:
 
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно.  
 
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно.  
  
Чтобы показать это точнее, пусть <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>G</tex> {{---}} это <tex>R</tex>-ичный полный цикл Грея, имеющий последовательность перехода <tex>(\delta_k)</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>.  
 
Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть <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>.  
Строка 108: Строка 105:
 
Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в <tex>1</tex> градус нужно, по крайней мере, <tex>360</tex> различных позиций на оборот, который требует минимум <tex>9</tex> бит данных, и тем самым такое же количество контактов.
 
Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в <tex>1</tex> градус нужно, по крайней мере, <tex>360</tex> различных позиций на оборот, который требует минимум <tex>9</tex> бит данных, и тем самым такое же количество контактов.
  
'''Не путать''' с [[:Цепные_коды|цепными кодами]], получаемых циклическим сдвигом.
+
'''Не путать''' с [[:Цепные_коды|цепными кодами.]], получаемых циклическим сдвигом
  
 
== Применение ==
 
== Применение ==
Строка 139: Строка 136:
 
Пусть <tex>n</tex> — количество дисков. Начнём с кода Грея длины <tex>n</tex>, состоящего из одних нулей (т.е. <tex>G(0)</tex>), и будем двигаться по кодам Грея (от <tex>G(i)</tex> переходить к <tex>G(i+1)</tex>).  
 
Пусть <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>i</tex>-ому биту текущего кода Грея <tex>i</tex>-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита <tex>i</tex> как перемещение <tex>i</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>
+
Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <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>.
 
 
 
==См. Также==
 
 
 
*[[:Коды_антигрея|Коды антигрея]]
 
  
 
==Примечания==
 
==Примечания==
Строка 163: Строка 154:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 +
 +
==См. Также==
 +
 +
[[:Коды_антигрея|Коды антигрея]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)