El (15,5) de punta a punta

El ejercicio recorre un decodificador BCH entero sobre un solo ejemplo. El código es el código BCH (15,5) con $t=3$, sobre $\mathrm{GF}(2^4)$, cuyo polinomio generador es el MCM de los polinomios mínimos de $\alpha$, ${\alpha }^3$ y ${\alpha }^5$:

con ${\phi }_1(X)=1+X+X^4$, ${\phi }_3(X)=1+X+X^2+X^3+X^4$ y ${\phi }_5(X)=1+X+X^2$. Su distancia mínima es 7: es el mismo (15,5) de la clase práctica de la Unidad 5, visto ahora desde sus raíces. El cuerpo es el de la Tabla 1 del apunte, con $p(X)=1+X+X^4$ y ${\alpha }^4=1+\alpha$. Los vectores van con la posición 0 a la izquierda.

01 · El enunciado

Planteado como ejercicio, el ejemplo integral del apunte pide:

1. Codificar en forma sistemática el mensaje $\mathrm{u}=(\mathrm{1\; 1\; 0\; 0\; 1})$.
2. El canal invierte los bits de las posiciones 2, 7 y 13. Escribir la palabra recibida $\mathrm{r}$.
3. Calcular los seis síndromes $S_1,\dots ,S_6$ con la Tabla 1, y verificar que $S_{2i}=S_i^2$.
4. Hallar el polinomio localizador $\sigma (X)$ con el algoritmo iterativo binario, fila por fila, con cada discrepancia.
5. Hallar sus raíces por búsqueda de Chien y las posiciones erradas.
6. Corregir, comprobar que la decodificación es consistente y recuperar el mensaje.

Antes de resolver: qué se entrega. Seis cosas de forma distinta. Dos vectores binarios de quince bits, $\mathrm{v}$ y $\mathrm{r}$. Seis elementos de $\mathrm{GF}(2^4)$, escritos como potencias de $\alpha$. Una tabla de $t+2=5$ filas que termina en un polinomio de grado a lo sumo 3 con coeficientes en el cuerpo. Tres posiciones. Y, al final, cinco bits que tienen que ser los del principio.

El mensaje, leído con la posición 0 a la izquierda, es

$$u(X)=1+X+X^4$$

02 · Las herramientas

La Tabla 1. Todas las cuentas del decodificador son sumas y productos en $\mathrm{GF}(2^4)$. Se multiplica sumando exponentes módulo 15, porque ${\alpha }^{15}=1$; se suma con el vector $(a_0{a}_1{a}_2{a}_3)$, bit a bit.

Codificar es una división. Como en cualquier código cíclico, la paridad es el resto de correr el mensaje $n-k=10$ lugares y dividirlo por $g(X)$, y la palabra es la paridad seguida del mensaje:

$$b(X)=R_{g(X)}\{X^{10}u(X)\},v(X)=b(X)+X^{10}u(X)$$

Los síndromes son evaluaciones. Con $r(X)=v(X)+e(X)$ y $e(X)$ el patrón de error, el síndrome $i$ es $r(X)$ evaluado en ${\alpha }^i$. Como las seis potencias son raíces de $g(X)$, la palabra no aporta nada:

$$S_i=r({\alpha }^i)=e({\alpha }^i),S_{2i}=S_i^2$$

La segunda igualdad es de los códigos binarios: elevar al cuadrado una suma es sumar los cuadrados. Sólo hay que evaluar $S_1$, $S_3$ y $S_5$. Lo explica la nota de los síndromes y el localizador.

El localizador. Si los errores están en $j_1,\dots ,j_{\nu }$, los números localizadores son $X_l={\alpha }^{j_l}$ y el polinomio localizador es

$$\sigma (X)=\prod _{l=1}^{\nu }(1+X_{l}X)=1+{\sigma }_{1}X+\cdots +{\sigma }_{\nu }{X}^{\nu }$$

Sus raíces son los inversos de los localizadores, y su grado es la cantidad de errores.

El algoritmo iterativo binario. Es la versión de Berlekamp-Massey para códigos binarios: $t$ iteraciones, sólo sobre los síndromes impares. La fila $\mu$ guarda ${\sigma }^{(\mu )}(X)$, su grado $l_{\mu }$ y la discrepancia, que mide cuánto le falta para generar el síndrome siguiente:

$$d_{\mu }=S_{2\mu +1}+{\sigma }_1^{(\mu )}{S}_{2\mu }+\cdots +{\sigma }_{l_{\mu }}^{(\mu )}{S}_{2\mu +1-l_{\mu }}$$

Si $d_{\mu }=0$, el polinomio pasa igual a la fila siguiente. Si no, se busca entre las filas anteriores con discrepancia no nula la $\rho$ que tenga el mayor $2\rho -l_{\rho }$, y se corrige:

$${\sigma }^{(\mu +1)}(X)={\sigma }^{(\mu )}(X)+d_{\mu }{d}_{\rho }^{-1}{X}^{2(\mu -\rho )}{\sigma }^{(\rho )}(X)$$

con grado $l_{\mu +1}=max(l_{\mu },l_{\rho }+2(\mu -\rho ))$. La tabla arranca con dos filas fijas: $\mu =-\frac{1}{2}$, con $\sigma =1$, $d=1$ y $l=0$; y $\mu =0$, con $\sigma =1$ y $d_0=S_1$. Termina en la fila $\mu =t$.

La búsqueda de Chien. Se evalúa $\sigma (X)$ en $1,\alpha ,\dots ,{\alpha }^{14}$. Si ${\alpha }^l$ es raíz, su inverso ${\alpha }^{15-l}$ es un localizador, y la posición errada es $15-l$. La búsqueda de Chien encadena las evaluaciones: el término ${\sigma }_i{\alpha }^{il}$ pasa al siguiente multiplicado por ${\alpha }^i$.

Las dos comprobaciones. Antes de corregir: que el grado de $\sigma (X)$ no pase de $t$, y que Chien encuentre tantas raíces distintas como ese grado. Si alguna falla, el decodificador declara falla de decodificación en vez de corregir.

03 · Codificar: la división a la vista

Primero pensar. $X^{10}u(X)=X^{10}+X^{11}+X^{14}$ tiene grado 14 y $g(X)$ grado 10: el cociente tiene grado 4 y la división, a lo sumo cinco pasos. Cada paso suma $X^{s}g(X)$ para matar el término de mayor grado, hasta que el resto baja de grado 10.

Después escribir.

Hubo tres pasos y no cinco, porque el cociente sólo tiene término donde el resto parcial lo pide. Después de $X^{4}g(X)$ el término más alto es $X^{12}$ y no $X^{13}$, así que no hay $X^3$ en el cociente; y después de $Xg(X)$ el resto ya tiene grado 8, así que tampoco hay término independiente. El cociente es $a(X)=X+X^2+X^4$ y la paridad, como vector de diez posiciones, $0100001110$. La palabra es

$$v(X)=X+X^6+X^7+X^8+X^{10}+X^{11}+X^{14}$$ $$\mathrm{v}=\underset{\text{paridad}}{\underbrace{0100001110}}\underset{\text{mensaje}}{\underbrace{11001}}$$

de peso 7, el mínimo del código. El control: $a(X)g(X)$ da exactamente $v(X)$, o, lo que es lo mismo, $v({\alpha }^i)=0$ para $i=1,\dots ,6$.

04 · El canal y los seis síndromes

Los errores son $e(X)=X^2+X^7+X^{13}$: el bit 2 pasa de 0 a 1, el 7 de 1 a 0 y el 13 de 0 a 1.

$$\mathrm{r}=011000101011011$$ $$r(X)=X+X^2+X^6+X^8+X^{10}+X^{11}+X^{13}+X^{14}$$

Primero pensar. El decodificador no conoce $e(X)$: evalúa $r(X)$, que tiene ocho términos. Para $S_1$ se suman las ocho potencias de $\alpha$ con la Tabla 1. Para $S_3$ y $S_5$ conviene reducir antes los exponentes módulo 15: muchos se repiten y se cancelan de a pares.

Después escribir. $S_1$, en vectores:

$S_3$: los exponentes $3j$ de las ocho posiciones son 3, 6, 18, 24, 30, 33, 39 y 42, que módulo 15 dan 3, 6, 3, 9, 0, 3, 9, 12. El ${\alpha }^3$ aparece tres veces y queda una; el ${\alpha }^9$, dos, y se va:

$S_5$: los exponentes son 5, 10, 0, 10, 5, 10, 5, 10. Tres ${\alpha }^5$ dejan uno y cuatro ${\alpha }^{10}$ se cancelan:

$$S_5=1+{\alpha }^5=1000+0110=1110={\alpha }^{10}$$

Los pares, elevando al cuadrado: $S_2=S_1^2={\alpha }^2$, $S_4=S_2^2={\alpha }^4$ y $S_6=S_3^2={\alpha }^{18}={\alpha }^3$.

El control. Con los tres errores a la vista, las mismas cuentas salen por otro camino, con tres términos en lugar de ocho: $S_1={\alpha }^2+{\alpha }^7+{\alpha }^{13}=\alpha$, $S_3={\alpha }^6+{\alpha }^{21}+{\alpha }^{39}={\alpha }^6+{\alpha }^6+{\alpha }^9={\alpha }^9$ y $S_5={\alpha }^{10}+{\alpha }^{35}+{\alpha }^{65}={\alpha }^{10}+{\alpha }^5+{\alpha }^5={\alpha }^{10}$. Coinciden porque $v(X)$ se anula en las seis raíces; si la palabra del punto 1 estuviera mal, acá no coincidirían.

05 · El localizador, fila por fila

Primero pensar. Con $t=3$ hay tres iteraciones, $\mu =0,1,2$, y cada una usa un síndrome impar nuevo: $S_1$, $S_3$, $S_5$. Si hay tres errores, el grado tiene que subir hasta 3. Si una discrepancia diera cero, el polinomio no cambiaría en ese paso.

Fila 0. $d_0=S_1=\alpha$, no nula. La única fila anterior con discrepancia no nula es $\rho =-\frac{1}{2}$. El corrimiento es $2(0+\frac{1}{2})=1$ y el factor $d_0/d_{-\frac{1}{2}}=\alpha$:

$${\sigma }^{(1)}(X)=1+\alpha X,l_1=max(0,0+1)=1$$

Fila 1. La discrepancia usa $S_3$, $S_2$ y el ${\sigma }_1$ recién calculado:

$$d_1=S_3+{\sigma }_1{S}_2={\alpha }^9+\alpha ·{\alpha }^2={\alpha }^9+{\alpha }^3=0101+0001=\alpha$$

Hay dos candidatas a $\rho$: $-\frac{1}{2}$, con $2\rho -l_{\rho }=-1$, y $0$, con $0$. Gana $\rho =0$. El corrimiento es $2(1-0)=2$ y el factor $d_1/d_0=\alpha /\alpha =1$:

$${\sigma }^{(2)}(X)=(1+\alpha X)+X^2·1=1+\alpha X+X^2,l_2=2$$

Fila 2. Con ${\sigma }_1=\alpha$ y ${\sigma }_2=1$:

Ahora hay tres candidatas, con $2\rho -l_{\rho }$ igual a −1, 0 y 1: gana $\rho =1$. Corrimiento $2(2-1)=2$, factor $d_2/d_1={\alpha }^7/\alpha ={\alpha }^6$, y el que se suma es ${\sigma }^{(1)}(X)$:

porque $1+{\alpha }^6=1000+0011=1011={\alpha }^{13}$. El grado sube a $l_3=max(2,1+2)=3$, y con $\mu =t$ el algoritmo termina:

$$\sigma (X)=1+\alpha X+{\alpha }^{13}{X}^2+{\alpha }^7{X}^3$$

El control. Para $t=3$ el método de Peterson tiene fórmula cerrada, con otras cuentas: ${\sigma }_1=S_1=\alpha$; $S_1^3+S_3={\alpha }^3+{\alpha }^9=\alpha$ y $S_1^2{S}_3+S_5={\alpha }^{11}+{\alpha }^{10}={\alpha }^{14}$, así que ${\sigma }_2={\alpha }^{14}/\alpha ={\alpha }^{13}$ y ${\sigma }_3=\alpha +\alpha ·{\alpha }^{13}=\alpha +{\alpha }^{14}={\alpha }^7$. El mismo polinomio.

06 · Chien: dónde se anula σ

Primero pensar. Un polinomio de grado 3 sobre un cuerpo de 16 elementos se resuelve probando: hay quince candidatos no nulos. Si los errores son tres y $\sigma (X)$ es el correcto, exactamente tres de las quince evaluaciones dan cero.

Después escribir. Los tres registros arrancan en ${\sigma }_1=\alpha$, ${\sigma }_2={\alpha }^{13}$ y ${\sigma }_3={\alpha }^7$, y en cada paso se multiplican por $\alpha$, ${\alpha }^2$ y ${\alpha }^3$. La suma con el 1 es $\sigma ({\alpha }^l)$:

La fila 2, sumada a mano:

Las raíces son ${\alpha }^2$, ${\alpha }^8$ y ${\alpha }^{13}$. Sus inversos, ${\alpha }^{13}$, ${\alpha }^7$ y ${\alpha }^2$, son los localizadores: los errores están en las posiciones 13, 7 y 2.

Cambiá el mensaje en cualquier etapa después de los síndromes: la palabra cambia, la recibida también, y los seis síndromes no se mueven. Después sacá el error de la posición 13 y mirá la fila 2: su discrepancia da cero, y el polinomio llega a la última fila con grado 2. Y por último agregá un cuarto error.

07 · La resolución, como se entrega

1. La paridad es el resto de $X^{10}+X^{11}+X^{14}$ por $g(X)$, $b(X)=X+X^6+X^7+X^8$, con cociente $X+X^2+X^4$. La palabra es $\mathrm{v}=010000111011001$, o $v(X)=X+X^6+X^7+X^8+X^{10}+X^{11}+X^{14}$.

2. $\mathrm{r}=011000101011011$.

3. $S_1=\alpha$, $S_2={\alpha }^2$, $S_3={\alpha }^9$, $S_4={\alpha }^4$, $S_5={\alpha }^{10}$, $S_6={\alpha }^3$. Los pares son los cuadrados de $S_1$, $S_2$ y $S_3$.

4. La tabla del algoritmo iterativo binario, la Tabla 8 del apunte:

Al lado de cada $2\mu -l_{\mu }$ va la $\rho$ con la que se armó esa fila. $\sigma (X)=1+\alpha X+{\alpha }^{13}{X}^2+{\alpha }^7{X}^3$.

5. $\sigma (X)$ se anula en ${\alpha }^2$, ${\alpha }^8$ y ${\alpha }^{13}$. Los localizadores son ${\alpha }^{13}$, ${\alpha }^7$ y ${\alpha }^2$: posiciones 13, 7 y 2.

6. El grado de $\sigma (X)$ es 3, que no pasa de $t=3$, y Chien encontró tres raíces distintas: la decodificación es consistente. Con $e(X)=X^2+X^7+X^{13}$, $r(X)+e(X)=v(X)$, y las cinco últimas posiciones devuelven $\mathrm{u}=(\mathrm{1\; 1\; 0\; 0\; 1})$.

08 · Lo que se lleva a otros ejercicios

El síndrome no ve el mensaje. Los seis síndromes dependen sólo de los errores. Con los errores en 2, 7 y 13, los 32 mensajes posibles dan los mismos seis valores: desde los síndromes en adelante, la cuenta es la misma para cualquier mensaje. El mensaje de un ejercicio así sirve para armar $\mathrm{r}$ y para comprobar el final, nada más.

El grado de $\sigma$ cuenta los errores, y la discrepancia nula lo muestra. Con un solo error, en la posición 7, $d_1=d_2=0$ y $\sigma (X)=1+{\alpha }^{7}X$. Con dos, en 2 y 13, $d_2=0$ y $\sigma (X)=1+{\alpha }^{14}X+X^2$. En las dos tablas, recorridas con el decodificador, el polinomio deja de cambiar en cuanto su grado llega a la cantidad de errores. El atajo de terminar antes de la fila $t$ cuando las discrepancias siguientes son nulas sale de acá.

Peterson es el control para $t\le 3$. La fórmula cerrada no comparte cuentas con el algoritmo iterativo: si los dos dan el mismo $\sigma (X)$, la tabla está bien.

Con un error de más, el decodificador no siempre avisa. A los tres errores del ejemplo se les puede agregar un cuarto en doce posiciones. Recorridas las doce con el decodificador: en ocho declara falla, porque $\sigma (X)$ sale de grado 3 y Chien no le encuentra ninguna raíz; en las otras cuatro —1, 5, 12 y 14— corrige tres posiciones y entrega, sin aviso, la misma palabra equivocada. Esa palabra difiere de $\mathrm{v}$ justo en $\{1,2,5,7,12,13,14\}$, una palabra de peso 7 que contiene a las tres posiciones del ejemplo. Por qué la cuenta la hacen esas palabras es la tesis de pasado t, la cuenta la hacen las palabras livianas.

En hardware, la mitad de los síndromes no se calcula. El circuito evalúa $S_1$, $S_3$ y $S_5$, y los pares salen elevando al cuadrado, que en $\mathrm{GF}(2^m)$ es lineal. Las tres etapas, con su costo, están en el decodificador BCH en hardware.

09 · Las trampas

Las raíces no son las posiciones. $\sigma (X)$ se anula en ${\alpha }^2$, ${\alpha }^8$ y ${\alpha }^{13}$. Leer esos exponentes como posiciones da 2, 8 y 13, y en este ejemplo dos de los tres coinciden con los errores verdaderos —2 y 13 son inversos entre sí, porque suman 15—, así que el error se esconde. La posición es $15-l$: la raíz ${\alpha }^8$ marca la posición 7, no la 8.

$\rho$ es la de mayor $2\rho -l_{\rho }$, no cualquiera. En la fila 2 hay dos filas anteriores con discrepancia $\alpha$, la 0 y la 1. Con $\rho =0$ el corrimiento sería $X^4$, el factor ${\alpha }^7/\alpha ={\alpha }^6$, y saldría $1+\alpha X+X^2+{\alpha }^6{X}^4$: grado 4, más que $t$. El decodificador declararía falla sobre un patrón que sabe corregir.

El corrimiento es $2(\mu -\rho )$. En la versión binaria las filas avanzan de a dos síndromes. Por eso la primera corrección, desde $\rho =-\frac{1}{2}$, corre una posición, y las otras dos corren dos.

Los exponentes se reducen. $S_3^2={\alpha }^{18}$ es ${\alpha }^3$, y ${\alpha }^{18}$ no está en la Tabla 1. Lo mismo con los $3j$ y $5j$ de los síndromes: reducirlos primero es lo que deja ver las cancelaciones.

El mensaje está al final de la palabra. En la forma sistemática del apunte la paridad ocupa las posiciones 0 a 9 y el mensaje las 10 a 14. Los cinco primeros bits de $\mathrm{v}$ son 01000, y eso es paridad, no el mensaje.

La última fila no tiene discrepancia. En $\mu =t$ el algoritmo termina: no hay $S_7$ con qué calcularla, y la casilla queda vacía.

Para tener a mano

1. $v(X)=R_{g(X)}\{X^{n-k}u(X)\}+X^{n-k}u(X)$. Acá $\mathrm{v}=010000111011001$.
2. $S_i=r({\alpha }^i)=e({\alpha }^i)$ y $S_{2i}=S_i^2$. Acá $\alpha ,{\alpha }^2,{\alpha }^9,{\alpha }^4,{\alpha }^{10},{\alpha }^3$.
3. $d_{\mu }=S_{2\mu +1}+{\sigma }_1^{(\mu )}{S}_{2\mu }+\cdots$; si no es nula, ${\sigma }^{(\mu +1)}(X)={\sigma }^{(\mu )}(X)+d_{\mu }{d}_{\rho }^{-1}{X}^{2(\mu -\rho )}{\sigma }^{(\rho )}(X)$, con $\rho$ la fila anterior de discrepancia no nula y mayor $2\rho -l_{\rho }$. Son $t$ iteraciones.
4. Acá las discrepancias son $\alpha$, $\alpha$ y ${\alpha }^7$, y $\sigma (X)=1+\alpha X+{\alpha }^{13}{X}^2+{\alpha }^7{X}^3$.
5. Si $\sigma ({\alpha }^l)=0$, la posición errada es $n-l$. Acá las raíces ${\alpha }^2$, ${\alpha }^8$ y ${\alpha }^{13}$ dan las posiciones 13, 7 y 2.
6. Antes de corregir: grado de $\sigma (X)$ a lo sumo $t$, y tantas raíces distintas como el grado. Si no, falla de decodificación.
7. El control de cada etapa por otro camino: los síndromes desde $e(X)$, $\sigma (X)$ por Peterson, y el mensaje recuperado contra el de partida.