LFSR Taps for 64 bit registers?

[Dave Feustel]

I'm looking for taps for 64-bit linear feedback shift registers.
Can someone post either values for such taps or a source
of information for generating the taps?

Thanks,

Dave Feustel
Fort Wayne, Indiana

[Mark Curry]

Dave,

Xilinx has an excellent app note:

http://www.xilinx.com/xapp/xapp052.pdf

Regards,

Mark

[Peter Alfke]

I checked several sources, and they agree:
Take a 64-bit shift register.
Number the bits 1 through 64 ( that's the habit of the folks in
LFSR and Crypto-land)
Generate the XNOR of outputs Q60, Q61, Q63, and Q64.
XNOR means "even parity", ( the output of the XNOR is a 1 if 0, 2
or 4 of the inputs are 1. Maybe that's a dumb use of the word
"exclusive", but that's the way it is.)
You could also have picked XOR = odd parity, but that would have
made the all-zero state persistent ( and thus illegal). Most
circuitry has a reset input, perhaps even a power-on reset, that
makes it more meaningful to make all-zeros legal as the starting
code, and make the all-ones illegal. The normal sequence never gets
you into the illegal state, but if you ever get there, you are
stuck. And a detector costs you some gating and might sacrifice
speed.

Of course, you can put the first 60 bits into a RAM, and the SRL16
in Virtex is especially nice and cheap, since you can stuff up to
16 shift-register bits into a 4-input Look-Up-Table (LUT).

Good luck, and tell us when you reach max count.
It will take more than 5,000 years @ 100 MHz, so don't hold your
breath. :-)

Peter Alfke, Xilinx Applications
==============================================================

[Pjc]

please tell me how to design a fast (unsigned)32bit divider
thanks

[Tim Jaynes]

Hi Dave,
Peter Alfke's done this in a Xilinx application note:
http://support.xilinx.com/xapp/xapp210.pdf
On page 4-5 it lists the taps for maximum-length LFSR counters up to 168
bits.
Regards,
Tim Jaynes
CAE

[glen herrmannsfeldt]

"Pjc" <p...@tomail.com.tw> writes:

>please tell me how to design a fast (unsigned)32bit divider
>thanks

How fast, and how much hardware can you supply to it?

There is always a tradeoff.

Are both dividend and divisor 32 bits?
(Traditionally, the dividend is twice as long as the divisor.)

-- glen

[Peter Alfke]

glen herrmannsfeldt wrote:

> How fast, and how much hardware can you supply to it?
>
> There is always a tradeoff.
>
> Are both dividend and divisor 32 bits?
> (Traditionally, the dividend is twice as long as the divisor.)
>

And is the divisor realy a variable, or is it fairly stable and
1/x can be pre-computed, so that the problem becomes one of
multiplication ?
As an aside: Virtex-II now has many 18 x 18 combinatorial
multipliers that can help speed up the division, if you go for
the one-bit-per -clock successsive approximation method...

Peter Alfke, Xilinx Applications

[eteam]

There also some compact radix-4 divide algorithms that use
add/subtract/accumulate rather than multiply in the
"inner loop". I designed one at Bipolar Integrated Technology in
the mid-80s, based largely on work published by a Greg Taylor.

I'm unfamiliar with the V-II multiplier block performance, but
using add/sub/acc usually results in a very fast iteration cycle.

-- Bob Elkind, et...@aracnet.com

You might turn up some references with some web searching...

[Subbu Meiyappan]

Pick up any Error Control Coding / Algebraic coding book (for example Lin
and Costello or Wicker) and their
appendices usually have the minimal polynomials for different lengths.

HTH,
Subbu
"Dave Feustel" <dfeu...@mindspring.com> wrote in message
news:9ec4nt$ipc$1...@slb6.atl.mindspring.net...

[Ray Andraka]

If you need just one feedback combination, one of the xilinx app notes lists
the feedback taps for LFSRs from 3 bits to 168 bits. I think it is XAPP052,
but my memory might not be accurate. I do have a link directly to the app
note on the links page of my website.

Subbu Meiyappan wrote:

--
-Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email r...@andraka.com
http://www.andraka.com

[VhdlCohen]

See my web site for an lfsr implementation in vhdl.
--------------------------------------------------------------------------
----------------------------------------
Ben Cohen     Publisher, Trainer, Consultant    (310) 721-4830
http://www.vhdlcohen.com/                 vhdl...@aol.com  
Author of following textbooks:
* Component Design by Example ... a Step-by-Step Process Using
  VHDL with UART as Vehicle",  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
--------------------------------------------------------------------------
------------------------------------------

[glen herrmannsfeldt]

>"Dave Feustel" <dfeu...@mindspring.com> wrote in message
>news:9ec4nt$ipc$1...@slb6.atl.mindspring.net...
>> I'm looking for taps for 64-bit linear feedback shift registers.
>> Can someone post either values for such taps or a source
>> of information for generating the taps?

If you want the longest period, then you want what is called a
primitive polynomial modulo 2. There are a number of descriptions,
the one I have is in "Numerical Recipes in C".

(64,4,3,1,0). Depending on which way you put the logic together
(there are symmetry operations), that is taps 0, 1, 3, 4.

-- glen

[Bitter Spock]

Go to www.xilinx.com,
search for LFSR,
There is a PDF doc there with a table of all the LFSR
feedback taps positions for an N-bit LFSR.

64-bits is among them. I wave empirically proven using
C-code that the 16-bit and 32-bit are indeed maximal length. I would expect
I could trust the others too.

Regards,

Spock

"Subbu Meiyappan" <msu...@cisco.com> wrote in message
news:993161117.666970@sj-nntpcache-3...