Код Грея

Определение

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

Например, для чисел длины 3 бита имеем такую последовательность кодов Грея: $000$ , $001$ , $011$ , $010$ , $110$ , $111$ , $101$ , $100$ . Например, $G(4)=6$ .

Этот код был изобретен Фрэнком Грэем (Frank Gray) в 1953 году.

Нахождение кода Грея

Рассмотрим биты числа $n$ и биты числа $G(n)$ . Заметим, что $i$ -ый бит $G(n)$ равен единице только в том случае, когда $i$ -ый бит $n$ равен единице, а $i+1$ -ый бит равен нулю, или наоборот ( $i$ -ый бит равен нулю, а $i+1$ -ый равен единице). Таким образом, имеем: $G(n) = n \oplus (n>>1)$ :

int g (int n) {
	return n ^ (n >> 1);
}

Нахождение обратного кода Грея

Требуется по коду Грея $g$ восстановить исходное число $n$ .

Будем идти от старших битов к младшим (пусть самый младший бит имеет номер 1, а самый старший — $k$ ). Получаем такие соотношения между битами $n_i$ числа $n$ и битами $g_i$ числа $g$ :

$n_k = g_k,$
$n_{k-1} = g_{k-1} \oplus n_k = g_k \oplus g_{k-1}[...]$
$n_{k-2} = g_{k-2} \oplus n_{k-1} = g_k \oplus g_{[...]$
$n_{k-3} = g_{k-3} \oplus n_{k-2} = g_k \oplus g_{[...]$
$\ldots$

В виде программного кода это проще всего записать так:

int rev_g (int g) {
	int n = 0;
	for (; g; g>>=1)
		n ^= g;
	return n;
}

Применения

Коды Грея имеют несколько применений в различных областях, иногда достаточно неожиданных:

$n$ -битный код Грея соответствует гамильтонову циклу по $n$ -мерному кубу.
В технике, коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках). В частности, коды Грея и были открыты в связи с этим применением.
Коды Грея применяются в решении задачи о Ханойских башнях.
Пусть $n$ — количество дисков. Начнём с кода Грея длины $n$ , состоящего из одних нулей (т.е. $G(0)$ ), и будем двигаться по кодам Грея (от $G(i)$ переходить к $G(i+1)$ ). Поставим в соответствие каждому $i$ -ому биту текущего кода Грея $i$ -ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита $i$ как перемещение $i$ -го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если $n$ нечётно, то последовательность перемещений наименьшего диска имеет вид $f \rightarrow t \rightarrow r \rightarrow f \rightarrow t \rightarrow r \rightarrow \ldots$ (где $f$ — стартовый стержень, $t$ — финальный стержень, $r$ — оставшийся стержень), а если $n$ чётно, то $f \rightarrow r \rightarrow t \rightarrow f \rightarrow r \rightarrow t \rightarrow \ldots$ .
Коды Грея также находят применение в теории генетических алгоритмов.

Задачи в online judges

Список задач, которые можно сдать, используя коды Грея:

SGU #249 "Matrix" [сложность: средняя]