Registro de desplazamiento de retroalimentación lineal

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. 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.

LFSR de Fibonacci

Un Fibonacci LFSR de 16 bits. Los números de grifo de retroalimentación mostrados corresponden a un polinomio primitivo en la tabla, por lo que los ciclos de registro a través del número máximo de 65535 estados excluyendo el estado de todos los ceros. El estado mostrado, 0xACE1 (hexadecimal) será seguido por 0x5670.

Las posiciones de bits que afectan al 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 tomas son XOR'd secuencialmente con el bit de salida y luego 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.

• Los bits en el estado LFSR que influencian la entrada se llaman grifos.
• Una LFSR de longitud máxima produce una secuencia de m (es decir, ciclos a través de todos los posibles 2^m− 1 estados dentro del registro de cambios excepto el estado donde todos los bits son cero), a menos que contenga todos los ceros, en cuyo caso nunca cambiará.
• Como alternativa a la retroalimentación basada en XOR en un LFSR, también se puede utilizar XNOR. Esta función es un mapa affine, no estrictamente un mapa lineal, pero resulta en un contador polinomio equivalente cuyo estado es el complemento del estado de una LFSR. Un estado con todos es ilegal al usar una retroalimentación XNOR, de la misma manera que un estado con todos los ceros es ilegal al usar XOR. Este estado es considerado ilegal porque el contador permanecería "cerrado" en este estado. Este método puede ser ventajoso en hardware LFSRs usando volteretas que comienzan en un estado cero, ya que no comienza en un estado de bloqueo, lo que significa que el registro no necesita ser sembrado para comenzar a operar.

La secuencia de números generada por un LFSR o su contraparte XNOR puede considerarse un sistema numérico binario tan válido como el código Gray o el código binario natural.

La disposición de las derivaciones para la retroalimentación en un LFSR se puede expresar en aritmética de campos finitos como un polinomio mod 2. Esto significa que los coeficientes del polinomio deben ser 1 o 0. Esto se llama polinomio de retroalimentación o polinomio de característica recíproca. Por ejemplo, si las derivaciones están en los bits 16, 14, 13 y 11 (como se muestra), el polinomio de retroalimentación es

x16+x14+x13+x11+1.{displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1.}

El "uno" en el polinomio no corresponde a un toque, corresponde a la entrada del primer bit (es decir, x⁰, que es equivalente a 1). Las potencias de los términos representan los bits tocados, contando desde la izquierda. El primer y el último bit siempre están conectados como toma de entrada y salida respectivamente.

El LFSR tiene una longitud máxima si y solo si el polinomio de retroalimentación correspondiente es primitivo sobre el campo de Galois GF(2). Esto significa que las siguientes condiciones son necesarias (pero no suficientes):

• El número de grifos es incluso.
• El conjunto de grifos es co-prime ajustado; es decir, no debe haber divisor aparte de 1 común a todos los grifos.

Las tablas de polinomios primitivos a partir de los cuales se pueden construir LFSR de longitud máxima se proporcionan a continuación y en las referencias.

Puede haber más de una secuencia de pulsaciones de longitud máxima para una longitud de LFSR dada. Además, una vez que se ha encontrado una secuencia de pulsaciones de longitud máxima, otra sigue automáticamente. Si la secuencia de pulsaciones en un LFSR de n bits es [n, A, B, C, 0], donde el 0 corresponde al término x⁰ = 1, luego el correspondiente & #34;espejo" la secuencia es [n, n − C, n − B, n − A, 0]. Entonces, la secuencia de toques [32, 22, 2, 1, 0] tiene como contrapartida [32, 31, 30, 10, 0] . Ambos dan una secuencia de longitud máxima.

A continuación se muestra un ejemplo en C:

#include - No.no firmado lfsr_fib()vacío){} uint16_t start_state = 0xACE1u; /* Cualquier estado de inicio no cero funcionará. */ uint16_t lfsr = start_state; uint16_t bit; /* Debe ser de 16 bits para permitir el bit observado15 más adelante en el código */ no firmado período de sesiones = 0; do {} /* grifos: 16 14 13 11; polinomial de retroalimentación: x^16 + x^14 + x^13 + x^11 + 1 */ bit = ()lfsr > 0) ^ ()lfsr > 2) ^ ()lfsr > 3) ^ ()lfsr > 5) " 1u; lfsr = ()lfsr > 1) Silencio ()bit .. 15); ++período de sesiones; } mientras ()lfsr ! start_state); retorno período de sesiones;}

Si se encuentra disponible una operación rápida de paridad o de conteo, el bit de retroalimentación se puede calcular de manera más eficiente como el producto escalar del registro con el polinomio característico:

• bit = parity(lfsr & 0x002Du);, o equivalente
• bit = popcnt(lfsr & 0x002Du) /* & 1u */;. (El & 1u convierte el popcnt en una verdadera función de paridad, pero el bitshift más tarde bit << 15 hace que los bits más altos sean irrelevantes.)

Si una operación de rotación está disponible, el nuevo estado se puede calcular como

• lfsr = rotateright((lfsr & ~1u) | (bit & 1u), 1);, o equivalente
• lfsr = rotateright(((bit ^ lfsr) & 1u) ^ lfsr, 1);

Esta configuración LFSR también se conoce como estándar, muchos a uno o compuertas XOR externas. La configuración alternativa de Galois se describe en la siguiente sección.

Ejemplo en Python

Una implementación de Python de muestra de un LFSR de Fibonacci similar (toques de 16 bits en [16,15,13,4]) sería

start_state = 1 .. 15 Silencio 1lfsr = start_stateperíodo de sesiones = 0mientras Cierto.: #taps: 16 15 13 4; feedback polynomial: x^16 + x^15 + x^13 + x^4 + 1 bit = ()lfsr ^ ()lfsr > 1) ^ ()lfsr > 3) ^ ()lfsr > 12) " 1 lfsr = ()lfsr > 1) Silencio ()bit .. 15) período de sesiones += 1 si ()lfsr == start_state): impresión()período de sesiones) descanso

Donde se utiliza un registro de 16 bits y la pulsación xor en el cuarto, 13, 15 y 16 bits establece una longitud de secuencia máxima.

Galois LFSR

Un Galois LFSR de 16 bits. Los números de registro arriba corresponden al mismo polinomio primitivo que el ejemplo Fibonacci, pero se cuentan en reversa a la dirección de cambio. Este registro también se extiende a través del número máximo de 65535 estados excluyendo el estado de todos los ceros. El hex ACE1 del estado mostrado será seguido por E270 hex.

Nombrado en honor al matemático francés Évariste Galois, un LFSR en configuración de Galois, que también se conoce como modular, XOR interno o uno a muchos LFSR, es una estructura alternativa que puede generar el mismo flujo de salida que un LFSR convencional (pero compensado en el tiempo). En la configuración de Galois, cuando el sistema está cronometrado, los bits que no son derivaciones se desplazan una posición a la derecha sin cambios. Las derivaciones, por otro lado, se someten a XOR con el bit de salida antes de que se almacenen en la siguiente posición. El nuevo bit de salida es el siguiente bit de entrada. El efecto de esto es que cuando el bit de salida es cero, todos los bits en el registro se desplazan hacia la derecha sin cambios, y el bit de entrada se convierte en cero. Cuando el bit de salida es uno, todos los bits en las posiciones de derivación se invierten (si son 0, se convierten en 1, y si son 1, se convierten en 0), y luego todo el registro se desplaza a la derecha y el bit de entrada se convierte en 1

Para generar el mismo flujo de salida, el orden de los toques es el contraparte (ver arriba) del orden del LFSR convencional; de lo contrario, el flujo será inverso. Tenga en cuenta que el estado interno del LFSR no es necesariamente el mismo. El registro de Galois que se muestra tiene el mismo flujo de salida que el registro de Fibonacci en la primera sección. Existe una compensación de tiempo entre las corrientes, por lo que se necesitará un punto de inicio diferente para obtener el mismo resultado en cada ciclo.

• Galois LFSRs no concatenan cada grifo para producir la nueva entrada (la XORing se hace dentro de la LFSR, y ninguna puerta XOR se ejecuta en serie, por lo tanto los tiempos de propagación se reducen a la de un XOR en lugar de una cadena entera), por lo que es posible que cada grifo se computa en paralelo, aumentando la velocidad de ejecución.
• En una aplicación de software de la LFSR, la forma Galois es más eficiente, ya que las operaciones XOR pueden ser implementadas una palabra a la vez: sólo el bit de salida debe ser examinado individualmente.

A continuación se muestra un ejemplo de código C para el ejemplo de LFSR de Galois de período máximo de 16 bits en la figura:

#include - No.no firmado lfsr_galois()vacío){} uint16_t start_state = 0xACE1u; /* Cualquier estado de inicio no cero funcionará. */ uint16_t lfsr = start_state; no firmado período de sesiones = 0; do {}#ifndef LEFT no firmado lsb = lfsr " 1u; /* Obtener LSB (es decir, el bit de salida). */ lfsr > 1; * Registro de cambios */ si ()lsb) /* Si el bit de salida es 1, */ lfsr ^= 0xB400u; /* aplicar máscara de toggle. */#else no firmado msb = ()int16_t) lfsr . 0; /* Obtener MSB (es decir, el bit de salida). */ lfsr " 1; * Registro de cambios */ si ()msb) /* Si el bit de salida es 1, */ lfsr ^= 0x002 Du; /* aplicar máscara de toggle. */#endif ++período de sesiones; } mientras ()lfsr ! start_state); retorno período de sesiones;}

La rama if (lsb) lfsr ^= 0xB400u;también se puede escribir como lfsr ^= (-lsb) & 0xB400u; que puede producir un código más eficiente en algunos compiladores. Además, la variante de desplazamiento a la izquierda puede producir un código aún mejor, ya que el msb es el acarreo de la adición de lfsr a sí mismo.

Galois LFSR no binario

Los LFSR binarios de Galois como los que se muestran arriba se pueden generalizar a cualquier alfabeto q-ario {0, 1,..., q − 1} (por ejemplo, para binario, q = 2, y el alfabeto es simplemente {0, 1}). En este caso, el componente o exclusivo se generaliza a la suma módulo-q (nótese que XOR es suma módulo 2), y el bit de retroalimentación (bit de salida) se multiplica (módulo-q ) por un valor q-ario, que es constante para cada punto de toque específico. Tenga en cuenta que esto también es una generalización del caso binario, donde la retroalimentación se multiplica por 0 (sin retroalimentación, es decir, sin toque) o 1 (hay retroalimentación). Dada una configuración de derivación adecuada, tales LFSR se pueden usar para generar campos de Galois para valores primos arbitrarios de q.

LFSR Xorshift

Como lo muestra George Marsaglia y lo analiza con más detalle Richard P. Brent, los registros de desplazamiento de retroalimentación lineal se pueden implementar mediante operaciones XOR y Shift. Este enfoque se presta a una ejecución rápida en el software porque estas operaciones generalmente se asignan de manera eficiente a las instrucciones del procesador moderno.

A continuación se muestra un ejemplo de código C para un LFSR Xorshift de período máximo de 16 bits que usa el triplete 7,9,13 de John Metcalf:

#include - No.no firmado lfsr_xorshift()vacío){} uint16_t start_state = 0xACE1u; /* Cualquier estado de inicio no cero funcionará. */ uint16_t lfsr = start_state; no firmado período de sesiones = 0; do {} // 7,9,13 triplet de http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html lfsr ^= lfsr > 7; lfsr ^= lfsr .. 9; lfsr ^= lfsr > 13; ++período de sesiones; } mientras ()lfsr ! start_state); retorno período de sesiones;}

Formas de matriz

Los LFSR binarios de ambas configuraciones Fibonacci y Galois pueden expresarse como funciones lineales usando matrices en F2{displaystyle mathbb {F} _{2} (véase GF(2)). Usando la matriz compañera del polinomio característico de la LFSR y denotando la semilla como vector de columna ()a0,a1,...... ,an− − 1)T{displaystyle (a_{0},a_{1},dotsa_{n-1}^{mathrm {T}, el estado del registro en la configuración Fibonacci después k{displaystyle k} pasos dados por

()akak+1ak+2⋮ ⋮ ak+n− − 1)=()010⋯ ⋯ 0001⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ 000⋯ ⋯ 01c0c1⋯ ⋯ ⋯ ⋯ cn− − 1)()ak− − 1akak+1⋮ ⋮ ak+n− − 2)=()010⋯ ⋯ 0001⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ 000⋯ ⋯ 01c0c1⋯ ⋯ ⋯ ⋯ cn− − 1)k()a0a1a2⋮ ⋮ an− − 1){displaystyle {begin{pmatrix}a_{k}a_{k+1}a_{k+2}\vdots {a_{k+n-1}end{pmatrix}}={begin{pmatrix}0 limit1 limitcdots &0 limit0 limit1 limitddots >vdots > > } {begin{pmatrix}a_{k-1}a_{k}a_{k}a_{k+1}\vdots {a_{k+n-2}end{pmatrix}}={begin{pmatrix}0 limit1 limitcdots &0 concdots <vdots >vdots >ddots > > {begin{pmatrix}a_{2}vdots {fn1}end{pmatrix}}}

La matriz para la forma de Galois correspondiente es:

()c010⋯ ⋯ 0c101⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ 0cn− − 20⋯ ⋯ 01cn− − 10⋯ ⋯ ⋯ ⋯ 0){displaystyle {begin{pmatrix}c_{0} diez1 ventaja0cdots > \c_{1} limit0 ventaja1ddots &vdots \vdots &vdots &ddots > "0c_{n-2cdots > }

Para una inicialización adecuada,

<math alttext="{displaystyle a'_{i}=sum _{i=0}^{j}a_{i-j}c_{n-j}, 0leq iai.=.. i=0jai− − jcn− − j,0≤ ≤ i.n{displaystyle a'_{i}=sum ¿Qué? 0leq I didnn}<img alt="{displaystyle a'_{i}=sum _{i=0}^{j}a_{i-j}c_{n-j}, 0leq i

el coeficiente superior del vector columna:

()c010⋯ ⋯ 0c101⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ 0cn− − 20⋯ ⋯ 01cn− − 10⋯ ⋯ ⋯ ⋯ 0)k()a0.a1.a2.⋮ ⋮ an− − 1.){displaystyle {begin{pmatrix}c_{0} diez1 ventaja0cdots >c_{1} limit0 implica1ddots &vdots \vdots > 'ddots > {0c_{n-2}cdots >}c_{n-1}cdots >cdots > {pmatrix}{k}{k}{k}{pmatrix}a'_{0}a'_{1}a'_{2}\vdots}\\cdots\\cdots} {fn1}}}

da el término ak de la secuencia original.

Estas formas se generalizan naturalmente a campos arbitrarios.

Ejemplos de polinomios para LFSR máximos

La siguiente tabla enumera ejemplos de polinomios de retroalimentación de longitud máxima (polinomios primitivos) para longitudes de registro de desplazamiento de hasta 24. El formalismo para los LFSR de longitud máxima fue desarrollado por Solomon W. Golomb en su libro de 1967. El número de diferentes polinomios primitivos crece exponencialmente con la longitud del registro de desplazamiento y se puede calcular exactamente usando la función totient de Euler (secuencia A011260 en el OEIS).

Bits (n)	Feedback polynomial	Taps	Taps (hex)	Período (2n− − 1{displaystyle 2^{n}-1})
2	x2+x+1{displaystyle x^{2}+x+1}	11	0x3	3
3	x3+x2+1{displaystyle x^{3}+x^{2}+1}	110	0x6	7
4	x4+x3+1{displaystyle x^{4}+x^{3}+1}	1100	0xC	15
5	x5+x3+1{displaystyle x^{5}+x^{3}+1}	10100	0x14	31
6	x6+x5+1{displaystyle x^{6}+x^{5}+1}	110000	0x30	63
7	x7+x6+1{displaystyle x^{7}+x^{6}+1}	1100000	0x60	127
8	x8+x6+x5+x4+1{displaystyle x^{8}+x^{6}+x^{5}+x^{4}+1}	10110100	0xB4	255
9	x9+x5+1{displaystyle x^{9}+x^{5}+1}	100010000	0x110	511
10	x10+x7+1{displaystyle x^{10}+x^{7}+1}	1001000000	0x240	1.023
11	x11+x9+1{displaystyle x^{11}+x^{9}+1}	10100000	0x500	2.047
12	x12+x11+x10+x4+1{displaystyle x^{12}+x^{11}+x^{10}+x^{4}+1}	111000001000	0xE08	4.095
13	x13+x12+x11+x8+1{displaystyle x^{13}+x^{12}+x^{11}+x^{8}+1}	1110010000	0x1C80	8.191
14	x14+x13+x12+x2+1{displaystyle x^{14}+x^{13}+x^{12}+x^{2}+1}	11100000000010	0x3802	16.383
15	x15+x14+1{displaystyle x^{15}+x^{14}+1}	110000000000	0x6000	32.767
16	x16+x15+x13+x4+1{displaystyle x^{16}+x^{15}+x^{13}+x^{4}+1}	1101000001000	0xD008	65.535
17	x17+x14+1{displaystyle x^{17}+x^{14}+1}	10010000000000000	0x12000	131.071
18	x18+x11+1{displaystyle x^{18}+x^{11}+1}	100000010000000000	0x20400	262,143
19	x19+x18+x17+x14+1{displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}	1110010000000000000	0x72000	524.287
20	x20+x17+1{displaystyle x^{20}+x^{17}+1}	10010000000000000000000	0x90000	1.048.575
21	x21+x19+1{displaystyle x^{21}+x^{19}+1}	101000000000000000000000	0x140000	2,097,151
22	x22+x21+1{displaystyle x^{22}+x^{21}+1}	1100000000000000000000000000	0x300000	4,194,303
23	x23+x18+1{displaystyle x^{23}+x^{18}+1}	10000000000000000000000000	0x420000	8.388.607
24	x24+x23+x22+x17+1{displaystyle x^{24}+x^{23}+x^{22}+x^{17}+1}	111000010000000000000000	0xE10000	16,777,215

Xilinx publicó una lista ampliada de contadores de pulsaciones de hasta 168 bits. Las tablas de polinomios de longitud máxima están disponibles en http://users.ece.cmu.edu/~koopman/lfsr/ y pueden ser generadas por el proyecto https://github.com/hayguen/mlpolygen.

Propiedades del flujo de salida

• Unos y ceros ocurren en "runs". El flujo de salida 1110010, por ejemplo, consta de cuatro carreras de longitudes 3, 2, 1, 1, en orden. En un período de un LFSR maximal, 2n−1 se produce (en el ejemplo anterior, la LFSR de 3 bits tiene 4 carreras). Exactamente la mitad de estas carreras son un poco largos, un cuarto son dos bits largos, hasta una sola carrera de ceros n− 1 bits de largo, y una sola carrera de uno n Hace mucho. Esta distribución casi iguala el valor de expectativa estadística para una secuencia verdaderamente aleatoria. Sin embargo, la probabilidad de encontrar exactamente esta distribución en una muestra de una secuencia verdaderamente aleatoria es bastante baja.
• Los flujos de salida LFSR son deterministas. Si se conoce el estado actual y las posiciones de las puertas XOR en la LFSR, se puede predecir el siguiente estado. Esto no es posible con eventos verdaderamente aleatorios. Con LFSRs de máxima longitud, es mucho más fácil calcular el siguiente estado, ya que sólo hay un número fácilmente limitado de ellos para cada longitud.
• El flujo de salida es reversible; un LFSR con grifos retrovisores cicloará a través de la secuencia de salida en orden inverso.
• El valor consistente en todos los ceros no puede aparecer. Así un LFSR de longitud n no se puede utilizar para generar los 2n valores.

Aplicaciones

Los LFSR se pueden implementar en hardware y esto los hace útiles en aplicaciones que requieren una generación muy rápida de una secuencia pseudoaleatoria, como la radio de espectro ensanchado de secuencia directa. Los LFSR también se han utilizado para generar una aproximación de ruido blanco en varios generadores de sonido programables.

Usos como contadores

La secuencia repetitiva de estados de un LFSR permite que se use como un divisor de reloj o como un contador cuando una secuencia no binaria es aceptable, como suele ser el caso cuando el índice de computadora o las ubicaciones de encuadre deben ser legibles por máquina.. Los contadores LFSR tienen una lógica de retroalimentación más simple que los contadores binarios naturales o los contadores de código Gray y, por lo tanto, pueden operar a velocidades de reloj más altas. Sin embargo, es necesario asegurarse de que el LFSR nunca entre en un estado de todos ceros, por ejemplo preestableciéndolo en el arranque a cualquier otro estado en la secuencia. La tabla de polinomios primitivos muestra cómo se pueden organizar los LFSR en forma de Fibonacci o Galois para dar períodos máximos. Se puede obtener cualquier otro período agregando a un LFSR que tiene un período más largo alguna lógica que acorte la secuencia omitiendo algunos estados.

Usos en criptografía

Los LFSR se han utilizado durante mucho tiempo como generadores de números pseudoaleatorios para su uso en cifrados de flujo, debido a la facilidad de construcción a partir de circuitos electromecánicos o electrónicos simples, largos períodos y flujos de salida distribuidos de manera muy uniforme. Sin embargo, un LFSR es un sistema lineal, lo que lleva a un criptoanálisis bastante sencillo. Por ejemplo, dado un tramo de texto sin formato conocido y el texto cifrado correspondiente, un atacante puede interceptar y recuperar un tramo del flujo de salida LFSR utilizado en el sistema descrito y, a partir de ese tramo del flujo de salida, puede construir un LFSR de tamaño mínimo que simule la intención. receptor utilizando el algoritmo de Berlekamp-Massey. Este LFSR se puede alimentar con el tramo interceptado del flujo de salida para recuperar el texto sin formato restante.

Se emplean tres métodos generales para reducir este problema en los cifrados de flujo basados en LFSR:

• Combinación no lineal de varios bits del estado LFSR;
• Combinación no lineal de los bits de salida de dos o más LFSRs (ver también: generador de reducción); o usando algoritmo Evolutionary para introducir no linearidad.
• El reloj irregular de la LFSR, como en el generador de paso alternado.

Entre los cifrados de flujo importantes basados en LFSR se incluyen A5/1 y A5/2, utilizados en teléfonos móviles GSM, E0, utilizado en Bluetooth y el generador de reducción. El cifrado A5/2 se ha roto y tanto A5/1 como E0 tienen serias debilidades.

El registro de desplazamiento de retroalimentación lineal tiene una fuerte relación con los generadores lineales congruentes.

Usos en pruebas de circuitos

Los LFSR se utilizan en pruebas de circuitos para generar patrones de prueba (para pruebas exhaustivas, pruebas pseudoaleatorias o pruebas pseudoexhaustivas) y para el análisis de firmas.

Generación de patrones de prueba

Los LFSR completos se usan comúnmente como generadores de patrones para pruebas exhaustivas, ya que cubren todas las entradas posibles para un circuito de entrada n. Los LFSR de longitud máxima y los LFSR ponderados se utilizan ampliamente como generadores de patrones de prueba pseudoaleatorios para aplicaciones de prueba pseudoaleatorias.

Análisis de firma

En las técnicas de autocomprobación integradas (BIST), no es posible almacenar todas las salidas del circuito en el chip, pero la salida del circuito se puede comprimir para formar una firma que luego se comparará con la firma dorada (de la buena circuito) para detectar fallas. Dado que esta compresión tiene pérdidas, siempre existe la posibilidad de que una salida defectuosa también genere la misma firma que la firma dorada y las fallas no se puedan detectar. Esta condición se denomina enmascaramiento de errores o creación de alias. BIST se logra con un registro de firma de entrada múltiple (MISR o MSR), que es un tipo de LFSR. Un LFSR estándar tiene una sola puerta XOR o XNOR, donde la entrada de la puerta está conectada a varios "taps" y la salida está conectada a la entrada del primer flip-flop. Un MISR tiene la misma estructura, pero la entrada a cada flip-flop se alimenta a través de una puerta XOR/XNOR. Por ejemplo, un MISR de 4 bits tiene una salida paralela de 4 bits y una entrada paralela de 4 bits. La entrada del primer flip-flop es XOR/XNORd con bit cero de entrada en paralelo y los 'taps'. Cualquier otra entrada de flip-flop es XOR/XNORd con la salida de flip-flop anterior y el bit de entrada en paralelo correspondiente. En consecuencia, el siguiente estado del MISR depende de los últimos estados opuestos al estado actual. Por lo tanto, un MISR siempre generará la misma firma dorada dado que la secuencia de entrada es siempre la misma. Las aplicaciones recientes proponen flip-flops de configuración y reinicio como "toques" de la LFSR. Esto permite que el sistema BIST optimice el almacenamiento, ya que los flip-flops set-reset pueden guardar la semilla inicial para generar todo el flujo de bits del LFSR. Sin embargo, esto requiere cambios en la arquitectura de BIST, es una opción para aplicaciones específicas.

Usos en radiodifusión y comunicaciones digitales

Revoltoso

Para evitar que secuencias repetitivas breves (p. ej., series de 0 o 1) formen líneas espectrales que puedan complicar el seguimiento de símbolos en el receptor o interfiere con otras transmisiones, la secuencia de bits de datos se combina con la salida de un registro de retroalimentación lineal antes de la modulación y la transmisión. Esta codificación se elimina en el receptor después de la demodulación. Cuando el LFSR se ejecuta a la misma tasa de bits que el flujo de símbolos transmitido, esta técnica se denomina codificación. Cuando el LFSR se ejecuta considerablemente más rápido que el flujo de símbolos, la secuencia de bits generada por el LFSR se denomina código de chip. El código de chip se combina con los datos de forma exclusiva o antes de la transmisión mediante modulación por desplazamiento de fase binaria o un método de modulación similar. La señal resultante tiene un ancho de banda mayor que los datos y, por lo tanto, este es un método de comunicación de espectro ensanchado. Cuando se usa solo para la propiedad de espectro ensanchado, esta técnica se denomina espectro ensanchado de secuencia directa; cuando se utiliza para distinguir varias señales transmitidas en el mismo canal al mismo tiempo y frecuencia, se denomina acceso múltiple por división de código.

Ninguno de los esquemas debe confundirse con el cifrado o cifrado; la codificación y la difusión con LFSR no protegen la información de las escuchas. En cambio, se utilizan para producir flujos equivalentes que poseen propiedades de ingeniería convenientes para permitir una modulación y demodulación robusta y eficiente.

Sistemas de transmisión digital que utilizan registros de retroalimentación lineal:

• ATSC Estándares (sistema de transmisión digital – Norteamérica)
• DAB (Digital Audio Broadcasting system – for radio)
• DVB-T (sistema de transmisión digital de televisión – Europa, Australia, partes de Asia)
• NICAM (sistema de audio digital para televisión)

Otros sistemas de comunicaciones digitales que utilizan LFSR:

• INTELSAT business service (IBS)
• Tasa de datos intermedia (IDR)
• HDMI 2.0
• SDI (transmisión digital en serie)
• Transferencia de datos sobre PSTN (según las recomendaciones de la serie V de la UIT-T)
• CDMA (Code Division Multiple Access) telefonía celular
• 100BASE-T2 "fast" Ethernet scrambles bits utilizando un LFSR
• 1000BASE-T Ethernet, la forma más común de Gigabit Ethernet, scrambles bits utilizando un LFSR
• PCI Express
• SATA
• SCSI en serie (SAS/SPL)
• USB 3.0
• IEEE 802.11a revuelva bits usando un LFSR
• Bluetooth Low Energy Link Layer está haciendo uso de LFSR (referido como blanqueamiento)
• Sistemas de navegación por satélite como GPS y GLONASS. Todos los sistemas actuales utilizan salidas LFSR para generar algunos o todos sus códigos de rango (como el código de bloqueo para CDMA o DSSS) o para modular el transportista sin datos (como código de rango GPS L2 CL). GLONASS también utiliza el acceso multidivisión de frecuencia combinado con DSSS.

Otros usos

Los LFSR también se utilizan en sistemas de interferencia de radio para generar ruido pseudoaleatorio para elevar el ruido de fondo de un sistema de comunicación de destino.

La señal de tiempo alemana DCF77, además de la modulación de amplitud, emplea modulación por cambio de fase impulsada por un LFSR de 9 etapas para aumentar la precisión del tiempo recibido y la solidez del flujo de datos en presencia de ruido.