Corregir errores en Reed-Solomon

En la lección anterior recuperamos borrones: sabíamos qué símbolos faltaban y bastaba interpolar con los que quedaban. Con los errores es más difícil, porque nadie avisa de dónde están. Un lector de QR no sabe qué módulos ha manchado el café: lee una palabra, algunos símbolos son falsos y tiene que descubrir cuáles. Veremos cómo se hace con un sistema lineal, y cerraremos el curso.

La idea

Si la palabra recibida $r$ tiene como mucho $t$ errores, el polinomio correcto coincide con $r$ en al menos $n-t$ posiciones. Y es el único que lo hace cuando $2t \le n-k$. Dos polinomios distintos de grado menor que $k$ coinciden en como mucho $k-1$ posiciones. Si los dos coincidieran con $r$ en $n-t$ posiciones, coincidirían entre ellos en al menos $n-2t \ge k$ de ellas: imposible.

Seguimos con el ejemplo hilo: el código $[7,3,5]$ sobre $\mathbb{F}_8$, el mensaje $f(x) = 1+\alpha x+x^2$ y su palabra $c = (\alpha, 1, \alpha^2, \alpha, \alpha^2, \alpha^5, \alpha^5)$. El canal cambia la posición 2 (punto $\alpha$): llega $\alpha^5$ en vez de $1$. Recibimos

$$r = (\alpha,\ \alpha^5,\ \alpha^2,\ \alpha,\ \alpha^2,\ \alpha^5,\ \alpha^5).$$

Buscamos un polinomio de grado menor que 3 que coincida con $r$ en al menos 6 posiciones. Una forma ingenua es probar ternas de posiciones e interpolar. Con las posiciones 1, 2 y 3 sale $\alpha^5x^2+x+\alpha^2$, que solo coincide con $r$ en esas 3: descartado. Con 1, 3 y 4 sale $f$, que coincide en 6: es el bueno. En un código $[255,223]$ habría que probar un número astronómico de combinaciones: hace falta algo mejor.

Berlekamp-Welch: el error como incógnita

El truco es convertir la posición del error en una incógnita más. Si el error está en el punto $a_e$ (que no conocemos), llamamos localizador de errores a

$$E(x) = x - a_e,$$

que se anula justo ahí. Y definimos $Q(x) = E(x)\,f(x)$, de grado como mucho 3. Entonces, en cada posición $i$, con punto $a_i$,

$$Q(a_i) = r_i\,E(a_i).$$

¿Por qué? Si la posición es correcta, $r_i = f(a_i)$ y es la definición de $Q$. Si es la del error, los dos lados valen 0, porque $E(a_e) = 0$. El localizador «tapa» el error.

Lo bueno es que esas ecuaciones son lineales. Las incógnitas son los coeficientes de $Q(x) = q_0+q_1x+q_2x^2+q_3x^3$ y el de $E(x) = x + e_0$ (en $\mathbb{F}_8$, $-a_e = a_e$). La ecuación de la posición $i$ queda

$$q_0 + q_1a_i + q_2a_i^2 + q_3a_i^3 + r_i\,e_0 = r_i\,a_i.$$

Son 7 ecuaciones con 5 incógnitas. Con $t$ errores, $E$ tiene grado $t$ y $Q$ grado menor que $k+t$: salen $k+2t$ incógnitas, que no pasan de $n$ porque $2t \le n-k$.

Ejemplo resuelto: un error con Berlekamp-Welch

Con los siete puntos $1, \alpha, \dots, \alpha^6$ y los valores de $r$ (usando $\alpha^7 = 1$), la matriz ampliada del sistema, con columnas $q_0, q_1, q_2, q_3, e_0$ y el término independiente, es:

$$\left(\begin{array}{ccccc|c} 1 & 1 & 1 & 1 & \alpha & \alpha\\ 1 & \alpha & \alpha^2 & \alpha^3 & \alpha^5 & \alpha^6\\ 1 & \alpha^2 & \alpha^4 & \alpha^6 & \alpha^2 & \alpha^4\\ 1 & \alpha^3 & \alpha^6 & \alpha^2 & \alpha & \alpha^4\\ 1 & \alpha^4 & \alpha & \alpha^5 & \alpha^2 & \alpha^6\\ 1 & \alpha^5 & \alpha^3 & \alpha & \alpha^5 & \alpha^3\\ 1 & \alpha^6 & \alpha^5 & \alpha^4 & \alpha^5 & \alpha^4 \end{array}\right)$$

Por ejemplo, la fila 4 es el punto $\alpha^3$: $(\alpha^3)^2 = \alpha^6$, $(\alpha^3)^3 = \alpha^9 = \alpha^2$, $r_4 = \alpha$ y $r_4a_4 = \alpha^4$.

Resolver. Gauss, como con cualquier sistema, da una única solución:

$$q_0 = \alpha,\quad q_1 = \alpha^6,\quad q_2 = 0,\quad q_3 = 1,\quad e_0 = \alpha.$$

Es decir, $Q(x) = x^3 + \alpha^6x + \alpha$ y $E(x) = x + \alpha$. Puedes comprobar que cumple las siete ecuaciones $Q(a_i) = r_iE(a_i)$:

posición	$a_i$	$r_i$	$E(a_i)$	$r_iE(a_i)$	$Q(a_i)$
1	$1$	$\alpha$	$\alpha^3$	$\alpha^4$	$\alpha^4$
2	$\alpha$	$\alpha^5$	$0$	$0$	$0$
3	$\alpha^2$	$\alpha^2$	$\alpha^4$	$\alpha^6$	$\alpha^6$
4	$\alpha^3$	$\alpha$	$1$	$\alpha$	$\alpha$
5	$\alpha^4$	$\alpha^2$	$\alpha^2$	$\alpha^4$	$\alpha^4$
6	$\alpha^5$	$\alpha^5$	$\alpha^6$	$\alpha^4$	$\alpha^4$
7	$\alpha^6$	$\alpha^5$	$\alpha^5$	$\alpha^3$	$\alpha^3$

Dónde está el error. $E(x) = x+\alpha$ se anula en $\alpha$, el punto de la posición 2.

El mensaje. Dividimos $Q$ entre $E$:

1. $x^2\cdot(x+\alpha) = x^3+\alpha x^2$. Queda $\alpha x^2 + \alpha^6x + \alpha$.
2. $\alpha x\cdot(x+\alpha) = \alpha x^2 + \alpha^2x$. Queda $(\alpha^6+\alpha^2)x + \alpha = x + \alpha$.
3. $1\cdot(x+\alpha) = x+\alpha$. Resto 0.

El cociente es $f(x) = x^2 + \alpha x + 1$: el mensaje $(1, \alpha, 1)$. El símbolo correcto de la posición 2 es $f(\alpha) = 1$, y el error valía $\alpha^5 - 1 = \alpha^4$.

Un detalle: si hay menos errores de los previstos, $E$ puede salir con raíces de más (posiciones correctas), pero el cociente $Q/E$ siempre es el polinomio del mensaje.

En la práctica: Berlekamp-Massey y Euclides

En un código $[255,223]$ con $t = 16$, Berlekamp-Welch plantea un sistema de 255 incógnitas, y Gauss es caro. Los decodificadores reales usan Berlekamp-Massey o el algoritmo de Euclides: parten del síndrome (el de las lecciones 6 y 8) y calculan el localizador con un número de operaciones que crece como $t^2$. Después buscan sus raíces y los valores de los errores. La demo de abajo usa Berlekamp-Massey.

Errores y borrones a la vez

Como vimos en la lección anterior, un borrón gasta un símbolo de redundancia y un error, dos: se corrigen $e$ errores y $b$ borrones si $2e + b \le n-k$. Las posiciones borradas simplemente se quitan; las que quedan forman un código de Reed-Solomon más corto.

Ejemplo. En el $[7,3,5]$ caben $e=1$ y $b=2$. El canal borra las posiciones 1 y 7 de $c$ y cambia la 4: llega $\alpha^4$ en vez de $\alpha$. Quedan las posiciones 2 a 6, con valores $(1, \alpha^2, \alpha^4, \alpha^2, \alpha^5)$: es un código de longitud 5 con $k=3$ y $d = 3$, que corrige 1 error. Buscamos un polinomio de grado menor que 3 que coincida en al menos 4 de esas 5 posiciones. De las 10 ternas posibles, las 4 que no usan la posición 4 dan $f$, que coincide en las posiciones 2, 3, 5 y 6. Las 6 que la usan dan polinomios que solo coinciden en sus 3 puntos. El error está en la posición 4. (Berlekamp-Welch también vale aquí: basta quitar las ecuaciones de las posiciones borradas.)

Ráfagas y entrelazado

Un arañazo estropea símbolos seguidos, y un código que corrige $t$ errores falla si caen más de $t$ en una misma palabra. El entrelazado reparte la ráfaga:

1. Escribe $s$ palabras código una debajo de otra, como filas de una tabla.
2. Transmite la tabla por columnas.
3. El receptor la reordena y decodifica cada fila.

Símbolos seguidos en la transmisión van a filas distintas. Una ráfaga de hasta $s\cdot t$ símbolos deja a cada fila con $t$ errores como mucho.

Pruébalo

En la demo, raya la imagen y pulsa corregir: las rayas cuentan como errores. Sube el daño hasta que falle. Luego repite con la casilla «Sé dónde he dañado» activada: las rayas pasan a ser borrones y el decodificador aguanta aproximadamente el doble. El ruido cuenta siempre como errores.

Ejercicios

Ejercicio 1

Un código $[255,223]$ sobre $\mathbb{F}_{256}$ corrige $t = 16$ errores por palabra. Se entrelazan $s = 5$ palabras (escritas en filas y transmitidas por columnas). ¿Cuántos bytes seguidos puede destruir una ráfaga sin que falle la decodificación?

Ver la solución

En la transmisión por columnas, los bytes van pasando por las filas 1, 2, 3, 4, 5, 1, 2… Una ráfaga de $L$ bytes seguidos toca cada fila como mucho $\lceil L/5 \rceil$ veces ($L/5$ redondeado hacia arriba). Para que ninguna fila pase de 16 errores hace falta $\lceil L/5 \rceil \le 16$, es decir, $L \le 80$.

Sin entrelazar, solo aguantaría 16: se multiplica por 5 sin añadir redundancia.

Ejercicio 2

Con el mismo mensaje $f(x) = 1+\alpha x+x^2$, ahora llega $r = (\alpha,\ 1,\ \alpha^2,\ \alpha,\ \alpha^4,\ \alpha^5,\ \alpha^5)$. El sistema de Berlekamp-Welch da $E(x) = x + \alpha^4$ y $Q(x) = x^3 + \alpha^2x^2 + \alpha^4x + \alpha^4$. ¿En qué posición está el error? Divide $Q$ entre $E$ y di cuánto valía el error.

Ver la solución

$E$ se anula en $\alpha^4$, el punto de la posición 5. Ahí está el error.

División de $Q$ entre $E = x+\alpha^4$:

1. $x^2\cdot(x+\alpha^4) = x^3 + \alpha^4x^2$. Queda $(\alpha^2+\alpha^4)x^2 + \alpha^4x + \alpha^4 = \alpha x^2 + \alpha^4x + \alpha^4$, porque $\alpha^2 + (\alpha^2+\alpha) = \alpha$.
2. $\alpha x\cdot(x+\alpha^4) = \alpha x^2 + \alpha^5x$. Queda $(\alpha^4+\alpha^5)x + \alpha^4 = x + \alpha^4$, porque $(\alpha^2+\alpha)+(\alpha^2+\alpha+1) = 1$.
3. $1\cdot(x+\alpha^4) = x+\alpha^4$. Resto 0.

El cociente es $x^2 + \alpha x + 1 = f(x)$. El símbolo correcto de la posición 5 es $f(\alpha^4) = \alpha^2$ (está en $c$), y llegó $\alpha^4$. El error valía $\alpha^4 - \alpha^2 = (\alpha^2+\alpha) + \alpha^2 = \alpha$.

Comprobación de la ecuación de la posición 5: $E(\alpha^4) = 0$ y $Q(\alpha^4) = 0$, así que se cumple valga lo que valga $r_5$.

En resumen

• Con $t$ errores, el polinomio correcto es el único de grado menor que $k$ que coincide con lo recibido en al menos $n-t$ posiciones, si $2t \le n-k$.
• Berlekamp-Welch añade el localizador $E$ como incógnita: las ecuaciones $Q(a_i) = r_iE(a_i)$ son lineales, $E$ señala el error y $f = Q/E$.
• En la práctica se usan Berlekamp-Massey o Euclides, que parten del síndrome.
• Errores y borrones se mezclan con la regla $2e+b \le n-k$.
• El entrelazado reparte una ráfaga entre varias palabras.

Y ahora, ¿qué?

Aquí termina el curso. Has visto qué es un código, los cuerpos finitos, los códigos lineales, la matriz generatriz y la de paridad, los errores y los borrones, el síndrome, los códigos cíclicos y Reed-Solomon, con su decodificación. Para seguir:

• Códigos BCH: los cíclicos con distancia garantizada; Reed-Solomon es un caso particular.
• Códigos LDPC: matrices de paridad muy dispersas, decodificación iterativa, y muy cerca del límite teórico del canal (la capacidad de Shannon).
• Códigos polares: alcanzan esa capacidad de forma asintótica, cuando la longitud tiende a infinito, en los canales binarios simétricos sin memoria.
• Códigos cuánticos: la misma idea de redundancia aplicada a cúbits, necesaria para construir ordenadores cuánticos que funcionen.

Para profundizar, Essential Coding Theory (libre) sigue con la parte algebraica, y el libro de MacKay (también libre) con LDPC y la teoría de la información. Tienes el mapa completo en la guía de códigos correctores, y puedes volver a Raya y corrige cuando quieras.