On Arbitrary Cycle n-Bit LFSRs

Home

Site News >>
<< 3-D rendering

Usenet Postings
  By Subject
  By Date

FPGA CPUs
  Why FPGA CPUs?
  Homebuilt processors
  Altera, Xilinx Announce
  Soft cores
  Porting lcc
  32-bit RISC CPU
  Superscalar FPGA CPUs
  Java processors
  Forth processors
  Reimplementing Alto
  Transputers
  FPGA CPU Speeds
  Synthesized CPUs
  Register files
  Register files (2)
  Floating point
  Using block RAM
  Flex10K CPUs
  Flex10KE CPUs

Multiprocessors
  Multis and fast unis
  Inner loop datapaths
  Supercomputers

Systems-on-a-Chip
  SoC On-Chip Buses
  On-chip Memory
  VGA controller
  Small footprints

CNets
  CNets and Datapaths
  Generators vs. synthesis

FPGAs vs. Processors
  CPUs vs. FPGAs
  Emulating FPGAs
  FPGAs as coprocessors
  Regexps in FPGAs
  Life in an FPGA
  Maximum element

Miscellaneous
  Floorplanning
  Pushing on a rope
  Virtex speculation
  Rambus for FPGAs
  3-D rendering
  LFSR Design
 

Google SiteSearch
Newsgroups: comp.arch.fpga
Subject: on arbitrary m-cycle n-bit lfsrs
Date: Mon, 3 Jul 2000 22:50:14 -0700

One way to make an 2^n-cycle lfsr is to use an n+1 bit lfsr and arrange it
to cycle with a length of 2^n by complementing the shift-in at the right
time (counter pattern) so as to generate a 2^n count cycle.

My lfsr design program finds such things, as well as bit patterns of
arbitrary counter taps in arbitrary m-cycle n-bit lfsrs.

To design an m-cycle lfsr in an n-bit lfsr, n > 2 and 1 < m < 2^n - 1, build
a table w[] of lfsr counter bit patters.  w[0] is the initial bit pattern
0000...0.  w[i+1] is w[i] after shifting in (at the lsb) the next 0 or 1
(the xor-of-taps input) and shifting out (discarding) w[i]'s msb.

If after some number of cycles i, w[i] ^ w[i-m] == 0000...1, we can form an
m-cycle counter by complementing the xor-of-taps input when the counter is
at bit pattern w[i-1].

Conjecture: for m, n, and w[] as above, there always exists an i such that
w[i] ^ w[i-m] == 0000...1

For example, if you want an 8-cycle counter using a 4-bit LFSR, we have:

% lfsr -v 4 8

       n w 8-back
       - - ------
       0 0
       1 1
       2 3
       3 7
       4 E
       5 D
       6 B
       7 6
       8 C 0
       9 9 1
      10 2 3 8-cycle [2-9]: complement d0 when w==9 maps 2=>3

    lfsr 4-bits 8-cycle=9
    lfsr 4-bits 8-cycle: d0=xnor(q3,q2, /*9*/and(q3,~q2,~q1,q0));

Here w[2]=3, w[9]=9, and w[10]=2.  If we complement the lfsr input bit shift
into w[10], we would have w'[10]=3 and the lfsr would cycle
3,7,E,D,B,6,0,1,3,...

The lfsr design program (verbose mode) therefore reports that the logic
required is:
  d0=xnor(q3,q2, /*9*/and(q3,~q2,~q1,q0));

Here are some more examples.

% lfsr 6 32
    lfsr 6-bits 32-cycle=23
    lfsr 6-bits 32-cycle: d0=xnor(q5,q4, /*23*/and(q5,~q4,~q3,~q2,q1,q0));

% lfsr 7 64
    lfsr 7-bits 64-cycle=07
    lfsr 7-bits 64-cycle: d0=xnor(q6,q5,
/*07*/and(~q6,~q5,~q4,~q3,q2,q1,q0));

% lfsr 8 128
    lfsr 8-bits 128-cycle=43
    lfsr 8-bits 128-cycle: d0=xnor(q7,q5,q4,q3,
/*43*/and(~q7,q6,~q5,~q4,~q3,~q2,q1,q0));

You can also build an 8-cycle counter in something larger than a 4-bit lfsr.
Here is one in a 6-bit lfsr:

% lfsr 6 8
    lfsr 6-bits 8-cycle=0B
    lfsr 6-bits 8-cycle: d0=xnor(q5,q4, /*0B*/and(~q5,~q4,q3,~q2,q1,q0));

I used this tool to design area-efficient horizontal and vertical
sync/blanking counters in the VGA controller in XSOC.  (There's not too much
space left in a XC4005x after you've implemented a pipelined RISC processor
and the rest of the SoC -- every 4-LUT is precious.)  For XSOC, with a 25
MHz dot clock, we need a 397-cycle horizontal counter with events at 288,
315, and 362cycles, and a 528-cycle vertical counter with events at 455,
486, and 488 cycles.  To keep things simple, both are implemented with
10-bit lfsrs:

% lfsr 10 397 288 315 362
    lfsr 10-bits 397-cycle=31D 288=1C4 315=122 362=3B6
    lfsr 10-bits 397-cycle: d0=xnor(q9,q6,
/*31D*/and(q9,q8,~q7,~q6,~q5,q4,q3,q2,~q1,q0));

% lfsr 10 528 455 486 488
    lfsr 10-bits 528-cycle=27D 455=01D 486=3F5 488=3D7
    lfsr 10-bits 528-cycle: d0=xnor(q9,q6,
/*27D*/and(q9,~q8,~q7,q6,q5,q4,q3,q2,~q1,q0));


This is how I used this in the Verilog version of XSOC/xr16:

/* vga.v -- XSOC bilevel VGA controller synthesizable Verilog model
 *
 * Copyright (C) 1999, 2000, Gray Research LLC.  All rights reserved.
 * The contents of this file are subject to the XSOC License Agreement;
...
module vga(clk, rst, vack, pixels_in, vreq, vreset, hsync_n, vsync_n, r, g,
b);
...
 // Horizontal and vertical sync and enable timings, 12.5 MHz
 wire [9:0] hc, vc;
 wire  h0  = hc == 10'h31D;
 wire  v0  = vc == 10'h27D;
...
 lfsr10  hctr(.clk(clk), .rst(rst), .ce(1'b1), .cycle(h0), .q(hc));
 lfsr10  vctr(.clk(clk), .rst(rst), .ce(h0),   .cycle(v0), .q(vc));
...
endmodule


// lfsr10 -- 10-bit linear feedback shift register counter
//
module lfsr10(clk, rst, ce, cycle, q);
 input   clk;  // global clock
 input   rst;  // global async reset
 input   ce;   // counter clock enable
 input   cycle;  // toggle LFSR input to force short cycle
 output [9:0] q;   // counter output
 reg  [9:0] q;

 always @(posedge clk or posedge rst) begin
  if (rst)
   q <= 0;
  else if (ce)
   q <= { q[8:0], ~(q[9] ^ q[6] ^ cycle) };
 end
endmodule


The 152-line lfsr.c, and its Win32 binary, are available as part of the XSOC
kit, available under the XSOC License Agreement, at www.fpgacpu.org/xsoc

Jan Gray
Gray Research LLC


Reference
"Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence
Generators", Peter Alfke, Xilinx App Note, Aug. 1995



Newsgroups: comp.arch.fpga
Subject: Re: on arbitrary m-cycle n-bit lfsrs
Date: Wed, 5 Jul 2000 10:04:08 -0700

"Jan Gray"  wrote in message
news:vWe85.1205$q94.384510@paloalto-snr1.gtei.net...

>        n w 8-back
>        - - ------
>        0 0
>        1 1
>        2 3
>        3 7
>        4 E
>        5 D
>        6 B
>        7 6
>        8 C 0
>        9 9 1
>       10 2 3 8-cycle [2-9]: complement d0 when w==9 maps 2=>3
>
>     lfsr 4-bits 8-cycle=9
>     lfsr 4-bits 8-cycle: d0=xnor(q3,q2, /*9*/and(q3,~q2,~q1,q0));
>
> Here w[2]=3, w[9]=9, and w[10]=2.  If we complement the lfsr input bit
shift
> into w[10], we would have w'[10]=3 and the lfsr would cycle
> 3,7,E,D,B,6,0,1,3,...

Correction: 3,7,E,D,B,6,C,9,3, ...

One other comment.  If you build an m-cycle n-bit lfsr with m < 2^n - 1, and
reset it to the bit pattern 0000...0, and if 0000...0 is not in the m-cycle,
then it may take up to 2^n - m-1 cycles for the counter to first reach a
valid m-cycle bit pattern.  In the above example, it takes 2 cycles for the
lfsr to first reach an m-cycle bit pattern 0x3, and 9 cycles (9 > 8) to
first reach the terminal m-cycle bit pattern 0x9.

If you were to design, e.g. a 3-cycle 6-bit lfsr (for some strange reason)
such as

    lfsr 6-bits 3-cycle: d0=xnor(q5,q4, /*2D*/and(q5,~q4,q3,q2,~q1,q0));

it takes 37 cycles before it reaches the bit pattern 0x1B and starts its
3-cycle (0x1B, 0x36, 0x2D, 0x1B, ...).  If this is not acceptable, you must
of course ensure you reset the lfsr to some valid bit pattern in the
m-cycle.

Jan Gray
Gray Research LLC


Copyright © 2000, Gray Research LLC. All rights reserved.
Last updated: Feb 03 2001