On Arbitrary Cycle n-Bit LFSRs |
|||
Home Site News >> << 3-D rendering
Usenet Postings |
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"
Copyright © 2000, Gray Research LLC. All rights reserved. |