Autor Tema: Números aleatorios generados mediante registros LFSR  (Leído 895 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Carlos

  • Moderador Global
  • ****
  • Mensajes: 325
Números aleatorios generados mediante registros LFSR
« en: 27/May./2015, 18:46:35 p. m. »
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.
« Última modificación: 27/May./2015, 18:56:10 p. m. por Carlos »

Carlos

  • Moderador Global
  • ****
  • Mensajes: 325
Re:Números aleatorios generados mediante registros LFSR
« Respuesta #1 en: 27/May./2015, 19:17:28 p. m. »
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.
« Última modificación: 27/May./2015, 22:52:22 p. m. por Carlos »

Carlos

  • Moderador Global
  • ****
  • Mensajes: 325
Re:Números aleatorios generados mediante registros LFSR
« Respuesta #2 en: 27/May./2015, 19:29:29 p. m. »
Ejemplo de programa en Arduino:

Código: Text
  1. /*
  2.    Ejemplo de implementación de un registro LFSR
  3.    para generar números aleatorios
  4.  
  5.    Fuente: https://www.picuino.com/foro/index.php?topic=19
  6. */
  7.  
  8. unsigned int lfsr16;   // Declara el registro de desplazamiento
  9.  
  10. void setup() {
  11.    Serial.begin(115200);
  12.  
  13.    // Semilla inicial para los números aleatorios
  14.    // Debe ser diferente a cero  
  15.    lfsr16 = 1;              
  16.  
  17.    // Calcula e imprime los 65535 número aleatorios posibles
  18.    for(unsigned int i=0xFFFF; i>0; i--) {
  19.       Serial.println(lfsr16); // Imprime por el puerto serie el número aleatorio
  20.       lfsr16_next();          // Calcula el siguiente número aleatorio
  21.    }
  22. }
  23.  
  24. void lfsr16_next(void) {
  25.    if (lfsr16 & 1) {
  26.       lfsr16 >>= 1;
  27.       lfsr16 ^= (1<<15) + (1<<14) + (1<<12) + (1<<3);
  28.    }
  29.    else {
  30.       lfsr16 >>= 1;
  31.    }
  32. }
  33.  
  34.  
  35. void loop() {
  36. }
  37.  
« Última modificación: 02/Dic./2015, 17:07:55 p. m. por Carlos »