Números aleatorios generados mediante registros LFSR

[Carlos]

Información sobre números aleatorios generados mediante registros LFSR:

A 16-bit Fibonacci LFSR:
   

Ventajas
   La implementación es muy sencilla
   El cálculo es muy rápido
   Pueden generar series muy largas de números pseudoaleatorios
   Salida uniformemente distribuida

Inconvenientes
   No son criptográficamente seguros, aunque existen técnicas para mejorar su seguridad   
   

Enlaces
   http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Saludos.

[Carlos]

Código para generar números aleatorios y contadores con LFSR:


LFSR de 8 bits:

Código: [Seleccionar]


unsigned char lfsr8;

void lfsr8_next(void) {
   if (lfsr8 & 1) {
      lfsr8 >>= 1;
      lfsr8 ^= (1<<7) + (1<<5) + (1<<4) + (1<<3);
   }
   else {
      lfsr8 >>= 1;
   }
}



LFSR de 16 bits:

Código: [Seleccionar]


unsigned long lfsr16;

void lfsr16_next(void) {
   if (lfsr16 & 1) {
      lfsr16 >>= 1;
      lfsr16 ^= (1<<15) + (1<<14) + (1<<12) + (1<<3);
   }
   else {
      lfsr16 >>= 1;
   }
}



LFSR de 32 bits:

Código: [Seleccionar]


unsigned long lfsr32;

void lfsr32_next(void) {
   if (lfsr32 & 1) {
      lfsr32 >>= 1;
      lfsr32 ^= (1UL<<31) + (1UL<<21) + (1UL<<1) + (1UL<<0);
   }
   else {
      lfsr32 >>= 1;
   }
}


Polinomios generadores de longitud máxima:
   http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Estos polinomios pasan por todos los valores posibles excepto cero.
El valor inicial no puede ser igual a cero porque el LFSR no cambia en ese caso.

Saludos.

[Carlos]

Ejemplo de programa en Arduino:

Código: (Arduino) [Seleccionar]

/*
   Ejemplo de implementación de un registro LFSR
   para generar números aleatorios

   Fuente: https://www.picuino.com/foro/index.php?topic=19
*/

unsigned int lfsr16;   // Declara el registro de desplazamiento

void setup() {
   Serial.begin(115200);

   // Semilla inicial para los números aleatorios
   // Debe ser diferente a cero 
   lfsr16 = 1;               

   // Calcula e imprime los 65535 número aleatorios posibles
   for(unsigned int i=0xFFFF; i>0; i--) {
      Serial.println(lfsr16); // Imprime por el puerto serie el número aleatorio
      lfsr16_next();          // Calcula el siguiente número aleatorio
   }
}

void lfsr16_next(void) {
   if (lfsr16 & 1) {
      lfsr16 >>= 1;
      lfsr16 ^= (1<<15) + (1<<14) + (1<<12) + (1<<3);
   }
   else {
      lfsr16 >>= 1;
   }
}


void loop() {
}