Код Грея

Код Грея — це двійкова система числення, у якій два сусідні значення відрізняються лише в одному біті.

Позначимо через $G(n)$ представлення числа $n$ у коді Грея. Послідовність кодів Грея для 3-бітових чисел така: 000, 001, 011, 010, 110, 111, 101, 100, тож $G(4) = (110)_2 = 6$. Наприклад, $G(3) = (010)_2$ і $G(4) = (110)_2$ відрізняються рівно в одному біті — найлівішому. Аналогічно, $G(4) = 110$ і $G(5) = (111)_2$ відрізняються рівно в одному біті — найправішому. Це справджується для всіх послідовних чисел.

Цей код винайшов Frank Gray у 1953 році.

Знаходження коду Грея

Розгляньмо біти числа $n$ і біти числа $G(n)$. Зауважимо, що $i$-й біт $G(n)$ дорівнює 1 лише тоді, коли $i$-й біт числа $n$ дорівнює 1, а $i + 1$-й біт дорівнює 0, або навпаки ($i$-й біт дорівнює 0, а $i + 1$-й біт дорівнює 1). Отже, $G(n) = n \oplus (n >> 1)$:

C++

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

Python

def g(n: int) -> int:
    return n ^ (n >> 1)

TypeScript

function g(n: number): number {
    return n ^ (n >> 1);
}

Go

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

Знаходження оберненого коду Грея

Маючи код Грея $g$, відновимо початкове число $n$.

Рухатимемося від старших бітів до молодших (молодший біт має індекс 1, а старший біт — індекс $k$). Зв'язок між бітами $n_i$ числа $n$ і бітами $g_i$ числа $g$:

$$\begin{align} 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_{k-1} \oplus g_{k-2}, \\ n_{k-3} &= g_{k-3} \oplus n_{k-2} = g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3}, \vdots \end{align}$$

Найпростіше це записати в коді так:

C++

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

Python

def rev_g(g: int) -> int:
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n

TypeScript

function revG(g: number): number {
    let n = 0;
    for (; g; g >>= 1)
        n ^= g;
    return n;
}

Go

func revG(g int) int {
    n := 0
    for ; g != 0; g >>= 1 {
        n ^= g
    }
    return n
}

Практичні застосування

Коди Грея мають кілька корисних застосувань, інколи доволі несподіваних:

• Код Грея з $n$ бітів утворює гамільтонів цикл на гіперкубі, де кожен біт відповідає одному виміру.

• Коди Грея використовують для мінімізації помилок під час цифро-аналогового перетворення сигналів (наприклад, у сенсорах).

• Код Грея можна застосувати для розв'язання задачі про Ханойські вежі. Нехай $n$ позначає кількість дисків. Почнемо з коду Грея довжини $n$, який складається з самих нулів ($G(0)$), і рухаймося між послідовними кодами Грея (від $G(i)$ до $G(i+1)$). Нехай $i$-й біт поточного коду Грея відповідає $n$-му диску (молодший біт відповідає найменшому диску, а старший біт — найбільшому). Оскільки на кожному кроці змінюється рівно один біт, ми можемо трактувати зміну $i$-го біта як переміщення $i$-го диска. Зауважимо, що для кожного диска (крім найменшого) на кожному кроці (крім початкової та кінцевої позицій) існує рівно один варіант переміщення. Для найменшого диска завжди є два варіанти переміщення, але існує стратегія, яка завжди приводить до відповіді: якщо $n$ непарне, то послідовність переміщень найменшого диска має вигляд $f \to t \to r \to f \to t \to r \to ...$ (де $f$ — початковий стрижень, $t$ — кінцевий стрижень, а $r$ — стрижень, що залишився), а якщо $n$ парне: $f \to r \to t \to f \to r \to t \to ...$.

• Коди Грея також використовують у теорії генетичних алгоритмів.

Задачі для практики

• Gray Code      [Difficulty: easy]
• SGU #249 "Matrix"      [Difficulty: medium]

Відеоматеріали