A Linear Feedback Shift Register is a sequential shift register with combinational logic that causes it to pseudo-randomly cycle through a sequence of binary values. Linear feedback shift registers have multiple uses in digital systems design.

Applications Include:

• Data Encryption/Decryption
• Digital Signal Processing
• Wireless Communications
• Built-in Self Test (BIST)
• Data Integrity Checksums
• Data Compression
• Pseudo-random Number Generation (PN)
• Direct Sequence Spread Spectrum
• Scrambler/Descrambler
• Optimized Counters

A design modeled after LFSRs often has both speed and area advantages over a functionally equivialent design that does not use LFSRs.

An explanation of how to use LFSRs for these applications can be found in the sales primer for a Linear Feedback Shift Register Megafunction sold by Altera. This is a PDF file.

Feedback around an LFSR's shift register comes from a selection of points (taps) in the register chain and constitutes XORing these taps to provide tap(s) back into the register. Register bits that do not need an input tap, operate as a standard shift register. It is this feedback that causes the register to loop through repetitive sequences of pseudo-random value. The choice of taps determines how many values there are in a given sequence before the sequence repeats. The implemented LFSR uses a one-to-many structure, rather than a many-to-one structure, since this structure always has the shortest clock-to-clock delay path.

A diagram of an eight bit LFSR is as follows:

The following table shows a minimum number of taps that yield maximal length sequences for LFSRs ranging from 2 to 32 bits.

The implemented LFSR is coded for maximal length (2^N-1), where N is the number of bits in the LFSR. The VHDL entity can be instantiated with an LFSR bit width of 2 to 32.

The parallel "seed" input port (same length as the bit width) can be used to start the LFSR sequence at a certain position in the pseudo-random sequence. Assertion of the Active High "Load" signal at the rising edge of a clock will load the seed value into the LFSR.  

Before the LFSR is used for the first time, the Active Low "Reset" must first be asserted to initialize the Taps lookup table. One should ensure that "Load" and "Reset" are not asserted at the same time or else undetermined behavior will result.

The LFSR outputs pseudo-random sequences in both serial and parallel format for extra flexibility.

The VHDL code for the LFSR as well as a component instantiation example are provided.

Our group has tested this code in MAX+plus II. If you attempt to use this code and it does not work, please email Raymond Sung

VHDL Code

lfsr_generic.vhd

lfsr_pkg.vhd

lfsr_generic_test.vhd

Authors: Raymond Sung, Andrew Sung, Patrick Chan, Jason Mah