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.
properties
Noteworthy properties of the LFSR with the length N bits are
- the maximum non-repeating bitstream is 2^N -1 when the taps are well choosen.
- the maximum number of identical subsequent bits (0 or 1) is N
- the lowest contained frequeny is clock / N
- the highest contained frequency is the clock
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 :
- the longest possible cycle
- the distribution of parallel values
- the minimum contained frequency
- the maximum contained frequency
Some observations :
for the output width being equal the shift register length :
- each value except zero is being read out, this means the value
distribution is flat
- Since each value is different, it can be assumed the highest
frequency is the clock
- Since the sequence repeats after at most 2^n, this is the lowest
freqency available
for the output width being shorter than the shift register length :
- As the output values are truncated they repeat twice for
each missing bit
- While in the n=m setup each value may appear just once per
maximum cycle, in the n>m setup each value may appear n/m times.
- the distribuution of values is still flat
for sequences shorter than the maximum length :
- the distribution is still flat, but some values are missing,
and they appear to form a pattern - to be examined
- the sequence repeats as often as the sequence is shorter
detailed research
general proofs may be made with induction.
I'll look into that when time permits.
simulations
home
last updated 26.june.03 or perhaps later
Copyright (99,2003) Ing.Büro R.Tschaggelar