|
</pre>
|-
|
| <span style="font-size:smaller;">4-битный код Грея</span>
<pre>
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
</pre>
|}
'''Код Гре́я''' — [[двоичный код]], иначе зеркальный код, он же код с отражением, в котором две «соседние» ([[Лексикографический порядок|в упорядоченном, то есть лексикографическом, наборе]]) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, [[расстояние Хэмминга]] между соседними кодовыми комбинациями равно 1.
Наиболее часто на практике применяется '''рефлексивный [[двоичный код]] Грея''', хотя в общем случае существует бесконечное множество кодов Грея со значениями цифр в разрядах, взятых из различных алфавитов. В большинстве случаев, под термином «код Грея» понимают именно рефлексивный бинарный код Грея.
Изначально предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и [[Обнаружение и исправление ошибок|исправления ошибок]] в системах связи, а также в формировании сигналов обратной связи в системах управления.
== Название ==
Код Грея назван «рефлексивным» (отражённым) из-за того, что первая половина значений при изменении порядка эквивалентна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется (см. [[самоподобие]]).
Код назван в честь исследователя {{iw|Грей, Фрэнк|Фрэнка Грея|en|Frank Gray (researcher)}}, работавшего в лаборатории «[[Bell Labs|Bell labs]]». Грей запатентовал (патент № 2632058) и впервые использовал этот код в своей импульсной системе связи.
== Применения ==
Код Грея используется в передаче меняющихся цифровых сигналов в отсутствие [[Тактовый сигнал|тактового сигнала синхронизации]] (например, во многих видах датчиков). Представим себе, что код (обычный двоичный) перескакивает 3→4, или {{nobr|011<sub>2</sub> → 100<sub>2</sub>}}. Если из-за несовершенства считывателя мы прочитаем первый бит от 011, а остальные два — от 100, мы получим 000<sub>2</sub>=0 — число, далёкое от реальных значений. В коде Грея никаких посторонних значений не будет: перескок будет в одном разряде, {{nobr|010<sub>G</sub> → 110<sub>G</sub>}}, и мы считаем либо старое 010<sub>G</sub>=3, либо новое 110<sub>G</sub>=4.
Если считыватель настолько медленный, что за время считывания показания несколько раз сменились, код Грея гарантирует, что ошибка будет невелика — меньше, чем реальное изменение сигнала. Например, если за время считывания показания сменились {{nobr|1=010<sub>G</sub>=3 → 110<sub>G</sub> → 111<sub>G</sub>=5}}, то помимо этих трёх значений, можно получить {{nobr|1=011<sub>G</sub>=2}} — выходит ошибка на единицу.
Если датчик круговой (например, угловой [[энкодер]]), то ему приходится перескакивать и с максимума до нуля. Такой перескок (с {{nobr|1=100<sub>G</sub>=7}} до {{nobr|1=000<sub>G</sub>=0}}) тоже изменяет один разряд.
[[Файл:US02632058 Gray.png|center|thumb|500px|Фрагмент главной страницы патента Грея]]
[[Файл:Encoder Disc (3-Bit).svg|thumb|Круговой энкодер с трёхбитным кодом Грея]]
Коды Грея часто используются в датчиках-[[энкодер]]ах. Их использование удобно тем, что два соседних значения шкалы сигнала отличаются только в одном разряде. Также они используются для кодирования номера дорожек в [[жёсткий диск|жёстких дисках]].
Код Грея можно использовать также и для решения задачи о [[Ханойские башни|Ханойских башнях]]<!--<ref>http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html</ref> Error 404 -->.
Широко применяются коды Грея и в [[генетический алгоритм|теории генетических алгоритмов]] для кодирования генетических признаков, представленных целыми числами.
Код Грея используется для генерации [[Сочетание|сочетаний]] [[метод вращающейся двери|методом вращающейся двери]]<ref>{{книга|автор=[[Кнут, Дональд Эрвин|Кнут, Дональд Э.]]|заглавие=Искусство программирования|том=4| ответственный =выпуск 3: генерация всех сочетаний и разбиений (раздел 7.2.1.3): Пер. с англ.|место=М.|издательство=ООО «И. Д. Вильямс»|год=2007|страниц=208|иллюстрации=илл.}}</ref>.
В некоторых [[Компьютерные игры|компьютерных играх]] (например, [[Duke Nukem 3D]]) для успешного прохождения уровня требуется подобрать нужную комбинацию положений нескольких переключателей. Никаких подсказок нет, надо просто перебрать все комбинации. Для минимизации числа переключений при переборе вариантов следует использовать код Грея. Например, если переключателей три, пробуем их в порядке 000, 001, 011, 010, 110…
Сложные датчики, требующие синхросигнала, отходят от кода Грея и работают в обычном двоичном<ref>[http://www.megatron.de/en/products/hall-effect-singleturn-rotary-encoder/hall-effect-absolute-encoder-series-mab25/download/92.html Спецификация магнитного энкодера Megatron MAB-25]{{ref-en}}</ref>.
== Алгоритмы преобразования ==
=== Преобразование двоичного кода в код Грея ===
Коды Грея легко получаются из двоичных чисел путём побитовой операции «[[Исключающее ИЛИ]]» с тем же числом, сдвинутым вправо на один бит и в котором старший разряд заполняется нулём. Следовательно, ''i''-й бит кода Грея ''G<sub>i</sub>'' выражается через биты двоичного кода ''B<sub>i</sub>'' следующим образом:
<center><math>G_i = B_i \oplus B_{i+1},
</math></center>
где <math> \oplus </math> — операция «исключающее ИЛИ»; биты нумеруются справа налево, начиная с младшего.
Ниже приведён алгоритм преобразования из [[двоичная система счисления|двоичной системы счисления]] в код Грея, записанный на языке [[Си (язык программирования)|C]]:
<source lang="C">
unsigned int grayencode(unsigned int g)
{
return g ^ (g >> 1);
}
</source>
Однако, необходимо помнить, что данный алгоритм будет работать правильно, если компилятор реализует ''нециклический'' логический сдвиг (например, стандарт языка C не уточняет тип сдвига для знаковых чисел, но для unsigned типов поддержка гарантируется).
Тот же самый алгоритм, записанный на языке Паскаль:
<source lang="pascal">
function BinToGray(b: integer): integer;
begin
BinToGray := b xor (b shr 1)
end;
</source>
Пример: преобразовать двоичное число 10110 в код Грея.
<pre>
10110
01011
----- XOR
11101
</pre>
=== Преобразование кода Грея в двоичный код ===
Обратный алгоритм — преобразование кода Грея в двоичный код — можно выразить рекуррентной формулой
<center><math>B_i = B_{i+1} \oplus G_i,
</math></center>
причём преобразование осуществляется побитно, начиная со старших разрядов, и значение <math>B_{i+1}</math>, используемое в формуле, вычисляется на предыдущем шаге алгоритма. Действительно, если подставить в эту формулу вышеприведённое выражение для ''i''-го бита кода Грея, получим
<center><math>B_i = B_{i+1} \oplus G_i = B_{i+1} \oplus (B_i \oplus B_{i+1}) = B_i \oplus (B_{i+1} \oplus B_{i+1}) = B_i \oplus 0 = B_i.
</math></center>
Однако приведённый алгоритм, связанный с манипуляцией отдельными битами, неудобен для программной реализации, поэтому на практике используют видоизменённый алгоритм:
<center><math>B_k = \bigoplus \limits^N_{i=k} G_i,
</math></center>
где ''N'' — число битов в коде Грея (для увеличения быстродействия алгоритма в качестве ''N'' можно взять номер старшего ненулевого бита кода Грея); знак <math> \oplus </math> означает суммирование при помощи операции «исключающее ИЛИ», то есть
<center><math>\bigoplus \limits^N_{i=k} G_i = G_k \oplus G_{k+1} \oplus ... \oplus G_{N-1} \oplus G_N.
</math></center>
Действительно, подставив в формулу выражение для ''i''-го бита кода Грея, получим
<center><math>B_k = \bigoplus \limits^N_{i=k} G_i =
\bigoplus \limits^N_{i=k} (B_i \oplus B_{i+1})=
(B_k \oplus B_{k+1}) \oplus (B_{k+1} \oplus B_{k+2}) \oplus ... \oplus (B_{N-1} \oplus B_N) \oplus (B_{N} \oplus B_{N+1})
=
</math>
<math>
= B_k \oplus (B_{k+1} \oplus B_{k+1}) \oplus ... \oplus ( B_N \oplus B_N) \oplus B_{N+1}
= B_k \oplus B_{N+1} = B_k
</math></center>
Здесь предполагается, что бит, выходящий за рамки разрядной сетки (<math>B_{N+1}</math>), равен нулю.
Ниже приведена функция на языке С, реализующая данный алгоритм. Она осуществляет последовательный сдвиг вправо и суммирование исходного двоичного числа, до тех пор, пока очередной сдвиг не обнулит слагаемое.
<source lang="Cpp">
unsigned int graydecode(unsigned int gray)
{
unsigned int bin;
for (bin = 0; gray; gray >>= 1) {
bin ^= gray;
}
return bin;
}
</source>
Тот же самый алгоритм, записанный на языке Паскаль:
<source lang="pascal">
function GrayToBin(b: integer): integer;
var g: integer;
begin
g := 0;
while b > 0 do begin
g := g xor b;
b := b shr 1;
end;
GrayToBin := g;
end;
</source>
Пример: преобразовать код Грея 11101 в двоичный код.
<pre>
11101
01110
00111
00011
00001
-----
10110
</pre>
Быстрое преобразование 8/16/24/32-разрядного значения кода Грея в '''двоичный''' код на языке C (Примечание: исходный код Грея является составным. Где каждая тетрада бит является отдельным числом и закодирована отдельно. Этот код не является полноценным кодом Грея. И правило изменения одного бита при переходе к новому числу сохраняется только в пределах каждой четвёрки. Например при переходе от 0x0F к 0x10 изменяются одновременно два бита так как мы имеем изменение двух тетрад 0->1 и F->0):
<source lang="c">
int gray2bin(int x)
{
return x ^ ((x & 0x88888888) >> 3) ^ ((x & 0xCCCCCCCC) >> 2) ^ ((x & 0xEEEEEEEE) >> 1);
}
</source>
Простой способ преобразования двоичного числа в код Грея выполняется по правилу: старший разряд записывается без изменения, каждый следующий символ кода Грея нужно инвертировать, если в натуральном коде перед этим была получена «1», и оставить без изменения, если в натуральном коде был получен «0».
=== Генерация кодов Грея ===
Код Грея для n бит может быть рекурсивно построен на основе кода для n-1 бит путём переворачивания списка бит (то есть записыванием кодов в обратном порядке), конкатенации исходного и перевёрнутого списков, дописывания нулей в начало каждого кода в исходном списке и единиц — в начало кодов в перевёрнутом списке. Так, для генерации списка для n = 3 бит на основании кодов для двух бит необходимо выполнить следующие шаги:
{|
|-
| Коды для n = 2 бит: || 00, 01, 11, 10 ||
|-
| Перевёрнутый список кодов: || || 10, 11, 01, 00
|-
| Объединённый список: || 00, 01, 11, 10 || 10, 11, 01, 00
|-
| К начальному списку дописаны нули: || 000, 001, 011, 010 || 10, 11, 01, 00
|-
| К перевёрнутому списку дописаны единицы: || 000, 001, 011, 010 || 110, 111, 101, 100
|}
Ниже представлен один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке [[Perl]]:
<source lang="perl">
my $depth = 16; # generate 16 Gray codes, 4 bits wide each
my @gray_codes = ( '0', '1' );
while(scalar(@gray_codes)<$depth)
{
my @forward_half=map{'0'.$_} @gray_codes;
my @reverse_half=map{'1'.$_} reverse(@gray_codes);
@gray_codes=(@forward_half,@reverse_half);
}
</source>
Рекурсивная функция построения кода Грея на языке [[Си (язык программирования)|C]]:
<source lang="C">
//n -- требуемая длина кода,
//m -- указатель на массив, способный хранить
// все коды Грея, длиной до n
// (должен быть выделен до вызова функции)
//depth -- параметр рекурсии
int gray (int n, int* m, int depth)
{
int i, t = (1 << (depth - 1));
if (depth == 0)
m[0] = 0;
else {
//массив хранит десятичные записи двоичных слов
for (i = 0; i < t; i++)
m[t + i] = m[t - i - 1] + (1 << (depth - 1));
}
if (depth != n)
gray(n, m, depth + 1);
return 0;
}
</source>
Быстрое преобразование 8/16/24/32-разрядного '''двоичного''' кода в код Грея на языке C. (Примечание: полученный код не является полноценным кодом Грея. Данный код преобразовывает в код Грея каждые 4 бита отдельно, рассматривая их как отдельные числа. В результате полученный код состоит из множества 4 битных кодов грея. И правило изменения одного бита при переходе к новому числу сохраняется только в пределах каждой четвёрки. Например при переходе от 0x0F к 0x10 изменяются одновременно два бита так как мы имеем изменение двух тетрад 0->1 и F->0):
<source lang="C">
int bin2gray(int x)
{
return x ^ ((x & 0xEEEEEEEE) >> 1);
}
</source>
== Необычные вариации кода Грея ==
<!--
=== Код Грея с основанием, большим 2 ===
-->
=== Сбалансированный код Грея ===
Если датчики имеют ограниченный [[ресурс (техника)|ресурс]] по количеству переключений, хотелось бы, чтобы они изнашивались равномерно. В сбалансированном коде Грея в разных разрядах количество переключений настолько близко, насколько можно.
0 '''1''' 1 1 1 1 1 '''0''' 0 0 0 0 0 '''1''' 1 '''0'''
0 0 '''1''' 1 1 1 '''0''' 0 '''1''' 1 1 1 '''0''' 0 0 0
0 0 0 0 '''1''' 1 1 1 1 '''0''' 0 '''1''' 1 1 '''0''' 0
'''0''' 0 0 '''1''' 1 '''0''' 0 0 0 0 '''1''' 1 1 1 1 1
Здесь в 4-битном коде каждый разряд переключается четырежды. В 5-битном коде такое невозможно, приходится переключать один бит 8 раз, остальные — по 6.
=== Однодорожечный код Грея ===
Код Грея является однодорожечным, если все столбцы матрицы являются кольцевыми сдвигами друг друга. Это позволяет сделать угловой датчик с одной дорожкой.
Двухбитный код Грея является однодорожечным, это можно увидеть в [[компьютерная мышь|компьютерной мыши]] — как в шариковом механизме старых мышей, так и в колесе прокрутки новых. Два датчика стоят в разных точках одной дорожки. Если довести эту систему до крайности — половина диска «чёрная», половина «белая», и датчики стоят на 90° друг относительно друга — то можно узнать абсолютное положение диска с дискретностью в 90°.
Для кодов Грея более высокой разрядности это не так, приходится увеличивать количество дорожек, это делает датчик громоздким и дорогим. Поэтому, если возможно, обходятся двумя дорожками — одна для двухбитного кода Грея, и одна — позиция нуля. Однако существуют коды, где дорожка именно одна, правда, все 2<sup>n</sup> позиций так закодировать невозможно. Для 5 бит рекорд — 30 позиций, для 9 — 360.
=== Двухмерный код Грея ===
Используется в [[квадратурная модуляция|квадратурной модуляции]] сигналов. Соседние точки «[[Сигнальное созвездие|созвездия]]» отличаются одним битом, диагональные — двумя.
== См. также ==
* [[Код Хэмминга]]
* [[Код Джонсона]]
| 