Introducción
Esta página se puede resumir en una frase: si quieres convertir el polinomio de un LFSR de su forma de Galois a su forma de Fibonacci, invierte el orden de los coeficientes.
Por ejemplo, este es el esquema del LFSR que se utiliza a menudo en los aleatorizadores (scramblers):
Cada bloque marcado con D es un retardo de un ciclo de reloj. La representación de este LFSR como polinomio de Galois es:
G(x) = x16 + x5 + x4 + x3 + 1
Observa que los exponentes del polinomio (3, 4 y 5) reflejan el número de elementos de retardo que hay a la izquierda de cada XOR.
El mismo LFSR se puede implementar en forma de Fibonacci, como se muestra en este esquema:
A pesar de la similitud entre ambos esquemas, el sentido de las flechas está invertido. Las implementaciones de ambos LFSR son completamente distintas.
El polinomio de Fibonacci (o polinomio de realimentación) es este:
F(x) = x16 + x13 + x12 + x11 + 1
El grado del polinomio es n=16, así que cada xi de G(x) se representa en F(x) por xn-i. El resto de la página explica por qué esto no es una coincidencia.
Para una explicación general sobre los LFSR, consulta la página de Wikipedia sobre este tema.
LFSR y filtros digitales
La teoría de los filtros digitales (por ejemplo, los filtros FIR y los filtros IIR) se suele aplicar sobre el cuerpo de los números complejos. Sin embargo, también es posible aplicar esta teoría sobre GF(2), que es el cuerpo finito (también llamado cuerpo de Galois) formado por dos números: 0 y 1. Hay que tener en cuenta algunas particularidades:
- El operador suma en este cuerpo equivale a una XOR.
- Todas las multiplicaciones se hacen con números enteros. De hecho, multiplicar por un número par equivale a multiplicar por 0. Del mismo modo, multiplicar por un número impar equivale a multiplicar por 1. No importa si el número es positivo o negativo.
- Debido a esta regla de las multiplicaciones, la suma y la resta significan lo mismo. Ambas se pueden sustituir por ⊕ (que significa XOR).
La teoría básica de los filtros digitales solo exige que el sistema sea lineal e invariante en el tiempo (LTI). Un LFSR cumple estos requisitos, porque la XOR es lineal y el comportamiento del LFSR es invariante en el tiempo.
La consecuencia más interesante es que se puede utilizar la transformada z para analizar LFSR. Por ejemplo, considera este esquema:
Esto se puede describir con la siguiente ecuación:
y(t) = x(t) ⊕ x(t-1)
t es un número entero que representa el tiempo.
Se puede tratar como un filtro FIR y escribir la transformada z de esta ecuación:
Y(z) = X(z) + X(z)z-1 = X(z) (1 + z-1)
Por consiguiente, la «respuesta al impulso» se puede definir como es habitual: H(z) = Y(z)/X(z), o simplemente:
H(z) = 1 + z-1
¿Y si ponemos dos de estos filtros uno a continuación del otro? ¿Cuál es la «respuesta al impulso» de este filtro?
La teoría de los filtros digitales tiene una respuesta sencilla:
H2(z) = H(z)H(z) = (1 + z-1)(1 + z-1) = 1 + 2z-1 + z-2
Recuerda que en GF(2), multiplicar por un número par equivale a multiplicar por cero. Por tanto,
H2(z) = 1 + 2z-1 + z-2 = 1 + 0z-1 + z-2 = 1 + z-2
lo cual corresponde a este esquema:
No es fácil ver que los filtros que se muestran en los dos últimos esquemas son equivalentes. Pero ambos filtros producen la misma y(t) cuando se les aplica la misma x(t). Por tanto, son el mismo filtro, aunque los valores almacenados en el segundo elemento de retardo no sean los mismos.
Este ejemplo muestra la ventaja de utilizar la transformada z (y técnicas similares con polinomios) para analizar filtros lógicos.
Debo mencionar que los símbolos D o D-1 se utilizan a menudo en lugar de z-1. De hecho, el uso de x en los polinomios de Galois y de Fibonacci tiene el mismo significado que z-1. Todos estos símbolos significan un retardo.
El LFSR de Galois
Para encontrar la representación de Fibonacci, voy a empezar examinando el LFSR de Galois.
Considera el esquema del LFSR de Galois de más arriba. La cadena de retardos y tomas (taps) se puede ver como un filtro FIR, que denotaré como A(z). El LFSR de Galois es, por tanto, equivalente a esto:
Debido a la realimentación, la ecuación para Y(z) es:
Y(z) = Y(z)A(z)
Entonces, ¿qué relación hay entre los parámetros de este filtro FIR y el polinomio de Galois? Escribamos la forma general del polinomio de Galois:
G(x) = xn + gn-1xn-1+ gn-2xn-2+…+ g0
Observa que gn no aparece en esta expresión, para simplificar las matemáticas que vienen a continuación. Además, gn siempre vale 1.
La relación entre G(x) y A(z) es la siguiente:
A(z) = gn-1z-1+gn-2z-2+…+g1z1-n+g0z-n
¿Por qué es correcto esto? Tomemos el LFSR de Galois del esquema anterior y veamos cómo funciona esta expresión.
Primero, fijémonos en la XOR que corresponde a g5. El número 5 indica que hay cinco elementos de retardo a la izquierda de esta XOR. Pero el exponente de z depende del número de elementos de retardo que hay entre la XOR y la salida del filtro FIR. Es decir, depende de los elementos de retardo que están a la derecha de la XOR. En total hay 16 elementos de retardo. Por tanto, g5 aparece en A(z) como g5z-11. Esto coincide con el patrón gn-iz-i.
Otra forma de explicarlo es ver A(z) como un filtro FIR en el dominio del tiempo. La entrada de este filtro FIR es x(t), y su salida es y(t):
y(t) = x(t–16) ⊕ x(t–13) ⊕ x(t–12) ⊕ x(t–11)
Una vez más, t es un número entero que representa el tiempo. Esta expresión representa el LFSR de Galois sin la realimentación. La función de transferencia de este filtro FIR es:
A(z) = Y(z)/X(z) = z-16 + z-13 + z-12 + z-11
Esto es coherente con la expresión general de A(z) para G(x) = x16 + x5 + x4 + x3 + 1.
El equivalente en forma de Fibonacci
Un LFSR en forma de Fibonacci se representa mediante el siguiente polinomio:
F(x) = fnxn+fn-1xn-1+…+f1x + 1
Observa que f0 no aparece en este polinomio porque siempre vale 1. Esto es similar a que gn no aparezca en G(x).
La implementación de este polinomio es:
y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)
Su transformada z es, por tanto:
Y(z) = f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n
Definamos B(z) como sigue:
B(z) = f1z-1+f2z-2+…+fnz-n
En consecuencia, Y(z) se puede escribir como:
Y(z) = Y(z)B(z)
Recuerda que antes teníamos Y(z) = Y(z)A(z). Por tanto, si la forma de Fibonacci del LFSR se comporta igual que el LFSR definido por el polinomio de Galois, se deduce que A(z) = B(z). Lo cual también significa que:
fi=gn-i (i=1,2, … , n)
Como dije desde el principio: para convertir el polinomio de un LFSR de su forma de Galois a su forma de Fibonacci, invierte el orden de los coeficientes.
El filtro inverso del LFSR
Una vez más, esta es la implementación de Fibonacci del LFSR:
y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)
Pero esta expresión también se puede reescribir como:
y(t) + f1y(t-1) + f2y(t-2) +…+ fny(t-n) = 0
(recuerda que + y – son lo mismo en GF(2))
Así pues, los coeficientes del polinomio de Fibonacci también nos indican cómo aplicar la XOR a los valores de y(t-i) para obtener siempre el valor cero. En otras palabras, esto describe un filtro FIR interesante.
La transformada z de la última expresión es:
Y(z) + f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n = 0
O, de forma equivalente:
Y(z)(1+ f1z-1+f2z-2+…+fnz-n) = Y(z)H(z) = 0
Y(z)H(z) es la salida que se obtiene al aplicar el filtro H(z) a Y(z). Y esa salida es cero.
Por tanto, H(z) es la función de transferencia de un filtro FIR. Si alimentas este filtro FIR con la salida del LFSR definido por F(x), la salida será cero en todo momento. Según la definición de B(z) más arriba, la función de transferencia de este filtro FIR es:
H(z) = 1 + f1z-1+f2z-2+…+fnz-n
O bien, en el dominio del tiempo, si la entrada es x(t) y la salida es y(t):
y(t) = x(t) ⊕ f1x(t-1) ⊕ f2x(t-2) ⊕ … ⊕ fnx(t-n)
Si x(t) es la salida del LFSR definido por F(x), entonces y(t) es cero para todo t.