Registro de desplazamiento con retroalimentación lineal

En informática , 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 la función exclusiva-o (XOR). Por lo tanto, un LFSR suele ser un registro de desplazamiento cuyo bit de entrada está controlado por la función XOR de algunos bits del valor total del registro de desplazamiento.

El valor inicial del LFSR se denomina semilla y, como el funcionamiento del registro es determinista, el flujo de valores producido por el registro está completamente determinado por su estado actual (o anterior). Asimismo, como el registro tiene un número finito de estados posibles, eventualmente debe ingresar en un ciclo repetitivo. Sin embargo, un LFSR con una función de retroalimentación bien elegida puede producir una secuencia de bits que parezca aleatoria y tenga un ciclo muy largo .

Las aplicaciones de los LFSR incluyen la generación de números pseudoaleatorios , secuencias pseudorruido , contadores digitales rápidos y secuencias de blanqueamiento . Las implementaciones de LFSR tanto en hardware como en software son comunes.

Las matemáticas de una verificación de redundancia cíclica , que se utiliza para proporcionar una verificación rápida de 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 un objeto para estudiar e implementar. Se pueden 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 LFSR Fibonacci de 16 bits . Los números de retroalimentación que se muestran corresponden a un polinomio primitivo en la tabla, por lo que el registro recorre el número máximo de 65535 estados, excluyendo el estado de todos ceros. El estado que se muestra, 0xACE1 ( hexadecimal ), será seguido por 0x5670.

Un registro de desplazamiento de retroalimentación lineal de Fibonacci de 31 bits con tomas en las posiciones 28 y 31, lo que le otorga un ciclo y período máximos a esta velocidad de casi 6,7 años.

Las posiciones de los bits que afectan al siguiente estado se denominan tomas . En el diagrama, las tomas son [16,14,13,11]. El bit más a la derecha del LFSR se denomina bit de salida, que siempre es también una toma. Para obtener el siguiente estado, los bits de la toma se combinan secuencialmente mediante XOR; luego, todos los bits se desplazan un lugar hacia la derecha, y se descarta el bit más a la derecha. El resultado de combinar los bits de la toma se devuelve al bit más a la izquierda, que ahora está vacío. Para obtener el flujo de salida pseudoaleatorio, lea el bit más a la derecha después de cada transición de estado.

Un LFSR de longitud máxima produce una secuencia m (es decir, recorre todos los 2 ^m − 1 estados posibles dentro del registro de desplazamiento, excepto el estado donde todos los bits son cero), a menos que contenga todos ceros, en cuyo caso nunca cambiará.
Como alternativa a la retroalimentación basada en XOR en un LFSR, también se puede utilizar XNOR . ^[2] Esta función es un mapa afín , no estrictamente un mapa lineal , pero da como resultado un contador polinomial equivalente cuyo estado es el complemento del estado de un LFSR. Un estado con todos unos es ilegal cuando se utiliza una retroalimentación XNOR, de la misma manera que un estado con todos ceros es ilegal cuando se utiliza XOR. Este estado se considera ilegal porque el contador permanecería "bloqueado" en este estado. Este método puede ser ventajoso en LFSR de hardware que utilizan flip-flops que comienzan en un estado cero, ya que no comienzan en un estado de bloqueo, lo que significa que el registro no necesita ser inicializado para comenzar la operación.

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 tomas para la retroalimentación en un LFSR se puede expresar en aritmética de campo finito como un polinomio módulo 2. Esto significa que los coeficientes del polinomio deben ser 1 o 0. Esto se denomina polinomio de retroalimentación o polinomio característico recíproco. Por ejemplo, si las tomas están en los bits 16, 14, 13 y 11 (como se muestra), el polinomio de retroalimentación es

x^{16}+x^{14}+x^{13}+x^{11}+1.

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

La 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). ^[3]^[4] Esto significa que las siguientes condiciones son necesarias (pero no suficientes):

El número de toques es par .
El conjunto de tomas es coprimo por conjunto ; es decir, no debe haber ningún divisor distinto de 1 común a todas las tomas.

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

Puede haber más de una secuencia de derivaciones de longitud máxima para una longitud de LFSR dada. Además, una vez que se ha encontrado una secuencia de derivaciones de longitud máxima, otra sigue automáticamente. Si la secuencia de derivaciones en un LFSR de n bits es [ n , A , B , C , 0] , donde el 0 corresponde al término x ⁰ = 1, entonces la secuencia "espejo" correspondiente es [ n , n − C , n − B , n − A , 0] . Por lo tanto, la secuencia de derivaciones [32, 22, 2, 1, 0] tiene como contraparte [32, 31, 30, 10, 0] . Ambas dan una secuencia de longitud máxima.

A continuación se muestra un ejemplo en C :

#include <stdint.h> unsigned lfsr_fib ( void ) { uint16_t start_state = 0xACE1u ; /* Cualquier estado de inicio distinto de cero funcionará. */ uint16_t lfsr = start_state ; uint16_t bit ; /* Debe ser de 16 bits para permitir el bit<<15 más adelante en el código */ unsigned period = 0 ;                   hacer { /* toques: 16 14 13 11; polinomio 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 ) | ( bit << 15 ); ++ período ; } while ( lfsr != estado_inicial );                                     periodo de retorno ; }

Si está disponible una operación de paridad rápida o de recuento de bits , 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 equivalentemente
bit = popcnt(lfsr & 0x002Du) /* & 1u */;(Esto & 1uconvierte el popcnt en una verdadera función de paridad, pero el bitshift posterior bit << 15hace que los bits superiores sean irrelevantes).

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

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

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

Ejemplo en Python

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

estado_inicial  =  1  <<  15  |  1 lfsr  =  estado_inicial periodo  =  0mientras sea  verdadero :  # tomas: 16 15 13 4; polinomio de retroalimentación: x^16 + x^15 + x^13 + x^4 + 1  bit  =  ( lfsr  ^  ( lfsr  >>  1 )  ^  ( lfsr  >>  3 )  ^  ( lfsr  >>  12 ))  &  1  lfsr  =  ( lfsr  >>  1 )  |  ( bit  <<  15 )  periodo  +=  1  si  lfsr  ==  estado_inicial :  print ( periodo )  break

Donde se utiliza un registro de 16 bits y la toma xor en el cuarto, decimotercero, decimoquinto y decimosexto bit establece una longitud de secuencia máxima.

LFSR de Galois

Un LFSR en configuración Galois, que recibe su nombre del matemático francés Évariste Galois , también conocido como modular , XOR interno o LFSR uno a muchos , es una estructura alternativa que puede generar el mismo flujo de salida que un LFSR convencional (pero desplazado en el tiempo). ^[5] En la configuración Galois, cuando el sistema está sincronizado, los bits que no son tomas se desplazan una posición a la derecha sin cambios. Las tomas, por otro lado, se combinan con el bit de salida antes de almacenarse 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 del registro se desplazan a 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 las tomas 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 las tomas es el equivalente (ver arriba) del orden del LFSR convencional; de lo contrario, el flujo estará en sentido 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 un desfase temporal entre los flujos, por lo que se necesitará un punto de inicio diferente para obtener la misma salida en cada ciclo.

Los LFSR de Galois no concatenan cada toma para producir la nueva entrada (la operación XOR se realiza dentro del LFSR y no se ejecutan puertas XOR en serie, por lo tanto, los tiempos de propagación se reducen a los de una XOR en lugar de una cadena completa), por lo que es posible calcular cada toma en paralelo, lo que aumenta la velocidad de ejecución.
En una implementación de software de un LFSR, la forma de Galois es más eficiente, ya que las operaciones XOR se pueden implementar palabra por palabra: solo se debe examinar individualmente el bit de salida.

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

#include <stdint.h> unsigned lfsr_galois ( void ) { uint16_t start_state = 0xACE1u ; /* Cualquier estado de inicio distinto de cero funcionará. */ uint16_t lfsr = start_state ; unsigned period = 0 ;                do { #ifndef LEFT unsigned lsb = lfsr & 1u ; /* Obtener LSB (es decir, el bit de salida). */ lfsr >>= 1 ; /* Registro de desplazamiento */ if ( lsb ) /* Si el bit de salida es 1, */ lfsr ^= 0xB400u ; /* aplicar máscara de alternancia. */ #else unsigned msb = ( int16_t ) lfsr < 0 ; /* Obtener MSB (es decir, el bit de salida). */ lfsr <<= 1 ; /* Registro de desplazamiento */ if ( msb ) /* Si el bit de salida es 1, */ lfsr ^= 0x002Du ; /* aplicar máscara de alternancia. */ #endif ++ period ; } while ( lfsr != start_state );                                             periodo de retorno ; }

La rama también se puede escribir como , lo 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 incluso mejor, ya que el bit más significativo es el acarreo de la adición de a sí mismo.if (lsb) lfsr ^= 0xB400u;lfsr ^= (-lsb) & 0xB400u;lfsr

Cálculo paralelo de Galois LFSR

Los bits de estado y resultantes también se pueden combinar y calcular en paralelo. La siguiente función calcula los siguientes 64 bits utilizando el polinomio de 63 bits x⁶³ + x⁶² + 1:

#include <stdint.h> uint64_t prsg63 ( uint64_t lfsr ) { lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; devolver lfsr ; }

LFSR de Galois 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 toma específico. Nótese 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 toma) o 1 (hay retroalimentación). Dada una configuración de toma apropiada, tales LFSR se pueden usar para generar campos de Galois para valores primos arbitrarios de q .

LFSR de Xorshift

Como lo demostró George Marsaglia ^[6] y lo analizó más a fondo Richard P. Brent ^[7] , los registros de desplazamiento con retroalimentación lineal se pueden implementar utilizando operaciones XOR y Shift. Este enfoque se presta a una ejecución rápida en software porque estas operaciones suelen asignarse de manera eficiente a las instrucciones de los procesadores modernos.

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

#include <stdint.h> unsigned lfsr_xorshift ( void ) { uint16_t start_state = 0xACE1u ; /* Cualquier estado de inicio distinto de cero funcionará. */ uint16_t lfsr = start_state ; unsigned period = 0 ;                hacer { // 7,9,13 triplete de http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html lfsr ^= lfsr >> 7 ; lfsr ^= lfsr << 9 ; lfsr ^= lfsr >> 13 ; ++ período ; } mientras ( lfsr != estado_inicial );                        periodo de retorno ; }

Formas matriciales

Los LFSR binarios de las configuraciones de Fibonacci y Galois se pueden expresar como funciones lineales utilizando matrices en (ver GF(2) ). ^[9] Utilizando la matriz compañera del polinomio característico del LFSR y denotando la semilla como un vector columna , el estado del registro en la configuración de Fibonacci después de los pasos se da por $\mathbb {F}_{2}$ $(a_{0},a_{1},\puntos ,a_{n-1})^{\mathrm {T} }$ ${\estilo de visualización k}$

{\begin{pmatrix}a_{k}\\a_{k+1}\\a_{k+2}\\\vpuntos \\a_{k+n-1}\end{pmatrix}}={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}{\begin{pmatrix}a_{k-1}\\a_{k}\\a_{k+1}\\\vdots \\a_{k+n-2}\end{pmatrix}}={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}^{k}{\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\\\vdots \\a_{n-1}\end{pmatrix}}

La matriz para la forma de Galois correspondiente es:

{\begin{pmatrix}c_{0}&1&0&\cdots &0\\c_{1}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{n-2}&0&\cdots &0&1\\c_{n-1}&0&\cdots &\cdots &0\end{pmatrix}}

Para una inicialización adecuada,

a'_{i}=\sum _{i=0}^{j}a_{ij}c_{nj},\ 0\leq i<n

El coeficiente superior del vector columna:

{\begin{pmatrix}c_{0}&1&0&\cdots &0\\c_{1}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{n-2}&0&\cdots &0&1\\c_{n-1}&0&\cdots &\cdots &0\end{pmatrix}}^{k}{\begin{pmatrix}a'_{0}\\a'_{1}\\a'_{2}\\\vdots \\a'_{n-1}\end{pmatrix}}

da el término $a k$ 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 LFSR de longitud máxima fue desarrollado por Solomon W. Golomb en su libro de 1967. ^{[10] El número de}polinomios primitivos diferentes crece exponencialmente con la longitud del registro de desplazamiento y se puede calcular exactamente utilizando la función totient de Euler ^[11] (secuencia A011260 en la OEIS ).

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

Propiedades del flujo de salida

Los unos y los ceros se dan en "ejecuciones". El flujo de salida 1110010, por ejemplo, consta de cuatro ejecuciones de longitudes 3, 2, 1, 1, en orden. En un período de un LFSR máximo, se dan 2 ^{n −1} ejecuciones (en el ejemplo anterior, el LFSR de 3 bits tiene 4 ejecuciones). Exactamente la mitad de estas ejecuciones tienen una longitud de un bit, una cuarta parte tienen una longitud de dos bits, hasta una única ejecución de ceros de n − 1 bits de longitud y una única ejecución de unos de n bits de longitud. Esta distribución casi iguala el valor de la 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 ^{[ vague ]} .
Los flujos de salida de LFSR son deterministas . Si se conocen el estado actual y las posiciones de las puertas XOR en el LFSR, se puede predecir el siguiente estado. ^[12] Esto no es posible con eventos verdaderamente aleatorios. Con LFSR de longitud máxima, es mucho más fácil calcular el siguiente estado, ya que solo hay un número fácilmente limitado de ellos para cada longitud.
El flujo de salida es reversible; un LFSR con tomas reflejadas recorrerá la secuencia de salida en orden inverso.
El valor que consta de todos ceros no puede aparecer. Por lo tanto, no se puede utilizar un LFSR de longitud n para generar los 2 valores ⁿ .

Aplicaciones

Los LFSR se pueden implementar en hardware, lo que 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 lo utilice como divisor de reloj o como contador cuando una secuencia no binaria es aceptable, como suele ser el caso donde las ubicaciones de índice o encuadre de la computadora deben ser legibles por máquina. ^[12]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 garantizar que el LFSR nunca entre en un estado de bloqueo (todos ceros para un LFSR basado en XOR y todos unos para un LFSR basado en XNOR), por ejemplo, preestableciéndolo en el inicio en cualquier otro estado en la secuencia. Es posible contar hacia arriba y hacia abajo con un LFSR. Los LFSR también se han utilizado como un contador de programa para CPU, esto requiere que el programa en sí esté "mezclado" y se hace para ahorrar en puertas cuando son una prima (usando menos puertas que un sumador) y para la velocidad (ya que un LFSR no requiere una cadena de acarreo larga).

La tabla de polinomios primitivos muestra cómo se pueden organizar las secuencias de polinomios de fase lineal en forma de Fibonacci o Galois para obtener períodos máximos. Se puede obtener cualquier otro período agregando a una secuencia de polinomios de fase lineal que tenga un período más largo alguna lógica que acorte la secuencia saltando 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 , períodos largos y flujos de salida distribuidos de manera muy uniforme . Sin embargo, un LFSR es un sistema lineal, lo que conduce a un criptoanálisis bastante fácil . Por ejemplo, dado un tramo de texto simple conocido y el texto cifrado correspondiente , un atacante puede interceptar y recuperar un tramo del flujo de salida del 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 el receptor previsto utilizando el algoritmo Berlekamp-Massey . Luego, este LFSR puede alimentarse con el tramo interceptado del flujo de salida para recuperar el texto simple 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 LFSR (ver también: generador de contracción ); o utilizando un algoritmo evolutivo para introducir no linealidad. ^[13]
Sincronización irregular del LFSR, como en el generador de pasos alternos .

Entre los cifrados de flujo basados en LFSR más importantes se encuentran A5/1 y A5/2 , utilizados en teléfonos móviles GSM , E0 , utilizado en Bluetooth , y el generador de encogimiento . El cifrado A5/2 ha sido descifrado y tanto A5/1 como E0 presentan graves debilidades. ^[14]^[15]

El registro de desplazamiento de retroalimentación lineal tiene una fuerte relación con los generadores congruenciales lineales . ^[16]

Usos en pruebas de circuitos

Los LFSR se utilizan en pruebas de circuitos para la generación de 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 utilizan comúnmente como generadores de patrones para pruebas exhaustivas, ya que cubren todas las entradas posibles para un circuito de n entradas. 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 autoprueba incorporada (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 (del circuito en buen estado) 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 aliasing. BIST se logra con un registro de firma de múltiples entradas (MISR o MSR), que es un tipo de LFSR. Un LFSR estándar tiene una sola compuerta XOR o XNOR, donde la entrada de la compuerta está conectada a varias "tomas" 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 compuerta 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 el bit de entrada paralelo cero y los "taps". Cada entrada de cada flip-flop es XOR/XNORd con la salida del flip-flop anterior y el bit de entrada paralelo correspondiente. En consecuencia, el siguiente estado del MISR depende de los últimos estados en lugar de solo del estado actual. Por lo tanto, un MISR siempre generará la misma firma dorada dado que la secuencia de entrada es la misma cada vez. Aplicaciones recientes ^[17] proponen flip-flops de restablecimiento de configuración como "taps" del LFSR. Esto permite que el sistema BIST optimice el almacenamiento, ya que los flip-flops de restablecimiento de configuración pueden guardar la semilla inicial para generar todo el flujo de bits del LFSR. Sin embargo, esto requiere cambios en la arquitectura de BIST y es una opción para aplicaciones específicas.

Usos en la radiodifusión y las comunicaciones digitales

Pelea

Para evitar que secuencias cortas repetidas (por ejemplo, series de 0 o 1) formen líneas espectrales que puedan complicar el seguimiento de símbolos en el receptor o interferir 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 velocidad 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 chipping . El código de chipping se combina con los datos utilizando modulación exclusiva o antes de transmitir utilizando 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 utiliza 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 estos esquemas debe confundirse con el cifrado o la codificación ; la codificación y la propagación con LFSR no protegen la información de las escuchas clandestinas. En cambio, se utilizan para producir flujos equivalentes que poseen propiedades de ingeniería convenientes para permitir una modulación y demodulación robustas y eficientes.

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

Normas ATSC (sistema de transmisión de televisión digital – América del Norte)
DAB ( Sistema de transmisión de audio digital para radio)
DVB-T (sistema de transmisión de televisión digital: Europa, Australia y partes de Asia)
NICAM (sistema de audio digital para televisión)

Otros sistemas de comunicaciones digitales que utilizan LFSR:

Servicio comercial Intelsat (IBS)
Velocidad de datos intermedia (IDR)
HDMI 2.0
SDI (Transmisión de interfaz digital en serie)
Transferencia de datos a través de PSTN (según las recomendaciones de la serie V de la UIT-T )
Telefonía celular CDMA (Acceso Múltiple por División de Código)
La Ethernet "rápida" 100BASE-T2 codifica bits mediante un LFSR
Ethernet 1000BASE-T , la forma más común de Gigabit Ethernet, codifica bits mediante un LFSR
PCI Express
SATA ^[18]
SCSI conectado en serie (SAS/SPL)
USB 3.0
IEEE 802.11a codifica bits utilizando un LFSR
La capa de enlace de Bluetooth de bajo consumo utiliza LFSR (conocido 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 medición de distancia (como el código de chip para CDMA o DSSS) o para modular la portadora sin datos (como el código de medición de distancia GPS L2 CL). GLONASS también utiliza acceso múltiple por división de frecuencia combinado con DSSS.

Otros usos

Los LFSR también se utilizan en sistemas de interferencia de radio para generar ruido pseudoaleatorio que eleva el nivel de ruido de un sistema de comunicación objetivo.

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

Véase también

Molinillo
Tornado de Mersenne
Secuencia de longitud máxima
Registro de desplazamiento de retroalimentación analógica
NLFSR , registro de desplazamiento de retroalimentación no lineal
Contador de anillos
Secuencia binaria pseudoaleatoria
Secuencia de oro
Secuencia del JPL
Secuencia de Kasami
Algoritmo de Berlekamp-Massey

Referencias

^ Geremia, Patrick. "Cálculo de comprobación de redundancia cíclica: una implementación con el TMS320C54x" (PDF) . Texas Instruments. pág. 6 . Consultado el 16 de octubre de 2016 .
^ Registros de desplazamiento con retroalimentación lineal en dispositivos Virtex
^ Gentil, James E. (2003). Generación de números aleatorios y métodos de Monte Carlo (2ª ed.). Nueva York: Springer. pag. 38.ISBN 0-387-00178-6.OCLC 51534945 .
^ Tausworthe, Robert C. (abril de 1965). "Números aleatorios generados por recurrencia lineal módulo dos" (PDF) . Matemáticas de la computación . 19 (90): 201–209. doi :10.1090/S0025-5718-1965-0184406-1. S2CID 120804149.
^ Press, William; Teukolsky, Saul; Vetterling, William; Flannery, Brian (2007). Recetas numéricas: el arte de la computación científica, tercera edición . Cambridge University Press . pág. 386. ISBN. 978-0-521-88407-5.
^ Marsaglia, George (julio de 2003). "Generadores aleatorios Xorshift". Revista de software estadístico . 8 (14). doi : 10.18637/jss.v008.i14 .
^ Brent, Richard P. (agosto de 2004). "Nota sobre los generadores de números aleatorios Xorshift de Marsaglia". Journal of Statistical Software . 11 (5). doi : 10.18637/jss.v011.i05 . hdl : 1885/34049 .
^ Metcalf, John (22 de julio de 2017). «Números pseudoaleatorios de 16 bits Xorshift en ensamblador Z80». Programación retro . Consultado el 5 de enero de 2022 .
^ Klein, A. (2013). "Registros de desplazamiento con retroalimentación lineal". Stream Ciphers . Londres: Springer. págs. 17-18. doi :10.1007/978-1-4471-5079-4_2. ISBN 978-1-4471-5079-4.
^ Golomb, Solomon W. (1967). Secuencias de registros de desplazamiento . Laguna Hills, California: Aegean Park Press. ISBN 978-0894120480.
^ Weisstein, Eric W. "Polinomio primitivo". mathworld.wolfram.com . Consultado el 27 de abril de 2021 .
^ ab http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf ^{[ URL básica PDF ]}
^ A. Poorghanad, A. Sadr, A. Kashanipour "Generación de números pseudoaleatorios de alta calidad mediante métodos evolutivos", Congreso IEEE sobre inteligencia computacional y seguridad, vol. 9, págs. 331-335, mayo de 2008 [1]
^ Barkam, Elad; Biham, Eli; Keller, Nathan (2008), "Criptoanálisis instantáneo de texto cifrado únicamente de comunicaciones cifradas GSM" (PDF) , Journal of Cryptology , 21 (3): 392–429, doi :10.1007/s00145-007-9001-y, S2CID 459117, archivado desde el original (PDF) el 25 de enero de 2020 , consultado el 15 de septiembre de 2019
^ Lu, Yi; Willi Meier; Serge Vaudenay (2005). "El ataque de correlación condicional: un ataque práctico al cifrado Bluetooth". Avances en criptología – CRYPTO 2005. Apuntes de clase en informática. Vol. 3621. Santa Bárbara, California, EE. UU., págs. 97–117. CiteSeerX 10.1.1.323.9416 . doi :10.1007/11535218_7. ISBN. 978-3-540-28114-6. {{cite book}}: |journal=ignorado ( ayuda )CS1 maint: location missing publisher (link)
^ RFC 4086 sección 6.1.3 "Secuencias pseudoaleatorias tradicionales"
^ Martínez LH, Khursheed S, Reddy SM. Generación de LFSR para una alta cobertura de pruebas y una baja sobrecarga de hardware. IET Computers & Digital Techniques. 21 de agosto de 2019. Repositorio UoL
^ Sección 9.5 de la Especificación SATA, revisión 2.6
^ Hetzel, P. (16 de marzo de 1988). Time spread via the LF receiver DCF77 using a pseudo-random phase-shift keying of the carrier (PDF) (Difusión horaria mediante el transmisor LF DCF77 utilizando una modulación por desplazamiento de fase pseudoaleatoria de la portadora) (PDF) . 2nd European Frequency and Time Forum (Segundo Foro Europeo de Frecuencia y Tiempo). Neuchâtel. pp. 351–364 . Consultado el 11 de octubre de 2011 .

Lectura adicional

http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
https://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf
http://users.ece.cmu.edu/~koopman/lfsr/index.html — Tablas de polinomios de retroalimentación de longitud máxima para 2-64 bits.
https://github.com/hayguen/mlpolygen — Código para generar polinomios de retroalimentación de longitud máxima

Enlaces externos

Registros de desplazamiento de retroalimentación lineal en Wayback Machine (archivado el 1 de octubre de 2018): teoría e implementación de LFSR, secuencias de longitud máxima y tablas de retroalimentación integrales para longitudes de 7 a 16 777 215 (de 3 a 24 etapas), y tablas parciales para longitudes de hasta 4 294 967 295 (de 25 a 32 etapas).
Recomendación O.151 de la Unión Internacional de Telecomunicaciones (agosto de 1992)
Tabla LFSR de longitud máxima con longitud de 2 a 67.
Rutina de generación de números pseudoaleatorios para el microprocesador MAX765x
http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html
http://www.quadibloc.com/crypto/co040801.htm
Explicación sencilla de los LFSR para ingenieros
Términos de retroalimentación
Teoría general del LFSR
Una implementación de LFSR en VHDL.
Codificación VHDL simple para LFSR de Galois y Fibonacci.
mlpolygen: un generador de polinomios de longitud máxima

LFSR y generación intrínseca de aleatoriedad: notas de NKS