In the previous post I mentioned that a maximum length LFSR can be modified quite easily to generate the *“all zero”* state. The resulting sequence is then called a **De Bruijn** code. It has many uses in our business but also in remote areas like card tricks!!

The normal maximum length LFSR circuit cannot generate the “all zero” state or the trivial state, because it will get stuck in this state forever. The picture below shows as an example a 4-bit maximum length LFSR circuit.

The trick is to try to insert the “all zero” state in between the “00..01” and the “10..00” states. Normally after the “00..01” state the next value to be pushed in from the left would be a “1”, so the state “10..00” could be generated. If we would like to squeeze the “00..00” state next, we need to flip this to “0”. Then we have to make sure that for the next cycle a “1” will be pushed. This is done by detecting when the entire set of registers – less the rightmost one – are all zero, and using this as another input in the XOR feedback path. The result is a 2^n counting space sequence which is called a De Bruijn sequence. The figure of the completed De Bruijn counter is shown below.

Since it is a bit hard to follow the words, you can convince yourself by following the sequence – the table below will be of some help.

If you plot a single bit of the De Bruijn counter over time (doesn’t matter which bit) you will see something similar to the next figure. Notice how over time, observing 4 consecutive bits in the sequence not only gives a unique result (until it wraps around) but also gives all possible 4-bit combinations! A simple LFSR will only fulfill the first criteria.

If you like LFSRs and want to investigate a bit more, there is an excellent (albeit quite “heavy to digest”) book from Solomon Golomb called shift register sequences. The book is from the 1960s!! who said all good things in our industry are new…