La captura de errores

El decodificador de Meggitt gira la palabra recibida y en cada ciclo pregunta si el síndrome está en un conjunto: en el (15,5), uno de 106 síndromes. Hay un caso en que esa pregunta se reemplaza por otra mucho más barata, ¿pesa el síndrome $t$ o menos?, y la respuesta trae además el error entero, bit por bit. Es la captura de errores. Funciona siempre que los errores estén juntos, y cuánto es «juntos» depende de qué fracción del anillo de posiciones cubre la paridad.

01 · El síndrome que es el error

Se transmite $v (X)$ , una palabra de un código cíclico $(n, k)$ de polinomio generador $g (X)$ , y llega $r (X) = v (X) + e (X)$ , con $e (X)$ el patrón de error. El síndrome es el resto de dividir lo recibido por el generador, y como $v (X)$ es múltiplo de $g (X)$ no deja resto:

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

Tiene $n - k$ coeficientes, de $s_{0}$ a $s_{n - k - 1}$ . Ahora, el caso particular: todos los errores caen en las primeras $n - k$ posiciones, de $X^{0}$ a $X^{n - k - 1}$ , o sea, $e (X)$ tiene grado menor que $n - k$ . Dividir un polinomio por otro de grado mayor da cociente nulo, y el resto es el propio dividendo:

s (X) = e (X)

El síndrome no es una pista sobre el error: es el error. En la forma sistemática cíclica la paridad va primero y el mensaje al final, así que esas $n - k$ posiciones son las de paridad, y se las llama la ventana de paridad. Con el (15,5) de $g (X) = 1 + X + X^{2} + X^{4} + X^{5} + X^{8} + X^{10}$ y errores en $X^{2}$ y $X^{7}$ , el registro de síndrome termina en 0010000100, con la posición 0 a la izquierda: un uno en la 2 y otro en la 7. Corregir es sumar el registro a las primeras diez posiciones de lo recibido. No hay tabla ni lógica de reconocimiento.

02 · Girar hasta capturar

Si los errores no están en la ventana pero están juntos, algún desplazamiento cíclico puede llevarlos ahí. El desplazamiento de orden $i$ de lo recibido, $r^{(i)} (X) = R_{X^{n} + 1} {X^{i} r (X)}$ , es otra palabra del código más el patrón girado $e^{(i)} (X)$ , porque el código es cíclico. Y su síndrome no hay que calcularlo de nuevo:

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

Cada giro de la palabra es un ciclo más del registro de desplazamiento que calculó el síndrome, sin entrada. La captura de errores es este procedimiento, para un código que corrige $t$ errores:

Paso 1: el síndrome y su peso. Se calcula $s (X)$ y se mira su peso $w (s)$ , la cantidad de unos.

Paso 2: si pesa $t$ o menos, los errores están capturados. Si $w (s^{(i)}) \leq t$ , entonces $e^{(i)} (X) = s^{(i)} (X)$ , y deshaciendo el giro,

e (X) = R_{X^{n} + 1} {X^{n - i} s^{(i)} (X)}

Paso 3: si no, un giro más. Se avanza el registro un ciclo y se vuelve al paso 2, hasta $n$ giros. Si en los $n$ el peso nunca bajó a $t$ , se declara un fallo de decodificación.

En el (15,5), con $t = 3$ y errores en $X^{11}$ y $X^{13}$ , fuera de la ventana: el síndrome pesa 5, y en los giros siguientes 5, 8 y 5. En el giro 4 el registro tiene 1010000000, que pesa 2, o sea $s^{(4)} (X) = 1 + X^{2}$ . Deshacer el giro es multiplicar por $X^{15 - 4} = X^{11}$ : sale $X^{11} + X^{13}$ , el patrón que entró.

El circuito es el registro de síndrome de $n - k$ etapas, un buffer con lo recibido que gira junto con él, y una sola compuerta de umbral de $n - k$ entradas, que vale 1 cuando a lo sumo $t$ están en uno. Donde Meggitt reconoce 106 síndromes, la captura cuenta unos. Lo que se paga es lo mismo, $n$ ciclos por palabra, y algo más: sólo funciona con errores que algún giro meta en la ventana.

03 · Por qué alcanza con mirar el peso

No es evidente que un síndrome liviano sea el error. Podría ser un síndrome cualquiera que, por casualidad, tenga pocos unos. No puede, y la razón es la distancia.

Proposición. Sea un código de distancia mínima $d_{min} \geq 2 t + 1$ y un patrón con a lo sumo $t$ errores. Entonces $w (s^{(i)}) \leq t$ si y sólo si $s^{(i)} (X) = e^{(i)} (X)$ , es decir, si y sólo si en el giro $i$ todos los errores están en la ventana.

Paso 1: la suma es una palabra. $s^{(i)} (X)$ es el resto de dividir $e^{(i)} (X)$ por $g (X)$ , así que $e^{(i)} (X) + s^{(i)} (X)$ es múltiplo de $g (X)$ y tiene grado menor que $n$ : es una palabra del código.

Paso 2: pesa demasiado poco para no ser la nula. Si $w (s^{(i)}) \leq t$ , esa palabra pesa a lo sumo $w (e^{(i)}) + w (s^{(i)}) \leq 2 t < d_{min}$ . Toda palabra no nula pesa al menos $d_{min}$ : ésta es la nula, y $s^{(i)} = e^{(i)}$ .

Paso 3: la vuelta. Si los errores del giro $i$ están en la ventana, la sección 01 da $s^{(i)} = e^{(i)}$ , que pesa lo mismo que $e$ : a lo sumo $t$ .

La consecuencia práctica es que, con hasta $t$ errores, la captura nunca corrige mal: o los captura, o recorre los $n$ giros sin que el umbral se dispare y declara el fallo. Medido sobre todos los patrones de peso $\leq t$ del (15,7), el (15,5) y el Golay, ninguno sale mal corregido.

El Paso 2 necesita que el patrón tenga a lo sumo $t$ errores, y sin eso el test se engaña. En el (15,5), cuatro errores en ${0, 1, 2, 4}$ están dentro de la ventana desde el principio, pero el registro pesa 4 y el decodificador sigue girando. En el giro 10 el registro pesa 3, y lo que se corrige es $X^{5} + X^{8} + X^{10}$ : con los cuatro del canal suman siete errores, que son una palabra del código. De los 1365 patrones de peso 4, contados uno por uno, 510 terminan corregidos así, mal, y 855 se declaran.

Arranca en el (15,5) con un error adentro de la ventana y dos afuera, y el registro pesa 6. Los tres errores no se ven juntos, pero mirá los huecos entre ellos antes de apostar. Después pasá al Golay y poné dos errores a once lugares uno del otro.

04 · Qué patrones entran en la ventana

Por la proposición, un patrón de hasta $t$ errores se captura si y sólo si algún giro lo deja en $n - k$ posiciones consecutivas del anillo, contando la vuelta de $X^{n - 1}$ a $X^{0}$ . Dicho al revés, que es como se cuenta mejor: hay $k$ posiciones seguidas sin ningún error, porque lo que queda afuera de la ventana son $k$ posiciones.

Con dos errores, el anillo queda partido en dos tramos sin error que suman $n - 2$ , y el más largo tiene al menos $⌈ (n - 2) / 2 ⌉$ . En el (15,7) de $g (X) = 1 + X^{4} + X^{6} + X^{7} + X^{8}$ , con $d_{min} = 5$ y $t = 2$ , eso es $⌈ 13 / 2 ⌉ = 7 = k$ : todo par de errores tiene siete posiciones libres seguidas, justo las que hacen falta. Ahí la captura no es una heurística: corrige todo lo que el código promete. Contados los patrones uno por uno, corriendo el registro, en tres códigos:

código	ventana	t	1 error	2 errores	3 errores
(15,7)	8 de 15	2	15 de 15	105 de 105	—
(15,5)	10 de 15	3	15 de 15	105 de 105	450 de 455
Golay (23,12)	11 de 23	3	23 de 23	230 de 253	1035 de 1771

Los que faltan no salen mal corregidos: se declaran. Contados también por la otra vía, buscando una ventana sobre el anillo sin pasar por el registro, salen exactamente los mismos patrones en los tres códigos: es la proposición, verificada patrón por patrón.

El (15,5) y el Golay tienen la misma distancia, 7, y la misma capacidad de corrección, 3. Lo que los separa es la fracción del anillo que cubre la ventana: dos tercios en el (15,5), menos de la mitad en el Golay. En el Golay $⌈ 21 / 2 ⌉ = 11 < 12 = k$ , y ya hay dobles que no entran: los dos errores a once lugares por un lado y doce por el otro, como $X^{11} + X^{22}$ . La captura simple corrige ahí 1288 de los 2047 patrones no nulos de peso $\leq 3$ , el 62,9 %. Los dos códigos, patrón por patrón, están resueltos en atrapar errores y ráfagas.

La regla de diseño sale de la tabla: la captura rinde cuando $n - k$ es grande frente a $n$ , o sea en códigos de tasa baja o moderada, y se vuelve ineficaz en los largos de tasa alta. Y rinde siempre que los errores vengan agrupados: una ráfaga de largo $\leq n - k$ cabe en la ventana por definición. Por eso es el método de elección de los códigos correctores de ráfagas.

05 · Kasami: unos pocos errores afuera

Para el Golay hacen falta patrones con casi todos los errores en la ventana y uno afuera. La idea de Kasami es adivinar la parte de afuera. Se parte el patrón en dos: $e_{P} (X)$ , los errores en las posiciones de paridad, y $e_{I} (X)$ , los de las posiciones de mensaje, de $X^{n - k}$ en adelante.

Paso 1: la parte de mensaje deja un resto. Sea $ρ (X) = R_{g (X)} {e_{I} (X)}$ . Como $e_{P} (X)$ tiene grado menor que $n - k$ , es su propio resto, y el síndrome es la suma de los dos restos: $s (X) = e_{P} (X) + ρ (X)$ .

Paso 2: conocida la parte de mensaje, la de paridad sale del síndrome. Despejando, $e_{P} (X) = s (X) + ρ (X)$ . La captura simple es el caso $e_{I} = 0$ .

Paso 3: una lista corta de candidatos. Se eligen polinomios de cobertura $φ_{j} (X)$ , de grado menor que $k$ , tales que todo patrón corregible tenga, en algún giro, la parte de mensaje exactamente igual a $X^{n - k} φ_{j} (X)$ para algún $j$ . Sus restos $ρ_{j} = R_{g (X)} {X^{n - k} φ_{j} (X)}$ se calculan una vez, y en cada giro una compuerta por candidato prueba

w (s^{(i)} + ρ_{j}) \leq t - w (φ_{j})

Si la compuerta $j$ se dispara, $e^{(i)} = s^{(i)} + ρ_{j} + X^{n - k} φ_{j}$ . El candidato pesa a lo sumo $t$ y tiene el mismo síndrome que el patrón verdadero, así que el argumento de la sección 03 vale igual: con hasta $t$ errores, ninguna compuerta se dispara en falso.

Para el Golay de $g_{1} (X) = 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10} + X^{11}$ alcanzan tres: $φ_{1} = 0$ , $φ_{2} = X^{5}$ y $φ_{3} = X^{6}$ , un error de mensaje en la posición 16 o en la 17, con umbrales 3, 2 y 2. Los restos son

ρ_{2} = X + X^{2} + X^{5} + X^{6} + X^{8} + X^{9}, ρ_{3} = X ρ_{2}

y el segundo sale del primero sin dividir: $X^{17} = X \cdot X^{16}$ , y $X ρ_{2}$ tiene grado 10, menor que 11, así que ya es un resto. Medido sobre los 2047 patrones no nulos de peso $\leq 3$ , cada compuerta tiene su razón de estar:

compuertas	corregidos	declarados	lo que queda afuera
φ₁	1288	759	23 dobles y 736 triples
φ₁, φ₂	2024	23	los giros de X⁰ + X⁶ + X¹¹
φ₁, φ₂, φ₃	2047	0	nada

La primera fila es la captura simple. La segunda compuerta rescata los 23 dobles y casi todos los triples, y deja afuera un solo patrón con sus 23 giros. La tercera es para ése. Ninguno de los 2047 sale mal corregido. El precio es una compuerta de umbral por polinomio de cobertura, y encontrar el conjunto no es fácil. Con $n$ y $t$ grandes las compuertas se vuelven demasiadas: el método sirve en códigos cortos y de tasa baja.

06 · La búsqueda sistemática

La otra forma de llevar el Golay a sus tres errores usa una sola compuerta. Se apoya en un hecho del anillo de 23: en todo patrón de tres errores o menos hay al menos un error que, sacado, deja a los demás dentro de once posiciones consecutivas. Medido: vale en los 2047.

Paso 1: la captura simple. Se gira con umbral 3. Si se captura, listo.

Paso 2: invertir un dígito y volver a capturar. Si no, se invierte un dígito de lo recibido y se repite la captura con umbral 2. Si el umbral se dispara, ese dígito estaba mal y el registro tiene los otros dos errores. Si no, se lo vuelve a invertir y se prueba con el siguiente.

Invertir un dígito correcto no engaña al umbral. Deja un patrón de a lo sumo cuatro errores, y un registro de peso $\leq 2$ sumaría con él una palabra de peso $\leq 6 < 7$ : la nula. Eso pasa sólo si el patrón invertido tiene a lo sumo dos errores, o sea si el original tenía a lo sumo uno, y a ése ya lo había capturado el Paso 1.

La condición dice «un error», no «un error de mensaje», y la diferencia importa. En $X^{0} + X^{11} + X^{12}$ , sacar $X^{11}$ deja $X^{0} + X^{12}$ , a once lugares por un lado y doce por el otro: no entra. Sacar $X^{12}$ deja $X^{0} + X^{11}$ , igual. El que hay que sacar es $X^{0}$ , que está en la paridad. Probando sólo los doce dígitos de mensaje de lo recibido quedan once patrones sin corregir, los ${i, i + 11, i + 12}$ con $i = 0, \dots, 10$ : corrige 2036 de 2047. La búsqueda tiene que hacer pasar cada una de las 23 posiciones por la inversión, girando la palabra para que todas atraviesen la zona de mensaje. Así corrige los 2047.

Frente a Kasami, una compuerta en vez de tres, pagada en tiempo: cada dígito que se prueba es otra vuelta entera del registro, y la lógica de temporizado que ordena las inversiones es más compleja.

07 · La cuenta en Python

El decodificador entero, con listas de bits: el registro divisor, la compuerta de umbral y el giro que se deshace al final. Cuenta los patrones capturados de los tres códigos de la sección 04. Lo de los comentarios es la salida de correrlo.

from itertools import combinations

def reloj(s, g, entrada=0):
    """Un ciclo del registro divisor por g: s' = X s + entrada mod g."""
    f = s[-1]
    return [entrada ^ f] + [s[j - 1] ^ (g[j] & f) for j in range(1, len(s))]

def sindrome(r, g):
    s = [0] * (len(g) - 1)
    for bit in reversed(r):          # entra r_{n-1} primero
        s = reloj(s, g, bit)
    return s

def capturar(r, g, t):
    """El patrón de error y el giro que lo capturó, o (None, None)."""
    n, nk = len(r), len(g) - 1
    s = sindrome(r, g)
    for i in range(n):
        if sum(s) <= t:              # la compuerta de umbral
            e_i = s + [0] * (n - nk) # e^(i) = s^(i)
            return e_i[i:] + e_i[:i], i
        s = reloj(s, g)              # un giro sin entrada
    return None, None

def contar(n, g, t, w):
    ok = 0
    for pos in combinations(range(n), w):
        e = [int(j in pos) for j in range(n)]
        ok += capturar(e, g, t)[0] == e
    return ok

g157 = [1, 0, 0, 0, 1, 0, 1, 1, 1]          # 1 + X⁴ + X⁶ + X⁷ + X⁸
g155 = [1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1]    # 1 + X + X² + X⁴ + X⁵ + X⁸ + X¹⁰
gol = [1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1]  # 1 + X² + X⁴ + X⁵ + X⁶ + X¹⁰ + X¹¹
for nombre, n, g, t in [("(15,7)", 15, g157, 2), ("(15,5)", 15, g155, 3), ("Golay", 23, gol, 3)]:
    print(nombre, [contar(n, g, t, w) for w in range(1, t + 1)])
# (15,7) [15, 105]
# (15,5) [15, 105, 450]
# Golay [23, 230, 1035]

e = [int(j in (11, 13)) for j in range(15)]
print(capturar(e, g155, 3))
# ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0], 4)

El giro se deshace con e_i[i:] + e_i[:i]: rotar $i$ lugares hacia la izquierda es multiplicar por $X^{n - i}$ . En el circuito ese paso no existe, porque el buffer gira junto con el registro y la corrección se aplica a medida que los dígitos salen.

Para tener a mano

Si $e (X)$ tiene grado menor que $n - k$ , entonces $s (X) = e (X)$ : con los errores en la ventana de paridad, el síndrome es el error.
Captura: girar el registro, $s^{(i)} = R_{g (X)} {X^{i} s}$ , hasta que pese $\leq t$ ; entonces $e = R_{X^{n} + 1} {X^{n - i} s^{(i)}}$ . Si en $n$ giros no baja, fallo declarado. Una compuerta de umbral en vez de una tabla.
El test de peso es necesario y suficiente con hasta $t$ errores: $s + e$ sería una palabra de peso $\leq 2 t < d_{min}$ . Nunca corrige mal: captura o declara. Con más de $t$ sí puede corregir mal.
Se captura si y sólo si hay $k$ posiciones seguidas sin error en el anillo. (15,7): todo, porque $⌈ 13 / 2 ⌉ = 7$ . (15,5): todos los dobles y 450 de 455 triples. Golay: 230 de 253 dobles y 1035 de 1771 triples.
Rinde con $n - k$ grande frente a $n$ y con ráfagas de largo $\leq n - k$ .
Kasami: $e_{P} = s + R_{g} {e_{I}}$ , y una compuerta por polinomio de cobertura. En el Golay, $0, X^{5}, X^{6}$ con umbrales 3, 2, 2: 1288, 2024 y 2047 corregidos al sumar cada una.
Búsqueda sistemática: invertir un dígito y capturar con umbral 2. El error que hay que sacar puede estar en la paridad: todas las posiciones tienen que pasar por la inversión, o quedan los once ${i, i + 11, i + 12}$ .