Go Down

Topic: Problem reading random noise generator (Read 11379 times) previous topic - next topic

acegard


I am very fond of the debugging approach of throwing away the parts of code that aren't working for me, and either recoding from scratch or even better trying a different approach/algorithm.

Me too! I have rewritten and refactored this sketch four or five times since the inception of the project. I have since layered XOR whitening on top of the Von Neumann, and am currently implementing the Jenkins hash you provided. It's making the 0-255 distribution improve each time, but not the mapped distribution, which remains pretty terrible. I would be surprised if it's something in your algorithm, because I've seen the vast and corroborated results of your tests.

wanderson

Ok, I have collected about 75,000 numbers from 0-19, using my original library code.  Looks like the algorithm itself is working (chi sq of 29.9283, p-value of 0.05272, so when I get finished playing with my new 3D printer that just arrived I will look at seeing what is wrong with your code in a day or two!

Code: [Select]

> library(foreign)
> tmp <- read.csv("log20.txt")
> tmp <- tmp$X3
> cb <- table(tmp)
> pb <- rep(1/20,20)
> cb <- as.integer(cb)
> chisq.test(cb, p = pb)

Chi-squared test for given probabilities

data:  cb
X-squared = 29.9283, df = 19, p-value = 0.05272

> length(tmp)
[1] 73958
> sum(cb)
[1] 73958
>

acegard


Ok, I have collected about 75,000 numbers from 0-19, using my original library code.  Looks like the algorithm itself is working (chi sq of 29.9283, p-value of 0.05272, so when I get finished playing with my new 3D printer that just arrived I will look at seeing what is wrong with your code in a day or two!

Great! Have fun with the printer! I'll keep posting things as I run tests or figure out what is wrong.

acegard

After some days of tinkering with my code, I am pleased to say that I think I have reached an acceptable level of randomness in the mapped values!
I implemented your suggestion to limit bit-length and toss out any number greater than my maximum required value, and it seems to work well. The map20() method I used which was based on your algorithm does not work, and I can't figure out why, but this method does seem to.

Thank you very much for your help! If you have any other input or notes for me, I would be glad to hear them.

Code: [Select]

#define BINS_SIZE 256
#define CALIBRATE_SIZE 10000

#define NO_BIAS_REMOVAL 0
#define EXCLUSIVE_OR 1
#define VON_NEUMANN 2

#define ASCII_BYTE 0
#define BINARY 1
#define ASCII_BOOL 2

#define BYTE_LENGTH 8
#define LONG_NIBBLE_LENGTH 5
#define NIBBLE_LENGTH 4
#define TWO_BIT_LENGTH 2
#define COIN_FLIP 1

#define MAP_MAX 20

#define LED_PIN 13
#define ADC_PIN A0

/***  Configure the RNG **************/
int bias_removal = VON_NEUMANN;
boolean TWO_LEVEL_WHITENING = true;
int output_format = ASCII_BOOL;
int max_length = LONG_NIBBLE_LENGTH;
boolean mapResults = true;
unsigned long maxSamples = 500000;
int baud_rate = 19200;
/*************************************/


unsigned int Bins[BINS_SIZE];
unsigned int Results[MAP_MAX];
boolean initializing = true;
unsigned int calibration_counter = 0;

boolean bufferFull = false;
byte buffer = 0;
byte threshold = 0;

unsigned long samples = 0;


void setup(){
  pinMode(LED_PIN, OUTPUT);
  Serial.begin(baud_rate);
  for (int i=0; i < BINS_SIZE; i++){
    Bins[i] = 0;
  } 
  for (int i=0; i < MAP_MAX; i++){
    Results[i] = 0;
  } 

  analogReference(EXTERNAL);
}

void loop(){

  Serial.println("Initializing...");
  Serial.println("Calibrating...");
  threshold = calibrate();
  Serial.print("Threshold: ");
  Serial.println(threshold);
  delay(2000);
  Serial.println("Collecting Data");
  for (int i=0; i < BINS_SIZE; i++){
    Bins[i] = 0;
  } 
  while(samples < maxSamples)
  {
    byte rand = getRandomByte(threshold);
    if(mapResults)
    {
      if(rand < MAP_MAX)
      {
        Results[rand]++;
        samples++;
        Serial.print(samples);Serial.print(": ");Serial.println(rand);
      }
    }
    else
    {
      Bins[rand]++;
      samples++;
      Serial.print(samples);Serial.print(": ");Serial.println(rand);
    }


  }

  Serial.println("Distribution:");
  for (int i=0; i < BINS_SIZE; i++){
    Serial.print(i);
    Serial.print(": ");
    Serial.println(Bins[i]);
  } 
  for (int i=0; i < 20; i++){
    Serial.print(i);
    Serial.print(": ");
    Serial.println(Results[i]);
  }
  while(true){
  }
}

byte getRandomByte(byte tHold)
{
  while(!bufferFull)
  {
    int adc_value = analogRead(ADC_PIN);
    byte adc_byte = adc_value >> 2;
    processInput(adc_byte, tHold);
  }
  bufferFull = false;
  return buffer;
}

void processInput(byte adc_byte, byte threshold){
  boolean input_bool;
  input_bool = (adc_byte < threshold) ? 1 : 0;
  switch(bias_removal){
  case VON_NEUMANN:
    vonNeumann(input_bool);
    break;
  case EXCLUSIVE_OR:
    exclusiveOr(input_bool);
    break;
  case NO_BIAS_REMOVAL:
    buildByte(input_bool);
    break;
  }
}

void exclusiveOr(byte input){
  static boolean flip_flop = 0;
  flip_flop = !flip_flop;
  buildByte(flip_flop ^ input);
}

void vonNeumann(byte input){
  static int count = 1;
  static boolean previous = 0;
  static boolean flip_flop = 0;

  flip_flop = !flip_flop;

  if(flip_flop){
    if(input == 1 && previous == 0){
      if(TWO_LEVEL_WHITENING)
        exclusiveOr(0);
      else
        buildByte(0);
    }
    else if (input == 0 && previous == 1){
      if(TWO_LEVEL_WHITENING)
        exclusiveOr(1);
      else
        buildByte(1);
    }
  }
  previous = input;
}

void buildByte(boolean input){
  static int byte_counter = 0;
  static byte out = 0;

  if (input == 1){
    out = (out << 1) | 0x01;
  }
  else{
    out = (out << 1);
  }
  byte_counter++;
  byte_counter %= max_length;
  if(byte_counter == 0){
    buffer = out;
    bufferFull = true;
    out = 0;
    return;
  }
  bufferFull = false;
}



unsigned int calibrate()
{
  digitalWrite(LED_PIN,HIGH);
  for(int i = 0; i < CALIBRATE_SIZE; i++)
  {
    int adc_value = analogRead(ADC_PIN);
    byte analog = adc_value >>2;//truncates to 0-255
    Bins[analog]++;
  }

  //find the median
  unsigned long half;
  unsigned long total = 0;
  int i;

  for(i=0; i < 256; i++){
    total += Bins[i];
  }

  half = total >> 1;
  total = 0;
  for(i=0; i < 256; i++){
    total += Bins[i];
    if(total > half){
      break;
    }
  }
  digitalWrite(LED_PIN,LOW);
  return i;
}



wanderson

Glad to here you got the code working.  I am still climbing the 3D printing learning curve!

Go Up