Random number generator (Part 1)

Part 1, 2, 3

As I was stumbling the web looking for advanced information on thermal noise, I found some very interesting papers on RNGs, aka Random Number Generators. These devices feature hardware components which are responsible for a generating unpredictable random numbers !

This is a very interesting matter as it involves physics, electronics, mathematics, software and … ultimately cryptography. Credit is due to people smarter than I am which publications can be found at the end of this post. The idea here is to described a surprisingly simple and yet powerful method for generating random numbers of various length, actually from 1 to 32 bits.

The principle of operation relys on the amplification of the signal produced on the base of a reverse-biased transistor. The emitter is saturated with electrons and occasionally they will “tunnel” through the band gap and exit via the base. This signal is then amplified through two transistors one of them behind biased through a decoupling capacitor in order to get rid of the DC component of the signal.

Here is the electronic section of the project: All you need is a trio of general purpose NPN transistors such as the popular 2N3904 a pair of capacitor and few resistors. The schematic is rather simple.

schematics

I brought a little refinement to the original design by feeding the amplifying stage with a stable +5 V. Note that both Vin and +5 V should be decoupled by 10 µF capacitors (Watch out the operating voltage of the capacitor attached to Vin !). Under these conditions, the circuit outputs a 0 to 1  V signal which fits very well the analog to digital conversion using the 1.1  V internal reference. Please note that 5 V will not suffice to create a reverse bias condition on the base-emetter junction of T1. I managed to get a stable running state starting with Vin = 9 V.

scope

I also brought few refinements to the original code originally written by Rob Seward (v1.0 dated 4/20/2009 ). Firstly, the analog read function is replaced by a custom one which is way faster, thanks to its 8 bits resolution, low prescaler and refined code. the SetADC() function must be inserted within the setup() part of the code

/* Set adc parameters for 8 bits resolution, fast mode */
void SetADC(uint8_t adcChannel) 
{
	/* Clear ADC control registers */
	ADCSRA = 0x00;
	ADCSRB = 0x00;
	ADMUX  = 0x00;
	// ADMUX |= (1 << REFS0); /* DEFAULT 5 V*/
	ADMUX |= (1 << REFS1) | (1 << REFS0); /* INTERNAL 1.1 V */
	ADMUX |= adcChannel; /* Set channel */
	ADMUX |= (1 << ADLAR); /* Left align adc value, so as to say 8 bits resolution */
	ADCSRA |= 3; /* Set ADC prescaler */
	ADCSRA |= (1 << ADEN); /* Enable ADC */
	ReadADC(); /* Run one mock read */
}

inline uint8_t ReadADC(void) 
{
	const uint8_t ADSCmask = (1 << ADSC);
	/* Start conversion */
	ADCSRA |= ADSCmask; 
	/* Wait for conversion */
	while (ADCSRA & ADSCmask);
	/* Read digital value */
	uint8_t result = ADCH;
	/* Returned value */
	return(result);
}

Please note that in spite of its higher sampling rate capacity (about 100 kHz), we are still far from optimal sampling rate (1 Mhz or better). However, that will be enough for an experiment.

I also brought few refinements to the application specific functions:

/* Porcess the input value, so as to say the adc reading */
void ProcessInput(uint8_t adcValue)
{
	/* Set default value */
	uint8_t input = 0;
	if (adcValue > _adcThreshold) {
		input = 1;
	}
	switch(_biasRemovalType){
	case VON_NEUMANN:
		VonNeumann(input); 
		break;
	case EXC_OR:
		ExclusiveOr(input);
		break;
	case NO_BIAS_REMOVAL:
		BuildRandomNumber(input);
		break;
	}
}

/* Apply exclusive or to pairs of bits (thanks to the flip flop flag) */
void ExclusiveOr(uint8_t input)
{
	static uint8_t flipFlop = 0;
	static uint8_t previousInput = 0;
	if (flipFlop) {
		BuildRandomNumber(previousInput ^ input);
	}
	previousInput = input;
	flipFlop = !flipFlop;
}


/* Apply Von Neumann to pairs of bits (thanks to the flip flop flag) */
void VonNeumann(uint8_t input)
{
	static uint8_t flipFlop = 0;
	static uint8_t previousInput = 0;
	if (flipFlop) {
		if (input & ~previousInput){
			BuildRandomNumber(0);
		} else if (~input & previousInput){
			BuildRandomNumber(1); 
		}
	}
	previousInput = input;
	flipFlop = !flipFlop;
}


/* Append new bit to the currently built random number */
void BuildRandomNumber(uint8_t input)
{
	/* Shift previous bits */
	_outputBuffer <<= 1UL;
	/* Append input bit as LSB */
	_outputBuffer |= (input & 0x01);
	/* Update bits counter */
	_bitsCounter += 1;
	if (_bitsCounter == _outputBits) {
		/* Reset bytes counter */
		_bitsCounter = 0;
		/* Output data */
		_mainCounter += 1;
		Serial.print(_mainCounter, DEC);
		Serial.print(';');
		switch(_outputFormat){
		case BINARY:
			Serial.print(_outputBuffer, BIN); 
			break;
		case DECIMAL:
			Serial.print(_outputBuffer, DEC);
			break;
		case HEXADECIMAL:
			Serial.print(_outputBuffer, HEX);
			break;
		}
		Serial.println();
		_outputBuffer = 0x00;
	}
}

/* Record occurences of adc values in their corresponding bins */
void SortAdcValue(uint8_t byteValue)
{
	/* Update occurences counter of the current adc vlaue */
	_vSorter[byteValue] += 1; 
	/* Update counter of sorted values */
	_sortedValuesCounter += 1;
}

/* 
Compute the adc threshold which is the median of the counts of occurences for 
each adc value void 
*/
void ComputeAdcThreshold(void)
{
	uint32_t sum = 0;
	/* Compute the sum of adc occurences in all bins */
	for (uint16_t i = 0; i < _sorterSize; i++){
		sum += _vSorter[i];
	}	
	/* Compute half the sum of all observations */
	uint32_t halfSum = (sum >> 1);
	/* Reset sum */
	sum = 0;
	/* Find the adc value corresponding to half the sum of occurences */
	_adcThreshold = 0;
	while (sum < halfSum) {
		sum += _vSorter[_adcThreshold];
		_adcThreshold += 1;
	} 
}

This is how the code was looking like when I performed early tests which were not so bad in the end !

Next picture illustrates the probability mass function (aka pmf) from 65536 random numbers ranging from 0 to 65535:

pmf

As you can see, the spectrum is pretty homogeneous, showing a fine spreading of random numbers over the expected range. Next is the FFT from the raw data:

fft

Once again, the spectrum is pretty homogeneous, showing no particular recurring pattern. Additional statistics show an average value of 32711.29 which turns to a -0.17 % error. The skewness (symetry of data versus average) is 0.003. All these statistics are very encouraging. However, I might have a use the Dieharder, “A Random Number Test Suite” which looks it is the perfect tool for checking randomness of numbers.

Next steps ? I think that I will pack this material in a library (Why not PlainRNG ?) and run some long term testing…

Links:

Next post on same subject

Leave a Reply

You must be logged in to post a comment.