El LFSR y las m-secuencias

El registro de desplazamiento que divide por $g(X)$ codifica y calcula síndromes porque le entra un dato. Sin el dato, lo que queda no calcula nada sobre nadie: genera una secuencia que depende sólo de sus conexiones y de dónde arrancó. Con el polinomio de conexión bien elegido, esa secuencia tarda en repetirse lo máximo posible, y sale de ahí el mismo objeto que ya generaba el código de Hamming.

01 · El registro divisor sin entrada

Un registro de desplazamiento realimentado (linear feedback shift register, LFSR) es un registro divisor sin entrada. Tiene $p$ etapas, y el polinomio que fija sus realimentaciones se llama polinomio de conexión:

$$g(X)=1+g_{1}X+\cdots +g_{p-1}{X}^{p-1}+X^p$$

El estado es el contenido de las etapas, $(b_0,b_1,\dots ,b_{p-1})$, y cada ciclo de reloj lo transforma así:

$$b_0^{\prime }=f,b_j^{\prime }=b_{j-1}+g_{j}f(1\le j\le p-1),f=b_{p-1}$$

La salida es $f$, el bit que abandona el registro por arriba: $y_i=b_{p-1}$ del estado en el ciclo $i$. Con $1+X+X^4$ y arrancando en $1000$, con $b_0$ a la izquierda:

Tres cosas salen de la definición, sin cuentas.

Hay $2^p$ estados y la transición es determinista, así que tarde o temprano un estado se repite y la salida se vuelve periódica.

La transición se puede desandar. Del estado nuevo se lee $f=b_0^{\prime }$, y con $f$ se despeja cada $b_{j-1}=b_j^{\prime }+g_{j}f$. Todo estado tiene un único antecesor: el registro no entra a un ciclo desde afuera, cada estado ya está en uno.

El estado nulo se queda quieto. Con todo en cero, $f=0$ y nada cambia. Queda afuera, y el período más largo posible es el de un ciclo que recorra los otros: $2^p-1$.

02 · Cada ciclo multiplica por X

Leído como polinomio, el estado es $b(X)=b_0+b_{1}X+\cdots +b_{p-1}{X}^{p-1}$, y la transición tiene una lectura de una línea:

$$b^{\prime }(X)=R_g(X)\{Xb(X)\}$$

Paso 1: desplazar es multiplicar por $X$. Cada $b_{j-1}$ pasa a la etapa $j$, que es pasar de multiplicar a $X^{j-1}$ a multiplicar a $X^j$. El que estaba arriba queda como $f{X}^p$, fuera del registro.

Paso 2: la realimentación reduce. Módulo $g(X)$, $X^p\equiv 1+g_{1}X+\cdots +g_{p-1}{X}^{p-1}$, porque en GF(2) restar es sumar. Cambiar $f{X}^p$ por eso es poner $f$ en $b_0$ y sumar $g_{j}f$ en cada etapa: exactamente la ecuación de la transición.

Arrancado en $1000$, que es el polinomio $1$, después de $i$ ciclos el registro tiene $R_g(X)\{X^i\}$. Simulado ciclo a ciclo durante 30 ciclos con $1+X+X^4$ y con $1+X+X^2+X^3+X^4$, el estado coincide en todos con ese resto. Es la construcción de GF(2⁴) con $P(x)$ en el papel de $g(X)$: los estados son ${\alpha }^0,{\alpha }^1,{\alpha }^2,\dots$ en su representación de 4 bits, uno por ciclo. El LFSR es el circuito que recorre las potencias de α.

03 · La recurrencia va por el recíproco

Eliminando el estado de la transición queda una relación entre los bits de salida solos:

$$y_i=\sum _{j=0}^{p-1}{g}_j{y}_{i-p+j}$$

El coeficiente $g_j$ multiplica al bit que salió $p-j$ ciclos atrás. Ordenada por retardo, la recurrencia lee los coeficientes de $g(X)$ al revés, y el polinomio que la satisface es el recíproco:

$$g^{\ast }(X)=X^{p}g(X^{-1}),\sum _{j=0}^p{g}_j^{\ast }{y}_{i-j}=0$$

Para $1+X+X^4$ el recíproco es $1+X^3+X^4$, y la recurrencia es $y_i=y_{i-3}+y_{i-4}$. Sobre la salida de la tabla, $y_4=y_1+y_0=0$ y $y_7=y_4+y_3=1$. Comprobada sobre los ocho polinomios de grado 4, desde cada uno de los 15 estados no nulos y durante 60 bits, la recurrencia por $g^{\ast }(X)$ no falla nunca.

Multiplicando la serie $y(X)={\sum }_i{y}_i{X}^i$ por $g^{\ast }(X)$, la recurrencia anula todos los coeficientes desde $X^p$ en adelante. Lo que sobrevive es un polinomio $d(X)$ de grado menor que $p$, fijado por el estado inicial:

$$y(X)=\frac{d(X)}{g^{\ast }(X)}$$

El codificador se quedaba con el resto de una división. El LFSR entrega el cociente de una división larga que no termina nunca, bit a bit. Y el recíproco no es nuevo en la unidad: el dual de un cíclico lo genera $X^{k}h(X^{-1})$, el recíproco del polinomio de paridad. Vuelve en la sección 07.

04 · Las órbitas y el orden

Como cada estado está en un ciclo, los $2^p-1$ estados no nulos se parten en ciclos disjuntos: las órbitas. El estado inicial no elige el polinomio, pero sí en qué órbita cae el registro. Lo que mide las órbitas es el orden de $g(X)$: el menor $N$ con $g(X)\mid X^N+1$.

La órbita de $1000$ mide exactamente el orden. Sus estados son los $R_g(X)\{X^i\}$, y vuelve a $1$ en el primer $N$ con $X^N\equiv 1$ módulo $g(X)$, que es el primero con $g(X)\mid X^N+1$.

El largo de toda otra órbita divide al orden. Después de $N$ ciclos cualquier estado se multiplicó por $X^N\equiv 1$: volvió. Su órbita pudo haberse cerrado antes, en un divisor de $N$.

Con $g(X)$ irreducible, todas miden lo mismo. Un estado $b(X)\ne 0$ vuelve en $M$ ciclos si $g(X)$ divide a $(X^M+1)b(X)$. Como $b(X)$ tiene grado menor que $p$, $g(X)$ no lo divide, y un irreducible que no divide a un factor divide al otro: $g(X)\mid X^M+1$, y $M$ es múltiplo del orden, para todo estado.

Los ocho polinomios de grado 4 con término independiente, simulados estado por estado:

En las ocho filas la órbita más larga es el orden, y las demás lo dividen. Con un reducible, el período sí depende del estado inicial: $1+X^4$ da 4 ciclos desde $1000$, 2 desde $1010$ y 1 desde $1111$, que se transforma en sí mismo.

05 · Irreducible no alcanza

Para recorrer los $2^p-1$ estados no nulos en una sola órbita, el orden tiene que ser $2^p-1$. Un $g(X)$ reducible no llega: en la tabla, los cinco reducibles tienen orden 7 o menos. Y la tabla tiene un irreducible que tampoco llega.

$1+X+X^2+X^3+X^4$ no tiene factores, pero $(1+X)(1+X+X^2+X^3+X^4)=X^5+1$: su orden es 5, y los quince estados se reparten en tres órbitas de cinco. La condición que hace falta tiene nombre: un polinomio primitivo de grado $p$ es un irreducible de orden $2^p-1$.

Es la misma distinción que separa, en GF(2⁴), un cuerpo de un cuerpo que $\alpha$ recorre entero. Con $P(x)$ ese mismo polinomio, el ciclo de α se cerraba en el paso cinco sobre $\{1,2,4,8,15\}$, y diez elementos quedaban afuera. En el registro, la órbita de $1000$ son esos cinco: $1000$, $0100$, $0010$, $0001$, $1111$. Los diez de afuera no se pierden: son las otras dos órbitas, la de $1100$ y la de $1010$. Cada una es la primera multiplicada por un elemento fijo, $1+X$ y $1+X^2$, porque un ciclo multiplica por $X$ cualquiera sea el estado.

Arranca en $1+X+X^2+X^3+X^4$, que es irreducible: apostá antes de mover. Después pasá a $1+X+X^4$ y compará la autocorrelación de su única órbita con la de una órbita de cinco. Y probá $1+X+X^2+X^4$, que es reducible: mirá qué valores toma la autocorrelación de su órbita de siete. La sección que sigue explica por qué.

06 · La m-secuencia

La salida de un LFSR de $p$ etapas es de longitud máxima, una m-secuencia, si su período es $N=2^p-1$. Por la sección anterior, pasa exactamente cuando $g(X)$ es primitivo, y entonces pasa desde cualquier estado no nulo. Con $1+X+X^4$ desde $1000$, un período es

$$y=000100110101111$$

Tiene tres propiedades, y las tres salen de que el estado recorre todos los no nulos una vez por período.

Balance. Cada bit de salida es el $b_{p-1}$ de un estado, y en un período pasan los $2^p-1$ estados no nulos. De ellos, $2^{p-1}$ tienen un uno arriba y $2^{p-1}-1$ un cero: falta el nulo. En $y$, 8 unos y 7 ceros.

Ventana. Los $p$ bits que salen a partir del ciclo $i$ los decide el estado en el ciclo $i$, y como la cuenta es lineal y sin pérdida, también lo determinan: con $1+X+X^4$, los quince estados dan quince ventanas distintas. Deslizando una ventana de $p$ bits sobre un período aparece cada $p$-tupla no nula exactamente una vez, y nunca la nula.

Autocorrelación de dos valores. Con $z_i=(-1{)}^{y_i}$, que lleva el 0 a $+1$ y el 1 a $-1$, la autocorrelación cíclica es

$$r(\tau )=\frac{1}{N}\sum _{i=0}^{N-1}{z}_i{z}_{i+\tau }=\{\begin{array}{ll}1& \tau =0\\ -1/N& \tau \ne 0\end{array}$$

con los índices módulo $N$. El segundo valor pide prueba.

Paso 1: correlar es contar diferencias. El producto $z_i{z}_{i+\tau }$ vale $+1$ donde $y$ y su versión girada coinciden y $-1$ donde difieren. Si difieren en $w$ lugares, $Nr(\tau )=N-2w$, y $w$ es el peso de la suma de $y$ con su giro.

Paso 2: la suma es otro giro. El registro es lineal: la salida desde la suma de dos estados es la suma de las salidas. Con una sola órbita, las salidas desde los $N$ estados no nulos son los $N$ giros de $y$. La suma de dos giros distintos es la salida desde un estado no nulo, o sea otro giro de $y$.

Paso 3: todo giro pesa lo mismo. Por el balance, $w=2^{p-1}$, y $Nr(\tau )=(2^p-1)-2^p=-1$ para todo $\tau \ne 0$.

Medido sobre la salida desde $1000$ de los siete primitivos de la tabla de la sección 08, de grado 2 a 8, con $N$ de 3 a 255: $Nr(\tau )=-1$ en cada uno de los $N-1$ desplazamientos no nulos, y el balance da $2^{p-1}$ unos en los siete. Cuanto más largo el período, más se parece $r(\tau )$ a una delta, y de ahí el nombre de secuencia pseudoaleatoria: un receptor que corre una réplica local encuentra el sincronismo en el único pico. Sumada módulo 2 a un flujo de datos, rompe las corridas largas de símbolos iguales, y sumarla otra vez la saca.

Sin primitivo, la forma se rompe. La órbita de $1000$ en $1+X+X^2+X^3+X^4$ sale $00011$, y $5r(\tau )$ vale $5,1,-3,-3,1$: tres valores. Pero la recíproca no vale. La órbita de $1000$ en $1+X+X^2+X^4$ sale $0001011$, de período 7, y su autocorrelación es $-1/7$ en los seis desplazamientos: dos valores, en un registro que no es de longitud máxima. Es que $1+X+X^2+X^4=(1+X)(1+X^2+X^3)$, y esa salida es el complemento de la m-secuencia de $1+X^2+X^3$, que tiene tres etapas: el complemento no cambia ninguna coincidencia. Lo que delata al registro de cuatro es la ventana: sobre esos siete bits aparecen 7 de las 15 cuaternas no nulas. Dos valores dicen que hay una m-secuencia; el período y la ventana dicen de qué largo.

07 · Hamming, símplex y m-secuencia

Un primitivo $g(X)$ de grado $m$, con $n=2^m-1$, hace tres cosas que son la misma.

1. Genera el Hamming cíclico $(2^m-1,2^m-1-m)$. Su matriz de paridad tiene por columnas $1,\alpha ,\dots ,{\alpha }^{n-1}$, que por la sección 02 son, en orden, los estados del LFSR arrancado en $1000$.

2. Su dual es el símplex $(2^m-1,m)$, en el que las $2^m-1$ palabras no nulas pesan todas $2^{m-1}$.

3. Las palabras no nulas de ese símplex son los $n$ giros de la m-secuencia del LFSR con el mismo $g(X)$. La m-secuencia cumple su recurrencia en forma cíclica, porque su período es $n$, y ${\sum }_j{g}_j^{\ast }{y}_{i-j}=0$ para todo $i$ módulo $n$ es justamente

$$y(X)g^{\ast }(X)\equiv 0mod{X}^n+1$$

la condición de palabra del cíclico con polinomio de paridad $h(X)=g^{\ast }(X)$. El dual de ese código lo genera el recíproco de su $h$, que es $g(X)$ otra vez: el Hamming.

Medido con $1+X+X^4$: los 15 giros de $y$ más la palabra nula son 16 palabras distintas, todas en el dual del Hamming (15,11), que tiene 16; las 15 no nulas pesan 8. Con $1+X+X^3$, los 7 giros de $0010111$ y la nula son el dual del (7,4), con las 7 no nulas de peso 4.

Cuál $h$ es importa. La m-secuencia de $1+X+X^4$ es palabra del cíclico de paridad $1+X^3+X^4$, no del de paridad $1+X+X^4$: ése contiene la m-secuencia de $1+X^3+X^4$, que es la misma leída al revés. Son los dos símplex de largo 15, y los dos generadores con $d_{\text{min}}=8$ que aparecen con $n-k=11$ en el catálogo de largo 15.

El mismo polinomio resuelve dos problemas que no parecían relacionados: un código que corrige un error a cualquier largo, y una secuencia de período máximo. El circuito es, en los dos casos, un registro de $m$ etapas. En la Unidad 6 el registro cambia de papel: dada una secuencia de síndromes, buscar el LFSR más corto que la genera es el algoritmo de Berlekamp-Massey.

08 · Lo que cuesta el registro

Un LFSR de $p$ etapas son $p$ biestables y una compuerta XOR por cada coeficiente intermedio no nulo de $g(X)$. Los primitivos de uso corriente:

Un trinomio primitivo, $1+X^a+X^p$, deja el generador en $p$ biestables y una sola compuerta. No siempre hay uno: probados todos los trinomios de grado 2 a 30, en nueve grados ninguno es primitivo, el 8, 12, 13, 14, 16, 19, 24, 26 y 27. En el grado 8 no hay ni siquiera un trinomio irreducible. Con cuatro términos nunca hay irreducible, así que el siguiente candidato es un pentanomio, con tres compuertas: es lo que trae la fila del grado 8. Medido grado por grado, los nueve tienen al menos un pentanomio primitivo.

El costo crece con $p$ y el período con $2^p$: con 32 etapas, $2^{32}-1=4294967295$ bits antes de repetir.

Para tener a mano

1. LFSR: el divisor por $g(X)$ sin entrada. $b_0^{\prime }=f$, $b_j^{\prime }=b_{j-1}+g_{j}f$, salida $f=b_{p-1}$. Cada ciclo es $b(X)\mapsto R_g(X)\{Xb(X)\}$: desde $1000$, las potencias de $\alpha$.
2. La salida cumple la recurrencia de $g^{\ast }(X)$, el recíproco, no la de $g(X)$. $y(X)=d(X)/g^{\ast }(X)$: un cociente que no termina.
3. Los estados no nulos se parten en órbitas. La de $1000$ mide el orden de $g(X)$, el menor $N$ con $g(X)\mid X^N+1$; las otras lo dividen; con $g(X)$ irreducible, todas lo igualan.
4. Período $2^p-1$ si y sólo si $g(X)$ es primitivo: irreducible y de orden $2^p-1$. $1+X+X^2+X^3+X^4$ es irreducible, de orden 5: tres órbitas de cinco.
5. La m-secuencia: $2^{p-1}$ unos y uno menos de ceros; cada $p$-tupla no nula una vez en la ventana; $r(\tau )=-1/N$ fuera del origen, porque la suma de dos giros es otro giro. Dos valores no alcanzan para certificar el largo: lo certifican el período y la ventana.
6. Un primitivo genera el Hamming; su dual es el símplex; las palabras no nulas del símplex son los giros de la m-secuencia, que cumple $y(X)g^{\ast }(X)\equiv 0$: su paridad es $g^{\ast }(X)$.
7. Trinomio primitivo: una compuerta. De grado 2 a 30 falta en nueve grados, el 8 entre ellos; ahí va un pentanomio.