Este dilema se puede abordar de diferentes maneras, sin embargo te mostramos la resolución más completa para nosotros.
Solución:
Como estaba buscando una implementación de LFSR en Python, me topé con este tema. Sin embargo, encontré que lo siguiente era un poco más preciso según mis necesidades:
def lfsr(seed, mask):
result = seed
nbits = mask.bit_length()-1
while True:
result = (result << 1)
xor = result >> nbits
if xor != 0:
result ^= mask
yield xor, result
El generador LFSR anterior se basa en GF (2k) cálculo de módulo (GF = campo de Galois). Habiendo completado un curso de Álgebra, voy a explicar esto de forma matemática.
Comencemos tomando, por ejemplo, GF (24), que equivale a a0, a1, …, a4 ∈ Z2 (aclarar, Znorte = 0,1, …, n-1 y por lo tanto Z2 = 0,1, es decir, un bit). Esto significa que este es el conjunto de todos los polinomios de cuarto grado con todos los factores presentes o no, pero sin múltiplos de estos factores (por ejemplo, no hay 2xk). X3, X4 + x3, 1 y x4 + x3 + x2 + x + 1 son todos ejemplos de miembros de este grupo.
Tomamos este módulo establecido como un polinomio de cuarto grado (es decir, P (x) ∈ GF (24)), por ejemplo, P (x) = x4+ x1+ x0. Esta operación de módulo en un grupo también se denota como GF (24) / P (x). Para su referencia, P (x) describe los ‘grifos’ dentro del LFSR.
También tomamos un polinomio aleatorio de grado 3 o menor (para que no se vea afectado por nuestro módulo, de lo contrario podríamos realizar la operación del módulo directamente sobre él), por ejemplo, A0(x) = x0. Ahora, cada A posteriorI(x) se calcula multiplicándolo por x: AI(x) = Ai-1(x) * x mod P (x).
Dado que estamos en un campo limitado, la operación del módulo puede tener un efecto, pero solo cuando la A resultanteI(x) tiene al menos un factor x4 (nuestro factor más alto en P (x)). Tenga en cuenta que, dado que estamos trabajando con números en Z2, realizar la operación del módulo en sí no es más que determinar si cadaI se convierte en 0 o 1 sumando los dos valores de P (x) y AI(x) juntos (es decir, 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0, o ‘xoring’ estos dos).
Cada polinomio se puede escribir como un conjunto de bits, por ejemplo x4+ x1+ x0 ~ 10011.0(x) puede verse como la semilla. La operación ‘veces x’ puede verse como una operación de desplazamiento a la izquierda. La operación de módulo puede verse como una operación de enmascaramiento de bits, siendo la máscara nuestra P (x).
Por lo tanto, el algoritmo descrito anteriormente genera (un flujo infinito de) patrones LFSR de cuatro bits válidos. Por ejemplo, para nuestro A definido0(X) (X0) y P (x) (X4+ x1+ x0), podemos definir los siguientes primeros resultados obtenidos en GF (24) (tenga en cuenta que A0 no se obtiene hasta el final de la primera ronda (los matemáticos generalmente comienzan a contar en ‘1’):
i Ai(x) 'x⁴' bit pattern
0 0x³ + 0x² + 0x¹ + 1x⁰ 0 0001 (not yielded)
1 0x³ + 0x² + 1x¹ + 0x⁰ 0 0010
2 0x³ + 1x² + 0x¹ + 0x⁰ 0 0100
3 1x³ + 0x² + 0x¹ + 0x⁰ 0 1000
4 0x³ + 0x² + 1x¹ + 1x⁰ 1 0011 (first time we 'overflow')
5 0x³ + 1x² + 1x¹ + 0x⁰ 0 0110
6 1x³ + 1x² + 0x¹ + 0x⁰ 0 1100
7 1x³ + 0x² + 1x¹ + 1x⁰ 1 1011
8 0x³ + 1x² + 0x¹ + 1x⁰ 1 0101
9 1x³ + 0x² + 1x¹ + 0x⁰ 0 1010
10 0x³ + 1x² + 1x¹ + 1x⁰ 1 0111
11 1x³ + 1x² + 1x¹ + 0x⁰ 0 1110
12 1x³ + 1x² + 1x¹ + 1x⁰ 1 1111
13 1x³ + 1x² + 0x¹ + 1x⁰ 1 1101
14 1x³ + 0x² + 0x¹ + 1x⁰ 1 1001
15 0x³ + 0x² + 0x¹ + 1x⁰ 1 0001 (same as i=0)
Tenga en cuenta que su máscara debe contener un ‘1’ en la cuarta posición para asegurarse de que su LFSR genere resultados de cuatro bits. También tenga en cuenta que un ‘1’ debe estar presente en la posición cero para asegurarse de que su flujo de bits no termine con un patrón de 0000 bits, o que el bit final no se use (si todos los bits se desplazan hacia la izquierda, lo haría también terminan con un cero en la posición 0 después de un turno).
No todos los P (x) son necesariamente generadores de GF (2k) (es decir, no todas las máscaras de k bits generan los 2k-1-1 números). Por ejemplo, x4 + x3 + x2 + x1 + x0 genera 3 grupos de 5 polinomios distintos cada uno, o “3 ciclos de período 5”: 0001,0010,0100,1000,1111; 0011,0110,1100,0111,1110; y 0101,1010,1011,1001,1101. Tenga en cuenta que 0000 nunca se puede generar y no puede generar ningún otro número.
Por lo general, la salida de un LFSR es el bit que se ‘desplaza’ hacia afuera, que es un ‘1’ si se realiza la operación de módulo y un ‘0’ cuando no lo está. LFSR con un período de 2k-1-1, también llamado pseudo-ruido o PN-LFSR, se adhiere a los postulados de aleatoriedad de Golomb, que dice tanto como que este bit de salida es “suficientemente” aleatorio.
Por lo tanto, las secuencias de estos bits tienen su uso en criptografía, por ejemplo, en los estándares de cifrado móvil A5 / 1 y A5 / 2, o en el estándar E0 Bluetooth. Sin embargo, no son tan seguros como uno quisiera: el algoritmo de Berlekamp-Massey se puede utilizar para aplicar ingeniería inversa al polinómico característico (el P (x)) del LFSR. Por lo tanto, los estándares de cifrado sólidos utilizan FSR no lineales o funciones no lineales similares. Un tema relacionado con esto son las S-Boxes utilizadas en AES.
Tenga en cuenta que he utilizado el int.bit_length() operación. Esto no se implementó hasta Python 2.7.
Si solo desea un patrón de bits finito, puede verificar si la semilla es igual al resultado y luego romper su ciclo.
Puede usar mi método LFSR en un bucle for (p. Ej. for xor, pattern in lfsr(0b001,0b10011)) o puede llamar repetidamente al .next() operación sobre el resultado del método, devolviendo un nuevo (xor, result)-par siempre.
De hecho, los algoritmos basados en LFSR son muy comunes. CRC en realidad se basa directamente en LFSR. Por supuesto, en las clases de ciencias de la computación la gente habla de polinomios cuando se habla de cómo se supone que el valor de entrada debe ser XORed con el valor acumulado, en ingeniería eléctrica hablamos de grifos. Son la misma terminología diferente.
CRC32 es muy común. Se utiliza para detectar errores en las tramas de Ethernet. Eso significa que cuando publiqué esta respuesta, mi PC usó un algoritmo basado en LFSR para generar un hash del paquete IP para que mi enrutador pueda verificar que lo que está transmitiendo no esté dañado.
Los archivos Zip y Gzip son otro ejemplo. Ambos usan CRC para la detección de errores. Zip usa CRC32 y Gzip usa tanto CRC16 como CRC32.
Los CRC son básicamente funciones hash. Y es lo suficientemente bueno para que Internet funcione. Lo que significa que los LFSR son funciones hash bastante buenas. No estoy seguro de saber esto, pero en general, las buenas funciones hash se consideran buenos generadores de números aleatorios. Pero lo que pasa con LFSR es que seleccionar los grifos correctos (polinomios) es muy importante para la calidad del hash / número aleatorio.
Su código es generalmente un código de juguete, ya que opera en un string de unos y ceros. En el mundo real, LFSR trabaja con bits en un byte. Cada byte que empuja a través del LFSR cambia el valor acumulado del registro. Ese valor es efectivamente una suma de comprobación de todos los bytes que ha introducido en el registro. Dos formas comunes de usar ese valor como un número aleatorio es usar un contador y empujar una secuencia de números a través del registro, transformando así la secuencia lineal 1,2,3,4 en una secuencia hash como 15306,22,5587, 994, o para retroalimentar el valor actual en el registro para generar un nuevo número en una secuencia aparentemente aleatoria.
Cabe señalar que hacer esto ingenuamente usando LFSR que manipula bits es bastante lento ya que tiene que procesar bits a la vez. Entonces, la gente ha ideado formas de usar tablas precalculadas para hacerlo de ocho bits a la vez o incluso de 32 bits a la vez. Es por eso que casi nunca ve el código LFSR en la naturaleza. En la mayoría de los códigos de producción, se disfraza de otra cosa.
Pero a veces, un LFSR simple y simple puede ser útil. Una vez escribí un controlador Modbus para un micro PIC y ese protocolo usaba CRC16. Una tabla precalculada requiere 256 bytes de memoria y mi CPU solo tenía 68 bytes (no estoy bromeando). Entonces tuve que usar un LFSR.
Hay muchas aplicaciones de LFSR. Uno de ellos es la generación de ruido, por ejemplo, el SN76489 y las variantes (utilizadas en Master System, Game Gear, MegaDrive, NeoGeo Pocket, …) utilizan un LFSR para generar ruido blanco / periódico. Hay una muy buena descripción del LFSR de SN76489 en esta página.
Aquí puedes ver las reseñas y valoraciones de los usuarios
Si entiendes que te ha sido útil este artículo, sería de mucha ayuda si lo compartieras con el resto seniors así contrubuyes a extender nuestro contenido.