El codificador cíclico

En un código lineal cualquiera, codificar es multiplicar el mensaje por la matriz generadora: en forma sistemática, cada uno de los $n-k$ bits de paridad es una suma sobre los $k$ bits del mensaje, y hay que guardar $k(n-k)$ coeficientes. En un código cíclico alcanza con dividir por un polinomio, y la división la hace un registro de desplazamiento con tantas etapas como bits de paridad. En el (15,5) son 10 etapas contra 50 coeficientes; y hay otro registro, de 5, que da las mismas palabras.

01 · La definición

Sea un código cíclico $(n,k)$ de polinomio generador $g(X)$, de grado $n-k$, y un mensaje $u(X)=u_0+u_{1}X+\cdots +u_{k-1}{X}^{k-1}$. La palabra $u(X)g(X)$ es del código, pero el mensaje no aparece en ella: habría que dividir para leerlo. La forma sistemática sale en tres pasos.

Paso 1: correr el mensaje. Se multiplica por $X^{n-k}$, que lo lleva a las $k$ posiciones de mayor orden y deja libres las $n-k$ de abajo.

Paso 2: dividir por $g(X)$.

$$X^{n-k}u(X)=a(X)g(X)+b(X),degb<n-k$$

Paso 3: sumar el resto. Sobre GF(2) sumar y restar es lo mismo, así que $b(X)+X^{n-k}u(X)=a(X)g(X)$ es un múltiplo de $g(X)$ de grado menor que $n$: una palabra del código. Queda

$$\begin{array}{rl}\hfill v(X)& =\underset{\text{paridad}}{\underbrace{b_0+b_{1}X+\cdots +b_{n-k-1}{X}^{n-k-1}}}\hfill \\ \hfill & +\underset{\text{mensaje}}{\underbrace{u_0{X}^{n-k}+\cdots +u_{k-1}{X}^{n-1}}}\hfill \end{array}$$

con

$$b(X)=R_{g(X)}\{X^{n-k}u(X)\}$$

Codificar en forma sistemática es una sola división, y de ella sólo interesa el resto. Escrita como vector, con la posición 0 a la izquierda, la palabra lleva la paridad primero y el mensaje al final: al revés que la $G=[IP]$ de la Unidad 3, que ponía el mensaje adelante.

En el (7,4) de $g(X)=1+X+X^3$, con $u=(1011)$, o sea $u(X)=1+X^2+X^3$, el corrimiento da $X^3+X^5+X^6$. Módulo $g(X)$ vale $X^3\equiv 1+X$, y de ahí, multiplicando por $X$ y reduciendo cada vez,

$$\begin{array}{rl}\hfill X^5& \equiv X^2+X^3\equiv 1+X+X^2\hfill \\ \hfill X^6& \equiv X+X^2+X^3\equiv 1+X^2\hfill \end{array}$$

Sumando, $b(X)=(1+X)+(1+X+X^2)+(1+X^2)=1$, la paridad es $(100)$ y la palabra $v=(1001011)$, que es $1+X^3+X^5+X^6$.

02 · El registro de n − k etapas

La división no se hace con lápiz: la hace un registro de desplazamiento realimentado. Tiene $n-k$ etapas, $b_0,\dots ,b_{n-k-1}$, que arrancan en cero, y una conexión por cada coeficiente no nulo de $g(X)$ por debajo del mayor. El mensaje entra un bit por ciclo, empezando por $u_{k-1}$, el de mayor orden. En cada ciclo, con $x$ el bit que entra:

$$\begin{array}{l}f=x+b_{n-k-1},b_0^{\prime }=f,\hfill \\ b_j^{\prime }=b_{j-1}+g_{j}f(1\le j<n-k)\hfill \end{array}$$

El bit $f$ es la realimentación: la entrada más lo que sale por la última etapa. Que eso calcule el resto se ve siguiendo qué guarda el registro.

Paso 1: lo que guarda. Sea $m_c(X)=u_{k-1}{X}^{c-1}+\cdots +u_{k-c}$ el polinomio de los $c$ bits que ya entraron. La afirmación es que, después de $c$ ciclos, el registro tiene $R_{g(X)}\{X^{n-k}{m}_c(X)\}$, leído como $b_0+b_{1}X+\cdots$. Con $c=0$ es el cero del arranque.

Paso 2: un ciclo es multiplicar por $X$ y sumar la entrada. Como $m_{c+1}=X{m}_c+x$, hay que calcular $Xb(X)+x{X}^{n-k}$ módulo $g(X)$. Multiplicar por $X$ corre cada etapa un lugar, y el coeficiente de arriba pasa a $X^{n-k}$, donde también cae la entrada: ahí queda $b_{n-k-1}+x=f$. Por eso el mensaje entra «por arriba»: es lo que antes se hacía multiplicando por $X^{n-k}$.

Paso 3: $X^{n-k}$ se reemplaza por lo que vale. Módulo $g(X)$, $X^{n-k}\equiv g_0+g_{1}X+\cdots +g_{n-k-1}{X}^{n-k-1}$. Si $f=1$, se suman esos coeficientes a las etapas corridas; si $f=0$, no se suma nada. Con $g_0=1$ es exactamente la regla de arriba.

Paso 4: después de $k$ ciclos. Ya entró el mensaje entero, $m_k=u$, y el registro tiene $R_{g(X)}\{X^{n-k}u(X)\}=b(X)$: la paridad.

La operación tiene dos fases. En los ciclos 1 a $k$ la compuerta de la realimentación está abierta, los bits del mensaje entran al registro y, a la vez, salen al canal: es la parte sistemática. En los ciclos $k+1$ a $n$ la compuerta se cierra, el registro se corre sin realimentar y descarga la paridad, de $b_{n-k-1}$ a $b_0$. Al canal sale $v_{n-1}$ primero y $v_0$ último. El (7,4) con $u=(1011)$, ciclo a ciclo:

Las cuatro veces la realimentación vale 1, aunque en el ciclo 3 entra un cero: ahí lo que realimenta es la última etapa. El registro termina en $(100)$, que es el $b(X)=1$ de la cuenta a mano.

El costo es $n-k$ biestables y un sumador módulo 2 por conexión, y crece linealmente con la redundancia. Contra los $k(n-k)$ coeficientes del producto por la matriz, es la primera ganancia concreta de que el código sea cíclico: 3 etapas contra 12 en el (7,4), 10 contra 50 en el (15,5), 11 contra 132 en el Golay (23,12).

03 · La traza del (15,5)

El (15,5) de la clase práctica tiene $g(X)=1+X+X^2+X^4+X^5+X^8+X^{10}$, así que el registro tiene diez etapas y seis conexiones, una por cada coeficiente no nulo por debajo de $X^{10}$: las del $1$, $X$, $X^2$, $X^4$, $X^5$ y $X^8$. Con $u=(10110)$, o sea $u(X)=1+X^2+X^3$, los bits entran en el orden $u_4,u_3,u_2,u_1,u_0$, que es 0, 1, 1, 0, 1:

El primer ciclo no cambia nada: entra un cero en un registro de ceros. El segundo carga los coeficientes de $g(X)$ sin el $X^{10}$, que es lo que vale $X^{10}$ módulo $g(X)$. En el quinto la entrada y la última etapa valen 1 las dos, se cancelan, y el registro sólo se corre.

Para comprobarlo sin el registro, se divide. El corrimiento es $X^{10}u(X)=X^{10}+X^{12}+X^{13}$, y cada potencia se reduce módulo $g(X)$:

$$\begin{array}{rl}\hfill X^{10}& \equiv 1+X+X^2+X^4+X^5+X^8\hfill \\ \hfill X^{12}& \equiv 1+X+X^3+X^5+X^6+X^7+X^8\hfill \\ \hfill X^{13}& \equiv X+X^2+X^4+X^6+X^7+X^8+X^9\hfill \end{array}$$

La suma, coeficiente por coeficiente, es $b(X)=X+X^3+X^8+X^9$, el $(0101000011)$ del ciclo 5, y la palabra es

$$v=(\underset{\text{paridad}}{\underbrace{0101000011}}\underset{\text{mensaje}}{\underbrace{10110}})$$

04 · El registro de k etapas, por h(X)

El registro de $g(X)$ no es el único. Con el polinomio de paridad $h(X)=(X^n+1)/g(X)$, de grado $k$, sale otro de $k$ etapas.

Paso 1: el producto por $h(X)$. Toda palabra es $v=ag$ con $dega<k$, así que $v(X)h(X)=a(X)(X^n+1)=a(X)+X^{n}a(X)$. El primer sumando vive por debajo de $X^k$ y el segundo desde $X^n$: los coeficientes de $X^k$ a $X^{n-1}$ del producto son cero.

Paso 2: $n-k$ ecuaciones. El coeficiente de $X^{n-j}$, para $1\le j\le n-k$, es $\sum _{i=0}^k{h}_i{v}_{n-i-j}=0$.

Paso 3: despejar. Como $h_k=1$, el término de $i=k$ pasa solo al otro lado:

$$v_{n-k-j}=\sum _{i=0}^{k-1}{h}_i{v}_{n-i-j},1\le j\le n-k$$

Paso 4: leerla como recurrencia. Con $j=1$, el bit $v_{n-k-1}$ sale de $v_{n-k},\dots ,v_{n-1}$, que son el mensaje. Con $j=2$, de los $k$ siguientes, que ya incluyen el bit recién calculado. Cada bit de paridad es una suma de los $k$ que tiene inmediatamente arriba.

El circuito es un registro de $k$ etapas que guarda esa ventana. En los primeros $k$ ciclos se carga con el mensaje, desde $u_{k-1}$, que sale al canal a la vez. En los $n-k$ siguientes suma las etapas conectadas según $h_0,\dots ,h_{k-1}$, manda el resultado al canal y lo vuelve a meter por la entrada. La palabra entera pasa por el registro, $v_{n-1}$ primero, y cada bit que entra empuja afuera el que ya no hace falta.

En el (7,4), $h(X)=1+X+X^2+X^4$ y la recurrencia es $v_{3-j}=v_{7-j}+v_{6-j}+v_{5-j}$. Con $u=(1011)$ en $v_3,\dots ,v_6$:

$$\begin{array}{l}{v}_2=v_6+v_5+v_4=1+1+0=0\hfill \\ v_1=v_5+v_4+v_3=1+0+1=0\hfill \\ v_0=v_4+v_3+v_2=0+1+0=1\hfill \end{array}$$

La misma paridad $(100)$, con cuatro etapas en vez de tres. En el (15,5) la cuenta se da vuelta: $h(X)=1+X+X^3+X^5$, cinco etapas y tres derivaciones, y la recurrencia es $v_{10-j}=v_{15-j}+v_{14-j}+v_{12-j}$. Con el mismo $u=(10110)$, el registro (leído $v_{10-j+1}\dots v_{15-j}$, el de menor índice a la izquierda) y el bit que produce:

Leídos de $v_0$ a $v_9$, los bits son $0101000011$: la paridad que dejó el registro de diez etapas. No es una coincidencia de este mensaje. Codificados todos los mensajes de los 30 códigos cíclicos de largo 15 —40 926 en total— y de los 6 de largo 7 —114—, la recurrencia por $h(X)$ y la división por $g(X)$ dan la misma palabra en todos. Y en los 4096 mensajes del Golay (23,12) también.

Las dos realizaciones hacen lo mismo con registros de largo distinto, así que se elige la más corta. Conviene la de $h(X)$ cuando hay más bits de paridad que de mensaje, $n-k>k$: el (15,5), 5 etapas contra 10, o el (7,3), 3 contra 4. En los códigos de tasa alta, que son los habituales, conviene la de $g(X)$. El Golay (23,12) está del lado de $g(X)$ por una etapa: 11 contra 12.

Arranca con el (7,4) y el mensaje de la tabla de la sección 02. Mirá el ciclo 3: entra un cero y la realimentación igual se enciende. Después pasá al (15,5) y comparalo con la tabla de la sección 03: en el primer ciclo no pasa nada y en el quinto la entrada y la última etapa se cancelan. Por último, cambiá al registro por $h(X)$: la mitad de etapas y la misma palabra, bit por bit.

05 · Los dos registros en Python

Los dos codificadores, en listas de bits con la posición 0 primero, y la comprobación sobre los 32 mensajes del (15,5):

from itertools import product

def registro_g(u, g):
    """n − k etapas: el mensaje entra desde u_{k−1}; queda b(X)."""
    r = len(g) - 1
    b = [0] * r
    for bit in reversed(u):
        f = bit ^ b[-1]                                  # la realimentación
        b = [f] + [b[j - 1] ^ (g[j] & f) for j in range(1, r)]
    return b + list(u)                                   # paridad primero

def registro_h(u, h, n):
    """k etapas: cada bit de paridad es la suma de los k siguientes, ec. (16)."""
    k = len(u)
    v = [0] * (n - k) + list(u)
    for j in range(1, n - k + 1):
        v[n - k - j] = sum(h[i] & v[n - i - j] for i in range(k)) % 2
    return v

s = lambda v: "".join(map(str, v))
g = [1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1]          # el g(X) del (15,5)
h = [1, 1, 0, 1, 0, 1]                         # 1 + X + X³ + X⁵
u = [1, 0, 1, 1, 0]
print(s(registro_g(u, g)), s(registro_h(u, h, 15)))
# 010100001110110 010100001110110
print(all(registro_g(m, g) == registro_h(m, h, 15)
          for m in product([0, 1], repeat=5)))
# True

Dos detalles muerden. El reversed(u) es el orden de entrada: el registro recibe $u_{k-1}$ primero. Y en registro_h el bit nuevo se escribe en v antes de pasar al j siguiente, porque el próximo lo usa: calcular todas las paridades a partir del mensaje solo, sin realimentar, sale mal desde $j=2$.

06 · Lo que el circuito no perdona

El orden de entrada. Si el mensaje entra desde $u_0$, el registro calcula el resto del mensaje dado vuelta, mientras la derivación directa sigue mandando el mensaje en su orden. Medido sobre todos los mensajes, la palabra sale mal en 12 de los 16 del (7,4) y en 24 de los 32 del (15,5); los que se salvan son los capicúa. Y ninguna de las palabras mal armadas es del código: el error no pasa en silencio, pero el receptor ve un síndrome no nulo en tres de cada cuatro mensajes, sin un solo error del canal.

El tiempo. El registro entrega un bit por ciclo, $n$ ciclos por palabra, y durante los $n-k$ de descarga tiene la compuerta cerrada y no acepta mensaje nuevo. Ahorra hardware a cambio de serializar: el producto por $G$, con sus $k(n-k)$ coeficientes, calcula todos los bits de paridad a la vez.

Lo que sigue sirviendo. El mismo divisor, alimentado con la palabra recibida, deja en el registro el resto de dividirla por $g(X)$, que es el síndrome del código cíclico. Sin entrada, realimentándose solo, es un LFSR. Y acortar el código no cambia el circuito: es la base del CRC.

Para tener a mano

1. $v(X)=b(X)+X^{n-k}u(X)$ con $b(X)=R_{g(X)}\{X^{n-k}u(X)\}$: una división. La paridad va en las posiciones 0 a $n-k-1$ y el mensaje al final.
2. El registro de $n-k$ etapas: $f=x+b_{n-k-1}$, $b_0^{\prime }=f$, $b_j^{\prime }=b_{j-1}+g_{j}f$. Cada ciclo multiplica por $X$, suma la entrada y reduce módulo $g(X)$.
3. El mensaje entra desde $u_{k-1}$. $k$ ciclos con la compuerta abierta, $n-k$ con la compuerta cerrada descargando la paridad; al canal sale $v_{n-1}$ primero.
4. (7,4), $u=1011$: registro 000, 110, 101, 100, 100 y $v=1001011$. (15,5), $u=10110$: $b(X)=X+X^3+X^8+X^9$ y $v=010100001110110$.
5. Por $h(X)$: $v_{n-k-j}={\sum }_{i=0}^{k-1}{h}_i{v}_{n-i-j}$, un registro de $k$ etapas y la misma palabra. Se elige el registro más corto: $h(X)$ si $n-k>k$, como en el (15,5); $g(X)$ en los de tasa alta y en el Golay (23,12).
6. Costo: $n-k$ (o $k$) biestables contra $k(n-k)$ coeficientes de la matriz, a cambio de $n$ ciclos por palabra.