Códigos de Reed-Solomon: polinomios que se dejan rayar

En las dos lecciones anteriores vimos que un polinomio puede servir de código: la palabra es un polinomio y el código, el conjunto de múltiplos de $g(x)$. Ahora los usaremos de otra manera: la que protege un QR rayado, un CD con arañazos y las imágenes de una sonda espacial. Son los códigos de Reed-Solomon y salen de una idea que ya conoces del instituto: por dos puntos pasa una sola recta.

La idea

Una recta $y = a + bx$ queda fijada por dos puntos. Una parábola, por tres. En general, un polinomio de grado menor que $k$ queda fijado por $k$ puntos cualesquiera de su gráfica.

Ahora imagina que tu mensaje son los $k$ coeficientes de un polinomio. No los mandas a ellos, sino los valores del polinomio en $n$ puntos, con $n$ mayor que $k$: como apuntar siete puntos de una parábola cuando bastan tres.

Si el canal destroza algunos valores, mientras sobrevivan $k$ la parábola se recupera, y con ella el mensaje. La redundancia son los $n-k$ puntos de más.

Los valores viven en un cuerpo finito, porque hay que sumar, multiplicar y dividir sin salirse de un conjunto de símbolos (por eso la lección 2 iba antes). Aquí usaremos $\mathbb{F}_8$.

Definición

Sea $\mathbb{F}_q$ un cuerpo finito y $\mathbb{F}_q[x]$ el conjunto de los polinomios con coeficientes en $\mathbb{F}_q$. Elige $n$ elementos distintos $a_1,\dots,a_n$ de $\mathbb{F}_q$ (los puntos de evaluación; por eso $n \le q$) y un número $k \le n$.

El código de Reed-Solomon es el conjunto de las palabras

$$c = \bigl(f(a_1), f(a_2), \dots, f(a_n)\bigr), \qquad f \in \mathbb{F}_q[x],\ \deg f < k.$$

El mensaje $(m_0, \dots, m_{k-1})$ son los coeficientes de $f(x) = m_0 + m_1 x + \dots + m_{k-1}x^{k-1}$. Es un código lineal (la suma de dos polinomios de grado menor que $k$ tiene grado menor que $k$) de dimensión $k$ y longitud $n$. Su matriz generatriz tiene en la fila $j$ las potencias $a_1^j, \dots, a_n^j$, para $j = 0, \dots, k-1$.

Distancia mínima. Es $d = n-k+1$. Dos palabras distintas vienen de dos polinomios distintos $f_1$ y $f_2$, y su diferencia $f_1-f_2$ es un polinomio no nulo de grado menor que $k$. Un polinomio así tiene como mucho $k-1$ raíces (recuadro de abajo), de modo que las dos palabras coinciden en como mucho $k-1$ posiciones. Difieren, pues, en al menos $n-(k-1)$.

Repaso Raíces de un polinomio

Un polinomio no nulo de grado $m$ tiene como mucho $m$ raíces en un cuerpo. Si $f(a) = 0$, la división entre $x-a$ da resto $f(a) = 0$, así que $f(x) = (x-a)\,h(x)$ con $h$ de grado $m-1$. Si $b \ne a$ es otra raíz, $(b-a)\,h(b) = 0$, y como en un cuerpo se puede dividir entre $b-a$, sale $h(b)=0$. Se repite con $h$, y cada raíz gasta un grado.

Por eso una recta corta al eje como mucho una vez y una parábola, dos. Sin cuerpo falla: en $\mathbb{Z}_8$, el polinomio $x^2-1$ tiene cuatro raíces (1, 3, 5 y 7).

Como la cota de Singleton de la lección 5 dice que $d \le n-k+1$, estos códigos llegan al máximo posible: son MDS (de distancia máxima separable).

Con $d = n-k+1$, un código de Reed-Solomon $[n,k,n-k+1]_q$ corrige:

• $n-k$ borrones (también se dice borrados; son los símbolos perdidos de los que se sabe la posición),
• $\lfloor (n-k)/2 \rfloor$ errores,
• o una mezcla con $2e + b \le n-k$.

Cada símbolo extra de redundancia corrige un borrón, pero hacen falta dos para corregir un error. Lo veremos en las dos próximas lecciones.

Símbolos, no bits

Los símbolos de $\mathbb{F}_{256}$ son bytes. Un código de Reed-Solomon sobre $\mathbb{F}_{256}$ (el GF(256) de los códigos QR) cuenta errores por byte: da igual que dentro del byte se hayan estropeado un bit o los ocho, es un símbolo erróneo.

Eso lo hace ideal para ráfagas: un arañazo estropea muchos bits seguidos, que caen en pocos bytes. Una ráfaga de 16 bits toca como mucho 3 bytes; bit a bit, serían 16 errores.

Versión cíclica

Cuando se toman como puntos todos los elementos no nulos de $\mathbb{F}_q$ en el orden $1, \alpha, \alpha^2, \dots, \alpha^{q-2}$, donde $\alpha$ genera los elementos no nulos del cuerpo, el código es cíclico (con $n = q-1$). Lo escribimos como en las lecciones 7 y 8, con índices desde 0: la palabra $(c_0,\dots,c_{n-1})$ es el polinomio $c(x)$, con $c_j = f(\alpha^j)$, y el código está formado por los múltiplos de

$$g(x) = (x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{n-k}).$$

Su grado es $n-k$, como corresponde a un código cíclico de dimensión $k$. Es el mismo código, visto como múltiplos de $g$. La ventaja es práctica: se codifica y se calcula el síndrome con divisiones de polinomios, como en la lección 8, que es lo que hacen los circuitos.

Ejemplo resuelto

Usamos el cuerpo $\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3+x+1)$, con $\alpha^3 = \alpha+1$ (la tabla de la lección 2):

potencia	polinomio en $\alpha$
$\alpha^0$	$1$
$\alpha^1$	$\alpha$
$\alpha^2$	$\alpha^2$
$\alpha^3$	$\alpha+1$
$\alpha^4$	$\alpha^2+\alpha$
$\alpha^5$	$\alpha^2+\alpha+1$
$\alpha^6$	$\alpha^2+1$

Sumar es sumar coeficientes módulo 2. Multiplicar es sumar exponentes módulo 7.

Tomamos $n = 7$ puntos, que son los siete elementos no nulos $1, \alpha, \alpha^2, \dots, \alpha^6$, y $k=3$. Es un código $[7,3,5]$ sobre $\mathbb{F}_8$, con $8^3 = 512$ palabras: corrige 2 errores, o 4 borrones, o 1 error y 2 borrones.

Ojo con la numeración. Como siempre en el curso, las posiciones van de 1 a 7, y la posición $i$ corresponde al punto $\alpha^{i-1}$: la posición 1 es el punto $1 = \alpha^0$ y la 7 es $\alpha^6$. En la versión cíclica, el símbolo $c_j$ es el de la posición $j+1$.

Mensaje: $(1, \alpha, 1)$, es decir, $f(x) = 1 + \alpha x + x^2$.

Evaluamos en cada punto:

• $f(1) = 1 + \alpha + 1 = \alpha$.
• $f(\alpha) = 1 + \alpha\cdot\alpha + \alpha^2 = 1 + \alpha^2 + \alpha^2 = 1$.
• $f(\alpha^2) = 1 + \alpha^3 + \alpha^4 = 1 + (\alpha+1) + (\alpha^2+\alpha) = \alpha^2$.
• $f(\alpha^3) = 1 + \alpha^4 + \alpha^6 = 1 + (\alpha^2+\alpha) + (\alpha^2+1) = \alpha$.
• $f(\alpha^4) = 1 + \alpha^5 + \alpha^8 = 1 + (\alpha^2+\alpha+1) + \alpha = \alpha^2$.
• $f(\alpha^5) = 1 + \alpha^6 + \alpha^{10} = 1 + (\alpha^2+1) + (\alpha+1) = \alpha^5$.
• $f(\alpha^6) = 1 + \alpha^7 + \alpha^{12} = 1 + 1 + \alpha^5 = \alpha^5$.

(Hemos usado $\alpha^7 = 1$ para bajar los exponentes.) La palabra código es

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

La distancia 5 se alcanza. El polinomio $(x-1)(x-\alpha) = x^2 + \alpha^3 x + \alpha$ tiene grado 2 y se anula en los puntos $1$ y $\alpha$. Su palabra es $(0,\ 0,\ \alpha^3,\ \alpha,\ 1,\ \alpha^3,\ 1)$, de peso 5. Más ceros no puede tener, porque un polinomio de grado 2 tiene como mucho 2 raíces.

Repaso Para quien quiera comprobarlo: la versión cíclica

Con $g(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)$ y sumando exponentes, se obtiene

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

Por ejemplo, el coeficiente de $x^3$ es $\alpha+\alpha^2+\alpha^3+\alpha^4 = \alpha + \alpha^2 + (\alpha+1) + (\alpha^2+\alpha) = \alpha+1 = \alpha^3$ (en $\mathbb{F}_8$, restar es sumar).

La palabra $c$ se escribe $c(x) = \alpha + x + \alpha^2x^2 + \alpha x^3 + \alpha^2x^4 + \alpha^5x^5 + \alpha^5x^6$. Al dividirla entre $g(x)$ sale el cociente $\alpha^5 + \alpha^6 x + \alpha^5 x^2$ y resto 0, así que $c$ también es $m(x)g(x)$ con ese $m(x)$ de grado 2.

Dónde se usan

• Códigos QR. Usan Reed-Solomon sobre GF(256). Por eso un QR se lee con un trozo tapado, y los niveles L, M, Q y H difieren en la redundancia (puedes probarlo en QR corrige errores).
• CD y DVD. Usan Reed-Solomon junto con entrelazado de símbolos para sobrevivir a arañazos y huellas.
• Comunicaciones espaciales. Es uno de los códigos estándar de las sondas lejanas, normalmente combinado con otro código.
• Almacenamiento RAID. El RAID 6 aguanta perder dos discos a la vez, y muchas implementaciones usan códigos de tipo Reed-Solomon: dos discos de redundancia reconstruyen dos borrones.

El CD y el espacio se cuentan en el libro de Wicker y Bhargava, y el RAID 6, en el artículo de Anvin (ver las fuentes).

Ejercicios

Ejercicio 1

En el código $[7,3,5]$ de arriba, calcula la palabra que corresponde al mensaje $(\alpha^3, \alpha^2, 0)$, es decir, a $f(x) = \alpha^3 + \alpha^2 x$.

Ver la solución

Evaluamos $f$ en los siete puntos, usando $\alpha^3 = \alpha+1$ y $\alpha^7=1$:

• $f(1) = \alpha^3 + \alpha^2 = (\alpha+1)+\alpha^2 = \alpha^5$.
• $f(\alpha) = \alpha^3 + \alpha^3 = 0$.
• $f(\alpha^2) = \alpha^3 + \alpha^4 = (\alpha+1)+(\alpha^2+\alpha) = \alpha^2+1 = \alpha^6$.
• $f(\alpha^3) = \alpha^3 + \alpha^5 = (\alpha+1)+(\alpha^2+\alpha+1) = \alpha^2$.
• $f(\alpha^4) = \alpha^3 + \alpha^6 = (\alpha+1)+(\alpha^2+1) = \alpha^2+\alpha = \alpha^4$.
• $f(\alpha^5) = \alpha^3 + \alpha^7 = (\alpha+1)+1 = \alpha$.
• $f(\alpha^6) = \alpha^3 + \alpha^8 = \alpha^3+\alpha = 1$.

La palabra es $(\alpha^5, 0, \alpha^6, \alpha^2, \alpha^4, \alpha, 1)$, de peso 6: un polinomio de grado 1 tiene una sola raíz.

Ejercicio 2

Un código de Reed-Solomon sobre $\mathbb{F}_8$ tiene $n = 7$ y $k = 4$. ¿Cuál es su distancia mínima? ¿Cuántos errores corrige? ¿Y cuántos borrones? ¿Cuál es su tasa?

Ver la solución

Por ser MDS, $d = n-k+1 = 7-4+1 = 4$.

• Errores: $t = \lfloor (4-1)/2 \rfloor = 1$.
• Borrones: $d-1 = 3$.
• Tasa: $R = k/n = 4/7$.

Frente al $[7,3,5]$, ganas tasa a costa de corregir 1 error en vez de 2.

Ejercicio 3

Un código de Reed-Solomon sobre $\mathbb{F}_{256}$ tiene $n = 255$ y $k = 223$. Calcula $d$, los errores que corrige y la tasa (en porcentaje, con un decimal). ¿Cuántos bytes puede perder, si se sabe cuáles son?

Ver la solución

• $d = 255-223+1 = 33$.
• Corrige $\lfloor 32/2 \rfloor = 16$ errores (bytes erróneos, sea cual sea el daño en sus bits).
• La tasa es $223/255 \approx 0{,}875$, es decir, $87{,}5\,\%$.
• Si se conocen las posiciones, son borrones, y se corrigen hasta $d-1 = 32$ bytes perdidos, seguidos o no.

En resumen

• Un código de Reed-Solomon codifica un mensaje de $k$ símbolos como los valores en $n$ puntos de un polinomio de grado menor que $k$.
• Dos polinomios distintos coinciden en como mucho $k-1$ puntos, y de ahí sale $d = n-k+1$, el máximo posible (código MDS).
• Corrige $n-k$ borrones, o $\lfloor (n-k)/2 \rfloor$ errores, o una mezcla con $2e+b \le n-k$.
• Trabaja con símbolos (por ejemplo, bytes), así que soporta muy bien las ráfagas.
• Con todos los puntos no nulos, en el orden $1, \alpha, \dots, \alpha^{n-1}$, es un código cíclico con $g(x) = (x-\alpha)\cdots(x-\alpha^{n-k})$.

Siguiente lección: Decodificar Reed-Solomon: recuperar borrones por interpolación