Código Gray

El código Gray es un sistema de numeración binario donde dos valores sucesivos difieren en un solo bit.

Denotemos por $G(n)$ la representación del número $n$ usando el código Gray. La secuencia de códigos Gray para números de 3 bits es: 000, 001, 011, 010, 110, 111, 101, 100, así que $G(4) = (110)_2 = 6$ . Por ejemplo, $G(3) = (010)_2$ y $G(4) = (110)_2$ difieren en exactamente un bit, el bit más a la izquierda. De forma similar, $G(4) = 110$ y $G(5) = (111)_2$ difieren en exactamente un bit, el más a la derecha. Esto vale para todos los números sucesivos.

Este código lo inventó Frank Gray en 1953.

Encontrar el código Gray

Miremos los bits del número $n$ y los bits del número $G(n)$ . Nótese que el $i$ -ésimo bit de $G(n)$ vale 1 solo cuando el $i$ -ésimo bit de $n$ vale 1 y el bit $i + 1$ vale 0, o al revés (el $i$ -ésimo bit vale 0 y el bit $i + 1$ vale 1). Así, $G(n) = n \oplus (n >> 1)$ :


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

Encontrar el código Gray inverso

Dado el código Gray $g$ , restaurar el número original $n$ .

Nos moveremos de los bits más significativos a los menos significativos (el bit menos significativo tiene índice 1 y el más significativo tiene índice $k$ ). La relación entre los bits $n_i$ del número $n$ y los bits $g_i$ del número $g$ :

$\begin{aligned} 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}, ⋮ \end{aligned}$

La forma más fácil de escribirlo en código es:


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

Aplicaciones prácticas

Los códigos Gray tienen algunas aplicaciones útiles, a veces bastante inesperadas:

El código Gray de $n$ bits forma un ciclo hamiltoniano en un hipercubo, donde cada bit corresponde a una dimensión.
Los códigos Gray se usan para minimizar los errores en la conversión de señales digital-analógica (por ejemplo, en sensores).
El código Gray se puede usar para resolver el problema de las Torres de Hanoi. Sea $n$ la cantidad de discos. Empezar con el código Gray de longitud $n$ que consiste de todos ceros ( $G(0)$ ) y moverse entre códigos Gray consecutivos (de $G(i)$ a $G(i+1)$ ). Sea el $i$ -ésimo bit del código Gray actual el que representa el $n$ -ésimo disco (el bit menos significativo corresponde al disco más chico y el más significativo al disco más grande). Como exactamente un bit cambia en cada paso, podemos tratar el cambio del $i$ -ésimo bit como mover el $i$ -ésimo disco. Nótese que hay exactamente una opción de movimiento para cada disco (excepto el más chico) en cada paso (excepto las posiciones de inicio y fin). Siempre hay dos opciones de movimiento para el disco más chico, pero hay una estrategia que siempre lleva a la respuesta: si $n$ es impar, la secuencia de movimientos del disco más chico se ve como $f \to t \to r \to f \to t \to r \to …$ donde $f$ es la varilla inicial, $t$ es la varilla terminal y $r$ es la varilla restante, y si $n$ es par: $f \to r \to t \to f \to r \to t \to …$ .
Los códigos Gray también se usan en la teoría de algoritmos genéticos.

Código Gray

Encontrar el código Gray

Encontrar el código Gray inverso

Aplicaciones prácticas

Problemas de práctica