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 <t...@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?
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.
-- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix.
>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?
On Thu, 29 Mar 2012 10:09:46 -0700, Rob Gaddi wrote:
> On Thu, 29 Mar 2012 11:51:31 -0500
> Tim Wescott <t...@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?
> 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?
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?
> 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?
On Mar 29, 1:34 pm, Tim Wescott <t...@seemywebsite.com> wrote:
> 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.
The more commonly used name for what you call a
prime polynomial is an _irreducible_ polynomial, meaning
that it cannot be factored into two polynomials of
smaller degree except trivially as f(x) = 1.f(x). This
is analogous to the concept of primes amongst integers.
However, with polynomials, there is an additional
twist: some irreducible polynomials are called _primitive_
polynomials and these primitive polynomials enjoy the
property that the corresponding LFSR generates a
maximal-length sequence of period 2^n - 1 where
n is the degree of the polynomial. What you have
found is an irreducible NONprimitive polynomial
of degree n = 6. The sequences generated by such
polynomials have periods that _divide_ 2^n - 1. In
this case, 9 is a divisor of 2^6 - 1 = 63.
If you want to have more fun, try x^4 + x^3 + x^2 + x + 1
as an LFSR feedback polynomial. This is an
irreducible polynomial (trust me on this, but verify
if you don't want to be thought of as gullible). What
sequence does it generate?
> 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
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.
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
> 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?
On Thu, 29 Mar 2012 10:09:46 -0700, Rob Gaddi wrote:
> On Thu, 29 Mar 2012 11:51:31 -0500 Tim Wescott <t...@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?
> 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.
>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.
> (And if you happen to
> know of a handy table of polynomials for LFSRs, feel free to speak up).
There is an excellent table of LFSR polynomials in [1].
[1] W. Stahnke, Primitive Binary Polynomials, Mathematics of Computation, vol. 27, no. 124, pp. 977980, Oct. 1973.
These may or may not be useful for your application. They were probably generated during a time when mainframe computing was all the rage and most scientists wore lab coats and ties. I've used the polynomials in this paper for generating maximum length sequences and I think that they work well.
> There is an excellent table of LFSR polynomials in [1].
> [1] W. Stahnke, Primitive Binary Polynomials,
> Computation, vol. 27, no. 124, pp. 977???980, Oct. 1973.
There is a table of CRC polynomials, and some description of
them, in Numerical Recipes.
Not exactly the same as LFSR polynomials, but usually
pretty close.
On Apr 1, 4:08 pm, Nicholas Kinar <n.ki...@usask.ca> wrote:
> [1] W. Stahnke, Primitive Binary Polynomials, Mathematics of
> Computation, vol. 27, no. 124, pp. 977980, Oct. 1973.
Stahnke's paper (available on-line for free from the American
Mathematical Society) deals with polynomials of higher degrees
than commonly available in tables. The abstract reads
"One primitive polynomial modulo two is listed for each degree n
through n = 168. Each polynomial has the minimum number of
terms possible for its degree. The method used to generate the
list is described."
In contrast, the book Error-Correcting Codes by Peterson and
Weldon (MIT Press) contains a list of _all_ irreducible binary
polynomials (primitive and non-primitive) of degrees up to 16.
Cryptic annotations are used to inform the reader of various
properties (primitive polynomials are marked E, F, G, H;
nonprimitive are A, B, C, D).
On Sun, 01 Apr 2012 20:28:28 +0000, glen herrmannsfeldt wrote:
> Nicholas Kinar <n.ki...@usask.ca> wrote:
> (snip)
>> There is an excellent table of LFSR polynomials in [1].
>> [1] W. Stahnke, Primitive Binary Polynomials,
>> Computation, vol. 27, no. 124, pp. 977???980, Oct. 1973.
> There is a table of CRC polynomials, and some description of
> them, in Numerical Recipes.
> Not exactly the same as LFSR polynomials, but usually
> pretty close.
> -- glen
Some of the CRC polynomials make good LFSRs; some don't.
We're all familiar with the "CRC32" that is used in Ethernet and several other protocols. It was decided on after much research into choosing polys to give good error detection.
Presumably due to the limited amount of compute grunt available in the Dark Ages, CRC32 wasn't chosen from an exhaustive search and isn't optimal; better 32 bit polys exist.
One such better poly is "CRC32C" a.k.a. "Castagnoli" that is used in iSCSI and several other protocols. It has better error detection properties than the Ethernet CRC32 (over the range of possible Ethernet frame sizes).
The thing that gets me about CRC32C is that it isn't primitive. The polynomial has an even number of terms and has (x+1) as a factor.
To me this is counterintuitive - I would have expected it to be primitive.
Getting back on topic ... CRC32C would make a bad LFSR despite being a good CRC.
On Apr 1, 10:53 pm, Allan Herriman <allanherri...@hotmail.com> wrote:
> The thing that gets me about CRC32C is that it isn't primitive. The
> polynomial has an even number of terms and has (x+1) as a factor.
> To me this is counterintuitive - I would have expected it to be primitive.
A CRC polynomial with a x+1 factor is guaranteed to detect
3 bit errors, but fails to detect some 4-bit error patterns. A
primitive polynomial used as a CRC is guaranteed to detect
2 bit errors but fails to detect some 3-bit error patterns. So
there _is_ a reason why many CRC polynomials have x+1
as a factor.
Allan Herriman <allanherri...@hotmail.com> writes:
> [...]
> The thing that gets me about CRC32C is that it isn't primitive. The
> polynomial has an even number of terms and has (x+1) as a factor. To
> me this is counterintuitive - I would have expected it to be
> primitive.
Allan,
Did you mean "irreducible?" I thought a primitive polynomial is one in
which none of the coefficients can be factored by a common factor. E.g.,
see the second definition here:
On Sun, 01 Apr 2012 23:07:01 -0500, Randy Yates wrote:
> Allan Herriman <allanherri...@hotmail.com> writes:
>> [...]
>> The thing that gets me about CRC32C is that it isn't primitive. The
>> polynomial has an even number of terms and has (x+1) as a factor. To me
>> this is counterintuitive - I would have expected it to be primitive.
> Allan,
> Did you mean "irreducible?" I thought a primitive polynomial is one in
> which none of the coefficients can be factored by a common factor. E.g.,
> see the second definition here:
Allan Herriman <allanherri...@hotmail.com> writes:
> [...]
> If it's not irreducible, it's not primitive.
Not true. Gauss's lemma states that the product of two primitive
polynomials is also primitive.
-- Randy Yates
DSP/Firmware Engineer
919-577-9882 (H)
919-720-2916 (C)
On Mon, 02 Apr 2012 06:41:57 -0500, Randy Yates wrote:
> Allan Herriman <allanherri...@hotmail.com> writes:
>> [...]
>> If it's not irreducible, it's not primitive.
> Not true. Gauss's lemma states that the product of two primitive
> polynomials is also primitive.
I think I get it now.
The Wikipedia page for Primitive Polynomials (field theory) states quite clearly "all primitive polynomials are ... irreducible." In this context a polynomial is irreducible if it cannot be expressed as the product of two or more polynomials.
The Wikipedia page for Primitive Polynomials (ring theory) redirects to the Gauss's Lemma page, which states quite clearly "the product of two primitive polynomials is also primitive ..."
Since a field is a ring, these two Wikipedia pages seem to contradict each other. Either that, or I'm really confused.
Allan Herriman <allanherri...@hotmail.com> writes:
> On Mon, 02 Apr 2012 06:41:57 -0500, Randy Yates wrote:
>> Allan Herriman <allanherri...@hotmail.com> writes:
>>> [...]
>>> If it's not irreducible, it's not primitive.
>> Not true. Gauss's lemma states that the product of two primitive
>> polynomials is also primitive.
> I think I get it now.
> The Wikipedia page for Primitive Polynomials (field theory) states quite > clearly "all primitive polynomials are ... irreducible." In this context > a polynomial is irreducible if it cannot be expressed as the product of > two or more polynomials.
> The Wikipedia page for Primitive Polynomials (ring theory) redirects to > the Gauss's Lemma page, which states quite clearly "the product of two > primitive polynomials is also primitive ..."
You are correct. I was correct, but not correct. (!)
The problem is that there are two definitions for primitive polynomial;
I was correct with respect to one definition (the ring theory one), but
that definition isn't the one that applies to LFSRs (the finite field
one).
> Since a field is a ring, these two Wikipedia pages seem to contradict > each other.
No, because they are two different definitions of "primitive
polynomial."
> Either that, or I'm really confused.
Well, I seem to be a member of an elite club then, Allan. :)
-- Randy Yates
DSP/Firmware Engineer
919-577-9882 (H)
919-720-2916 (C)
On Mon, 02 Apr 2012 13:29:40 -0500, Randy Yates wrote:
> Allan Herriman <allanherri...@hotmail.com> writes:
>> On Mon, 02 Apr 2012 06:41:57 -0500, Randy Yates wrote:
>>> Allan Herriman <allanherri...@hotmail.com> writes:
>>>> [...]
>>>> If it's not irreducible, it's not primitive.
>>> Not true. Gauss's lemma states that the product of two primitive
>>> polynomials is also primitive.
>> I think I get it now.
>> The Wikipedia page for Primitive Polynomials (field theory) states
>> quite clearly "all primitive polynomials are ... irreducible." In this
>> context a polynomial is irreducible if it cannot be expressed as the
>> product of two or more polynomials.
>> The Wikipedia page for Primitive Polynomials (ring theory) redirects to
>> the Gauss's Lemma page, which states quite clearly "the product of two
>> primitive polynomials is also primitive ..."
> You are correct. I was correct, but not correct. (!)
> The problem is that there are two definitions for primitive polynomial;
> I was correct with respect to one definition (the ring theory one), but
> that definition isn't the one that applies to LFSRs (the finite field
> one).
>> Since a field is a ring, these two Wikipedia pages seem to contradict
>> each other.
> No, because they are two different definitions of "primitive
> polynomial."
Thanks for the clarification.
I did some tests (using my VHDL BERT package) on the irreducible CRC32C that I mentioned earlier. It's most definitely *not* maximal length when used for an LFSR.
On Sun, 01 Apr 2012 20:17:01 -0700, dvsarwate wrote:
> On Apr 1, 10:53 pm, Allan Herriman <allanherri...@hotmail.com> wrote:
>> The thing that gets me about CRC32C is that it isn't primitive. The
>> polynomial has an even number of terms and has (x+1) as a factor.
>> To me this is counterintuitive - I would have expected it to be
>> primitive.
> A CRC polynomial with a x+1 factor is guaranteed to detect 3 bit errors,
> but fails to detect some 4-bit error patterns. A primitive polynomial
> used as a CRC is guaranteed to detect 2 bit errors but fails to detect
> some 3-bit error patterns. So there _is_ a reason why many CRC
> polynomials have x+1 as a factor.
It's a bit stronger than that: an (x+1) factor means it can detect all odd numbers of bit errors. A polynomial of just (x+1) is equivalent to a parity bit (which of course can detect all odd numbers of errors).
I think this might reduce the burst error detection capability slightly (e.g. by 1 bit) though.
There are certainly interesting tradeoffs to be made when selecting a polynomial.
On Tue, 03 Apr 2012 10:42:31 +0000, Allan Herriman wrote:
> I did some tests (using my VHDL BERT package) on the irreducible CRC32C
> that I mentioned earlier. It's most definitely *not* maximal length
> when used for an LFSR.
Sorry, that should have read "not irreducible" rather than "irreducible".
