LFSR

Discussion in 'VHDL' started by Spartan815, Jan 28, 2004.

  1. Spartan815

    Spartan815 Guest

    Can anyone point me to a good resource on LFSRs? Theres alot I don't
    know about them, my textbook lacks any actual information... I
    appreciate any help thats out there... thanks!
    Spartan815, Jan 28, 2004
    #1
    1. Advertising

  2. On 27 Jan 2004 18:47:48 -0800, (Spartan815)
    wrote:

    >Can anyone point me to a good resource on LFSRs? Theres alot I don't
    >know about them, my textbook lacks any actual information... I
    >appreciate any help thats out there... thanks!


    What is it that you want to know?

    - How to build one?
    - Where to get pre-written code?
    - How to deal with lock-up states?
    - WTF is a Galois field or a polynomial?
    - What do "primitive", "irreducible" and "maximal length" mean?
    - How to select a polynomial (from a table in one of the references)
    so that the generated sequence has particular properties?
    - How to make a *new* polynomial so that the generated sequence has
    particular properties?
    - How to find all possible polynomials of a particular length?
    - How to use non-linear feedback to make a sequence of length 2^N?
    - How to make a Bit Error Rate tester (BERT)? (a.k.a. how to detect an
    incoming sequence and accumulate the differences.)
    - What are the standard polynomials used for BERT?
    - How to turn the serial (one bit at a time) design into a parallel
    (multiple bits at a time) design that can work at interesting data
    rates?
    - How to design a scrambler for a modem?
    - How to design a direct sequence spread spectrum radio system?
    - How to use MLS for system frequency response measurements?


    I'm sure your quesion is in there somewhere, but you really must be
    more specific.

    These documents should get you started:
    http://www.xilinx.com/bvdocs/appnotes/xapp052.pdf
    http://www.xilinx.com/bvdocs/appnotes/xapp210.pdf

    Regards,
    Allan.
    Allan Herriman, Jan 28, 2004
    #2
    1. Advertising

  3. Spartan815

    Ronald Hecht Guest

    Spartan815 wrote:
    > Can anyone point me to a good resource on LFSRs? Theres alot I don't
    > know about them, my textbook lacks any actual information... I
    > appreciate any help thats out there... thanks!


    Some time ago I implemented a VHDL-function based on the XAPPs. This is
    my solution:

    package lfsr_pack is

    -- six taps are maximum
    type lfsr_taps_type is array (1 to 6) of integer;
    -- table for all taps, 3 to 168 bit-wide lfsr's are supported
    type lfsr_taps_table_type is array (3 to 168) of lfsr_taps_type;

    -- (C) 2000 Xilinx, Inc.
    -- XAPP052, XAPP210
    -- zero means no tap
    constant lfsr_taps_table : lfsr_taps_table_type := (
    (3, 2, 0, 0, 0, 0),
    (4, 3, 0, 0, 0, 0), (5, 3, 0, 0, 0, 0), (6, 5, 0, 0, 0, 0), (7, 6,
    0, 0, 0, 0),
    (8, 6, 5, 4, 0, 0), (9, 5, 0, 0, 0, 0), (10, 7, 0, 0, 0, 0), (11,
    9, 0, 0, 0, 0),
    (12, 6, 4, 1, 0, 0), (13, 4, 3, 1, 0, 0), (14, 5, 3, 1, 0, 0), (15,
    14, 0, 0, 0, 0),
    (16, 15, 13, 4, 0, 0), (17, 14, 0, 0, 0, 0), (18, 11, 0, 0, 0, 0),
    (19, 6, 2, 1, 0, 0),
    (20, 17, 0, 0, 0, 0), (21, 19, 0, 0, 0, 0), (22, 21, 0, 0, 0, 0),
    (23, 18, 0, 0, 0, 0),
    (24, 23, 22, 17, 0, 0), (25, 22, 0, 0, 0, 0), (26, 6, 2, 1, 0, 0),
    (27, 5, 2, 1, 0, 0),
    (28, 25, 0, 0, 0, 0), (29, 27, 0, 0, 0, 0), (30, 6, 4, 1, 0, 0),
    (31, 28, 0, 0, 0, 0),
    (32, 22, 2, 1, 0, 0), (33, 20, 0, 0, 0, 0), (34, 27, 2, 1, 0, 0),
    (35, 33, 0, 0, 0, 0),
    (36, 25, 0, 0, 0, 0), (37, 5, 4, 3, 2, 1), (38, 6, 5, 1, 0, 0),
    (39, 35, 0, 0, 0, 0),
    (40, 38, 21, 19, 0, 0), (41, 38, 0, 0, 0, 0), (42, 41, 20, 19, 0,
    0), (43, 42, 38, 37, 0, 0),
    (44, 43, 18, 17, 0, 0), (45, 44, 42, 41, 0, 0), (46, 45, 26, 25, 0,
    0), (47, 42, 0, 0, 0, 0),
    (48, 47, 21, 20, 0, 0), (49, 40, 0, 0, 0, 0), (50, 49, 24, 23, 0,
    0), (51, 50, 36, 35, 0, 0),
    (52, 49, 0, 0, 0, 0), (53, 52, 38, 37, 0, 0), (54, 53, 18, 17, 0,
    0), (55, 31, 0, 0, 0, 0),
    (56, 55, 35, 34, 0, 0), (57, 50, 0, 0, 0, 0), (58, 39, 0, 0, 0, 0),
    (59, 58, 38, 37, 0, 0),
    (60, 59, 0, 0, 0, 0), (61, 60, 46, 45, 0, 0), (62, 61, 6, 5, 0, 0),
    (63, 62, 0, 0, 0, 0),
    (64, 63, 61, 60, 0, 0), (65, 47, 0, 0, 0, 0), (66, 65, 57, 56, 0,
    0), (67, 66, 58, 57, 0, 0),
    (68, 59, 0, 0, 0, 0), (69, 67, 42, 40, 0, 0), (70, 69, 55, 54, 0,
    0), (71, 65, 0, 0, 0, 0),
    (72, 66, 25, 19, 0, 0), (73, 48, 0, 0, 0, 0), (74, 73, 59, 58, 0,
    0), (75, 74, 65, 64, 0, 0),
    (76, 75, 41, 40, 0, 0), (77, 76, 47, 46, 0, 0), (78, 77, 59, 58, 0,
    0), (79, 70, 0, 0, 0, 0),
    (80, 79, 43, 42, 0, 0), (81, 77, 0, 0, 0, 0), (82, 79, 47, 44, 0,
    0), (83, 82, 38, 37, 0, 0),
    (84, 71, 0, 0, 0, 0), (85, 84, 58, 57, 0, 0), (86, 85, 74, 73, 0,
    0), (87, 74, 0, 0, 0, 0),
    (88, 87, 17, 16, 0, 0), (89, 51, 0, 0, 0, 0), (90, 89, 72, 71, 0,
    0), (91, 90, 8, 7, 0, 0),
    (92, 91, 80, 79, 0, 0), (93, 91, 0, 0, 0, 0), (94, 73, 0, 0, 0, 0),
    (95, 84, 0, 0, 0, 0),
    (96, 94, 49, 47, 0, 0), (97, 91, 0, 0, 0, 0), (98, 87, 0, 0, 0, 0),
    (99, 97, 54, 52, 0, 0),
    (100, 63, 0, 0, 0, 0), (101, 100, 95, 94, 0, 0), (102, 101, 36, 35,
    0, 0), (103, 94, 0, 0, 0, 0),
    (104, 103, 94, 93, 0, 0), (105, 89, 0, 0, 0, 0), (106, 91, 0, 0, 0,
    0), (107, 105, 44, 42, 0, 0),
    (108, 77, 0, 0, 0, 0), (109, 108, 103, 102, 0, 0), (110, 109, 98,
    97, 0, 0), (111, 101, 0, 0, 0, 0),
    (112, 110, 69, 67, 0, 0), (113, 104, 0, 0, 0, 0), (114, 113, 33,
    32, 0, 0), (115, 114, 101, 100, 0, 0),
    (116, 115, 46, 45, 0, 0), (117, 115, 99, 97, 0, 0), (118, 85, 0, 0,
    0, 0), (119, 111, 0, 0, 0, 0),
    (120, 113, 9, 2, 0, 0), (121, 103, 0, 0, 0, 0), (122, 121, 63, 62,
    0, 0), (123, 121, 0, 0, 0, 0),
    (124, 87, 0, 0, 0, 0), (125, 124, 18, 17, 0, 0), (126, 125, 90, 89,
    0, 0), (127, 126, 0, 0, 0, 0),
    (128, 126, 101, 99, 0, 0), (129, 124, 0, 0, 0, 0), (130, 127, 0, 0,
    0, 0), (131, 130, 84, 83, 0, 0),
    (132, 103, 0, 0, 0, 0), (133, 132, 82, 81, 0, 0), (134, 77, 0, 0,
    0, 0), (135, 124, 0, 0, 0, 0),
    (136, 135, 11, 10, 0, 0), (137, 116, 0, 0, 0, 0), (138, 137, 131,
    130, 0, 0), (139, 136, 134, 131, 0, 0),
    (140, 111, 0, 0, 0, 0), (141, 140, 110, 109, 0, 0), (142, 121, 0,
    0, 0, 0), (143, 142, 123, 122, 0, 0),
    (144, 143, 75, 74, 0, 0), (145, 93, 0, 0, 0, 0), (146, 145, 87, 86,
    0, 0), (147, 146, 110, 109, 0, 0),
    (148, 121, 0, 0, 0, 0), (149, 148, 40, 39, 0, 0), (150, 97, 0, 0,
    0, 0), (151, 148, 0, 0, 0, 0),
    (152, 151, 87, 86, 0, 0), (153, 152, 0, 0, 0, 0), (154, 152, 27,
    25, 0, 0), (155, 154, 124, 123, 0, 0),
    (156, 155, 41, 40, 0, 0), (157, 156, 131, 130, 0, 0), (158, 157,
    132, 131, 0, 0), (159, 128, 0, 0, 0, 0),
    (160, 159, 142, 141, 0, 0), (161, 143, 0, 0, 0, 0), (162, 161, 75,
    74, 0, 0), (163, 162, 104, 103, 0, 0),
    (164, 163, 151, 150, 0, 0), (165, 164, 135, 134, 0, 0), (166, 165,
    128, 127, 0, 0), (167, 161, 0, 0, 0, 0),
    (168, 166, 153, 151, 0, 0));

    -- this function calculates the next lfsr value
    -- depending on the current value (cur_val)
    function next_lfsr (cur_val : std_logic_vector) return std_logic_vector;

    end lfsr_pack;

    package body lfsr_pack is

    function next_lfsr (cur_val : std_logic_vector) return
    std_logic_vector is
    variable next_val : std_logic_vector(cur_val'range);
    variable feedback : std_logic;
    begin
    -- initialize with '1' because '1' xnor X = X
    feedback := '1';
    for tap in 1 to 6 loop
    if lfsr_taps_table(cur_val'length)(tap) /= 0 then
    -- if not 0 do xnor
    feedback := feedback xnor
    cur_val(lfsr_taps_table(cur_val'length)(tap) - 1);
    end if;
    end loop; -- tap
    -- shift new feedback on right side in
    next_val := cur_val(cur_val'left - 1 downto cur_val'right) & feedback;
    -- and return it
    return next_val;
    end next_lfsr;

    end lfsr_pack;
    Ronald Hecht, Jan 28, 2004
    #3
  4. Spartan815

    David Jones Guest

    In article <>,
    Spartan815 <> wrote:
    >Can anyone point me to a good resource on LFSRs? Theres alot I don't
    >know about them, my textbook lacks any actual information... I
    >appreciate any help thats out there... thanks!


    Applied Cryptography, by Bruce Schneier.

    Everything you need to know...
    David Jones, Jan 28, 2004
    #4
  5. Spartan815

    Spartan815 Guest

    For anyone experienced with ModelSim and VHDL Im posting code below,
    and a do file. When I simulate it, it outputs the part I force, but
    it never changes. The way the code is written, I would expect things
    to change when the clock goes high. If anyone can catch an error in
    there (syntax or logic) Id be greatly appreciative...


    entity LFSR4_9 is
    port(clock:in bit; q:eek:ut bit_vector(3 downto 0));
    end;

    architecture RTL of LFSR4_9 is
    signal LFSR: bit_vector(3 downto 0);
    begin
    process(clock)
    begin
    if clock'EVENT and clock='1' then
    LFSR(0) <= LFSR(0) xor LFSR(3);
    LFSR(3 downto 1) <= LFSR(2 downto 0);
    end if;
    q <= LFSR;
    end process;
    end;


    Do File:
    force /LFSR4_9/LFSR 1000
    run 50ns
    force /LFSR4_9/clock 0
    run 50ns
    force /LFSR4_9/clock 1
    run 50ns
    force /LFSR4_9/clock 0
    run 50ns
    force /LFSR4_9/clock 1
    run 50ns
    force /LFSR4_9/clock 0
    run 50ns
    force /LFSR4_9/clock 1
    run 50ns
    force /LFSR4_9/clock 0
    run 50ns
    force /LFSR4_9/clock 1
    run 50ns
    force /LFSR4_9/clock 0
    run 50ns
    force /LFSR4_9/clock 1
    run 50ns
    force /LFSR4_9/clock 0
    run 50ns
    force /LFSR4_9/clock 1
    run 50ns
    force /LFSR4_9/clock 0
    Spartan815, Jan 28, 2004
    #5
  6. On Wed, 28 Jan 2004 12:25:57 GMT, (David Jones)
    wrote:

    >In article <>,
    >Spartan815 <> wrote:
    >>Can anyone point me to a good resource on LFSRs? Theres alot I don't
    >>know about them, my textbook lacks any actual information... I
    >>appreciate any help thats out there... thanks!

    >
    >Applied Cryptography, by Bruce Schneier.
    >
    >Everything you need to know...


    We have the second edition of Schneier here, and it says very little
    about LFSRs, and almost nothing about the hardware aspects.
    It does have a table of polynomials that goes further than XAPP052
    though.

    Interestingly, Schneier uses 0 rather than 1 as the origin for
    numbering taps. Much of the literature I've seen uses 1, and the
    difference can be a trap for the unwary.

    Regards,
    Allan.
    Allan Herriman, Jan 29, 2004
    #6
  7. Hi,

    (Spartan815) wrote:
    > process(clock)
    > begin
    > if clock'EVENT and clock='1' then
    > LFSR(0) <= LFSR(0) xor LFSR(3);
    > LFSR(3 downto 1) <= LFSR(2 downto 0);
    > end if;
    > q <= LFSR;
    > end process;


    Take the line q<=LFSR out of the process. Or do you like to have
    stupid latches?

    > Do File:
    > force /LFSR4_9/LFSR 1000
    > run 50ns


    Try writing a testbench doing the nasty thing for you.
    Your real error seems to me the force command without -deposit.
    If I'm right, a forced signal (without -deposit) will keep its value
    until the next force command for this signal occurs.

    bye Thomas
    Thomas Stanka, Jan 29, 2004
    #7
  8. On 28 Jan 2004 14:44:10 -0800, (Spartan815)
    wrote:

    >For anyone experienced with ModelSim and VHDL Im posting code below,
    >and a do file. When I simulate it, it outputs the part I force, but
    >it never changes. The way the code is written, I would expect things
    >to change when the clock goes high. If anyone can catch an error in
    >there (syntax or logic) Id be greatly appreciative...
    >
    >
    >entity LFSR4_9 is
    > port(clock:in bit; q:eek:ut bit_vector(3 downto 0));
    >end;
    >
    >architecture RTL of LFSR4_9 is
    > signal LFSR: bit_vector(3 downto 0);
    >begin
    > process(clock)
    > begin
    > if clock'EVENT and clock='1' then
    > LFSR(0) <= LFSR(0) xor LFSR(3);
    > LFSR(3 downto 1) <= LFSR(2 downto 0);
    > end if;
    > q <= LFSR;
    > end process;
    >end;


    In Modelsim, when you force the signal, it defaults to "-freeze" for
    unresolved signals (like your bit_vector). This will cause LFSR to
    stay the same (until you issue a noforce command), which is what you
    observe.
    The -deposit option on force may help here.


    Hint1: don't use force. Initialise your LFSR using the standard
    synchronous process template *with reset*. Drive the reset active at
    the start of simulation.

    Hint2: don't use bit_vector. Use std_logic or std_ulogic instead.


    Your next problem will be that there is no lockup detection. If LFSR
    ever becomes "0000" it will stay that way forever.
    There are two approaches:
    1. Intialise LFSR to something that has at least one '1' in it.
    2. Detect the "0000" state somehow, and force a bit to '1'.

    #2 is more robust in the real world, but uses more logic.

    >
    >Do File:
    >force /LFSR4_9/LFSR 1000
    >run 50ns
    >force /LFSR4_9/clock 0

    [snip]
    >run 50ns
    >force /LFSR4_9/clock 1
    >run 50ns
    >force /LFSR4_9/clock 0


    This is a very crude way to toggle a clock.

    Try writing a test bench that instantiates your design, and generate
    the clock this way:

    signal clk : std_logic := '0';

    ....

    clk <= not clk after 50 ns;

    (There are other ways of toggle a clock that are roughly equivalent.
    See the FAQ.)

    Regards,
    Allan.
    Allan Herriman, Jan 29, 2004
    #8
  9. Spartan815

    David Jones Guest

    In article <>,
    Allan Herriman <> wrote:
    >On Wed, 28 Jan 2004 12:25:57 GMT, (David Jones)
    >wrote:
    >
    >>In article <>,
    >>Spartan815 <> wrote:
    >>>Can anyone point me to a good resource on LFSRs? Theres alot I don't
    >>>know about them, my textbook lacks any actual information... I
    >>>appreciate any help thats out there... thanks!

    >>
    >>Applied Cryptography, by Bruce Schneier.
    >>
    >>Everything you need to know...

    >
    >We have the second edition of Schneier here, and it says very little
    >about LFSRs, and almost nothing about the hardware aspects.
    >It does have a table of polynomials that goes further than XAPP052
    >though.


    Nothing?

    There is a diagram of a Fibonacci configuration on p. 374, and a diagram
    of a Galois configuration on p. 379. You should be able to come up with
    VHDL code for those.

    You can't really simplify XOR functions, so the naive hardware implementations
    are the way to go for 1-bit output LFSRs.

    About the only thing not covered is parallel implementations (i.e.
    computing the CRC of 4-bit Ethernet MII data), but that is no longer
    strictly an LFSR. High-school algebra will carry the day here.
    David Jones, Jan 29, 2004
    #9
  10. (David Jones) writes:

    > In article <>,
    > Allan Herriman <> wrote:
    > >On Wed, 28 Jan 2004 12:25:57 GMT, (David Jones)
    > >wrote:
    > >
    > >>In article <>,
    > >>Spartan815 <> wrote:
    > >>>Can anyone point me to a good resource on LFSRs? Theres alot I don't
    > >>>know about them, my textbook lacks any actual information... I
    > >>>appreciate any help thats out there... thanks!
    > >>
    > >>Applied Cryptography, by Bruce Schneier.
    > >>
    > >>Everything you need to know...

    > >
    > >We have the second edition of Schneier here, and it says very little
    > >about LFSRs, and almost nothing about the hardware aspects.
    > >It does have a table of polynomials that goes further than XAPP052
    > >though.

    >
    > Nothing?
    >
    > There is a diagram of a Fibonacci configuration on p. 374, and a diagram
    > of a Galois configuration on p. 379. You should be able to come up with
    > VHDL code for those.
    >
    > You can't really simplify XOR functions, so the naive hardware implementations
    > are the way to go for 1-bit output LFSRs.
    >
    > About the only thing not covered is parallel implementations (i.e.
    > computing the CRC of 4-bit Ethernet MII data), but that is no longer
    > strictly an LFSR. High-school algebra will carry the day here.


    That, http://www.easics.ne/webtools/crctool and the posting Allan did
    about computing the Ethernet CRC over 64bit data about a year ago rules the day.

    /PS: Allan, that article was great help recently when we had to make a
    10G MAC run in an fpga @ 156.25MHz.

    Regards,


    Kai
    Kai Harrekilde-Petersen, Jan 29, 2004
    #10
  11. Spartan815

    VhdlCohen Guest

    I have at my site, under models and papers an LFSR package that addresses
    several widths.
    -----------------------------------------------------------------------------
    Ben Cohen Trainer, Consultant, Publisher (310) 721-4830
    http://www.vhdlcohen.com/
    Author of following textbooks:
    * Using PSL/SUGAR for Formal and Dynamic Verification 2nd Edition, 2004 isbn
    0-9705394-6-0
    * Real Chip Design and Verification Using Verilog and VHDL, 2002 isbn
    0-9705394-2-8
    * Component Design by Example ", 2001 isbn 0-9705394-0-1
    * VHDL Coding Styles and Methodologies, 2nd Edition, 1999 isbn 0-7923-8474-1
    * VHDL Answers to Frequently Asked Questions, 2nd Edition, isbn 0-7923-8115
    ------------------------------------------------------------------------------
    VhdlCohen, Jan 29, 2004
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    5
    Views:
    4,407
    OutputLogic
    May 22, 2009
  2. LFSR code

    , Mar 28, 2007, in forum: VHDL
    Replies:
    4
    Views:
    3,178
    Mike Treseler
    Mar 28, 2007
  3. mn19

    LFSR

    mn19, Jun 12, 2007, in forum: VHDL
    Replies:
    1
    Views:
    848
    Mike Treseler
    Jun 12, 2007
  4. timewing

    Is it correct to build a LFSR?

    timewing, Aug 30, 2008, in forum: VHDL
    Replies:
    0
    Views:
    513
    timewing
    Aug 30, 2008
  5. Martin
    Replies:
    6
    Views:
    1,027
Loading...

Share This Page