I have been using a 31 bit prbs function to generate random numbers. I never tested to see if this was of maximum length – guess what – it wasn’t! So after some trial and error I arrived at the following 31 bit prbs function which doesn’t repeat itself until after 2 billion cycles or so and is maximal length

#include <stdio.h>
unsigned prbs()
	// This is a verified 31 bit PRBS generator on an i3 running 64 bit Fedora Linux
	static unsigned long shift_register=0xa5a5a5a5;
	unsigned long new_bit=0;
	static int busy=0; // need to prevent re-entrancy here
	if (!busy)
		new_bit= ((shift_register >> 27) ^ (shift_register >> 30));
		new_bit= ~new_bit;
		new_bit = new_bit & 1;
		shift_register=shift_register << 1;
		shift_register=shift_register | (new_bit);
		shift_register=shift_register & 0x7fffffff;
	return shift_register; // return 31 LSB's
void main()
	unsigned first_run;
	unsigned count;
	int value;
	first_run = prbs();
	while(value != first_run)
		//printf("%d\n",value); // uncomment this to see the values (slows things down a lot)
	printf("Count = %d\n",count);

The “busy” flag is used in the prbs function in case the routine is called from with an interrupt service routine leading to a danger of re-entrancy.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s