Los síndromes y el polinomio localizador

Un código BCH se define por raíces: su generador se anula en $2t$ potencias consecutivas de un elemento $\beta$. Decodificarlo empieza por preguntarle a lo recibido cuánto vale en esas raíces. Lo que contesta son los síndromes, y lo que hay que sacar de ellos son las posiciones de los errores: un sistema no lineal que se vuelve lineal al cambiar de incógnita, y que resulta ser la descripción de un registro de desplazamiento.

01 · Lo recibido, evaluado en las raíces

Sea un BCH binario $(n,k)$ que corrige $t$ errores, con $g(X)=\text{MCM}\{{\phi }_1(X),\dots ,{\phi }_{2t}(X)\}$, donde ${\phi }_i(X)$ es el polinomio mínimo de ${\beta }^i$ y $\beta$ tiene orden $n$ en $\text{GF}(2^m)$. Llega $r(X)=v(X)+e(X)$. El componente $i$ del síndrome es

$$S_i=r({\beta }^i),i=1,2,\dots ,2t$$

Cada $S_i$ es un elemento de $\text{GF}(2^m)$, no un bit: el síndrome entero son $2t$ elementos del cuerpo, $2tm$ bits escritos. Los índices empiezan en 1 porque las raíces pedidas empiezan en $\beta$; con otro primer exponente se corren igual. Dos pasos lo llevan del canal al error.

Paso 1: lo transmitido no aporta. Toda palabra $v(X)$ es múltiplo de $g(X)$, que se anula en ${\beta }^i$. Entonces $v({\beta }^i)=0$ y $S_i=e({\beta }^i)$: el síndrome depende sólo del patrón de error, como en todo código lineal.

Paso 2: el error, posición por posición. Si hubo $\nu$ errores, en las posiciones $j_1,\dots ,j_{\nu }$, entonces $e(X)=X^{j_1}+\cdots +X^{j_{\nu }}$, y evaluado en ${\beta }^i$:

$$S_i=\sum _{l=1}^{\nu }{({\beta }^{j_l})}^i$$

Siendo binario, no hay magnitudes de error que averiguar: conocida una posición errada, se invierte el bit. Todo el problema es encontrar las $\nu$ posiciones.

Es el mismo síndrome de la Unidad 5, leído en otro cuerpo. Allá el síndrome era el resto $s(X)=R_{g(X)}\{r(X)\}$, que calcula el registro divisor de el síndrome cíclico. Como $r(X)=a(X)g(X)+s(X)$ y $g(X)$ se anula en las raíces,

$$S_i=s({\beta }^i)=b_i({\beta }^i),b_i(X)=R_{{\phi }_i(X)}\{r(X)\}$$

y la segunda igualdad sale igual, con ${\phi }_i(X)$ en el lugar de $g(X)$: alcanza un divisor de $m$ etapas por síndrome. En el (15,7), con $r(X)=1+X^8$: el resto por ${\phi }_1=1+X+X^4$ es $b_1=X^2$, y da $S_1={\alpha }^2$, $S_2={\alpha }^4$ y $S_4={\alpha }^8$, porque $\alpha$, ${\alpha }^2$ y ${\alpha }^4$ comparten polinomio mínimo; el resto por ${\phi }_3$ es $1+X^3$, y $S_3=1+{\alpha }^9={\alpha }^7$. La igualdad $S_i=s({\beta }^i)$ se comprobó sobre los 32 768 vectores de quince bits, en el (15,7) y en el (15,5).

02 · Los de índice par salen gratis

En un cuerpo de característica dos, ${(a+b)}^2=a^2+b^2$, porque el término cruzado $2ab$ es cero. Aplicado a la suma del paso 2:

$${S_i}^2={\left(\sum _{l=1}^{\nu }{X_l}^i\right)}^2=\sum _{l=1}^{\nu }{X_l}^{2i}=S_{2i}$$

con $X_l={\beta }^{j_l}$, que en la sección 03 recibe nombre. El paso descansa en que los coeficientes de $e(X)$ son 0 o 1, que al cuadrado no cambian: es propio del caso binario. Vale para cualquier patrón, con cualquier cantidad de errores, y por eso también para $r$ entero: $r({\beta }^{2i})={r({\beta }^i)}^2$. La consecuencia práctica: sólo hay que evaluar los $t$ síndromes de índice impar, y los otros $t$ salen de elevar al cuadrado, que en hardware es lógica fija. Con tres errores en las posiciones 3, 5 y 12 del (15,5):

$$\begin{array}{l}{S}_1=1,S_3={\alpha }^{10},S_5={\alpha }^{10}\hfill \\ S_2={S_1}^2=1,S_4={S_2}^2=1,S_6={({\alpha }^{10})}^2={\alpha }^5\hfill \end{array}$$

Y la cuenta de información cierra con lo que ya se sabía. Los $2t$ elementos ocupan $2tm$ bits, 24 en el (15,5), pero el síndrome cíclico tenía $n-k=10$, y los $S_i$ son evaluaciones suyas: no pueden decir más. Recorridos los 32 768 vectores de quince bits, salen exactamente 1024 vectores de síndromes distintos en el (15,5) y 256 en el (15,7), $2^{n-k}$ en los dos. En el (15,5) los diez bits se reparten así: $S_1$ y $S_3$ toman los 16 valores del cuerpo, cuatro bits cada uno, y $S_5$ toma sólo cuatro: 0, 1, ${\alpha }^5$ y ${\alpha }^{10}$. La razón es la misma propiedad, aplicada dos veces: ${S_5}^4=S_{20}=S_5$, porque ${\alpha }^{20}={\alpha }^5$, y los únicos elementos de $\text{GF}(2^4)$ con $x^4=x$ son esos cuatro. Es la clase conjugada $\{5,10\}$, de dos elementos: ${\phi }_5$ tiene grado 2 y su síndrome, dos bits. $4+4+2=10$.

03 · Los números localizadores

Conviene abreviar. El número localizador del error $l$ es

$$X_l={\beta }^{j_l},l=1,\dots ,\nu$$

Como $\beta$ tiene orden $n$, sus potencias ${\beta }^0,\dots ,{\beta }^{n-1}$ son todas distintas: conocer $X_l$ es conocer la posición. En el ejemplo, los localizadores son ${\alpha }^3$, ${\alpha }^5$ y ${\alpha }^{12}$. Con esta notación, lo que hay que resolver es

$$\begin{array}{l}{S}_1=X_1+X_2+\cdots +X_{\nu }\hfill \\ S_2={X_1}^2+{X_2}^2+\cdots +{X_{\nu }}^2\hfill \\ ⋮\hfill \\ S_{2t}={X_1}^{2t}+{X_2}^{2t}+\cdots +{X_{\nu }}^{2t}\hfill \end{array}$$

Tiene tres dificultades a la vez. Es no lineal: las incógnitas aparecen elevadas hasta la $2t$. La cantidad de incógnitas, $\nu$, no se conoce. Y es simétrico: intercambiar dos localizadores no cambia ninguna ecuación, así que no hay forma de despejarlos de a uno, porque nada distingue al primero del segundo.

Además tiene muchas soluciones. Todos los patrones de un mismo coset dan los mismos síndromes: $2^k$ patrones por vector de síndromes, 32 en el (15,5). La que se busca es la de menos errores, y si $\nu \le t$ es única: dos patrones de peso $\le t$ con los mismos síndromes sumarían una palabra no nula de peso $\le 2t$, por debajo de la distancia diseñada. Probar los patrones uno por uno son ${\sum }_{i\le t}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ intentos: 576 en el (15,5), 32 641 en el (255,239). Hace falta otra cosa.

04 · El polinomio localizador

La salida es no buscar los $X_l$, sino un polinomio que los tenga a todos adentro. El polinomio localizador de errores es

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

Tres cosas salen de la definición. Sus raíces son los inversos de los localizadores, $X_1^{-1},\dots ,X_{\nu }^{-1}$: el factor $1+X_{l}X$ vale $1+1=0$ en $X=X_l^{-1}$. Su grado es la cantidad de errores, porque ${\sigma }_{\nu }=X_1{X}_2\cdots X_{\nu }$ es un producto de elementos no nulos. Y sus coeficientes son las funciones simétricas elementales de los localizadores:

$${\sigma }_1=\sum _l{X}_l,{\sigma }_2=\sum _{l<l\prime }{X}_l{X}_{l\prime },\dots ,{\sigma }_{\nu }=X_1{X}_2\cdots X_{\nu }$$

Ahí está la ganancia del cambio de incógnitas. Los $X_l$ no tienen orden; los ${\sigma }_i$ sí están determinados, porque son simétricos: el mismo conjunto de posiciones da el mismo $\sigma (X)$ en cualquier orden. Y en la sección siguiente se relacionan con los síndromes por ecuaciones lineales.

En el ejemplo, con ${\alpha }^3$, ${\alpha }^5$ y ${\alpha }^{12}$:

$$\sigma (X)=(1+{\alpha }^{3}X)(1+{\alpha }^{5}X)(1+{\alpha }^{12}X)=1+X+{\alpha }^5{X}^3$$

El término en $X^2$ falta: ${\sigma }_2=0$, y sin embargo son tres errores. Lo que cuenta los errores es el grado, no la cantidad de términos. De los 455 patrones de tres errores del largo 15, 35 tienen ${\sigma }_2=0$. Encontrar las raíces de $\sigma (X)$ probando las $n$ potencias de $\beta$ es la búsqueda de Chien.

05 · Las identidades de Newton

Las sumas de potencias $S_i$ y las funciones simétricas ${\sigma }_i$ están ligadas por las identidades de Newton, que son clásicas. Sobre un cuerpo de característica dos tienen dos tramos. Para $i\le \nu$:

$$\begin{array}{l}{S}_1+{\sigma }_1=0\hfill \\ S_2+{\sigma }_1{S}_1+2{\sigma }_2=0\hfill \\ S_3+{\sigma }_1{S}_2+{\sigma }_2{S}_1+3{\sigma }_3=0\hfill \\ ⋮\hfill \\ S_{\nu }+{\sigma }_1{S}_{\nu -1}+\cdots +{\sigma }_{\nu -1}{S}_1+\nu {\sigma }_{\nu }=0\hfill \end{array}$$

donde el entero que multiplica al último término se reduce módulo 2: en las de índice par desaparece, en las de índice impar queda ${\sigma }_i$. Y para $i>\nu$:

$$S_i+{\sigma }_1{S}_{i-1}+{\sigma }_2{S}_{i-2}+\cdots +{\sigma }_{\nu }{S}_{i-\nu }=0$$

Las incógnitas ${\sigma }_i$ aparecen a la primera potencia, multiplicadas por síndromes, que se conocen. El sistema no lineal en los $X_l$ se volvió lineal en los ${\sigma }_i$, y resolverlo así es el método de Peterson. El segundo tramo se prueba en tres pasos, con un polinomio auxiliar: el recíproco de $\sigma (X)$,

$$\begin{array}{rl}\hfill {\sigma }^{\ast }(X)& =X^{\nu }\sigma (X^{-1})=\prod _{l=1}^{\nu }(X+X_l)\hfill \\ & =X^{\nu }+{\sigma }_1{X}^{\nu -1}+\cdots +{\sigma }_{\nu }\hfill \end{array}$$

que tiene por raíces a los localizadores mismos.

Paso 1: cada localizador anula al recíproco. ${X_l}^{\nu }+{\sigma }_1{X_l}^{\nu -1}+\cdots +{\sigma }_{\nu }=0$, para cada $l$.

Paso 2: correrla en potencias. Multiplicada por ${X_l}^{i-\nu }$, con $i>\nu$, queda ${X_l}^i+{\sigma }_1{X_l}^{i-1}+\cdots +{\sigma }_{\nu }{X_l}^{i-\nu }=0$.

Paso 3: sumar sobre los errores. Sumando las $\nu$ igualdades, cada columna es una suma de potencias, ${\sum }_l{X_l}^h=S_h$, y queda la identidad.

El primer tramo pide más cuenta, la de la fórmula clásica entre sumas de potencias y funciones simétricas, y está en el apunte y en el libro. En el ejemplo se comprueba a mano. Con $S_1=S_2=1$, $S_3={\alpha }^{10}$ y $\sigma (X)=1+X+{\alpha }^5{X}^3$: $S_1+{\sigma }_1=1+1=0$; $S_2+{\sigma }_1{S}_1=0$; y $S_3+{\sigma }_1{S}_2+{\sigma }_2{S}_1+{\sigma }_3={\alpha }^{10}+1+0+{\alpha }^5=0$, porque ${\alpha }^{10}=1+\alpha +{\alpha }^2$ y ${\alpha }^5=\alpha +{\alpha }^2$.

06 · Los síndromes salen de un registro

El segundo tramo, despejado, dice otra cosa:

$$S_i={\sigma }_1{S}_{i-1}+{\sigma }_2{S}_{i-2}+\cdots +{\sigma }_{\nu }{S}_{i-\nu },i>\nu$$

Cada síndrome es una combinación fija de los $\nu$ anteriores. Es una recurrencia lineal de orden $\nu$, y eso es un LFSR: $\nu$ etapas que guardan cada una un elemento de $\text{GF}(2^m)$, cargadas con $S_1,\dots ,S_{\nu }$, y una realimentación que multiplica la etapa $j$ por la constante ${\sigma }_j$. Cada ciclo sale el síndrome que sigue. En el ejemplo, cargado con $1,1,{\alpha }^{10}$:

$$\begin{array}{l}{S}_4={\sigma }_1{S}_3+{\sigma }_2{S}_2+{\sigma }_3{S}_1={\alpha }^{10}+0+{\alpha }^5=1\hfill \\ S_5=S_4+{\alpha }^5{S}_2=1+{\alpha }^5={\alpha }^{10}\hfill \\ S_6=S_5+{\alpha }^5{S}_3={\alpha }^{10}+{\alpha }^{15}={\alpha }^5\hfill \end{array}$$

exactamente los de la sección 02. El registro no es nuevo. El LFSR de la Unidad 5 dividía por un polinomio y su salida cumplía la recurrencia del recíproco. Acá la recurrencia es la de $\sigma (X)$, así que el registro divide por ${\sigma }^{\ast }(X)$, el polinomio cuyas raíces son los localizadores. Y se entiende por qué: ${X_l}^i$ es una progresión geométrica de razón $X_l$, que la genera un registro de una etapa; los síndromes son la suma de $\nu$ de esas progresiones.

El registro no se detiene en $2t$. La recurrencia vale para todo $i>\nu$, y $S_i=e({\beta }^i)$ tiene sentido para cualquier $i$. Como ${\beta }^n=1$, la sucesión es periódica de período $n$. En el ejemplo, de $S_7$ a $S_{15}$ el registro da 0, 1, ${\alpha }^5$, ${\alpha }^5$, 0, ${\alpha }^{10}$, 0, 0, 1, lo mismo que evaluar $e(X)$ directamente, y $S_{16}=S_1$. El decodificador ve sólo los primeros $2t$.

Con eso el problema cambia de forma. Lo que hay que hacer es encontrar el registro más corto que genera $S_1,\dots ,S_{2t}$, y eso es lo que hace Berlekamp-Massey. Que el más corto sea $\sigma (X)$ no es obvio, y vale si $\nu \le t$. Sea otro registro, de $L$ etapas con $L\le t$, que también genera los $2t$.

Paso 1: si coinciden en $2t$, coinciden siempre. La diferencia entre lo que sale de los dos registros cumple la recurrencia del producto de sus dos polinomios, que tiene orden $L+\nu \le 2t$. Sus primeros $2t$ términos son cero, así que la recurrencia sólo puede seguir produciendo ceros: el otro registro genera la sucesión entera $S_i=e({\beta }^i)$, no sólo los $2t$ que se ven.

Paso 2: la sucesión entera pide los $\nu$ localizadores. Si un registro con coeficientes $c_1,\dots ,c_L$ la genera, el mismo cálculo de la sección 05 al revés da ${\sum }_l{X_l}^{i-L}C(X_l)=0$ para todo $i>L$, con $C(X)=X^L+c_1{X}^{L-1}+\cdots +c_L$. Tomando $\nu$ valores seguidos de $i$ queda un sistema de Vandermonde en los $X_l$, que son distintos y no nulos: la única solución es $C(X_l)=0$ para cada $l$. Un polinomio mónico de grado $L$ con $\nu$ raíces distintas pide $L\ge \nu$, y si $L=\nu$, es ${\sigma }^{\ast }(X)$.

Con un Berlekamp-Massey general, que no usa la simplificación binaria, sobre todos los patrones de hasta $t$ errores: el registro más corto es el de $\sigma (X)$ en los 575 patrones no nulos del (15,5) y en los 120 del (15,7).

Arranca sin errores, y no hay nada que ver: seis ceros y $\sigma (X)=1$. Poné un error y mirá qué valen los seis. Después el patrón de las secciones de arriba, en 3, 5 y 12, y corré el registro hasta $S_{15}$. Pasá al registro más corto: con tres errores no cambia nada. Ahora cuatro, en 0, 1, 2 y 4, y compará los dos registros más allá de $S_6$.

07 · Con un error de más

Las identidades de Newton valen para cualquier $\nu$. Con cuatro errores en el (15,5), el registro de cuatro etapas de $\sigma (X)$ genera los seis síndromes en los 1365 patrones. Lo que deja de valer es la unicidad: el paso 1 pedía $L+\nu \le 2t$, y un registro de tres etapas contra el verdadero de cuatro suma 7, uno más que los seis síndromes que hay. Recorridos los 1365 patrones con Berlekamp-Massey:

En 1275 de los 1365 hay un registro más corto que el verdadero que genera los mismos seis síndromes, y el decodificador se queda con él porque es el más corto: es lo único que puede saber. En los 750 del medio, el registro corto no tiene ni una raíz en el cuerpo. Las fallas suman 840 y las palabras equivocadas 525: el mismo reparto que da el decodificador de Meggitt con cuatro errores, ahora visto desde el registro.

Un caso: errores en 0, 1, 2 y 4. Los síndromes son ${\alpha }^2$, ${\alpha }^4$, ${\alpha }^9$, ${\alpha }^8$, ${\alpha }^5$, ${\alpha }^3$, y hay dos registros que los generan:

$$\begin{array}{l}\sigma (X)=1+{\alpha }^{2}X+{\alpha }^{10}{X}^2+{\alpha }^{14}{X}^3+{\alpha }^7{X}^4\hfill \\ {\sigma }^{\prime }(X)=1+{\alpha }^{2}X+{\alpha }^2{X}^2+{\alpha }^8{X}^3\hfill \end{array}$$

Las raíces de ${\sigma }^{\prime }(X)$ señalan las posiciones 5, 8 y 10. El decodificador las invierte y entrega una palabra de código que difiere de la transmitida en las siete posiciones 0, 1, 2, 4, 5, 8 y 10: es $g(X)$ mismo, de peso 7. Los dos registros coinciden hasta $S_6$ y se separan en el primer síndrome que el decodificador no calcula: en $S_7$ el verdadero da ${\alpha }^{11}$ y el corto ${\alpha }^{12}$. Con $2t$ síndromes, un registro de $\nu$ etapas queda determinado si $2\nu \le 2t$; con uno más, los síndromes que se ven ya no alcanzan para distinguirlo. Cuántas veces termina en una palabra equivocada depende del código, y está en pasado t, la cuenta la hacen las palabras livianas.

08 · Las tres etapas

El decodificador de un BCH binario queda partido en tres etapas independientes, y esta nota cubre la primera y el planteo de la segunda.

Síndromes. Evaluar $r(X)$ en las $t$ raíces de índice impar, por Horner, con un multiplicador por constante en cada celda, y elevar al cuadrado para los pares. El costo es fijo y lineal en $n$. Entra binario, sale en $\text{GF}(2^m)$.

Polinomio localizador. Sacar $\sigma (X)$ de los síndromes: resolviendo el sistema lineal de Newton, que es el método de Peterson, o sintetizando el registro más corto, que es Berlekamp-Massey. Es la etapa difícil.

Raíces. Encontrar los ceros de $\sigma (X)$ entre las $n$ potencias de $\beta$, invertirlos para tener los localizadores, y corregir: la búsqueda de Chien. Si el grado de $\sigma (X)$ pasa de $t$, o no tiene tantas raíces distintas como su grado, el decodificador declara falla. Las tres etapas, sobre un mismo ejemplo de punta a punta, están en el (15,5) de punta a punta.

09 · La cuenta en Python

El ejemplo de las secciones 02 a 06, sin librerías: $\text{GF}(2^4)$ por tablas de potencias, los síndromes como sumas de potencias de los localizadores, $\sigma (X)$ multiplicando los factores de a uno, y el registro de Newton cargado con los tres primeros. Lo de los comentarios es la salida de correrlo.

EXP = [1]                                 # GF(2⁴) con 1 + X + X⁴: EXP[i] = α^i
for _ in range(14):
    x = EXP[-1] << 1
    EXP.append(x ^ 0b10011 if x & 0b10000 else x)
LOG = {v: i for i, v in enumerate(EXP)}

def mul(a, b):
    return 0 if a == 0 or b == 0 else EXP[(LOG[a] + LOG[b]) % 15]

def sum_gf(xs):
    s = 0
    for x in xs:
        s ^= x
    return s

def pot(x):                               # un elemento como potencia de α
    return '0' if x == 0 else '1' if x == 1 else f'α^{LOG[x]}'

def sindromes(errores, cuantos):
    """S_i = e(α^i) = Σ X_l^i, con X_l = α^(j_l)."""
    return [sum_gf(EXP[i * j % 15] for j in errores) for i in range(1, cuantos + 1)]

def localizador(errores):
    """σ(X) = Π (1 + X_l X), coeficientes de menor a mayor grado."""
    sigma = [1]
    for j in errores:
        Xl = EXP[j]
        sigma = [a ^ mul(Xl, b) for a, b in zip(sigma + [0], [0] + sigma)]
    return sigma

def registro(sigma, iniciales, hasta):
    """El registro de Newton: S_i = σ1 S_(i-1) + ... + σν S_(i-ν)."""
    S = list(iniciales)
    nu = len(sigma) - 1
    while len(S) < hasta:
        S.append(sum_gf(mul(sigma[k], S[-k]) for k in range(1, nu + 1)))
    return S

errores = [3, 5, 12]                      # el ejemplo, en el (15,5)
S = sindromes(errores, 6)
sigma = localizador(errores)
print([pot(s) for s in S])
# ['1', '1', 'α^10', '1', 'α^10', 'α^5']
print([pot(c) for c in sigma])
# ['1', '1', '0', 'α^5']
print([pot(s) for s in registro(sigma, S[:3], 6)])
# ['1', '1', 'α^10', '1', 'α^10', 'α^5']
print(all(S[2 * i + 1] == mul(S[i], S[i]) for i in range(3)))
# True
print([pot(s) for s in registro(sigma, S[:3], 16)[6:]])
# ['0', '1', 'α^5', 'α^5', '0', 'α^10', '0', '0', '1', '1']

La segunda línea es $1+X+{\alpha }^5{X}^3$, con el cero de ${\sigma }_2$ a la vista. La tercera es el registro cargado con $S_1,S_2,S_3$: devuelve los seis. La última sigue de $S_7$ a $S_{16}$, y el 1 final es $S_1$ otra vez. La línea de localizador que hace el zip es multiplicar por $1+X_{l}X$: el coeficiente nuevo de $X^i$ es el viejo más $X_l$ por el viejo de $X^{i-1}$.

Para tener a mano

1. $S_i=r({\beta }^i)=e({\beta }^i)$, para $i=1,\dots ,2t$: elementos de $\text{GF}(2^m)$. También $S_i=s({\beta }^i)=b_i({\beta }^i)$, con los restos por $g(X)$ o por ${\phi }_i(X)$.
2. $S_{2i}={S_i}^2$ en el caso binario: se evalúan los $t$ impares. Los $2t$ llevan $n-k$ bits de información: 1024 vectores distintos en el (15,5), con $S_5$ en $\{0,1,{\alpha }^5,{\alpha }^{10}\}$.
3. Localizadores $X_l={\beta }^{j_l}$ y $S_i={\sum }_l{X_l}^i$: un sistema no lineal, simétrico, con $\nu$ desconocido.
4. $\sigma (X)=\prod (1+X_{l}X)$: raíces en los inversos de los localizadores, grado $\nu$, coeficientes simétricos. Un coeficiente nulo no es un error menos.
5. Newton, para $i>\nu$: $S_i={\sigma }_1{S}_{i-1}+\cdots +{\sigma }_{\nu }{S}_{i-\nu }$. Lineal en los ${\sigma }_i$. Para $i\le \nu$, con el término $i{\sigma }_i$, que sólo queda en los impares.
6. Leída como registro: $\nu$ etapas sobre $\text{GF}(2^m)$, conexiones ${\sigma }_j$, cargado con $S_1,\dots ,S_{\nu }$. Divide por ${\sigma }^{\ast }(X)=\prod (X+X_l)$, y su salida tiene período $n$.
7. Con $\nu \le t$, el registro más corto que genera $S_1,\dots ,S_{2t}$ es $\sigma (X)$ y es único. Con $\nu =t+1$ deja de serlo: en el (15,5), 1275 de 1365 patrones tienen uno de tres etapas.
8. Tres etapas: síndromes, localizador (Peterson o Berlekamp-Massey), raíces (Chien). Falla si el grado pasa de $t$ o no hay tantas raíces como el grado.