En computación , un registro de desplazamiento de retroalimentación lineal ( LFSR ) es un registro de desplazamiento cuyo bit de entrada es una función lineal de su estado anterior.
La función lineal de bits individuales más utilizada es exclusiva-o (XOR). Por lo tanto, un LFSR suele ser un registro de desplazamiento cuyo bit de entrada está controlado por el XOR de algunos bits del valor general del registro de desplazamiento.
El valor inicial del LFSR se denomina semilla y, debido a que la operación del registro es determinista, el flujo de valores producido por el registro está completamente determinado por su estado actual (o anterior). Asimismo, debido a que el registro tiene un número finito de estados posibles, eventualmente debe entrar en un ciclo repetitivo. Sin embargo, un LFSR con una función de retroalimentación bien elegida puede producir una secuencia de bits que parece aleatoria y tiene un ciclo muy largo .
Las aplicaciones de los LFSR incluyen la generación de números pseudoaleatorios , secuencias de pseudoruido , contadores digitales rápidos y secuencias de blanqueamiento . Las implementaciones de hardware y software de los LFSR son comunes.
Las matemáticas de una comprobación de redundancia cíclica , que se utilizan para comprobar rápidamente los errores de transmisión, están estrechamente relacionadas con las de un LFSR. [1] En general, la aritmética detrás de los LFSR los hace muy elegantes como objeto de estudio e implementación. Uno puede producir lógicas relativamente complejas con bloques de construcción simples. Sin embargo, también se deben considerar otros métodos, que son menos elegantes pero funcionan mejor.
Las posiciones de bits que afectan el siguiente estado se denominan derivaciones. En el diagrama, los grifos son [16,14,13,11]. El bit más a la derecha del LFSR se llama bit de salida. Las derivaciones se someten a XOR secuencialmente con el bit de salida y luego se retroalimentan al bit más a la izquierda. La secuencia de bits en la posición más a la derecha se denomina flujo de salida.