El decodificador de Meggitt

Decodificar por síndrome un código lineal cualquiera pide una tabla: a cada síndrome, su líder de coset. En un código cíclico alcanza con una pregunta mucho más chica —¿hay un error en la última posición?— hecha n veces, girando la palabra entre una y otra. El circuito que la hace es el decodificador de Meggitt, publicado por J. E. Meggitt en 1961.

01 · La pregunta

Sea un código cíclico $(n,k)$ con polinomio generador $g(X)$, que corrige $t$ errores. Si llega $r(X)=v(X)+e(X)$, el síndrome es el resto

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

Depende sólo del patrón de error, y lo calcula el mismo registro de desplazamiento de $n-k$ etapas que divide por $g(X)$. Y en un código cíclico el síndrome gira con la palabra, que es el teorema 5: si $r^{(i)}(X)$ es la palabra recibida girada $i$ lugares, su síndrome es

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

y se obtiene dando $i$ ciclos más de reloj al registro, con la entrada en cero. No hace falta volver a dividir: está en el síndrome cíclico.

Con eso, una pregunta sobre una sola posición alcanza para todas. El conjunto de detección es

$$S_{n-1}=\{R_{g(X)}\{e(X)\}:w(e)\le t,e_{n-1}=1\}$$

los síndromes de los patrones corregibles que tienen un error en la posición de mayor orden, $X^{n-1}$. El circuito que decide si el síndrome corriente está en $S_{n-1}$ es combinacional y tiene una sola salida: un bit. Al girar la palabra $i$ lugares, la posición $n-1-i$ pasa a ocupar el lugar $n-1$, y en $n$ giros cada posición pasa una vez por el único lugar que el circuito mira.

02 · El procedimiento

El circuito tiene dos registros que avanzan al mismo ritmo: un buffer de $n$ etapas que guarda la palabra recibida, y el registro de síndrome, de $n-k$. Entre los dos, la lógica de detección.

Paso 1: cargar. $r(X)$ entra al registro de síndrome empezando por $r_{n-1}$, y a la vez al buffer. Al cabo de $n$ ciclos el registro tiene $s(X)$, y la última etapa del buffer tiene $r_{n-1}$, el primer bit que sale.

Paso 2: preguntar. En el desplazamiento $i$, con $i=0,1,\dots ,n-1$, la lógica mira el registro. Si su contenido está en $S_{n-1}$, el bit de la última etapa del buffer, que es $r_{n-1-i}$, está mal: se lo invierte a la salida y se le quita su efecto al registro.

Paso 3: girar. Un ciclo de reloj a los dos registros, y vuelta al paso 2.

Después de $n$ desplazamientos el buffer entregó la palabra entera. Si el registro de síndrome quedó en cero, lo que salió es una palabra de código. Si no, el patrón de error no era corregible y el decodificador lo detectó.

03 · Por qué funciona

Sea $e(X)$ el patrón de error, de peso a lo sumo $t$.

Paso 1: girar no cambia el peso. En el desplazamiento $i$ el registro tiene $s^{(i)}(X)$, el síndrome de $r^{(i)}(X)$. Como el código es cíclico, $v^{(i)}(X)$ es una palabra, y ese síndrome es el de $e^{(i)}(X)$, el patrón girado. Girar mueve los unos sin crear ni borrar ninguno: $e^{(i)}(X)$ sigue siendo corregible.

Paso 2: el síndrome contesta sin ambigüedad. Dos patrones distintos de peso $\le t$ no comparten síndrome: su suma tendría síndrome nulo, sería una palabra no nula de peso $\le 2t$, y la distancia mínima, $d_{\text{min}}\ge 2t+1$, no lo permite. Entonces, si $s^{(i)}$ está en $S_{n-1}$, el patrón de $S_{n-1}$ que lo produce es $e^{(i)}$ mismo, y $e^{(i)}$ tiene un uno en $n-1$. Ese uno es $e_{n-1-i}$: el error de la posición que está en la última etapa. Y si no está, esa posición está bien.

Paso 3: corregir deja otro patrón corregible. Invertir el bit le suma $X^{n-1}$ a $r^{(i)}(X)$, y al síndrome le suma $R_{g(X)}\{X^{n-1}\}$. Lo que queda en el registro es el síndrome del patrón con un error menos, que sigue siendo corregible, y los pasos 1 y 2 valen para lo que falta.

El paso 3 tiene una versión de circuito más barata. El ciclo de reloj multiplica por $X$, y $X·X^{n-1}=X^n$ deja resto 1 al dividir por $g(X)$, porque $g(X)$ divide a $X^n+1$. Sumar $R_{g(X)}\{X^{n-1}\}$ antes del ciclo es lo mismo que sumar 1 después: alcanza con meter el bit de corrección por la entrada del registro, a través de una XOR.

Y la palabra vuelve a su orden: después de $n$ giros, $X^{n}r(X)\equiv r(X)$ módulo $X^n+1$. El registro termina con el síndrome de lo que salió, que es cero si y sólo si lo que salió es una palabra.

04 · El (7,4): una compuerta AND

El (7,4) de $g(X)=1+X+X^3$ corrige un error. Los patrones de peso $\le 1$ con un uno en $X^6$ son uno solo, $X^6$, y su síndrome es $R_{g(X)}\{X^6\}=1+X^2$. Escrito como $(s_0{s}_1{s}_2)$:

$$S_6=\{(101)\}$$

La lógica de detección entera es una compuerta AND de tres entradas, con la del medio negada: $s_0·{\bar{s}}_1·s_2$. Se transmite $v=(1001011)$ y se recibe $r=(1011011)$, con la posición 0 a la izquierda: un error en $X^2$. El síndrome cargado es $(001)$, que no es $(101)$. ¿En qué desplazamiento dispara la AND?

Arranca con el caso de recién, sin girar. Apostá y después corré el error a otra posición: mirá hacia dónde se mueve la corrección. Ponele dos errores al (7,4). Después pasá al (15,5), que arranca con la palabra del ejercicio 4 de la práctica y un error en $X^{12}$, el del ejercicio 5: probá con dos y tres errores, y después con cuatro.

05 · La traza, leída

El caso del (7,4), desplazamiento por desplazamiento. La última etapa del buffer es el bit de la derecha:

El síndrome arranca en 001, el de un error en $X^2$, y cada desplazamiento lo gira: 110, 011, 111. En el cuarto llega a 101, justo cuando el bit errado, que estaba en la posición 2, ocupa la etapa 6. Se corrige, el registro vuelve a cero, y los tres desplazamientos que faltan no tocan nada. En el séptimo el buffer tiene $v$ en su orden.

La regla es general: un error en $X^j$ se corrige en el desplazamiento $n-1-j$. Medido en las siete posiciones del (7,4): el error en $X^6$ se corrige en el desplazamiento 0, el de $X^5$ en el 1, y así hasta el de $X^0$, en el 6. El bit de mayor orden se examina primero, y el de la posición 0, último. En el (15,5) del ejercicio 5 el error está en $X^{12}$ y la corrección cae en el desplazamiento 2: es el tercer síndrome que calcula la solución de la práctica, 1101100101, que es justamente $R_{g(X)}\{X^{14}\}$.

06 · Cuánto se ahorra

El conjunto de detección se cuenta sin enumerarlo. Un patrón suyo tiene su uno en $n-1$ y a lo sumo $t-1$ más entre las otras $n-1$ posiciones, y por el paso 2 de la sección 03 no hay dos con el mismo síndrome:

$$|S_{n-1}|=\sum _{i=0}^{t-1}\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)\text{frente a}\sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)$$

A la derecha están los patrones corregibles, que son los líderes que la tabla del standard array tendría que guardar. Con el conjunto armado síndrome por síndrome en cuatro códigos de la unidad:

Las distancias medidas son 3, 5, 7 y 7, así que la $t$ de cada fila es la que el código garantiza. El último es el Golay: perfecto, sus 2048 síndromes son todos de patrones corregibles. Con el (15,5), el decodificador corrige los 576 patrones de peso $\le 3$, recorridos uno por uno.

El cociente se puede predecir. De los $n$ giros de un patrón de peso $w$, exactamente $w$ tienen un uno en la última posición, y por eso

$$\left(\genfrac{}{}{0ex}{}{n-1}{w-1}\right)=\frac{w}{n}\left(\genfrac{}{}{0ex}{}{n}{w}\right)$$

El conjunto de detección es, como mucho, una fracción $t/n$ de los líderes: 106 de 576 en el (15,5), un 18 %, debajo del $3/15$, que es un 20 %. Pero el ahorro grande no está en cuántos síndromes hay que reconocer, sino en qué se contesta. La tabla devuelve, para cada síndrome, un patrón de $n$ bits. La lógica de Meggitt devuelve un bit. En el (7,4), una tabla de ocho entradas de siete bits se reduce a una AND.

07 · El precio: n ciclos

Meggitt trabaja en serie. Examina un bit por ciclo de reloj y tarda $n$ ciclos en entregar la palabra, además de los $n$ en que la palabra entra y el registro calcula el síndrome. Un decodificador combinacional construido sobre la tabla de síndromes, con el síndrome ya calculado, corrige los $n$ bits en un solo paso. La estructura cíclica cambia área por tiempo: en el (7,4), una AND en vez de una tabla, a cambio de siete ciclos de corrección en vez de uno.

Y la lógica crece con $t$. Con $t=3$, el Golay ya pide reconocer 254 síndromes de once bits, y para $t$ grande la cuenta se vuelve inmanejable: Meggitt es un decodificador para códigos que corrigen pocos errores. Hay un caso en que el reconocimiento se vuelve trivial: si los errores caben en las $n-k$ posiciones de paridad, el síndrome es el error, y la lógica se reduce a mirar su peso. Es la captura de errores.

08 · Con más de t errores

La prueba de la sección 03 supone que el patrón es corregible. Si no lo es, el registro tiene el síndrome de un patrón que no está en la cuenta, y el decodificador hace lo que ese síndrome le diga.

En el (7,4) el registro nunca termina distinto de cero. El código es perfecto: todo síndrome es el de un error simple, y Meggitt corrige uno. Recorridos los 21 patrones de dos errores, los 21 salen como otra palabra de código, con tres bits mal y el registro en cero.

El (15,5) corrige tres, con $d_{\text{min}}=7$, y no es perfecto. Recorridos sus 1365 patrones de cuatro errores sobre la palabra del ejercicio 4:

En los 840 declarados el buffer sale sin que se haya invertido un solo bit. Los 525 son exactamente los patrones que caen a distancia 3 de otra palabra: el código tiene 15 palabras de peso 7, y cada una contiene $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ patrones de peso 4, y $15·35=525$. Contrastado con un decodificador que busca a fuerza bruta, entre las 32 palabras, una a distancia $\le 3$: el mismo reparto, 525 y 840. Sobre estos patrones Meggitt hace lo mismo que la decodificación incompleta, sin tabla. Y el registro en cero no prueba que lo que salió sea lo transmitido: prueba que es una palabra.

09 · La entrada por la derecha

El registro también se puede cargar con $r(X)$ entrando por el extremo derecho, lo que equivale a multiplicarlo por $X^{n-k}$ antes de dividir. Al terminar de cargar, el registro no tiene $s(X)$ sino $s^{(n-k)}(X)$, el síndrome de la palabra ya girada $n-k$ lugares, y el conjunto de detección gira con él. En la palabra girada, $r_{n-1}$ está en la posición $n-k-1$, y en el (7,4) el patrón que hay que reconocer pasa a ser

$$R_{g(X)}\{X^2\}=X^2,(001)$$

El circuito es el mismo y la AND es otra: ${\bar{s}}_0·{\bar{s}}_1·s_2$. Como $X^{n-k-1}$ tiene grado menor que $g(X)$, quitar el efecto de una corrección es invertir la última etapa del registro. Un detector armado para una carga y un registro cargado de la otra no reconocen lo mismo: el conjunto de detección depende de por dónde entra la palabra.

10 · La cuenta en Python

El decodificador ciclo a ciclo, con listas de bits como si fueran los biestables. El registro divide por $g(X)$ con la entrada por la izquierda, el conjunto de detección se arma con los patrones de peso $\le t$ que tienen un uno arriba, y la corrección entra al registro por la misma entrada. Lo de los comentarios es la salida de correrlo.

from itertools import combinations

def reloj(s, g, entrada=0):
    """Un ciclo del divisor por g: s' = X s + entrada, módulo 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 primero r_{n-1}
        s = reloj(s, g, bit)
    return s

def conjunto_deteccion(n, g, t):
    """S_{n-1}: los síndromes de los patrones de peso ≤ t con e_{n-1} = 1."""
    S = set()
    for w in range(t):
        for pos in combinations(range(n - 1), w):
            e = [int(i in pos or i == n - 1) for i in range(n)]
            S.add(tuple(sindrome(e, g)))
    return S

def meggitt(r, g, S):
    s, buf = sindrome(r, g), list(r)
    for i in range(len(r)):
        corr = int(tuple(s) in S)         # ¿está mal el bit de la etapa n-1?
        print(i, ''.join(map(str, s)), ''.join(map(str, buf)), corr)
        buf[-1] ^= corr                   # se corrige al salir del buffer
        s = reloj(s, g, corr)             # y entra por la izquierda del registro
        buf = buf[-1:] + buf[:-1]         # los dos giran juntos
    return buf, not any(s)

g = [1, 1, 0, 1]                          # g(X) = 1 + X + X³
S = conjunto_deteccion(7, g, 1)
print(S)                                  # {(1, 0, 1)}
print(meggitt([1, 0, 1, 1, 0, 1, 1], g, S))
# 0 001 1011011 0
# 1 110 1101101 0
# 2 011 1110110 0
# 3 111 0111011 0
# 4 101 1011101 1
# 5 000 0101110 0
# 6 000 0010111 0
# ([1, 0, 0, 1, 0, 1, 1], True)

La salida es la traza de la sección 05, y el True del final es el registro en cero. La línea s = reloj(s, g, corr) es el paso 3 en su versión de circuito: la corrección no se resta del síndrome, entra por la XOR de la entrada en el mismo ciclo.

Para tener a mano

1. $S_{n-1}$: los síndromes de los patrones de peso $\le t$ con $e_{n-1}=1$. Una sola pregunta, hecha en los $n$ desplazamientos.
2. En el desplazamiento $i$ el registro tiene $s^{(i)}=R_{g(X)}\{X^{i}s(X)\}$ y se examina $r_{n-1-i}$. Un error en $X^j$ se corrige en el desplazamiento $n-1-j$.
3. Funciona porque girar no cambia el peso y dos patrones corregibles no comparten síndrome.
4. Corregir: invertir el bit que sale y meterlo por la entrada del registro, porque $R_{g(X)}\{X^n\}=1$.
5. Registro en cero al final: salió una palabra de código. Distinto de cero: patrón no corregible, declarado.
6. (7,4) de $1+X+X^3$: $S_6=\{101\}$, una AND. Con el error en $X^2$: 001, 110, 011, 111, 101, y la corrección en el desplazamiento 4.
7. $|S_{n-1}|={\sum }_{i<t}\left(\genfrac{}{}{0ex}{}{n-1}{i}\right)$: 1 contra 8 en el (7,4), 15 contra 121 en el (15,7), 106 contra 576 en el (15,5), 254 contra 2048 en el Golay. La lógica contesta un bit, no un patrón.
8. El precio: $n$ ciclos en serie contra un paso combinacional, y una lógica que crece con $t$.
9. Con cuatro errores en el (15,5): 840 de 1365 declarados sin tocar un bit, 525 entregados como otra palabra.
10. Con la entrada por la derecha el registro tiene $s^{(n-k)}$ y el conjunto cambia: en el (7,4), 001.