¿Cómo se usan los LFSR en aplicaciones reales como PRNG?

Estoy programando un LFSR (Registro de desplazamiento de retroalimentación lineal) en software con fines de aprendizaje, y he encontrado algunas limitaciones en su uso como generador de números pseudoaleatorios (PRNG).

• Si la semilla tiene pocos bits '1' y se usan pocos toques, se requiere un gran "tiempo de inicio" para producir una salida aparentemente aleatoria, con una distribución casi igual entre las corridas '1' y '0' o '0' cortas. Supongo que con más toques, tal inicio sería mucho más rápido, pero todas las tablas precalculadas que encuentro dan dos o cuatro toques.
• Los números secuenciales están altamente correlacionados, lo cual es de esperar, dado que si el bit de salida es 0, el siguiente número será la mitad del anterior. Para un LFSR de 15 bits con toques [15, 14], trazar un par de números secuenciales como puntos en un plano da lo siguiente. Un PRNG ideal debería extender estos puntos por todo el lugar.

Sé que los LFSR se usan como contador rápido de hardware, pero también he visto que se usa como un PRNG para crear ruido blanco. ¿Cómo se usa en aplicaciones del mundo real con tan mala calidad?

Una fuente excelente para todo lo relacionado con PRNG son las "secuencias de registro de desplazamiento" de Solomon Golomb. Discute las diversas clases y técnicas.

Comenzar reiniciando todos los registros es unidireccional. O una carga paralela de una semilla es otra. Pero recuerde que una picadura de todos los ceros es un estado válido.

Elegir los códigos correctos es importante ya que no todas las configuraciones de retroalimentación en un registro de desplazamiento aseguran que obtenga una secuencia PRNG máxima.

La forma en que opera un PRNG afecta su rendimiento.

Para un registro de 15 bits y buscar los códigos, [15,4] es máximo como [15,1] pero [15,14] no está en la lista. -> Fuente- "Sistemas y aplicaciones de amplio espectro" - Robert Dixon 3rd Ed. Pág. 94. Este libro es una muy buena referencia sobre la implementación.

En general, los LFSR hacen PRNG deficientes y la práctica general es usar solo los bits más bajos. Alternativamente, puede generar dos PRNG de diferentes longitudes y códigos y xor los bits inferiores para generar el nuevo código. Probablemente se debe usar menos de la mitad de la longitud de bits. Entonces, un registro de longitud de 30 y 31 bits y XOR los 15 LSB.

NIST tiene un excelente código de prueba aquí . Entonces sí, apesta, para PRNG's.

Los números secuenciales están altamente correlacionados, lo cual es de esperar, dado que si el bit de salida es 0, el siguiente número será la mitad del anterior. Para un LFSR de 15 bits con toques [15, 14], trazar un par de números secuenciales como puntos en un plano da lo siguiente. Un PRNG ideal debería extender estos puntos por todo el lugar.

Si desea generar números aleatorios con un LFSR de 15 bits, no extraiga un nuevo número aleatorio en cada ciclo de reloj. Como usted ha dicho, ya que sólo va a añadir un nuevo bit en el registro de cada ciclo de reloj, el valor en el ciclo Ny N+1será muy fuertemente correlacionados. Si desea generar valores aleatorios (suponiendo que tenga toques adecuados), entonces solo necesita extraer un nuevo valor cada 15 relojes.

Un LFSR solo le garantiza un bit aleatorio cada ciclo, no 15 bits aleatorios.

Un ejemplo del mundo real se puede encontrar en el Manual de referencia de la familia de microprocesadores RISC MPC7450. El 7450 utilizó un pRNG para el reemplazo de L2 y L3 que se compone de 16 pestillos que tienen tres registros de desplazamiento simples con los bits 0 a 4, los bits 5 a 9 y los bits 10 a 15. El bit 0 proviene de un XOR de los bits 4 y 15, el bit 5 proviene de un XOR de los bits 4 y 9, y el bit 10 proviene de un XOR de los bits 6 y 15. La forma de reemplazo en los cachés de 8 vías se indica mediante los bits 4, 9 y 15 para L2 y los bits 0 , 5 y 10 para L3. Los bits se cambiaron cada ciclo, pero obviamente los reemplazos de caché no ocurrían con tanta frecuencia. (También se proporcionó un mecanismo alternativo de reemplazo basado en el contador).

Esto fue reconocido como potencialmente problemático:

Debido a la latencia de la búsqueda de caché L2, hay 3 ciclos de reloj entre una falta de lectura y la asignación de la línea de reemplazo. Por lo tanto, sería posible que se pueda elegir la misma forma para reemplazar dos, o incluso tres errores de lectura consecutivos con el algoritmo como se describió anteriormente. Para evitar esto, el algoritmo real compara una línea de reemplazo seleccionada con las tres líneas de reemplazo anteriores. Si la línea seleccionada coincide con una de las tres anteriores, se agrega automáticamente un valor de uno, dos o tres al valor que selecciona la forma de reemplazo.