LectureLectureLinear Feedback Shift Register (LFSR)Register (LFSR) CountersECE 5440/6370 Spring 2010Yuhua Chen1LFSR CountersLFSR Counters PrimerAn LFSR is a special type of counterAn LFSR is a special type of counter Counting Sequence is Pseudo Random Typically has 2n-1 states (primitive form)Can be made to have 2nstates withCan be made to have 2n states with “extended sequence” logic2LFSR Counters Implementation StylesLFSR Counters Implementation StylesUp / Down CountersUp / Down Counters Down counters (start w/ 111… typically) Use XOR gates for feedback terms Primitive forms do not have an all zeros state Up counters (start w/ 000… typically)UXNORtffdbktUse XNOR gates for feedback terms Primitive forms do not have an all ones stateFlipflop Feedback ConstructionFlip-flop Feedback Construction One-to-many – One output to many inputsMany-to-one-Many outputs to one input3Many-to-one -Many outputs to one inputMany to One ExamplesMany to One Examples4Different taps sometimes possible XOR vs. XNORLFSR CountersLFSR Counters One-to-many is fastest, since it can be implemented y, pin two levels of logic5http://www.e-insite.net/ednmag/archives/1996/010496/graph/01df4fg4.htm4-bitLFSR Schematic4bit LFSR SchematicDQQG3G2G1Q1Q0Q2 Q3DQQ DQQ DQQCLOCK6XNOR Version Counting Sequencebinary hex decimaly==================0000 0 00001 1 10010220010 220101 5 31010 A 40100 4 51001961001 960011 3 70110 6 81101 D 91011B101011B100111 7 111111 F 12 Å Added State1110 E 131100C1471100C141000 8 15LFSR CountersComparison to other counter typesComparison to other counter types PROS: Requires very little logic to implementqygp Even long counters are very efficient Low gate count High speedgp Easy to test for faults - typically only need 2*n clocks CONS:P i iti f t b i iti li d t lid t tPrimitive forms must be initialized to valid state Some applications require binary count sequences Not easy to predict count sequence – tough to roll 8your own…Fortunately there’s any easy wayFortunately, there s any easy way…Use theUse the LFSR Testbench Utility Careful… LSB is on the left Select the Verilog tab for code…9Recommended SettingsRecommended SettingsWhen counting sequences are longer than 256When counting sequences are longer than 256 states, it will be cumbersome to use the tool to determine the terminal count (last count before the pattern repeats).pattern repeats). Use many-to-one because patterns are more predictableWh f db k i NXOR th t i l t illWhen feedback is NXOR, the terminal count will have the characteristic of MSB = 1, all other bits are zero. When feedback is XOR, the terminal count will have the characteristic of MSB = 0, all other bits are one.See examples on the next page…10See examples on the next page…Many-to-one XNOR Exampleyp11Many-to-one XOR Exampleyp12Decoding LFSR StatesDecoding LFSR States To be useful, the LFSR flop outputs must be decoded Typically, we want to decode the terminal count (last counter state before the counting sequence repeats) However, when used for “timer” applications where the exact number of counts pprequired is not 2nor 2n-1, a shorter count sequence is needed The steps are:Combinatorially (assign statement) decode the LFSR pattern coresponding toCombinatorially (assign statement) decode the LFSR pattern coresponding to one count less than the desired length Synchronously reset the counter to its initial state when decoded state is activeFor example assume a simple XNOR many-to-one 8-bit LFSR and we want aFor example, assume a simple, XNOR, manytoone 8bit LFSR and we want a counter sequence length of 240 counts. Using the LFSR test bench, we determine that the LFSR pattern after 239 counts is 9Ch13counts is 9ChSimple, 8-Bit, Many-to-one NXOR DdiE lDecoding Example14Decoding LFSR StatesDecoding LFSR Statesmodule LFSR8_8E(reset_, clock, q, lfsr_to); Add the assign statement and reset litth dlinput clock, reset_;output [7:0] q, lfsr_to;reg [7:0] LFSR;wire lfsr_to;assign lfsr to = (LFSR == 8’h9C);logic to the module created by the LFSR testbenchassign lfsr_to = (LFSR == 8 h9C);always @(posedge clock or negedge reset_)beginif (!reset_) LFSR[7:0] <= 8’h00;else Add synchronous reset logicelsebeginif (lfsr_to) LFSR[7:0] <= 8’h00;elsebeginLFSR[0] <= ~LFSR[1] ^ LFSR[2] ^ LFSR[3] ^ LFSR[7];LFSR[7:1] <= LFSR[6:0];endendendassign q = LFSR;15assign q = LFSR;endmoduleLFSR CountersLFSR CountersMLFSRIf tiMore LFSR Information http://www.e-insite.net/ednmag/archives/1996/010496/01df4.htm http://www.e-insite.net/ednmag/archives/1998/052198/11df_06.htm