Re: Efficient reduction of polynoms with only one term

On 16/10/2010 11:08, Johannes Bauer wrote:

For my experiments I chose
explicitly a CRC polynomial as there are CRC generators out there (like
the said website) to verify my results. Aren't CRCs just that (i.e.
dividing some arbitrary polynomial by the CRC polynomial, yielding the

No, for three main reasons, then a few others:

1) In CRC as used in telecom, it is customary to add at the end
of the message as many bits as the order of the generator
polynomial, before division by the generator polynomial.
That's because during verification it then becomes possible to
enter the CRC itself in the CRC checker exactly as for the message,
which is handy when the end mark is after the CRC following the

2) It is customary to add an initialization pattern before the
message, with the effect that it reduces the odds that loss of
bits at start of the message remains undetected.

3) Hardware implementors want to map bits with the chronologically
first bit at the higher coefficient of polynomials, because that's
the only way to compute the CRC bit per bit; on the other hand,
ever since the telex, low order bits of characters have been
transmitted first, and that extended to 8-bit bytes. Therefore,
when computing in software a REALLY standard CRC, the low order bit
of a byte often represents a higher order polynomial coefficient
than the high order bit of that same byte; while mathematicians
and software guys want the other convention, for good reasons.

Francois Grieu