Decodificar Reed-Solomon: recuperar borrones por interpolación

En la lección anterior construimos el código $[7,3,5]$ sobre $\mathbb{F}_8$: un mensaje de 3 símbolos es un polinomio de grado menor que 3 y se envía como sus valores en 7 puntos. Ahora toca recuperarlo cuando el canal estropea parte de la palabra. Empezamos por el caso fácil, los borrones: cuando en un RAID 6 se estropea un disco, el sistema sabe cuál es, y solo tiene que reconstruir lo que había. En la próxima lección veremos los errores, en los que ni siquiera sabes dónde está el daño.

La idea

Un polinomio de grado menor que $k$ queda fijado por $k$ puntos cualesquiera de su gráfica. Si sabemos qué posiciones se han perdido, nos quedamos con $k$ de las que sobreviven y buscamos la única curva que pasa por ellas. Eso se llama interpolación.

Hay dos formas de hacerlo. Una es una fórmula que construye la curva pieza a pieza (Lagrange). La otra es plantear un sistema lineal cuyas incógnitas son los coeficientes del polinomio, y resolverlo como siempre. Las dos dan lo mismo.

Interpolación de Lagrange

Supongamos que conocemos los valores $y_1,\dots,y_k$ del polinomio $f$ en $k$ puntos distintos $x_1,\dots,x_k$. La fórmula de Lagrange da $f$ directamente:

$$f(x) = \sum_{i=1}^{k} y_i\, L_i(x), \qquad L_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j}.$$

El símbolo $\sum$ es una suma y $\prod$ un producto: $L_i$ multiplica las fracciones $\frac{x-x_j}{x_i-x_j}$ para todos los $j$ distintos de $i$. Así, $L_i$ vale 1 en $x_i$ y 0 en los demás $x_j$, y la suma pasa por todos los puntos. La fórmula funciona en cualquier cuerpo, también en $\mathbb{F}_8$.

Como sistema lineal. Escribe $f(x) = m_0 + m_1x + \dots + m_{k-1}x^{k-1}$. Cada punto conocido da una ecuación $f(x_i) = y_i$, lineal en los coeficientes. Son $k$ ecuaciones con $k$ incógnitas, y la matriz tiene filas $(1, x_i, x_i^2, \dots, x_i^{k-1})$ (en el ejemplo, $k=3$: $(1,x_i,x_i^2)$). Es una matriz de Vandermonde, invertible porque los $x_i$ son distintos, así que la solución es única.

Con $d = n-k+1$ se recuperan hasta $n-k$ borrones, porque sobreviven al menos $k$ posiciones. Con más no se puede: con menos de $k$ puntos pasan varios polinomios.

Ejemplo resuelto: 4 borrones

Seguimos con el ejemplo hilo, en $\mathbb{F}_8$ con $\alpha^3=\alpha+1$ y $\alpha^7=1$. Enviamos la palabra

$$c = (\alpha,\ 1,\ \alpha^2,\ \alpha,\ \alpha^2,\ \alpha^5,\ \alpha^5),$$

que viene del mensaje $(1,\alpha,1)$, o sea $f(x)=1+\alpha x+x^2$. La posición $i$ corresponde al punto $\alpha^{i-1}$.

El canal borra las posiciones 1, 2, 4 y 6 (son 4 borrones, el máximo que corrige el código). Recibimos:

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

Quedan tres puntos de la gráfica de $f$: $(\alpha^2,\alpha^2)$, $(\alpha^4,\alpha^2)$ y $(\alpha^6,\alpha^5)$. Como $k=3$, bastan. Recuerda que en $\mathbb{F}_8$ restar es sumar.

$L_1$ (punto $\alpha^2$). El numerador es $(x-\alpha^4)(x-\alpha^6) = x^2 + (\alpha^4+\alpha^6)x + \alpha^{10} = x^2 + \alpha^3 x + \alpha^3$, porque $\alpha^4+\alpha^6 = (\alpha^2+\alpha)+(\alpha^2+1) = \alpha^3$. El denominador es $(\alpha^2+\alpha^4)(\alpha^2+\alpha^6) = \alpha \cdot 1 = \alpha$. Dividir entre $\alpha$ es multiplicar por $\alpha^{-1} = \alpha^6$:

$$L_1(x) = \alpha^6 x^2 + \alpha^2 x + \alpha^2.$$

$L_2$ (punto $\alpha^4$). El numerador es $(x-\alpha^2)(x-\alpha^6) = x^2 + (\alpha^2+\alpha^6)x + \alpha^8 = x^2 + x + \alpha$, porque $\alpha^2+\alpha^6 = \alpha^2+(\alpha^2+1) = 1$. El denominador es $(\alpha^4+\alpha^2)(\alpha^4+\alpha^6) = \alpha\cdot\alpha^3 = \alpha^4$, y su inverso es $\alpha^3$:

$$L_2(x) = \alpha^3 x^2 + \alpha^3 x + \alpha^4.$$

$L_3$ (punto $\alpha^6$). El numerador es $(x-\alpha^2)(x-\alpha^4) = x^2 + (\alpha^2+\alpha^4)x + \alpha^6 = x^2 + \alpha x + \alpha^6$. El denominador es $(\alpha^6+\alpha^2)(\alpha^6+\alpha^4) = 1\cdot\alpha^3 = \alpha^3$, y su inverso es $\alpha^4$:

$$L_3(x) = \alpha^4 x^2 + \alpha^5 x + \alpha^3.$$

La suma. $f = \alpha^2 L_1 + \alpha^2 L_2 + \alpha^5 L_3$. Coeficiente a coeficiente:

• Término en $x^2$: $\alpha^2\alpha^6 + \alpha^2\alpha^3 + \alpha^5\alpha^4 = \alpha + \alpha^5 + \alpha^2 = 1$.
• Término en $x$: $\alpha^2\alpha^2 + \alpha^2\alpha^3 + \alpha^5\alpha^5 = \alpha^4 + \alpha^5 + \alpha^3 = \alpha$.
• Término independiente: $\alpha^2\alpha^2 + \alpha^2\alpha^4 + \alpha^5\alpha^3 = \alpha^4 + \alpha^6 + \alpha = 1$.

(Cada suma se hace pasando a vectores de la tabla: por ejemplo, $\alpha+\alpha^5+\alpha^2 = (0,1,0)+(1,1,1)+(0,0,1) = (1,0,0) = 1$.)

Resultado: $f(x) = 1 + \alpha x + x^2$, el polinomio original, y el mensaje es $(1,\alpha,1)$. Para recuperar la palabra entera, evaluamos $f$ en los puntos borrados: $f(1)=\alpha$, $f(\alpha)=1$, $f(\alpha^3)=\alpha$ y $f(\alpha^5)=\alpha^5$, que son los símbolos de las posiciones 1, 2, 4 y 6.

Con otras tres posiciones cualesquiera habría salido el mismo $f$: los siete valores de $c$ son puntos de $f$, y por tres puntos pasa un solo polinomio de grado menor que 3.

Por qué un borrón vale la mitad que un error

Ante un borrón conoces la posición y solo te falta el valor: una incógnita. Ante un error te faltan las dos cosas, la posición y el valor. Cada incógnita cuesta un símbolo de redundancia, así que un borrón gasta uno y un error gasta dos. Con $n-k$ símbolos de redundancia se recuperan $n-k$ borrones, pero solo $\lfloor (n-k)/2 \rfloor$ errores. Y en general, con $e$ errores y $b$ borrones, la regla es $2e + b \le n-k$.

Puedes verlo en Raya y corrige: raya la imagen hasta que el decodificador falle, y repite con la casilla «Sé dónde he dañado» activada. Con ella, los símbolos rayados pasan a ser borrones (el decodificador sabe dónde están) y aguanta aproximadamente el doble de rayas.

Ejercicios

Ejercicio 1

En $\mathbb{F}_7$ (los restos módulo 7) se usa un código de Reed-Solomon con los puntos $1, 2, 3, 4, 5, 6$ y $k = 2$: el mensaje es una recta $f(x) = m_0 + m_1x$. Se recibe $r = (?,\ 0,\ ?,\ ?,\ 6,\ ?)$. Recupera el mensaje y la palabra enviada.

Ver la solución

Sobreviven las posiciones 2 y 5: $f(2) = 0$ y $f(5) = 6$. Es decir,

$$m_0 + 2m_1 = 0, \qquad m_0 + 5m_1 = 6.$$

Restando, $3m_1 = 6$, así que $m_1 = 2$. Entonces $m_0 = -4 = 3$ (en $\mathbb{F}_7$, $-4 = 3$). El mensaje es $(3, 2)$, es decir, $f(x) = 3 + 2x$.

Evaluando en los seis puntos: $f(1) = 5$, $f(2) = 0$, $f(3) = 2$, $f(4) = 4$, $f(5) = 6$, $f(6) = 15 = 1$. La palabra es $(5, 0, 2, 4, 6, 1)$. Es un código $[6,2,5]$: aguanta $6-2 = 4$ borrones, justo los que había.

Ejercicio 2

En el código $[7,3,5]$ del ejemplo se recibe $r = (\alpha^5,\ ?,\ ?,\ \alpha^2,\ ?,\ \alpha,\ ?)$. Recupera el mensaje resolviendo el sistema lineal (no con Lagrange).

Ver la solución

Sobreviven las posiciones 1, 4 y 6, es decir, los puntos $1$, $\alpha^3$ y $\alpha^5$. Con $f(x) = m_0 + m_1x + m_2x^2$ y $(\alpha^5)^2 = \alpha^{10} = \alpha^3$:

$$\begin{aligned} m_0 + m_1 + m_2 &= \alpha^5,\\ m_0 + \alpha^3 m_1 + \alpha^6 m_2 &= \alpha^2,\\ m_0 + \alpha^5 m_1 + \alpha^3 m_2 &= \alpha. \end{aligned}$$

Sumamos la primera ecuación a las otras dos (en $\mathbb{F}_8$, sumar es restar), con $\alpha^3+1 = \alpha$, $\alpha^6+1 = \alpha^2$ y $\alpha^5+1 = \alpha^4$:

$$\alpha m_1 + \alpha^2 m_2 = \alpha^2+\alpha^5 = \alpha^3, \qquad \alpha^4 m_1 + \alpha m_2 = \alpha+\alpha^5 = \alpha^6.$$

Multiplicamos la primera por $\alpha^3$: $\alpha^4 m_1 + \alpha^5 m_2 = \alpha^6$. Sumada a la segunda queda $(\alpha+\alpha^5)\,m_2 = 0$, es decir, $\alpha^6 m_2 = 0$, y $m_2 = 0$. Entonces $\alpha m_1 = \alpha^3$, así que $m_1 = \alpha^2$. Y $m_0 = \alpha^5 + \alpha^2 = \alpha + 1 = \alpha^3$.

El mensaje es $(\alpha^3, \alpha^2, 0)$: el del ejercicio 1 de la lección 9, cuya palabra es $(\alpha^5, 0, \alpha^6, \alpha^2, \alpha^4, \alpha, 1)$.

Ejercicio 3

Del código $[7,3,5]$ solo llegan las posiciones 6 y 7 de la palabra $c$ del ejemplo, $\alpha^5$ y $\alpha^5$, y se sabe cuáles son: hay 5 borrones. Encuentra un polinomio de grado menor que 3, distinto de $f(x) = 1 + \alpha x + x^2$, que también encaje. ¿Cuántos encajan en total?

Ver la solución

El polinomio constante $\alpha^5$ vale $\alpha^5$ en todos los puntos, también en $\alpha^5$ y $\alpha^6$. Así que los mensajes $(\alpha^5, 0, 0)$ y $(1, \alpha, 1)$ son compatibles con lo recibido, y no hay forma de saber cuál se envió.

En total encajan 8: si además se fija el valor en un tercer punto, hay un único polinomio por los tres, y ese valor se puede elegir de 8 maneras (los 8 elementos de $\mathbb{F}_8$). Por eso 5 borrones son demasiados: $5 > n-k = 4$.

En resumen

• Con borrones, $k$ símbolos que sobrevivan bastan: se interpola y se recupera el polinomio, y con él el mensaje.
• La interpolación se hace con la fórmula de Lagrange o resolviendo un sistema lineal con matriz de Vandermonde.
• Se recuperan hasta $n-k$ borrones; con uno más, pasan varios polinomios por lo que queda.
• Un borrón cuesta un símbolo de redundancia y un error, dos: $2e+b \le n-k$.

Siguiente lección: Corregir errores en Reed-Solomon