La búsqueda de Chien

Un decodificador de código BCH trabaja en tres etapas: calcula los síndromes, arma con ellos el polinomio localizador —por Peterson o por Berlekamp-Massey— y busca sus raíces. Esta nota es la tercera. No hay fórmula para las raíces de un polinomio de grado arbitrario sobre $\mathrm{GF}(2^m)$, pero el cuerpo es finito y se pueden probar todos los candidatos. R. T. Chien mostró en 1964 cómo hacer esa prueba con multiplicaciones por constantes.

01 · Qué se busca

Si el canal metió $\nu$ errores, con números localizadores $X_1,\dots ,X_{\nu }$, el localizador es

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

y sus raíces son los inversos $X_l^{-1}$. Un localizador es una potencia del elemento de orden $n$ del código, $X_l={\beta }^{j_l}$, y el exponente $j_l$ es la posición errada. Por eso alcanza con probar $n$ candidatos, las potencias ${\beta }^l$ con $0\le l<n$, y la traducción es directa:

$$\sigma ({\beta }^l)=0\iff {\beta }^{-l}={\beta }^{n-l}\text{ es un localizador}$$

y entonces la posición $n-l$ está errada, con $l$ tomado módulo $n$: la raíz ${\beta }^0=1$ marca la posición 0. En un código primitivo $\beta =\alpha$ y $n=2^m-1$, que es el caso del resto de la nota hasta la sección 07.

El (15,5) del apunte, con tres errores en las posiciones 3, 5 y 12, da

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

Sustituyendo las quince potencias de $\alpha$, se anula en ${\alpha }^3$, ${\alpha }^{10}$ y ${\alpha }^{12}$. Los localizadores son sus inversos, ${\alpha }^{12}$, ${\alpha }^5$ y ${\alpha }^3$: las posiciones 12, 5 y 3.

02 · Encadenar por constantes

Probar los candidatos uno por uno, con Horner, cuesta $t$ productos generales por punto, $nt$ en total. Chien observó que cada evaluación sale de la anterior.

Paso 1: la evaluación, término por término. En ${\alpha }^l$,

$$\sigma ({\alpha }^l)=1+{\sigma }_1{\alpha }^l+{\sigma }_2{\alpha }^{2l}+\cdots +{\sigma }_t{\alpha }^{tl}$$

con ${\sigma }_i=0$ para $i>\nu$: el circuito se arma para $t$ errores y los coeficientes que sobran valen cero.

Paso 2: pasar a la posición siguiente es multiplicar por una constante. El término $i$ en ${\alpha }^{l+1}$ es el de ${\alpha }^l$ por ${\alpha }^i$:

$${\sigma }_i{\alpha }^{i(l+1)}=({\sigma }_i{\alpha }^{il})·{\alpha }^i$$

Paso 3: guardar los términos. Se cargan ${\sigma }_1,\dots ,{\sigma }_t$ en $t$ registros de $m$ bits. En cada paso se multiplica el registro $i$ por ${\alpha }^i$ y se suma todo con la constante 1. Después de $l$ pasos el registro $i$ tiene ${\sigma }_i{\alpha }^{il}$, y la suma es $\sigma ({\alpha }^l)$. Si da cero, la posición $n-l$ está errada y se invierte.

La cuenta de productos no cambia: siguen siendo $t$ por posición. Lo que cambia es su tipo. Multiplicar por una constante conocida de antemano es una transformación lineal fija sobre los $m$ bits, o sea un puñado de XOR cableadas. En $\mathrm{GF}(2^4)$ con $1+X+X^4$, como ${\alpha }^4=1+\alpha$,

$$\alpha ·(a_0,a_1,a_2,a_3)=(a_3,a_0+a_3,a_1,a_2)$$

una sola XOR. Por ${\alpha }^2$ son dos y por ${\alpha }^3$, tres: comprobado contra el producto del cuerpo en los dieciséis elementos. Un multiplicador general de $\mathrm{GF}(2^4)$ tiene dos entradas variables y necesita compuertas AND además de las XOR.

03 · El orden de las posiciones

La palabra recibida espera en un buffer mientras corren las tres etapas, y la búsqueda decide sobre cada bit en el momento en que sale. Así que importa qué posición examina cada paso.

El circuito multiplica antes de sumar. En el primer ciclo los registros pasan de ${\sigma }_i$ a ${\sigma }_i{\alpha }^i$ y la suma prueba $\alpha$, que corresponde a la posición $n-1$. El ciclo $l$ prueba ${\alpha }^l$ y la posición $n-l$, y el último, $l=n$, prueba ${\alpha }^n=1$ y la posición 0. Las posiciones salen de mayor a menor, $r_{n-1},r_{n-2},\dots ,r_0$, que es el orden en que el buffer las entrega.

La regla para leer una traza: un error en la posición $j$ aparece en el paso $l=n-j$. En el ejemplo de la sección 01, las posiciones 12, 5 y 3 dan sumas nulas en los pasos 3, 10 y 12. Y como la información de un código sistemático ocupa las $k$ posiciones de arriba, si sólo interesa corregir el mensaje alcanza con los primeros $k$ pasos.

04 · El circuito

Son $t$ registros de $m$ bits, cada uno realimentado a través de su multiplicador por ${\alpha }^i$; un árbol de sumadores que junta los $t$ registros con la constante 1; y una compuerta NOR de $m$ entradas que da 1 cuando la suma es cero. Esa salida va a una XOR con el bit que sale del buffer: es la corrección. Un bit de decisión por ciclo, $n$ ciclos por palabra.

En el (15,7), que corrige dos errores, el circuito tiene dos registros de cuatro bits, uno realimentado por $\alpha$ y el otro por ${\alpha }^2$: tres XOR entre los dos multiplicadores. En el (15,5) se suma un tercero, por ${\alpha }^3$. El costo por palabra es $nt$ productos por constante: 45 en el (15,5), 510 en el (255,239) del apunte, que corrige dos.

Abajo, el circuito del (15,5) y el del (15,7). Elegís dónde caen los errores, y $\sigma (X)$ sale de los síndromes por el algoritmo iterativo binario. Arranca con los tres errores de la sección 01, sin ningún paso dado. Antes de avanzar, apostá en qué paso se anula la suma por primera vez.

Después de ver dónde caen las tres, mové un error y fijate cuánto se corre su paso. Sacá uno: el registro de ${\sigma }_3$ queda en cero. Ponele un cuarto error al (15,5) y mirá qué pasa al final. Y en el (15,7) probá con errores en 0, 5 y 10.

05 · La traza, leída

El caso de la sección 01, paso por paso. Las columnas son los tres registros después de multiplicar, y la suma incluye la constante 1:

Tres cosas se leen sin hacer cuentas. El primer registro recorre las potencias de $\alpha$ de a una, porque ${\sigma }_1=1$. El segundo no se mueve de cero: ${\sigma }_2=0$, y cero por cualquier constante es cero; es lo mismo que pasa con los registros que sobran cuando hay menos de $t$ errores. El tercero avanza de a tres y vuelve a empezar cada cinco pasos, porque ${\alpha }^3$ tiene orden 5. Y la suma se anula en los pasos 3, 10 y 12, que son las posiciones 12, 5 y 3, como manda $l=n-j$.

El ejemplo integral del apunte, con errores en 2, 7 y 13, da $\sigma (X)=1+\alpha X+{\alpha }^{13}{X}^2+{\alpha }^7{X}^3$, y las sumas nulas caen en los pasos 2, 8 y 13. Está resuelto entero, de la palabra a la corrección, en el (15,5) de punta a punta.

06 · Las dos comprobaciones

Chien no decide nada: marca las posiciones donde la suma da cero. Antes de invertirlas, el decodificador comprueba dos cosas:

1. que el grado de $\sigma (X)$ no pase de $t$;
2. que la búsqueda encuentre tantas raíces distintas como el grado.

El porqué está en la definición. Un patrón de $\nu \le t$ errores tiene un localizador de grado $\nu$ que se parte en $\nu$ factores lineales distintos, con todas sus raíces entre las potencias de $\alpha$. Un $\sigma (X)$ que no cumple eso no es el localizador de ningún patrón corregible, y el decodificador declara la falla: sabe que el bloque está dañado aunque no pueda repararlo. Y al revés: si pasa las dos, lo que sale es una palabra de código a distancia a lo sumo $t$ de lo recibido. Recorridos todos los patrones de $t+1$ y de $t+2$ errores en los cuatro códigos de la tabla de abajo y en el (21,12) de la sección 07, ninguno pasa las dos sin salir así.

Con un error más que $t$ se ve qué atrapa cada una. Enumerados todos los patrones con el decodificador completo —síndromes, algoritmo iterativo binario y Chien—, y mirando primero el grado:

La que trabaja es la segunda. En el (15,5), de los 840 fallos, 750 los delata Chien y 90 el grado. Y en los dos códigos de largo 15 y en el (31,21), cuando faltan raíces no falta una: no hay ninguna. El localizador sale de grado $t$ y no se anula en ninguna de las $n$ posiciones, así que la búsqueda recorre la palabra entera sin marcar nada. En el (31,16) hay de los dos: de los 25 110, en 14 880 aparece una raíz sola. Los que pasan las dos se entregan como otra palabra sin aviso; cuántos son, y por qué, es el tema de pasado t, la cuenta la hacen las palabras livianas.

La primera comprobación tiene un costado menos obvio. Un $\sigma (X)$ de grado mayor que $t$ a veces tiene todas sus raíces. En el (15,7), con errores en 0, 5 y 10, el algoritmo entrega

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

que es el localizador verdadero: Chien encuentra las tres posiciones justas, y el decodificador igual declara la falla porque el grado es 3 y $t=2$. Pasa en 5 de los 35 patrones de grado alto del (15,7), y en los 5 las raíces son los errores. ¿Por qué no aceptarlas? Porque en el (15,5) la misma situación sale mitad y mitad: de los 90 de grado 4, en 30 Chien encuentra cuatro raíces; en 15 son los cuatro errores y en los otros 15 son cuatro posiciones distintas, que junto con los errores completan una palabra de peso 8. Sin la primera comprobación, esos 15 serían otra palabra entregada sin aviso. El decodificador que corrige hasta $t$ y nada más —el de decodificación incompleta— renuncia a los 15 buenos para no entregar los 15 malos.

07 · Dónde se limita

Los $n$ ciclos. El cálculo del síndrome y la búsqueda recorren la palabra a un bit por ciclo; el algoritmo iterativo binario tarda $t$. Con $t\ll n$, la búsqueda es el cuello de botella. Para examinar $J$ posiciones por ciclo se replica el circuito $J$ veces, cada réplica con las constantes de su posición, y la búsqueda se completa en $\lceil n/J\rceil$ ciclos a cambio de $Jt$ multiplicadores por constante. Con $t\le 3$ hay otra salida: las raíces de un polinomio de grado dos o tres se obtienen en forma directa, con un cambio de variable y una tabla, en pocos ciclos. Las dos están en el decodificador BCH en hardware.

Los códigos no primitivos. Cuando $n$ es un divisor propio de $2^m-1$, la búsqueda prueba sólo las $n$ potencias de $\beta$, no los $2^m-1$ elementos del cuerpo. En el (21,12) del apunte, sobre $\mathrm{GF}(2^6)$ con $\beta ={\alpha }^3$, recorridos los 1330 patrones de tres errores: en 1092 faltan raíces, y en 420 de esos $\sigma (X)$ sí se anula en algún elemento del cuerpo, pero fuera de las 21 potencias de $\beta$. Que Chien no las vea es lo correcto: una raíz así no corresponde a ninguna posición, y la segunda comprobación declara la falla igual.

08 · La cuenta en Python

El circuito con enteros de cuatro bits como registros, sobre $\mathrm{GF}(2^4)$ con $1+X+X^4$. Multiplica antes de probar, así que las posiciones salen de mayor a menor. Lo de los comentarios es la salida de correrlo.

# GF(2^4) con 1 + X + X^4: EXP[e] = α^e como entero de 4 bits, LOG al revés.
EXP, LOG = [1], {1: 0}
for e in range(1, 15):
    x = EXP[-1] << 1
    if x & 0b10000:
        x ^= 0b10011
    EXP.append(x)
    LOG[x] = e

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

def alfa(x):
    return '0' if x == 0 else '1' if LOG[x] == 0 else 'α' if LOG[x] == 1 else f'α^{LOG[x]}'

def chien(sigma, n=15, traza=False):
    """sigma = [1, σ1, ..., σt]. En el paso l se multiplica el registro i
    por α^i y después se prueba 1 + Σ registros = 0: la raíz es α^l y la
    posición errada, n − l."""
    reg = sigma[1:]
    const = [EXP[i] for i in range(1, len(reg) + 1)]
    pos = []
    for l in range(1, n + 1):
        reg = [mul(r, c) for r, c in zip(reg, const)]
        suma = 1
        for r in reg:
            suma ^= r
        if suma == 0:
            pos.append((n - l) % n)
        if traza:
            print(l, ' '.join(alfa(r) for r in reg), alfa(suma), '<- r_%d' % ((n - l) % n) if suma == 0 else '')
    return pos

a = lambda e: EXP[e % 15]
print(chien([1, 1, 0, a(5)], traza=True))         # σ(X) = 1 + X + α^5 X^3
# 1 α 0 α^8 α^5
# 2 α^2 0 α^11 α^7
# 3 α^3 0 α^14 0 <- r_12
# ...
# 10 α^10 0 α^5 0 <- r_5
# ...
# 12 α^12 0 α^11 0 <- r_3
# ...
# 15 1 0 α^5 α^5
# [12, 5, 3]
print(chien([1, a(1), a(13), a(7)]))              # el ejemplo integral
# [13, 7, 2]
print(chien([1, 0, 0, 1]))                        # σ(X) = 1 + X^3, grado 3
# [10, 5, 0]
print(chien([1, a(7), a(5)]))                     # grado 2, sin raíces
# []

Las filas omitidas son las de la tabla de la sección 05. La función devuelve las posiciones y nada más: las dos comprobaciones las hace quien la llama. El tercer caso es el de la sección 06, tres raíces justas que el decodificador del (15,7) rechaza por el grado; el cuarto, un $\sigma (X)$ de grado 2 que no se anula en ningún elemento de $\mathrm{GF}(2^4)$: es lo que el (15,7) obtiene con errores en 0, 1 y 3.

Para tener a mano

1. Las raíces de $\sigma (X)$ son los inversos de los localizadores: $\sigma ({\alpha }^l)=0$ marca la posición $n-l$.
2. Encadenar: el registro $i$ arranca en ${\sigma }_i$ y en cada paso se multiplica por ${\alpha }^i$; la suma con 1 es $\sigma ({\alpha }^l)$. Los ${\sigma }_i$ con $i>\nu$ van en cero.
3. $nt$ productos, pero por constantes: en $\mathrm{GF}(2^4)$, una XOR por $\alpha$, dos por ${\alpha }^2$, tres por ${\alpha }^3$.
4. Multiplicar antes de sumar: el paso $l$ examina $r_{n-l}$, de $r_{n-1}$ a $r_0$, el orden del buffer. Un error en $j$ aparece en el paso $n-j$; la información, en los primeros $k$.
5. El circuito: $t$ registros de $m$ bits, $t$ multiplicadores por constante, un árbol de sumadores, una NOR de $m$ entradas. $n$ ciclos.
6. (15,5), errores en 3, 5, 12: $\sigma =1+X+{\alpha }^5{X}^3$, sumas nulas en los pasos 3, 10 y 12. Errores en 2, 7, 13: pasos 2, 8 y 13.
7. Dos comprobaciones: grado $\le t$, y tantas raíces distintas como el grado. Si pasan, sale una palabra a distancia $\le t$; si no, falla declarada.
8. Con $t+1$ errores la que más atrapa es la de las raíces: 750 de los 840 fallos del (15,5), casi siempre sin ninguna raíz.
9. El grado alto con todas sus raíces existe: $1+X^3$ en el (15,7). Se rechaza igual, porque en el (15,5) la mitad de esos casos daría otra palabra.
10. Límites: $n$ ciclos, que se parten en $\lceil n/J\rceil$ con $J$ réplicas; y en un código no primitivo sólo se prueban las $n$ potencias de $\beta$.