Código de Gray

O código de Gray é um sistema numérico binário em que dois valores sucessivos diferem em apenas um bit.

Por exemplo, a sequência do código de Gray para números de 3 bits é: 000, 001, 011, 010, 110, 111, 101, 100, então $G(4) = 6$.

Este código foi inventado por Frank Gray em 1953.

Encontrando o código de Gray

Vejamos os bits do número $n$ e os bits do número $G(n)$. Observe que o $i$-th bit de $G(n)$ é igual a 1 apenas quando o $i$-th bit de $n$ é igual a 1 e $i + 1$-th bit é igual a 0 ou ao contrário($i$-th bit = 0 e $i + 1$-th bit = 1). Portanto, $G(n) = n \oplus (n >> 1)$:

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

Encontrado o código de Gray inverso

Dado um código de Gray $g$, retorne o número original $n$.

Passaremos dos bits mais significativos para os menos significativos (o bit menos significativo possui o índice 1 e o bit mais significativo tem o índice $k$). A relação entre os bits $n_i$ do número $n$ e os bits $g_i$ do número $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}$$

A maneira mais fácil de escrevê-lo no código é:

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

Aplicações

Os códigos de Gray têm algumas aplicações úteis, às vezes bastante inesperadas:

Problemas