LFSR

S

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!
 
On 27 Jan 2004 18:47:48 -0800, absolutspartan@hotmail.com (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!
Click to expand...
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.
 
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!
Click to expand...
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;
 
In article <d8a1d17c.0401271847.771cc2cb@posting.google.com>,
Spartan815 <absolutspartan@hotmail.com> 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!
Click to expand...
Applied Cryptography, by Bruce Schneier.

Everything you need to know...
 
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
 
On Wed, 28 Jan 2004 12:25:57 GMT, dej@coup.inode.org (David Jones)
wrote:

In article <d8a1d17c.0401271847.771cc2cb@posting.google.com>,
Spartan815 <absolutspartan@hotmail.com> 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...
Click to expand...
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.
 
Hi,

absolutspartan@hotmail.com (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;
Click to expand...
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
Click to expand...
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
 
On 28 Jan 2004 14:44:10 -0800, absolutspartan@hotmail.com (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;
Click to expand...
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
Click to expand...
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.
 
In article <roqg10dhohj42dm2e9bos5sn35qj1fdkt5@4ax.com>,
Allan Herriman <allan.herriman.hates.spam@ctam.com.au.invalid> wrote:
On Wed, 28 Jan 2004 12:25:57 GMT, dej@coup.inode.org (David Jones)
wrote:

In article <d8a1d17c.0401271847.771cc2cb@posting.google.com>,
Spartan815 <absolutspartan@hotmail.com> 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.
Click to expand...
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.
 
dej@coup.inode.org (David Jones) writes:

In article <roqg10dhohj42dm2e9bos5sn35qj1fdkt5@4ax.com>,
Allan Herriman <allan.herriman.hates.spam@ctam.com.au.invalid> wrote:
On Wed, 28 Jan 2004 12:25:57 GMT, dej@coup.inode.org (David Jones)
wrote:

In article <d8a1d17c.0401271847.771cc2cb@posting.google.com>,
Spartan815 <absolutspartan@hotmail.com> 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.
Click to expand...
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
 
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/ vhdlcohen@aol.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
------------------------------------------------------------------------------
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top