So, I needed to generate a bunch of different length sequences, and thought that the easiest way would be to use a code in an LFSR. I couldn't find any handy tables of polynomials (I know they're out there -- I think I even have one in a book someplace), so I whomped up a quick sieve and made a bunch of them. I had _thought_ that an LFSR defined by any degree N prime polynomial would emit a sequence of 2^N-1 bits before it repeated itself, but my sieve came up with x^6 + x^3 + 1, which makes a sequence that's 9 -- count 'em -- 9 bits long before it repeats. Clearly either my memory of the rule is incorrect, or my sieve has allowed a non-prime number through, or I have made some other dumb mistake. Is someone out there up to correcting my thinking? (And if you happen to know of a handy table of polynomials for LFSRs, feel free to speak up). -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Polynomial Codes, where is my mistake?
Started by ●March 29, 2012
Reply by ●March 29, 20122012-03-29
On Thu, 29 Mar 2012 11:51:31 -0500 Tim Wescott <tim@seemywebsite.com> wrote:> So, I needed to generate a bunch of different length sequences, and > thought that the easiest way would be to use a code in an LFSR. > > I couldn't find any handy tables of polynomials (I know they're out there > -- I think I even have one in a book someplace), so I whomped up a quick > sieve and made a bunch of them. > > I had _thought_ that an LFSR defined by any degree N prime polynomial > would emit a sequence of 2^N-1 bits before it repeated itself, but my > sieve came up with > > x^6 + x^3 + 1, > > which makes a sequence that's 9 -- count 'em -- 9 bits long before it > repeats. > > Clearly either my memory of the rule is incorrect, or my sieve has > allowed a non-prime number through, or I have made some other dumb > mistake. > > Is someone out there up to correcting my thinking? (And if you happen to > know of a handy table of polynomials for LFSRs, feel free to speak up). > > -- > My liberal friends think I'm a conservative kook. > My conservative friends think I'm a liberal kook. > Why am I not happy that they have found common ground? > > Tim Wescott, Communications, Control, Circuits & Software > http://www.wescottdesign.comI've never managed to come close to following the math of all this, but there's a good table of all the maximal-length LFSRs at the back of the late, great Peter Alfke's Xilinx app note XAPP052. -- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix.
Reply by ●March 29, 20122012-03-29
>So, I needed to generate a bunch of different length sequences, and >thought that the easiest way would be to use a code in an LFSR. > >I couldn't find any handy tables of polynomials (I know they're out there>-- I think I even have one in a book someplace), so I whomped up a quick >sieve and made a bunch of them. > >I had _thought_ that an LFSR defined by any degree N prime polynomial >would emit a sequence of 2^N-1 bits before it repeated itself, but my >sieve came up with > >x^6 + x^3 + 1, > >which makes a sequence that's 9 -- count 'em -- 9 bits long before it >repeats. > >Clearly either my memory of the rule is incorrect, or my sieve has >allowed a non-prime number through, or I have made some other dumb >mistake. > >Is someone out there up to correcting my thinking? (And if you happen to>know of a handy table of polynomials for LFSRs, feel free to speak up). > >-- >My liberal friends think I'm a conservative kook. >My conservative friends think I'm a liberal kook. >Why am I not happy that they have found common ground? > >Tim Wescott, Communications, Control, Circuits & Software >http://www.wescottdesign.com >I think only maximum length sequences guarantee n=2^m-1 length (repetition)
Reply by ●March 29, 20122012-03-29
On Thu, 29 Mar 2012 10:09:46 -0700, Rob Gaddi wrote:> On Thu, 29 Mar 2012 11:51:31 -0500 > Tim Wescott <tim@seemywebsite.com> wrote: > >> So, I needed to generate a bunch of different length sequences, and >> thought that the easiest way would be to use a code in an LFSR. >> >> I couldn't find any handy tables of polynomials (I know they're out >> there -- I think I even have one in a book someplace), so I whomped up >> a quick sieve and made a bunch of them. >> >> I had _thought_ that an LFSR defined by any degree N prime polynomial >> would emit a sequence of 2^N-1 bits before it repeated itself, but my >> sieve came up with >> >> x^6 + x^3 + 1, >> >> which makes a sequence that's 9 -- count 'em -- 9 bits long before it >> repeats. >> >> Clearly either my memory of the rule is incorrect, or my sieve has >> allowed a non-prime number through, or I have made some other dumb >> mistake. >> >> Is someone out there up to correcting my thinking? (And if you happen >> to know of a handy table of polynomials for LFSRs, feel free to speak >> up). >> >> -- >> My liberal friends think I'm a conservative kook. My conservative >> friends think I'm a liberal kook. Why am I not happy that they have >> found common ground? >> >> Tim Wescott, Communications, Control, Circuits & Software >> http://www.wescottdesign.com > > I've never managed to come close to following the math of all this, but > there's a good table of all the maximal-length LFSRs at the back of the > late, great Peter Alfke's Xilinx app note XAPP052.Well, apparently I don't follow it as well as I thought I had. That table isn't _all_ of the maximal-length LFSRs, by the way -- just one for each number of bits in the register. There's way more possibilities, but most of them require a lot more taps. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by ●March 29, 20122012-03-29
On Thu, 29 Mar 2012 12:26:48 -0500, jacobfenton wrote:>>So, I needed to generate a bunch of different length sequences, and >>thought that the easiest way would be to use a code in an LFSR. >> >>I couldn't find any handy tables of polynomials (I know they're out >>there > >>-- I think I even have one in a book someplace), so I whomped up a quick >>sieve and made a bunch of them. >> >>I had _thought_ that an LFSR defined by any degree N prime polynomial >>would emit a sequence of 2^N-1 bits before it repeated itself, but my >>sieve came up with >> >>x^6 + x^3 + 1, >> >>which makes a sequence that's 9 -- count 'em -- 9 bits long before it >>repeats. >> >>Clearly either my memory of the rule is incorrect, or my sieve has >>allowed a non-prime number through, or I have made some other dumb >>mistake. >> >>Is someone out there up to correcting my thinking? (And if you happen >>to > >>know of a handy table of polynomials for LFSRs, feel free to speak up). >> >>-- >>My liberal friends think I'm a conservative kook. My conservative >>friends think I'm a liberal kook. Why am I not happy that they have >>found common ground? >> >>Tim Wescott, Communications, Control, Circuits & Software >>http://www.wescottdesign.com >> >> > I think only maximum length sequences guarantee n=2^m-1 length > (repetition)Well, yes, but I thought that if the polynomial were prime that meant that the sequence would be maximal length -- if that's not my error, then I have a bug in my sieve. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by ●March 29, 20122012-03-29
On 3/29/12 12:51 PM, Tim Wescott wrote:> So, I needed to generate a bunch of different length sequences, and > thought that the easiest way would be to use a code in an LFSR. > > I couldn't find any handy tables of polynomials (I know they're out there > -- I think I even have one in a book someplace), so I whomped up a quick > sieve and made a bunch of them. > > I had _thought_ that an LFSR defined by any degree N prime polynomial > would emit a sequence of 2^N-1 bits before it repeated itself, but my > sieve came up with > > x^6 + x^3 + 1, > > which makes a sequence that's 9 -- count 'em -- 9 bits long before it > repeats. >are you sure that's a primitive polynomial? or that you set of the LFSR correctly, based on it? approximately the only math i know about this is at http://www.dspguru.com/dsp/tutorials/a-little-mls-tutorial there's a couple of other things. the only way that i know how to get a primitive polynomial is to test it with an LFSR and try out all possible combinations (let the computer do this overnight). i am sure that some Galois kinda mathematician would know other ways. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 29, 20122012-03-29
On Thu, 29 Mar 2012 17:20:29 -0400, robert bristow-johnson wrote:> On 3/29/12 12:51 PM, Tim Wescott wrote: >> So, I needed to generate a bunch of different length sequences, and >> thought that the easiest way would be to use a code in an LFSR. >> >> I couldn't find any handy tables of polynomials (I know they're out >> there -- I think I even have one in a book someplace), so I whomped up >> a quick sieve and made a bunch of them. >> >> I had _thought_ that an LFSR defined by any degree N prime polynomial >> would emit a sequence of 2^N-1 bits before it repeated itself, but my >> sieve came up with >> >> x^6 + x^3 + 1, >> >> which makes a sequence that's 9 -- count 'em -- 9 bits long before it >> repeats. >> >> > are you sure that's a primitive polynomial? or that you set of the LFSR > correctly, based on it? > > approximately the only math i know about this is at > > http://www.dspguru.com/dsp/tutorials/a-little-mls-tutorial > > there's a couple of other things. > > the only way that i know how to get a primitive polynomial is to test it > with an LFSR and try out all possible combinations (let the computer do > this overnight). i am sure that some Galois kinda mathematician would > know other ways.I was conflating irreducible, primitive, and prime. Irreducible polynomials in a G(p) field are a cognate of prime numbers (in fact, you can find them efficiently using a Sieve of Eratosthenes), but an irreducible polynomial isn't necessarily primitive. And, x^6 + x^3 + 1, while it certainly seems to be irreducible, isn't primitive, as I have just found out by doing the test. Oh, you learn something new every day. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by ●March 30, 20122012-03-30
On 3/29/12 12:51 PM, Tim Wescott wrote:> (And if you happen to > know of a handy table of polynomials for LFSRs, feel free to speak up). >i've seen some (and thought that Wikipedia sent me to them), but do not know exactly where they were at. found this: http://deepblue.lib.umich.edu/handle/2027.42/6596 looks like he has results in octal from the high-speed printer connected to a mainframe before i graduated from high school. or maybe http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html but i saw something better not to long ago. dunno where it was. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 30, 20122012-03-30
On Thu, 29 Mar 2012 10:09:46 -0700, Rob Gaddi wrote:> On Thu, 29 Mar 2012 11:51:31 -0500 Tim Wescott <tim@seemywebsite.com> > wrote: > >> So, I needed to generate a bunch of different length sequences, and >> thought that the easiest way would be to use a code in an LFSR. >> >> I couldn't find any handy tables of polynomials (I know they're out >> there -- I think I even have one in a book someplace), so I whomped up >> a quick sieve and made a bunch of them. >> >> I had _thought_ that an LFSR defined by any degree N prime polynomial >> would emit a sequence of 2^N-1 bits before it repeated itself, but my >> sieve came up with >> >> x^6 + x^3 + 1, >> >> which makes a sequence that's 9 -- count 'em -- 9 bits long before it >> repeats. >> >> Clearly either my memory of the rule is incorrect, or my sieve has >> allowed a non-prime number through, or I have made some other dumb >> mistake. >> >> Is someone out there up to correcting my thinking? (And if you happen >> to know of a handy table of polynomials for LFSRs, feel free to speak >> up). >> >> -- >> My liberal friends think I'm a conservative kook. >> My conservative friends think I'm a liberal kook. >> Why am I not happy that they have found common ground? >> >> Tim Wescott, Communications, Control, Circuits & Software >> http://www.wescottdesign.com > > I've never managed to come close to following the math of all this, but > there's a good table of all the maximal-length LFSRs at the back of the > late, great Peter Alfke's Xilinx app note XAPP052.More lists that might be useful: XAPP210 (which repeats the info from XAPP052) http://www.xilinx.com/support/documentation/application_notes/xapp210.pdf ITU-T O.150 standard LFSRs for BERT. "Digital test patterns for performance measurements on digital transmission equipment" http://www.itu.int/itu-t/recommendations/index.aspx?ser=O LFSRs with "dense" taps: http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/misc.txt Regards, Allan
Reply by ●March 30, 20122012-03-30
On Thu, 29 Mar 2012 10:09:46 -0700, Rob Gaddi <rgaddi@technologyhighland.invalid> wrote:>On Thu, 29 Mar 2012 11:51:31 -0500 >Tim Wescott <tim@seemywebsite.com> wrote: >[Snipped by Lyons]> >I've never managed to come close to following the math of all this, but >there's a good table of all the maximal-length LFSRs at the back of the >late, great Peter Alfke's Xilinx app note XAPP052.Hi Rob (& Tim), Alfke's 'app note' is at: http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf [-Rick-]
