Codul Gray este un sistem numeric binar în care două valori succesive diferă doar printr-un singur bit.

De exemplu, secvența de coduri Gray pentru numere de 3 biți este: 000, 001, 011, 010, 110, 111, 101, 100, deci \( G(4) = 6 \)

Acest cod a fost inventat de Frank Gray în 1953.

Găsirea codului Gray

Să ne uităm la biții numărului \( n \) și la biții numărului \( G(n) \). Observați că al i-lea bit al numărului \( G(n) \) este egal cu 1 numai atunci când al i-lea bit al lui n este egal cu 1 și al i+1-lea bit este egal cu 0 sau invers (al i-lea bit este egal cu 0 și al i+1-lea bit este egal cu 1). Astfel, \( G(n) = n \oplus (n >> 1) \):

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

Găsirea codului Gray invers

Dat fiind codul Gray g, restabiliți numărul original n.

Ne vom deplasa de la biții cei mai semnificativi la cei mai puțin semnificativi (bitul cel mai puțin semnificativ are indicele 1, iar bitul cel mai semnificativ are indicele k). Relația dintre biții \( n_i \) din numărul \( n \) și biții \( g_i \) din numărul \( 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}\)

Cel mai simplu mod de a o scrie în cod este:

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

Aplicații practice

Codurile Gray au câteva aplicații utile, uneori chiar neașteptate:

• Codul Gray de n biți formează un ciclu Hamiltonian pe un hipercub, unde fiecare bit corespunde unei dimensiuni.

• Codurile Gray sunt utilizate pentru a minimiza erorile în conversia semnalelor digitale în analogice (de exemplu, în cazul senzorilor).

• Codul Gray poate fi folosit pentru a rezolva problema Turnurilor din Hanoi. Fie \( n \) numărul de discuri. Se începe cu un cod Gray de lungime \( n \) care constă în toate zerourile (\( G(0) \)) și se trece de la un cod Gray consecutiv (de la \( G(i)\) la \( G(i+1) \)). Fie că al i-lea bit al codului Gray curent reprezintă al n-lea disc (bitul cel mai puțin semnificativ corespunde celui mai mic disc și bitul cel mai semnificativ celui mai mare disc). Deoarece la fiecare pas se schimbă exact un bit, putem considera că schimbarea celui de-al i-lea bit reprezintă deplasarea celui de-al i-lea disc. Observați că există exact o opțiune de mutare pentru fiecare disc (cu excepția celui mai mic) la fiecare pas (cu excepția pozițiilor de început și de sfârșit). Există întotdeauna două opțiuni de mutare pentru cel mai mic disc, dar există o strategie care va conduce întotdeauna la un răspuns: dacă n este impar, atunci secvența de mutare a celui mai mic disc arată ca \( f \to t \to r \to f \to t \to r \to … \) unde \( f \) este tija inițială, \( t \) este tija finală și \( r \) este tija rămasă), iar dacă este par: \( f \to r \to t \to f \to r \to t \to … \).

• Codurile Gray sunt, de asemenea, utilizate în teoria algoritmilor genetici.