ALGORITHMS
Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.
Например, для чисел длины 3 бита имеем такую последовательность кодов Грея: 000, 001, 011, 010, 110, 111, 101, 100. Например, G(4)=6.
Этот код был изобретен Фрэнком Грэем (Frank Gray) в 1953 году.
Применение Кода Грея
Коды Грея имеют несколько применений в различных областях, иногда достаточно неожиданных:
- Коды Грея применяются в решении головоломки о Ханойской_башне
- n-битный код Грея соответствует гамильтонову циклу по n-мерному кубу.
- В технике, коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках). В частности, коды Грея и были открыты в связи с этим применением.
- Коды Грея также находят применение в теории генетических алгоритмов.
Нахождение Кода Грея
(+) - XOR или, как еще его называют «исключающее_или»
Рассмотрим биты числа n и биты числа G(n). Заметим, что i-ый бит G(n) равен единице только в том случае, когда i-ый бит n равен единице, а i+1-ый бит равен нулю, или наоборот (i-ый бит равен нулю, а i+1-ый равен единице).
Таким образом, имеем: G(n) = n (+) (n>>1):
Таким образом, имеем: G(n) = n (+) (n>>1):
int g (int n) {
return n ^ (n >> 1);
}Обратный Код Грея:
int rev_g (int g) {
int n = 0;
for (; g; g>>=1)
n ^= g;
return n;
}