LFSR

S

Spartan815

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!
 
A

Allan Herriman

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.
 
R

Ronald Hecht

Spartan815 said:
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;
 
D

David Jones

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...
 
S

Spartan815

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
 
A

Allan Herriman

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.
 
T

Thomas Stanka

Hi,

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
 
A

Allan Herriman

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.
 
D

David Jones

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.
 
K

Kai Harrekilde-Petersen

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
 
V

VhdlCohen

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/ (e-mail address removed)
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
------------------------------------------------------------------------------
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,829
Latest member
PIXThurman

Latest Threads

Top