Codificar códigos cíclicos: del polinomio generador a los CRC

Ya sabes qué es un código cíclico: sus palabras son los múltiplos de un generador $g(x)$, divisor de $x^n - 1$. Queda lo práctico: ¿cómo se codifica, se comprueba y se corrige? Todo se reduce a multiplicar y dividir polinomios. Y verás qué hay detrás de la palabra «CRC» de tantos archivos y protocolos de red.

Seguimos numerando desde 0: $c = (c_0, \dots, c_{n-1}) \leftrightarrow c(x) = c_0 + \dots + c_{n-1}x^{n-1}$. Trabajamos con el Hamming cíclico $[7,4,3]$ de la lección anterior, con $g(x) = 1 + x + x^3$.

La idea

Hay dos maneras de pasar de 4 bits de mensaje a 7 de palabra.

1. Multiplicar. Ves el mensaje como un polinomio $m(x)$ de grado menor que 4 y calculas $c(x) = m(x)g(x)$. Es inmediato, pero el mensaje queda «mezclado» en la palabra.
2. Dividir. Pones el mensaje en las últimas posiciones y rellenas las primeras con la redundancia justa para que el polinomio sea múltiplo de $g$. La redundancia es el resto de una división, y el mensaje se lee al final de la palabra.

La segunda es la codificación sistemática, la misma idea que la forma $[I_k \mid P]$ de la lección 4, pero con polinomios. Ojo: aquí la redundancia va delante y el mensaje detrás, al revés que en la lección 4; es solo una convención. Es la idea de los CRC.

Codificación no sistemática

El código es $C = \{\,m(x)g(x)\,\}$. Para el mensaje $m = (1,0,1,1)$ tenemos $m(x) = 1 + x^2 + x^3$ y

es decir, $c = (1,1,1,1,1,1,1)$ ($x^3$ aparece tres veces y en módulo 2 queda una). El mensaje $1011$ no se ve por ninguna parte. Es lo mismo que calcular $mG$ con la matriz generatriz cíclica, cuyas filas son $g, xg, x^2g, x^3g$:

Multiplicar por $m(x)$ es sumar las filas que indica $m$: aquí $m = (1,0,1,1)$ suma las filas 1, 3 y 4.

Codificación sistemática

Queremos una palabra «redundancia + mensaje», con el mensaje en los $k$ últimos coeficientes. Receta:

1. Calcula $x^{n-k}m(x)$: es colocar el mensaje en las $k$ últimas posiciones.
2. Divide entre $g(x)$ y quédate con el resto $r(x)$, de grado menor que $n-k$.
3. La palabra es $c(x) = x^{n-k}m(x) + r(x)$ (en módulo 2, sumar es restar).

¿Por qué es múltiplo de $g$? Si $x^{n-k}m = q\,g + r$, entonces $x^{n-k}m + r = q\,g$. Y como $r$ tiene grado menor que $n-k$, solo toca las primeras posiciones y no estropea el mensaje.

Para $m = (1,0,1,1)$, con $n - k = 3$:

• $x^3m(x) = x^3 + x^5 + x^6$.
• Dividimos entre $g = x^3 + x + 1$: restamos $x^3 g$ (queda $x^4 + x^5$), luego $x^2 g$ (queda $x^2+x^3+x^4$), luego $x\,g$ (queda $x + x^3$) y por último $g$ (queda $1$).
• El resto es $r(x) = 1$.
• Palabra: $c(x) = 1 + x^3 + x^5 + x^6$, es decir, $c = (1,0,0,1,0,1,1)$.

Los 3 primeros símbolos, $100$, son la redundancia y los 4 últimos, $1011$, el mensaje. Comprobación: al dividir $c(x)$ entre $g$ el resto es 0 (es la división del ejemplo «que sí» de la lección anterior).

El polinomio de control

El polinomio de control es $h(x) = (x^n - 1)/g(x)$. Para nuestro código,

Comprueba palabras: $c$ está en el código si y solo si $c(x)h(x) \equiv 0 \pmod{x^n-1}$. Si $c = m\,g$, entonces $c\,h = m\,g\,h = m(x^n - 1)$, que vale 0 cuando $x^n=1$. Y al revés: si $c\,h = Q\,(x^n-1) = Q\,g\,h$, entonces $c = Q\,g$.

También da la matriz de paridad. Escribe los coeficientes de $h$ al revés, de $h_4$ a $h_0$: $1,0,1,1,1$. Las filas de $H$ son esa lista desplazada:

¿Por qué? Cada entrada de $GH^T$ resulta ser un coeficiente de $g(x)h(x) = x^7+1$ de grado entre 1 y 6, y todos ellos son 0. Así que $GH^T = 0$. Cuidado: no es la $H$ del hilo, porque este código tiene las posiciones en otro orden (es equivalente, no igual).

El síndrome es un resto

Si recibes $r(x) = c(x) + e(x)$, con $c$ palabra y $e$ el error, entonces el resto de dividir entre $g$ es

porque $c$ es múltiplo de $g$ y su resto es 0. El síndrome es el resto de dividir entre $g$ y solo depende del error, igual que en la lección 6. Basta una división, que un circuito con registros de desplazamiento hace al vuelo.

Ojo: hay dos síndromes, el vector $Hr^T$ de la lección 6 y este resto $s(x)$. Son objetos distintos, pero guardan la misma información: dos palabras recibidas tienen el mismo $Hr^T$ si y solo si tienen el mismo resto (en ambos casos, si y solo si su diferencia está en el código).

Un error en la posición $i$ es $e(x) = x^i$. Los restos de $x^i$ entre $g = 1+x+x^3$ son:

Los 7 restos son distintos y no nulos (son los 7 polinomios no nulos de grado menor que 3): el síndrome señala la posición del error.

CRC: detectar con el mismo truco

Los CRC (comprobación de redundancia cíclica) son, en esencia, la codificación sistemática de arriba, con un $g(x)$ elegido para detectar y mensajes larguísimos. El emisor ve la trama como un polinomio, calcula el resto de dividir $x^{\deg g}m(x)$ entre $g(x)$ y lo añade como redundancia. (Se transmite primero el coeficiente de mayor grado, así que el resto, de grados bajos, va al final de la trama.) El receptor divide lo que le llega; si el resto no es cero, hay un error y el dato no se acepta: Ethernet descarta la trama y un descompresor ZIP avisa de que el archivo está dañado. Los estándares reales, como el CRC-32 de Ethernet y ZIP, añaden detalles (un valor inicial y un complemento final) que no cambian la idea. En el ejercicio 3 calculas un CRC a mano.

Una ráfaga de longitud $\ell$ es un error cuyas posiciones dañadas caben en un tramo de $\ell$ símbolos seguidos (no tienen por qué cambiar todos). Si el término independiente de $g$ es 1, se detecta toda ráfaga de longitud menor o igual que $\deg g$, sea cual sea la longitud del mensaje. La razón: esa ráfaga es $x^i b(x)$ con $b \neq 0$ y $\deg b < \deg g$; como $g$ no tiene factor $x$, para dividir a $x^i b$ tendría que dividir a $b$, y no puede. Sin esa condición falla: $g = x^3 + x^2$ divide a la ráfaga $x^6 + x^5$. Los generadores de códigos cíclicos y de CRC estándar la cumplen.

Ejemplo resuelto

Enviamos $m = (1,0,1,1)$ con el código sistemático y hay un error en la posición 4.

1. Palabra enviada. Como arriba, $c = (1,0,0,1,0,1,1)$.

2. Palabra recibida. El error cambia el coeficiente de $x^4$: $r = (1,0,0,1,1,1,1)$, es decir, $r(x) = 1 + x^3 + x^4 + x^5 + x^6$.

3. Síndrome. Divide $r(x)$ entre $g(x) = 1 + x + x^3$:

• Resta $x^3g = x^3 + x^4 + x^6$: queda $1 + x^5$.
• Resta $x^2g = x^2 + x^3 + x^5$: queda $1 + x^2 + x^3$.
• Resta $g$: queda $x + x^2$.

El resto es $s(x) = x + x^2 \neq 0$: hay un error.

4. Posición. En la tabla, $x + x^2$ es el resto de $x^4$. Error en la posición 4.

5. Corrección. Cambia $r_4$: $(1,0,0,1,0,1,1)$, la palabra enviada. Sus 4 últimos símbolos dan el mensaje, $1011$.

Ejercicios

Ejercicio 1

Codifica de forma sistemática el mensaje $m = (0,1,1,1)$ con $g(x) = 1 + x + x^3$.

Ejercicio 2

Con la matriz de paridad $H$ de esta lección (la del código $g = 1+x+x^3$), decide si $1011100$ y $1011101$ son palabras del código. Si alguna no lo es, di qué columna de $H$ aparece en el síndrome.

Ejercicio 3

Calcula a mano un CRC de 3 bits con $g(x) = x^3+x+1$ para el mensaje de 8 bits $11010011$, escrito como se transmite (del coeficiente de mayor grado al de menor). Comprueba después que la trama completa da resto 0.

11010011000
1011
 1100011000
 1011
  111011000
  1011
   10111000
   1011
       1000
       1011
        011

En resumen

• No sistemática: $c(x) = m(x)g(x)$, o sea, $mG$ con $G$ de filas $g, xg, \dots$
• Sistemática: $c(x) = x^{n-k}m(x) + r(x)$, con $r$ el resto de dividir $x^{n-k}m$ entre $g$. El mensaje se lee al final.
• El polinomio de control $h = (x^n-1)/g$ comprueba palabras ($c\,h \equiv 0$) y da la matriz de paridad.
• El síndrome es el resto de dividir entre $g$; en Hamming cada resto $x^i \bmod g$ es distinto y señala la posición del error.
• Los CRC usan este mecanismo para detectar errores en datos largos. Si $g(0) = 1$, detectan toda ráfaga de longitud hasta $\deg g$.

Siguiente lección: Códigos Reed-Solomon