Para entender la conexión entre los grifos y los polinomios primitivos, es importante profundizar en el campo de Galois o en el campo finito. Sin embargo, trataré de resumirlo: El circuito LFSR básicamente realiza una multiplicación sobre un "campo". Un campo suele definirse como un conjunto con dos operaciones definidas (multiplicación y suma) y otras leyes como la asociativa y la distributiva.
Los campos finitos se denominan Campo de Galois tales Números binarios (0 y 1) con XOR (= suma de módulo 2) y AND (multiplicación) es un GF(2).
Los polinomios con coeficiente binario también forman un GF(2) con cada término (x^n) presente (1*x^n) o ausente (0*x^n). La suma y la multiplicación de estos polinomios forman un campo: Suma (= XOR de cada término) y Multiplicación (Desplazamiento a la izquierda).
![Addition]()
![Multiplication]()
Un polinomio primitivo es aquel que no puede ser factorizado. Y como dato: para cualquier grado existe al menos un polinomio primo ( Busca la Tabla de Polinomios Primitivos).
Tomando el resultado de la multiplicación anterior, y modulando un polinomio primo, podemos formar GF(2^n).
Como ejemplo: Consideremos un LFSR de 4 bits con los polinomios x^4 + x + 1. Con LFSR=> ![4 Bit LFSR]()
El patrón que genera : 0001, 0010, 0100, 1000, 0011, 0110, 1100, 1011 ....
Observe que siempre que el MSB (Q4) es uno, los valores del registro actual se xorrean con "10011" o si es cero, los valores sólo se desplazan a la izquierda.
Esto también se puede explicar en términos de elementos primitivos: a^3 = 1*x^3 + 0*x^2 + 0*x^1 + 0*x^0 a^4 = 1*x^4 xor x^4 + x + 1 = x + 1 = "0011"
En resumen : Multiplicación del campo de Galois => Desplazamiento a la izquierda en el hardware Tomando el resultado mod p(X) => Xoring cuando el MSB es 1
Espero que esto ayude.
Fuente: Recopilación de notas de estudio de la Universidad de Múnich y Berkeley.
0 votos
(Si lo he entendido bien, lo siguiente sólo se aplica a los LFSR de Galois, así que sólo lo comentaré). El truco está en que si representamos el estado $(a_0,a_1,a_2,a_3)$ como un polinomio $p(x)=a_0+a_1x+a_2x^2+a_3x^3$ y, a continuación, el nuevo estado (tras un único tick de reloj) $(a_3,a_0,a_1+a_3,a_2)$ corresponde al polinomio $q(x)=x p(x)+a_3(x^4+x^3+1)$ que es congruente con $xp(x)$ módulo del polinomio de retroalimentación. Los polinomios primitivos $r(x)$ de grado $d$ tienen la propiedad de que el coset $x+(r(x))$ genera el grupo multiplicativo del campo finito $GF(2^d)=GF(2)[x]/(r(x))$ .
0 votos
(cont.) y esto explica por qué el vector de estado recorre todos los estados distintos de cero. Nunca recuerdo cómo funciona el álgebra polinómica para los LFSR Fibonacci. IIRC el polinomio recíproco entra en juego o el reloj corre hacia atrás o algo así. Lo siento, es demasiado tarde para pensar con claridad :-/
1 votos
Eche un vistazo a John Kerl "Computación en campos finitos" parte V (lamentablemente, el documento está incompleto).
0 votos
@JyrkiLahtonen: Soy bastante autodidacta en este campo así que hay MUCHO que tengo que aprender empezando por lo que es $xp(x)$ ? No tengas miedo de hablarme como si fuera estúpido. En campos finitos y teoría de Galois, más o menos lo soy.
0 votos
Aquí se explica muy bien este problema: homepages.cae.wisc.edu/~ece553/handouts/LFSR-notes.PDF