Linear feedback shift register (LFSR)

4-bit LFSR example in C 
int rand4(void) {
        static unsigned seed = 1;

	if((((seed << 1) ^ seed) & 0x08) != 0)
                seed = (seed << 1) | 1;
        else
		seed <<= 1;
	seed &= 0x0F;
        return seed;
}
seed is used as a serial-in parallel-out (SIPO) shift register. Bits b3 and b2 are exclusive-ORed and fed back to the serial input, which is shifted into b0.

The feedback arrangement shown here produces a pseudorandom sequence with 15 values. This is the maximum for a 4-bit shift register. The missing state is the all-zeroes state (seed == 0). If the algorithm lands in this state, it will 'get stuck'.

XOR connections for maximal-length LFSRs

This data is taken from Table 6-3 of Don Lancaster's excellent 'CMOS Cookbook'. The length of each sequence is 2Bits - 1.

 
Bits XOR connections Bits XOR connections Bits XOR connections Bits XOR connections
2 0, 1 10 6, 9 18 10, 17 26 19, 23, 24, 25
3 1, 2 11 8, 10 19 13, 16, 17, 18 27 21, 24, 25, 26
4 2, 3 12 5, 7, 10, 11 20 16, 19 28 24, 27
5 2, 4 13 8, 10 11, 12 21 18, 20 29 26, 28
6 4, 5 14 3, 7, 12, 13 22 20, 21 30 6, 27, 28, 29
7 5, 6 15 13, 14 23 17, 22 31 27, 30
8 3, 4, 5, 7 16 3, 12, 14, 15 24 16, 21, 22, 23
9 4, 8 17 13, 16 25 21, 24

Using the modulus operator (%) to adjust the range of pseudorandom numbers can make them less random

Pseudorandom sequence generated by function rand4()
2 4 9 3 6 13 10 5 11 7 15 14 12 8 1

Probability histogram
* * * * * * * * * * * * * * *
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
There are 15 possible outcomes, and each is equally likely.

Pseudorandom sequence generated by rand4() % 4
2 0 1 3 2 1 2 1 3 3 3 2 0 0 1

Probability histogram
*
*
*		 *
*
*
*		 *
*
*
*		 *
*
*
*
0 1 2 3
The sequence length (15) is not an exact multiple of the modulus (4), so the new pseudorandom distribution is not uniform.