linear feedback shift registers LFSR

LFSRs are commonly used to generate pseudo random bitstreams.

A LFSR is a shift register where arbitrary intermediate bits are fed back by using an XOR with them and the shift register output. Notice that the state where all Flipflops are zero is prohibited and the NOR-ing of all intermediate bits enforces that.


Noteworthy properties of the LFSR with the length N bits are The above properties are well understood and verified. When requiring a parallel output eg for a DAC, no reference to properties was found.

for further information about practical implementations, have a look at
the Xilinx Application notes 210, 211, 217 & 220 ( XApp210.pdf, XApp211.pdf,
XApp217.pdf, XApp220.pdf ) to be found at Xilinx

simulating a parallel LFSR

Be the LFSR of n bits of which m are used as parallel output. The questions asked for the simulation : Some observations : for the output width being equal the shift register length : for the output width being shorter than the shift register length : for sequences shorter than the maximum length :

detailed research

general proofs may be made with induction.
I'll look into that when time permits.


last updated 26.june.03 or perhaps later

Copyright (99,2003) Ing.Büro R.Tschaggelar