Re: is CRC32 as good as it gets for 32 bits?

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 11/12/05 

Date: Sat, 12 Nov 2005 01:27:21 GMT

Ben Rudiak-Gould wrote:
> Bryan Olson wrote:
>> On the other hand, there should be a shorter three-bit-difference
>> collision.
>
> If the CRC polynomial has an even number of nonzero coefficients, then
> there are no three-bit-difference collisions because every valid
> codeword has even parity.
>
> But I just went and counted the coefficients in the standard CRC-32
> polynomial, and darned if there aren't an odd number of them. Oh well. I
> don't know what guided the choice of that particular polynomial.

As I pointed out, CRC-32 is primitive. A mod-2 polynomial
has an even number of non-zero coefficients if and only if
it has a factor of (x + 1), so all primitive mod-2
polynomials of degree greater than one have an odd number
of non-zero coefficients.

There had been a tradition of choosing a CRC polynomial as
a primitive (or at least irreducible) polynomial times
(x + 1). The CRC then acts like a CRC using the primitive
factor, plus a check of bit-parity. Engineers could pitch
these CRC's as strictly superior to parity checks; they
catch every error that parity catches, and many more.

By the time of CRC-32's design, people recognized
special-casing odd numbers of bit-flips to be silly. Real
channels don't have any particular tendency to produce an
odd number of bit-errors. 

-- 
--Bryan

Relevant Pages

  • Property of a polynomial , pattern
    ... While consedering the odd given polynomials: ... from k=3 and upwards we've got developments ...
    (sci.math)
  • Integrating Rational Functions
    ... as a linear combination of a rational function, ... tangents of polynomials of degree 1, ... of which will have real number coefficients. ... has complex roots that show up in complex conjugate ...
    (sci.math)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: Genetic Algorithms for factorize multivariate polynomials
    ... integer powers rather than integer coefficients, ... and both of the candidate factor polynomials for these values. ... selection and no selection. ... and X and Y are different then in the offspring replace them with one ...
    (comp.ai.genetic)