h1

De Bruijn and Maximum Length LFSR Sequences

February 15, 2008

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.

4-bit_lfsr.png

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.

4-bit_debruijn.png

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.

4-bit_debruijn_lfsr_comparison.png

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.

4-bit_debruijn_sequence.png

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…

Advertisements

6 comments

  1. I think that Druijn gives similar timing to sychronus counter and if so it is better to use sychronus counter.


  2. Lior,

    these counters ARE synchronous! an Asynchronous counter is where the clock input of a bit depends on the previous stage – e.g. a ripple counter.


  3. LFSRs are used as counters (with nonstandard number sequence) in some applications because they require less logic than binary or Gray code counters.


  4. The exact previous post talks about this application under these conditions – when only a terminal count is needed.


  5. I put together a site with online LFSR Counter generator tool that generates Verilog or VHDL code for counters of any value up to 31 bit. It’s on OutputLogic.com


  6. Hello Nir,
    Looking at your schematic for the LFSR you have taps at 2 and 4 for your feedback polynomial. My chart has taps at 3 and 4 for a four bit register to generate an m-sequence. Also, where did you learn about the deBruijn construction with the three imput OR gate in the feedback loop? I would like to build a 63 bit deBruijn generator, do you have any sources for this type of design? Thank you.
    William



Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: