Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!sdd.hp.com!hp-pcd!hplsla!tomb
From: tomb@hplsla.HP.COM (Tom Bruhns)
Newsgroups: sci.electronics
Subject: Re: Pseudo-random numbers
Message-ID: <5170126@hplsla.HP.COM>
Date: 1 Apr 91 17:41:12 GMT
References: <1991Mar27.101754.5326@specialix.co.uk>
Organization: HP Lake Stevens, WA
Lines: 26

>ressler@galileo.ifa.hawaii.edu (Mike "IR" Ressler) writes:
>In article <1991Mar27.101754.5326@specialix.co.uk> stevem@specialix.co.uk (Steven Murray) writes:
>>
>>There's the rub, has anyone got a definitive list of PRBS taps?
>>I saw one in a book once - a reference text - but didn't copy it.
>>The length of the PRBS sequence with proper taps ('maximal length')
>>is normally (2^n)-1, where n is the number of S/R bits - without
>>getting greedy, I saw taps for a 33 bit SR once - has anyone got
>>the taps for anything longer?
>
>Try page 227 of Numerical Recipes in C by William Press et al (Cambridge
>University Press). They give a table of primitive polynomials (taps) out to
>order 100 (100 bits). They are obviously mostly concerned about software
>implementations, but discuss it in hardware terms enough to be useful.
>Besides, they give the taps for ALL orders up to and including 100.
>----------

Actually, I doubt you want catalog of _all_ maximal length boolean
polynomials, even up to order 32, since there are somewhere around
2^25 of them.  And it just gets worse as the order gets larger ;-).
It's fun to test different polynomials to see which gives the best
results for a particular application (if the application is critical
enough to warrant it).  See Knuth's 'Algorithms...' book (I don't
recall the volume) for a good discussion of finding prime polynomials.
I've used search techniques to find them up to order 48 or so, but
it starts chewing up lots of CPU time and isn't real efficient.