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