El síndrome cíclico

En un código lineal cualquiera, el síndrome es un producto por la matriz de paridad: hace falta tener $H$ guardada y un árbol de sumas por cada fila. En un código cíclico es el resto de una división, y lo calcula el mismo registro que codifica. Lo que se gana no termina ahí: girar la palabra recibida cuesta un ciclo de ese registro, y no una división nueva. Toda la decodificación de la unidad se apoya en eso.

01 · La definición

Sea un código cíclico $(n,k)$ con polinomio generador $g(X)$, de grado $n-k$, y sea $r(X)=r_0+r_{1}X+\cdots +r_{n-1}{X}^{n-1}$ lo recibido. Dividido por $g(X)$,

$$r(X)=a(X)g(X)+s(X),\mathrm{grado}s(X)<n-k$$

El resto es el polinomio síndrome:

$$s(X)=R_{g(X)}\{r(X)\}=s_0+s_{1}X+\cdots +s_{n-k-1}{X}^{n-k-1}$$

Sus $n-k$ coeficientes son el vector síndrome $s=(s_0,s_1,\dots ,s_{n-k-1})$, que se escribe con $s_0$ a la izquierda, como las palabras.

Las dos propiedades del síndrome de siempre siguen valiendo, y salen en una línea cada una:

Es cero exactamente en las palabras. Las palabras de código son los múltiplos de $g(X)$, así que $s(X)=0$ si y sólo si $r(X)$ es una palabra.

Depende sólo del error. Con $r(X)=v(X)+e(X)$, donde $e(X)$ es el patrón de error, y $v(X)$ múltiplo de $g(X)$:

$$s(X)=R_{g(X)}\{r(X)\}=R_{g(X)}\{e(X)\}$$

Lo nuevo no es qué es el síndrome. Es cómo se calcula, y qué le pasa cuando se gira la palabra.

02 · El registro que divide

Dividir por $g(X)$ se hace con un registro de desplazamiento de $n-k$ etapas, que guardan $s_0,\dots ,s_{n-k-1}$, con una conexión de realimentación por cada coeficiente no nulo de $g(X)$. La palabra recibida entra un bit por ciclo, empezando por $r_{n-1}$. Por qué al cabo de $n$ ciclos el registro tiene el resto, en tres pasos:

Paso 1: la palabra, por Horner. El polinomio se puede armar desde el coeficiente de mayor orden, multiplicando por $X$ y sumando el que sigue:

$$r(X)=(\cdots (r_{n-1}X+r_{n-2})X+\cdots )X+r_0$$

Paso 2: se puede reducir en cada paso. El resto de una suma es la suma de los restos, y el de un producto se puede tomar antes de multiplicar. Si el registro guarda $s(X)$, el resto de lo que entró hasta ahí, el que sigue es $R_{g(X)}\{Xs(X)\}+r_j$: el bit que entra tiene grado 0 y no hay que reducirlo.

Paso 3: multiplicar por $X$ y reducir es un ciclo. $Xs(X)$ corre cada coeficiente una etapa a la derecha. Lo único que puede pasarse de grado es el que sale de la última, $s_{n-k-1}$, que se convierte en $X^{n-k}$; y como $X^{n-k}=g_0+g_{1}X+\cdots +g_{n-k-1}{X}^{n-k-1}$ módulo $g(X)$, ese bit vuelve a entrar en cada etapa $i$ con $g_i=1$. Eso es la realimentación. El bit recibido se suma en $s_0$.

Con $g(X)=1+X+X^3$ y $r=0010110$, que entra empezando por $r_6$, el registro pasa por

$$000\to 000\to 100\to 110\to 011\to 011\to 111\to 101$$

y termina en $s=101$, es decir $s(X)=1+X^2$. Es el resto de dividir $X^2+X^4+X^5$ por $g(X)$.

Las etapas y las conexiones son las del codificador. Lo único que cambia es por dónde entra la palabra: el codificador suma el mensaje en la realimentación, del lado de $s_{n-k-1}$, y eso equivale a multiplicarlo por $X^{n-k}$ antes de dividir. Para el síndrome, la palabra entra por $s_0$. Qué pasa si se la mete por el mismo lado que el mensaje está en la sección siguiente.

03 · El síndrome de siempre, con otra H

El resto es lineal: el de una suma es la suma de los restos. Entonces

$$s(X)=R_{g(X)}\{e(X)\}=\sum _{e_i=1}{R}_{g(X)}\{X^i\}$$

que es lo mismo que decía la Unidad 3: el síndrome es la suma de las columnas de la matriz de paridad donde hubo error. Acá la columna $i$ es $R_{g(X)}\{X^i\}$. Para $i<n-k$, $X^i$ ya tiene grado menor que $g(X)$ y es su propio resto: las primeras $n-k$ columnas son la identidad, y $H$ queda con la paridad primero y el mensaje al final, como la forma sistemática cíclica. En el (7,4) de $g(X)=1+X+X^3$, las siete columnas son los síndromes de los siete errores simples:

Los siete síndromes no nulos aparecen una vez cada uno, y por eso el código corrige un error. Es la tabla de síndromes del apunte.

El (7,4) de la Unidad 3, el de $G=[I_{4}P]$, tiene exactamente el mismo conjunto de palabras que este, y su $H$ tiene por columnas $110,011,111,101,100,010,001$. Es la misma fila de arriba, empezada en $X^3$. Comprobado sobre los 128 vectores de siete bits, el síndrome de la Unidad 3 es

$$r{H}^T=R_{g(X)}\{X^{3}r(X)\}$$

en los 128, y no coincide con ningún otro corrimiento salvo en las 16 palabras, donde los dos dan cero. Y $R_{g(X)}\{X^{n-k}r(X)\}$ es justo lo que calcula el registro si la palabra entra por el lado del codificador, con $n-k=3$: el calculador de síndrome de la Unidad 3, el de las tres ecuaciones de paridad, da bit por bit lo mismo que el codificador cíclico alimentado con lo recibido. Las dos maneras de entrar dan dos síndromes válidos, los dos nulos sólo en las palabras; lo que cambia es la tabla que hay que leer después.

Lo nuevo, entonces, es otra cosa. En la Unidad 3 el síndrome pedía $H$ entera, $(n-k)\times n$ bits cableados: 150 en el (15,5). Acá alcanzan $n-k$ etapas y las conexiones que marca $g(X)$, y el costo crece con la redundancia, no con el largo. Y aparece una propiedad que la matriz no tenía.

04 · Un ciclo más es la palabra girada

Sea $r^{(1)}(X)$ el desplazamiento cíclico de $r(X)$: cada bit una posición a la derecha, y $r_{n-1}$ vuelve a la posición 0.

Teorema 5. Si $s(X)$ es el síndrome de $r(X)$, el síndrome de $r^{(1)}(X)$ es

$$s^{(1)}(X)=R_{g(X)}\{Xs(X)\}$$

Paso 1: girar es multiplicar por $X$ y devolver el bit que sale. $Xr(X)$ corre todo un lugar, y el coeficiente $r_{n-1}$ cae en $X^n$, fuera de la palabra. Sumarle $r_{n-1}(X^n+1)$ lo saca de ahí y lo pone en la posición 0:

$$r^{(1)}(X)=Xr(X)+r_{n-1}(X^n+1)$$

Paso 2: reemplazar lo que se sabe. Con $r(X)=a(X)g(X)+s(X)$ y $X^n+1=g(X)h(X)$, porque $g(X)$ divide a $X^n+1$:

$$r^{(1)}(X)=Xs(X)+[Xa(X)+r_{n-1}h(X)]g(X)$$

Paso 3: el múltiplo de $g(X)$ no deja resto. El segundo término desaparece al dividir, y el resto de $r^{(1)}(X)$ es el de $Xs(X)$.

Y $R_{g(X)}\{Xs(X)\}$ es exactamente el Paso 3 de la sección 02 sin bit de entrada: un ciclo de reloj del registro, con la entrada cerrada. Iterando,

$$s^{(i)}(X)=R_{g(X)}\{X^{i}s(X)\}$$

Recorrer los $n$ giros de la palabra cuesta $n$ ciclos de reloj. Dividir desde cero cada palabra girada costaría $n$ ciclos por giro, $n^2$ en total, y además habría que volver a cargarla.

La tabla de la sección 03 se lee ahora de otra manera: cada columna es la anterior con un ciclo más, porque $X^{i+1}$ es $X^i$ girado. Con un error en $X^2$, el registro arranca en $001$ y recorre $110,011,111,101,100,010$, mientras el error pasa por $X^3,\dots ,X^6,1,X$. En el ejemplo de la sección 02, $s=101$ sigue con $s^{(1)}=100$ y $s^{(2)}=010$.

Un caso más largo, en el (15,5) de $g(X)=1+X+X^2+X^4+X^5+X^8+X^{10}$: el mensaje $10110$ se codifica como $v=010100001110110$, y con un error en $X^{12}$ llega $r=010100001110010$. Por el registro y dividiendo cada palabra girada desde cero:

Al tercer giro el error, que estaba en $X^{12}$, llegó a $X^{15}$, que es la posición 0. Cayó dentro de las diez primeras, donde $X^i$ es su propio resto, y el registro muestra el error mismo. Esa es la idea de la captura de errores. El teorema, por su parte, se comprobó sobre todo lo que puede llegar: los 128 vectores de siete bits y los 32 768 de quince.

Arranca con la palabra del codificador del (7,4) para el mensaje 1011, sin errores. Cargala y girala: el registro queda en cero y no se mueve, porque una palabra girada sigue siendo palabra. Volvé a empezar, tocá el bit 0, cargala y girala seis veces: la tabla que se arma abajo es la de la sección 03. En el (15,5), tocá el bit 12, cargala y mirá el tercer giro.

05 · El recorrido vuelve

Como $g(X)$ divide a $X^n+1$, $X^n\equiv 1$ módulo $g(X)$, y entonces $s^{(n)}(X)=s(X)$: después de $n$ ciclos el registro vuelve a donde estaba, igual que la palabra después de $n$ giros. Puede volver antes. Si girar $p$ veces deja al error igual, deja igual a su síndrome; y el largo de cada recorrido divide a $n$.

Medido haciendo andar el registro sin entrada desde cada uno de sus estados no nulos:

En el (7,4) hay un solo recorrido y pasa por los siete síndromes: desde cualquier error simple, siete ciclos visitan los siete. En el (15,5), $1+X^5+X^{10}$ es igual a sí mismo girado cinco veces, y su síndrome, $0110100010$, vuelve en cinco ciclos; $1+X^3+X^6+X^9+X^{12}$ vuelve en tres. Un decodificador que gira $n$ veces no pierde nada con eso: un recorrido corto se repite, y en $n$ ciclos pasa por todos sus estados. El registro sin entrada es un LFSR, y estos recorridos son sus órbitas.

06 · Lo que el teorema no da

No dice dónde está el error. El síndrome sigue siendo una de $2^{n-k}$ combinaciones, y algo tiene que traducirlo a un patrón. Lo que el teorema permite es preguntar siempre por la misma posición mientras la palabra gira: el decodificador de Meggitt reconoce sólo los síndromes de los errores que tocan la posición $n-1$, uno solo en el (7,4), y corrige un bit por ciclo. Cuando los errores caben en $n-k$ posiciones seguidas, la captura de errores no necesita ni eso.

Pide el giro de largo $n$. La propiedad habla del desplazamiento cíclico de las $n$ posiciones. Un código acortado $(n-l,k-l)$ ya no es cíclico: el registro sigue calculando el síndrome, pero el anillo sobre el que gira es el de $n$ posiciones, y $l$ de ellas no se transmiten. Si la palabra entra por el lado del codificador, para que el registro llegue al síndrome del primer bit a decodificar hacen falta $l$ ciclos más, o cablear la entrada de otra manera; está en los CRC y los códigos acortados.

No ve los errores que son palabras. $s(X)=0$ cuando $e(X)$ es múltiplo de $g(X)$, igual que en cualquier código lineal: en el (7,4) son 15 patrones no nulos, los mismos de un síndrome cero no prueba nada. Girarlos no ayuda, porque una palabra girada sigue siendo palabra y su síndrome se queda en cero.

Para tener a mano

1. $s(X)=R_{g(X)}\{r(X)\}=R_{g(X)}\{e(X)\}$, de grado menor que $n-k$. Es cero si y sólo si $r(X)$ es palabra.
2. Lo calcula el registro del codificador, de $n-k$ etapas, con $r(X)$ entrando por $s_0$ desde $r_{n-1}$: $n$ ciclos y el registro tiene el resto. Sin $H$.
3. La columna $i$ de $H$ es $R_{g(X)}\{X^i\}$: la identidad en las $n-k$ primeras. En el (7,4): 100, 010, 001, 110, 011, 111, 101.
4. Con la palabra entrando por el lado del codificador, el registro da $R_{g(X)}\{X^{n-k}r(X)\}$: en el (7,4), el síndrome de la Unidad 3, en los 128 vectores.
5. Teorema 5: $s^{(1)}(X)=R_{g(X)}\{Xs(X)\}$. Girar la palabra es un ciclo del registro con la entrada cerrada; $n$ giros cuestan $n$ ciclos, no $n$ divisiones.
6. Después de $n$ ciclos el registro vuelve; puede volver antes, en un divisor de $n$.