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

Una fuente excelente para todas las cosas PRNG es "Secuencias de registro de desplazamiento" por Solomon Golomb. Discute las diferentes clases y técnicas.

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

La elección de los códigos correctos es importante ya que no todos los ajustes de retroalimentación en un registro de desplazamiento garantizan que se obtenga una secuencia máxima de PRNG.

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 es [15,1] pero [15,14] no está listado. - > Fuente: "Sistemas y aplicaciones de espectro ensanchado" - Robert Dixon 3ª ed. Pg 94. Este libro es una muy buena referencia sobre la implementación.

En general, los LFSR hacen que los PRNG sean pobres 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 xo los bits inferiores para generar el nuevo código. Probablemente debe usarse menos de 1/2 de longitud de bit. Por lo tanto, un registro de 30 y 31 bits de longitud y XOR de los 15 LSB's.

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

  

Los números secuenciales están altamente correlacionados, lo que 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 pulsaciones [15, 14], trazar un par de números secuenciales como puntos en un plano da lo siguiente. Un PRNG ideal debería difundir 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 ha dicho, ya que solo está agregando un nuevo bit al registro en cada ciclo de reloj, el valor en el ciclo N y N+1 estará muy fuertemente relacionado. Si desea generar valores aleatorios (suponiendo que tiene los toques apropiados), entonces solo necesita extraer un nuevo valor cada 15 relojes.

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

Puede encontrar un ejemplo del mundo real 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 está compuesto por 16 latches que tienen tres registros de desplazamiento simple 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. El modo de reemplazo en los cachés de 8 vías se indica mediante los bits 4, 9 y 15 para L2 y para los bits 0 , 5 y 10 para L3. Los bits se cambiaron en cada ciclo, pero obviamente los reemplazos de caché no ocurrieron tan frecuentemente. (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 fallos de lectura consecutivos con el algoritmo descrito 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.