¿Por qué se usan ecuaciones polinomiales primitivas en los registros de desplazamiento de retroalimentación lineal?

La elección de qué pulsaciones se utilizarán en los Registros de Cambio de Retroalimentación Lineal (LFSR) determina cuántos registros retrasados, N se incluyen en una secuencia de valores del generador pseudoaleatorio (PRG) antes de que se repita la secuencia. Cada registro de retardo binario se puede expresar como potencia de 2 en la fórmula y se puede usar para retroalimentación con / sin inversión o avance, utilizando compuertas XOR combinadas para crear el algoritmo matemático.

Solo ciertos ajustes de tomas producen las secuencias de longitud máxima (MLS) de (2N-1). Dependiendo de la condición inicial válida (Semilla) y la paridad (par, impar) siempre habrá una condición no válida de todos los ceros o de todos.

Por lo tanto, los MLS LFSR son el diseño de elección para PRG o PRSG. (estas siglas pueden ayudar en futuras búsquedas)

Las aplicaciones incluyen;

Data Encryption/Decryption
Digital Signal Processing
Wireless Communications
Built-in Self Test (BIST)
Data Integrity Checksums
Data Compression
Pseudo-random Number Generation (PN)
Direct Sequence Spread Spectrum
Scrambler/Descrambler
Optimized Counters

    

Se refiere a los LFSR en el título de su pregunta, pero habla sobre la simplicidad de los registros de desplazamiento en el detalle de la pregunta. Tratar con LFSRs ...

Los registros de cambio de retroalimentación lineal son una demostración maravillosa de la simplicidad y el poder inherentes a las matemáticas. Un LFSR contará a través de cada valor posible que pueda mantener para su tamaño de bit, excepto un valor, en un orden aparentemente aleatorio que en realidad es fijo y repetible. El valor omitido es todo-1 o todo-0, dependiendo del tipo de LFSR que sea. El hecho de que pueda hacerlo con un registro de desplazamiento y quizás 4 o 5 puertas XOR, dependiendo de la longitud del LFSR, puede parecer increíble a primera vista.

Por lo tanto, no es sorprendente que las matemáticas subyacentes detrás de este circuito tan simple y útil tengan algo de profundidad. Los polinomios que describen su comportamiento solo son confusos si no estamos familiarizados con las matemáticas o no podemos entenderlas. Sin embargo, eso no nos impide apreciarlo.

La conversión del polinomio en un término de realimentación es bastante sencilla. Hay un montón de texto que muestra esto en Internet.

    

Puede ser más fácil abordar ejemplos específicos a partir del texto.

Pero se hace algo similar para los CRC. Los polinomios se usan ocasionalmente para expresar los valores en ciertas posiciones de bit. En su ejemplo, \ $ x ^ 4 + x + 1 \ $ sería 10011.

Si rellenas los ceros para el polinomio, esto tiene más sentido:

$$ 1x ^ 4 + 0x ^ 3 + 0x ^ 2 + 1x ^ 1 + 1x ^ 0 $$

Los coeficientes son el valor del bit y el resto es la posición del valor. Esto a veces puede ahorrarle algo de escritura y confusión si tuviera un número binario grande como:

$$ 10000000000000001000000000000000 $$

Esto simplemente se escribiría en forma polinomial con: $$ x ^ {31} + x ^ {15} $$

Para los LSFR, está definiendo qué posiciones de bit se están utilizando para generar el siguiente valor del registro. Es mucho más fácil proporcionar el polinomio que define las posiciones de los bits que proporcionar un número binario donde los 1 son las posiciones de los bits.