El método de Peterson

Decodificar un código BCH es, en el medio, encontrar el polinomio localizador a partir de los síndromes. El camino más directo lo publicó W. W. Peterson en 1960, y lo refinaron Gorenstein y Zierler: tomar las identidades de Newton como un sistema de ecuaciones lineales y resolverlo. Antes hay que saber de qué orden es el sistema, y eso lo dice un determinante.

01 · El sistema de Hankel

Sea un BCH binario de sentido estricto que corrige $t$ errores, y supongamos que hubo $\nu \le t$ errores, en las posiciones $j_1,\dots ,j_{\nu }$. Sus números localizadores son $X_l={\alpha }^{j_l}$, y los síndromes son las sumas de potencias

$$S_i=\sum _{l=1}^{\nu }{X}_l^i,i=1,\dots ,2t$$

y el localizador es $\sigma (X)=\prod (1+X_{l}X)=1+{\sigma }_{1}X+\cdots +{\sigma }_{\nu }{X}^{\nu }$. Para cada $i>\nu$, las identidades de Newton dicen

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

Tomadas para $i=\nu +1,\dots ,2\nu$ son $\nu$ ecuaciones lineales en las $\nu$ incógnitas ${\sigma }_i$, y los coeficientes son síndromes, que se conocen. Pasando el término sin $\sigma$ al otro lado:

La matriz de la izquierda es $M_{\nu }$. Su entrada $(i,j)$ es $S_{i+j-1}$: depende sólo de $i+j$, así que es constante a lo largo de cada antidiagonal. Eso es una matriz de Hankel, y se arma entera con los síndromes. El vector de incógnitas va de ${\sigma }_{\nu }$ a ${\sigma }_1$, del índice mayor al menor.

En un código binario, además, la mitad de los síndromes repite a la otra: $S_{2i}={S_i}^2$, porque elevar al cuadrado una suma en característica dos es sumar los cuadrados. En el sistema aparecen $S_2$, $S_4$, $S_6$, pero no aportan nada que $S_1$, $S_2$ y $S_3$ no tengan.

02 · Cuántos errores: el teorema 4

El sistema pide $\nu$, que no se conoce. Lo da el determinante:

Teorema 4. Si el patrón de error tiene exactamente $\nu \le t$ componentes no nulas, la matriz $M_{\mu }$ es no singular para $\mu =\nu$ y singular para todo $\nu <\mu \le t$.

Paso 1: la matriz se factoriza. La entrada $(i,j)$ de $M_{\mu }$ es

$$S_{i+j-1}=\sum _{l=1}^{\nu }{X}_l^{i-1}{X}_l{X}_l^{j-1}$$

que es la entrada $(i,j)$ de un producto: $M_{\mu }=VD{V}^T$, con $V$ la matriz de $\mu \times \nu$ cuya columna $l$ es $(1,X_l,X_l^2,\dots )$ y $D$ la diagonal de los $X_l$.

Paso 2: con $\mu >\nu$, el rango no alcanza. $V$ tiene $\nu$ columnas, así que su rango es a lo sumo $\nu$, y el del producto también. Una matriz de $\mu \times \mu$ con rango menor que $\mu$ tiene determinante nulo.

Paso 3: con $\mu =\nu$, todo es inversible. $V$ es cuadrada de Vandermonde, y su determinante es el producto de las diferencias de los nodos, ${\prod }_{l<k}(X_l+X_k)$. Las posiciones erradas son distintas y $\alpha$ tiene orden $n$, así que los $X_l$ son distintos y no nulos. Queda

$$det{M}_{\nu }=\prod _l{X}_l·\prod _{l<k}{(X_l+X_k)}^2\ne 0$$

El teorema se lee de arriba para abajo: arriba de $\nu$ todas las matrices son singulares, y en $\nu$ la primera que no lo es. Debajo de $\nu$ no promete nada, y no hace falta: el procedimiento nunca llega ahí.

03 · El procedimiento

Paso 1. Formar $M_t$ y calcular su determinante. Si no es cero, hubo $t$ errores.

Paso 2. Si es cero, bajar a $M_{t-1}$, y así hasta la primera no singular. Su orden es $\nu$. Si son todas singulares, no hubo errores.

Paso 3. Resolver el sistema de orden $\nu$ y armar $\sigma (X)$. Sus raíces, por la búsqueda de Chien, dan las posiciones.

En la práctica los pasos 1 y 2 son una sola cuenta: la eliminación gaussiana sobre $\mathrm{GF}(2^m)$ da el determinante como el producto de los pivotes, y si en alguna columna no hay pivote, el determinante es cero y se baja. Si hay, la misma eliminación resuelve el sistema.

El ejemplo 6 del apunte: el (15,5), con $t=3$, sobre $\mathrm{GF}(2^4)$ construido con $1+X+X^4$, con errores en las posiciones 3, 5 y 12. Los seis síndromes son

$$S_1=1,S_2=1,S_3={\alpha }^{10},S_4=1,S_5={\alpha }^{10},S_6={\alpha }^5$$

y la primera matriz ya es no singular:

$$M_3=\left(\begin{array}{ccc}1& 1& {\alpha }^{10}\\ 1& {\alpha }^{10}& 1\\ {\alpha }^{10}& 1& {\alpha }^{10}\end{array}\right),det{M}_3=1$$

Hubo tres errores. El sistema, con $(S_4,S_5,S_6)=(1,{\alpha }^{10},{\alpha }^5)$ a la derecha, da ${\sigma }_3={\alpha }^5$, ${\sigma }_2=0$ y ${\sigma }_1=1$: $\sigma (X)=1+X+{\alpha }^5{X}^3$, el mismo que da el algoritmo iterativo. La primera fila se comprueba a mano, con ${\alpha }^5=\alpha +{\alpha }^2$ y ${\alpha }^{10}=1+\alpha +{\alpha }^2$:

$$1·{\alpha }^5+1·0+{\alpha }^{10}·1=(\alpha +{\alpha }^2)+(1+\alpha +{\alpha }^2)=1=S_4$$

Con dos errores, ¿cuál de las tres matrices es la primera no singular? ¿Y con cuatro, que es uno más de los que el código corrige?

Arranca con dos errores y sin ningún determinante calculado. Apostá, bajá, y después probá con uno y con tres. Con cuatro errores el teorema ya no vale: probá 0, 1, 2 y 3; después 0, 1, 2 y 4; después 0, 1, 2 y 9. Y con tres errores, poné 0, 5 y 10, y mirá las de abajo.

04 · Debajo de ν, el teorema no dice nada

Con errores en 0, 5 y 10 los síndromes son $S_1=S_2=0$ y $S_3=1$. $M_3$ es no singular, con determinante 1, y el procedimiento para ahí con $\nu =3$ y $\sigma (X)=1+X^3$. Pero $M_2$ y $M_1$, que no se miran, son singulares las dos: $M_1=(S_1)=(0)$.

Pasa cada vez que $S_1=X_1+X_2+X_3=0$, o sea, cuando el tercer localizador es la suma de los otros dos. Recorridos todos los patrones de tres errores, son 35 de 455 en el (15,5) y 155 de 4495 en el (31,16). Por eso el procedimiento baja desde $t$: si subiera desde $M_1$ y se detuviera en la primera singular, en estas ternas concluiría que no hubo ningún error.

05 · Las fórmulas cerradas

Para $t$ chico el sistema se resuelve a mano una vez, y lo que queda es una fórmula. La cuenta sale más corta por las identidades de Newton de índice impar que por el sistema de Hankel. Escritas con ${\sigma }_j=0$ para $j>\nu$, valen para todo $i$:

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

con el coeficiente $i$ reducido módulo dos. Con $\nu \le 3$:

Paso 1: $i=1$. $S_1+{\sigma }_1=0$, así que ${\sigma }_1=S_1$.

Paso 2: $i=3$. $S_3+{\sigma }_1{S}_2+{\sigma }_2{S}_1+{\sigma }_3=0$. Con ${\sigma }_1=S_1$ y $S_2=S_1^2$: ${\sigma }_3=(S_1^3+S_3)+S_1{\sigma }_2$.

Paso 3: $i=5$. $S_5+{\sigma }_1{S}_4+{\sigma }_2{S}_3+{\sigma }_3{S}_2=0$. Con $S_4=S_1^4$ y el ${\sigma }_3$ del paso 2, los $S_1^5$ se cancelan y queda ${\sigma }_2(S_1^3+S_3)=S_1^2{S}_3+S_5$.

Para $t=2$ alcanza el paso 2 con ${\sigma }_3=0$. Las tres juntas, como en la ecuación (48) del apunte:

$$\begin{array}{lll}t=1:& {\sigma }_1=S_1& \\ t=2:& {\sigma }_1=S_1& {\sigma }_2=\frac{S_3+S_1^3}{S_1}\\ t=3:& {\sigma }_1=S_1& {\sigma }_2=\frac{S_1^2{S}_3+S_5}{S_1^3+S_3}\\ & & {\sigma }_3=(S_1^3+S_3)+S_1{\sigma }_2\end{array}$$

Con el ejemplo 6: $S_1^3+S_3=1+{\alpha }^{10}={\alpha }^5$, el numerador ${\alpha }^{10}+{\alpha }^{10}$ es cero, así que ${\sigma }_2=0$ y ${\sigma }_3={\alpha }^5$. El mismo $\sigma (X)$, sin eliminar nada.

La cantidad $S_1^3+S_3$ está en todas partes, y tiene una lectura limpia. En característica dos, ${(a+b+c)}^3+a^3+b^3+c^3=(a+b)(b+c)(c+a)$, y entonces

$$S_1^3+S_3=(X_1+X_2)(X_2+X_3)(X_3+X_1)$$

con $X_3=0$ si hubo dos errores, y $X_2=X_3=0$ si hubo uno. Con tres errores es un producto de diferencias de localizadores distintos, y no se anula. Con dos vale $X_1{X}_2(X_1+X_2)$, que tampoco. Y los tres determinantes del procedimiento salen en función de ella:

$$\begin{array}{rl}det{M}_1& =S_1\\ det{M}_2& =S_1(S_1^3+S_3)\\ det{M}_3& ={(S_1^3+S_3)}^2{\sigma }_3\end{array}$$

El teorema 4 de $t=3$ se lee ahí entero. Con dos errores ${\sigma }_3=0$ y $M_3$ es singular; con uno se anula $S_1^3+S_3$, y caen $M_3$ y $M_2$ juntas. Las tres igualdades se comprobaron en cada patrón de hasta tres errores del (15,5) y del (31,16), contra el determinante calculado por eliminación.

06 · Verificadas patrón por patrón

Las fórmulas (48) contra la eliminación gaussiana del procedimiento completo, en todos los patrones de hasta $t$ errores de cuatro códigos. «Coincide» quiere decir el mismo $\sigma (X)$, coeficiente por coeficiente, una vez quitado el ${\sigma }_3=0$ que la fórmula de $t=3$ entrega con dos errores:

En todos los casos el procedimiento completo encontró el $\nu$ verdadero, y la búsqueda de Chien sobre su $\sigma (X)$ devolvió exactamente las posiciones puestas. La fórmula de $t=3$ acierta siempre que hubo dos o tres errores, y no da nada en ninguno de los patrones de un error.

07 · Lo que la rompe: un error solo

Con un error, $S_1=X_1$ y $S_3=X_1^3$: el denominador $S_1^3+S_3$ es cero, y el numerador $S_1^2{S}_3+S_5=X_1^5+X_1^5$ también. La fórmula de $t=3$ da $0/0$.

No es una falla de Peterson. La fórmula es la solución del sistema de orden 3, y el procedimiento, con un error, nunca lo resuelve: $M_3$ y $M_2$ son singulares y baja a $M_1$, que da ${\sigma }_1=S_2/S_1=S_1$. Que la fórmula siga sirviendo con dos errores es la excepción: ${\sigma }_3$ sale cero solo, porque $S_1^3+S_3$ no se anula.

Un circuito que implemente sólo la fórmula tiene que mirar $S_1^3+S_3$. Si es cero y $S_1$ no, hubo un error y $\sigma (X)=1+S_{1}X$. Si los dos son cero, no hubo errores. La fórmula de $t=2$ no tiene este problema: con un error su numerador $S_3+S_1^3$ es cero pero su denominador $S_1$ no, y da ${\sigma }_2=0$, que es lo correcto.

08 · Con más de t errores

El teorema 4 supone $\nu \le t$. Con más, el procedimiento igual encuentra una primera matriz no singular, y resuelve. Recorridos los 1365 patrones de cuatro errores del (15,5):

En los 1275 de las dos primeras filas Peterson da el mismo $\sigma (X)$ que el algoritmo iterativo, y el reparto es el del decodificador: 525 se entregan como otra palabra. Los 90 de la última son los patrones de cuatro errores con $S_1^3+S_3=0$: $M_3$ y $M_2$ son singulares, Peterson concluye que hubo un error y $\sigma (X)=1+S_{1}X$, que tiene siempre exactamente una raíz. Las dos comprobaciones de falla —grado de $\sigma (X)$ a lo sumo $t$, y tantas raíces como el grado— pasan las dos, y se invierte un bit.

Lo que sale no es una palabra: un patrón de cuatro errores más un bit corregido daría, si lo fuera, una palabra de peso a lo sumo 5, y la distancia mínima es 7. El algoritmo iterativo declara falla en esos 90, porque su $\sigma (X)$ sale de grado mayor. En el (31,16) pasa lo mismo con 930 de los 31 465 patrones de cuatro errores. Peterson necesita una comprobación más: que el $\sigma (X)$ encontrado reproduzca todos los síndromes, no sólo los $2\nu$ que usó. Con $\nu =1$ es preguntar si $S_5=S_1^5$, y en los 90, y en los 930, no lo es.

09 · Cuánto cuesta

Las fórmulas cerradas se cuentan a mano. Elevar al cuadrado en $\mathrm{GF}(2^m)$ es lineal sobre los bits —un puñado de XOR—, así que se cuenta aparte. Para $t=2$: $S_1^2$, un cuadrado; $S_1^3=S_1^2·S_1$, una multiplicación; la inversa de $S_1$ y el producto por ella: dos multiplicaciones, un cuadrado y una inversión. Para $t=3$: el cuadrado, $S_1^3$, $S_1^2{S}_3$, la inversa de $S_1^3+S_3$, el producto por ella y $S_1{\sigma }_2$: cuatro multiplicaciones, un cuadrado y una inversión, sin iteraciones y con latencia fija.

La forma general se midió. Peterson con eliminación gaussiana —una inversión por pivote, sin multiplicar por los ceros ya conocidos, bajando desde $M_t$—, y el algoritmo iterativo binario, contando cada multiplicación y cada inversión sobre $\mathrm{GF}(2^8)$. Cada cifra es el promedio sobre 100 patrones al azar, con el número de errores de la columna, en los BCH de largo 255:

Cada celda es «multiplicaciones · inversiones». Tres lecturas.

La forma general pierde enseguida. Ya en $t=2$ la eliminación hace 6 multiplicaciones contra 5 del iterativo binario, y desde ahí la brecha es la de $t^3/3$ contra $t^2$: en $t=8$, 231 contra 65.

El peor caso de Peterson no es $\nu =t$. Con menos errores hay que pagar las matrices singulares de arriba: en el (255,191), con cinco errores, $M_8$, $M_7$ y $M_6$ se eliminan antes de llegar a $M_5$, y la cuenta sube a 463.

La fórmula cerrada gana mientras existe. En $t=3$, cuatro multiplicaciones y una inversión contra diez y tres del iterativo, y sin control secuencial.

Sobre dónde se cambia de método. Las curvas de costo asintótico que se suelen comparar son $t^3/3$ para Peterson, $2t^2$ para el algoritmo iterativo general y $t^2$ para el binario. $t^3/3$ alcanza a $t^2$ en $t=3$ y a $2t^2$ en $t=6$. El cambio que se hace en la práctica, alrededor de $t=4$, no es el corte de dos de esas curvas: es donde se termina la fórmula cerrada. Hasta $t=3$ se usa (48), que no crece y le gana a todo; desde $t=4$ la fórmula se vuelve inmanejable, y entre la forma general y el iterativo, la tabla ya decidió.

10 · La cuenta en Python

El procedimiento entero sobre $\mathrm{GF}(2^4)$, sin librerías: la tabla de potencias de $\alpha$, los síndromes como sumas de potencias, la eliminación que devuelve el determinante y la solución a la vez, y la fórmula de $t=3$ al lado. Lo de los comentarios es la salida de correrlo.

# GF(16) con 1 + X + X⁴: EXP[i] es α^i como entero de 4 bits, LOG lo inverso.
EXP = [1]
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 inv(a):
    return EXP[(15 - LOG[a]) % 15]

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

def sindromes(pos, t=3):
    """S_i = Σ X_l^i, con X_l = α^j por cada posición errada j."""
    S = []
    for i in range(1, 2 * t + 1):
        s = 0
        for j in pos:
            s ^= EXP[i * j % 15]
        S.append(s)
    return S

def eliminar(A):
    """Gauss sobre GF(16) de la matriz ampliada: devuelve (det, solución)."""
    A = [f[:] for f in A]
    n, det = len(A), 1
    for c in range(n):
        p = next((i for i in range(c, n) if A[i][c]), None)
        if p is None:
            return 0, None                    # sin pivote: det M = 0
        A[c], A[p] = A[p], A[c]               # en característica 2, sin signo
        det = mul(det, A[c][c])
        k = inv(A[c][c])
        A[c] = [mul(v, k) for v in A[c]]
        for i in range(n):
            if i != c and A[i][c]:
                f = A[i][c]
                A[i] = [v ^ mul(f, w) for v, w in zip(A[i], A[c])]
    return det, [f[-1] for f in A]

def peterson(S, t=3):
    for mu in range(t, 0, -1):
        M = [[S[i + j] for j in range(mu)] + [S[mu + i]] for i in range(mu)]
        det, x = eliminar(M)
        print(f'  det M{mu} = {alfa(det)}')
        if det:
            return [1] + x[::-1]              # x = (σ_µ, …, σ_1)
    return [1]

def cerrada_t3(S):
    S1, S3, S5 = S[0], S[2], S[4]
    D = mul(mul(S1, S1), S1) ^ S3             # S1³ + S3
    if D == 0:
        return None
    s2 = mul(mul(mul(S1, S1), S3) ^ S5, inv(D))
    return [1, S1, s2, D ^ mul(S1, s2)]

for pos in [(3, 5, 12), (4, 9), (6,), (0, 5, 10)]:
    S = sindromes(pos)
    print('errores en', pos, ' S =', ' '.join(alfa(s) for s in S))
    sigma = peterson(S)
    c = cerrada_t3(S)
    print('  Peterson:', ', '.join(alfa(s) for s in sigma),
          '  (48):', ', '.join(alfa(s) for s in c) if c else 'S1³ + S3 = 0')
# errores en (3, 5, 12)  S = 1 1 α^10 1 α^10 α^5
#   det M3 = 1
#   Peterson: 1, 1, 0, α^5   (48): 1, 1, 0, α^5
# errores en (4, 9)  S = α^14 α^13 0 α^11 α^10 0
#   det M3 = 0
#   det M2 = α^11
#   Peterson: 1, α^14, α^13   (48): 1, α^14, α^13, 0
# errores en (6,)  S = α^6 α^12 α^3 α^9 1 α^6
#   det M3 = 0
#   det M2 = 0
#   det M1 = α^6
#   Peterson: 1, α^6   (48): S1³ + S3 = 0
# errores en (0, 5, 10)  S = 0 0 1 0 0 1
#   det M3 = 1
#   Peterson: 1, 0, 0, 1   (48): 1, 0, 0, 1

Los cuatro casos son los de esta nota: el ejemplo 6, dos errores con ${\sigma }_3$ en cero, el error único con la fórmula en $0/0$, y la terna con $S_1=0$, donde la fórmula da $1+X^3$ con ${\sigma }_1=0$ sin ningún problema. La línea return [1] + x[::-1] es la del orden de las incógnitas.

Para tener a mano

1. Las identidades de Newton para $i=\nu +1,\dots ,2\nu$ son un sistema lineal: $M_{\nu }$, de Hankel, con entradas $S_{i+j-1}$, por $({\sigma }_{\nu },\dots ,{\sigma }_1)$, igual a $(S_{\nu +1},\dots ,S_{2\nu })$.
2. Teorema 4: $M_{\mu }=VD{V}^T$; singular para $\nu <\mu \le t$, no singular en $\mu =\nu$. Debajo de $\nu$, nada: con $S_1=0$ y tres errores, $M_2$ y $M_1$ son singulares.
3. Se baja desde $M_t$ hasta la primera no singular; su orden es $\nu$. La eliminación da el determinante y la solución en la misma pasada.
4. Las fórmulas (48): ${\sigma }_1=S_1$; ${\sigma }_2=(S_3+S_1^3)/S_1$ para $t=2$; ${\sigma }_2=(S_1^2{S}_3+S_5)/(S_1^3+S_3)$ y ${\sigma }_3=(S_1^3+S_3)+S_1{\sigma }_2$ para $t=3$.
5. $S_1^3+S_3=(X_1+X_2)(X_2+X_3)(X_3+X_1)$; $det{M}_2=S_1(S_1^3+S_3)$ y $det{M}_3={(S_1^3+S_3)}^2{\sigma }_3$.
6. Verificadas contra la eliminación en todos los patrones de hasta tres errores del (15,5) y del (31,16): coinciden con dos y tres errores; con uno, la de $t=3$ da $0/0$ y hay que caer a $\sigma (X)=1+S_{1}X$.
7. Con cuatro errores en el (15,5), 90 patrones tienen $S_1^3+S_3=0$: Peterson dice $\nu =1$, Chien encuentra una raíz y sale algo que no es palabra. Falta verificar que $\sigma (X)$ reproduzca los $2t$ síndromes.
8. Costo: (48) son 4 multiplicaciones y una inversión en $t=3$; la forma general, del orden de $t^3/3$ y peor con menos errores (463 en el (255,191) con cinco); el iterativo binario, $t^2$. Se cambia en $t=4$ porque ahí se termina la fórmula.