Generating Random Numbers using LFSRs

On a recent project I needed a simple random number generator. It didn't need to be anything fancy, nothing mathematically pure or statistically valid, just a quick'n'dirty little generator that would spit out numbers that looked random to the casual eye.

In a previous incarnation I worked for a mobile radio consultancy. One of the things I came across in that particular life was the concept of Pseudo Random Binary Sequences (PRBSs).

These are sequences of 0s and 1s that are generated deterministically, yet are random enough for many practical purposes. They are used extensively in communications to spread the bandwidth occupied by a signal. This makes the signal more immune to jamming, as the signal is smeared across a bigger chunk of spectrum than would otherwise be the case. It is also more difficult to intercept, since any receiver must know and be synchronised to the spreading sequence at the transmitter. A more subtle usage is that multiple signals can be spread across the same spectrum by multiple PRBSs, yet be teased apart at multiple receivers by correlation with the correct individual spreading sequences.

PRBSs are typically generated using Linear Feedback Shift Registers (LFSRs). These are cheap and easy to build in hardware, and easy to code in software.

At any time, a function of the LFSR contents is generated as the output bit value. This is fed back into the shift register as the next input. The output bit sequence is essentially random, as is the sequence of states formed by the LFSR contents.

The 'function of the LFSR contents' mentioned above is called a generator polynomial. It determines which LFSR cells are combined and fed back to form the LFSR input for the next state.

For instance, the Wikipedia article on LFSRs lists the following generator polynomial for an 8-bit PRBS:

x^8 + x^6 + x^5 + x^4 + 1

We now need to know how to convert this into code.

As we are generating an 8-bit polynomial, we start off with the 8-bit unsigned value 0x00u as our feedback function. If a power of x, say m, is used in the polynomial, assign a 1 to polynomial bit (m-1). The +1 in the polynomial corresponds to the output bit, and does not appear in the feedback settings. Here we have an 8-bit generator polynomial with bits 7, 5, 4, and 3 set, giving a value of 0xB8u.

Given this, and also using the example code in the Wikipedia article, we can now write a function that returns the next value in a pseudo-random 8-bit sequence.

#define LFSR_8_INITIAL_VALUE 0x01u
#define LFSR_8_POLYNOMIAL    0xB8u

uint8_t next_lfsr_8( void )
{
 /* seed LFSR */
 static uint8_t lfsr = LFSR_8_INITIAL_VALUE;

 /* get LFSR LSB */
 uint8_t lsb = (uint8_t)( lfsr & 0x01u );

 /* shift LFSR contents */
 lfsr = (uint8_t)( lfsr >> 1u );

 /* toggle feedback taps if we output a 1 */
 if( 1 == lsb )
 {
    lfsr ^= LFSR_8_POLYNOMIAL;
 }

 return lfsr;
}

An n-bit PRBS is said to be maximal length if the number of distinct output values it generates is 2^n - 1. That is, a maximal length 8-bit PRBS consists of 255 values. Our generator polynomial is indeed maximal length, and so the values returned will start to repeat after 255 calls.

In the above code I have set the initial value of the LFSR to 0x01u. The LFSR will generate a fixed sequence of output values, and the initial value merely determines where in the sequence the reported values will start.

Note that because the feedback taps uses the XOR operator, the LFSR will get stuck in the all-zeros state if it ever gets there. Care must be taken that an LFSR is not initialised with this value.

The corresponding 16-bit function is as follows.

#define LFSR_16_INITIAL_VALUE 0x0001u

#define LFSR_16_POLYNOMIAL 0xB400u

uint16_t next_lfsr_16( void )
{
 /* seed LFSR */
 static uint16_t lfsr = LFSR_16_INITIAL_VALUE;

 /* get LFSR LSB */
 uint8_t lsb = (uint8_t)( lfsr & 0x0001u );

 /* shift LFSR contents */
 lfsr = (uint16_t)( lfsr >> 1u );

 /* toggle feedback taps if we output a 1 */
 if( 1 == lsb )
 {
    lfsr ^= LFSR_16_POLYNOMIAL;
 }

 return lfsr;
}

Using the above approach, you can generate PRBSs of arbitrary length, given tables of generator polynomials (your search engine of choice will unearth plenty).