1
$\begingroup$

I tried to find information about how features of a CRC polynomials influence computation speed of implementations.

It is obvious that (depending from the CPU architecture the algorithm runs on) algorithms can be optimized for special CRC widths.

However, even when comparing CRC polynomials of the same width there still seems to exist differences in computation speed:

  1. I read a statement that low polynomial weights would increase computation speed.
  2. Also Prof. Koopman wrote on his 6sub8 CRC page: "Consider only polynomials with bits set in the bottom 8 bits (in addition to the topmost bit). This can help speed up computation and reduce lookup table sizes for CRC calculations in application programs."

I can see why pre-calculated CRC tables can be more compact using a sub8 polynomial. But I could not wrap my mind around the speed related statements. All implementations I had a look at (various C implementation of bit-wise and table-based algorithms) seem not to benefit from low-weight or sub8 polynomials. Maybe I missed the point or there are environments (like other algorithms, hardware implementations, special CPU architectures) that would benefit.

My question: Given a certain CRC width, in which way and under which circumstances does a low polynomial weight and/or a sub8 polynomial speed-up the computation of a CRC?

$\endgroup$
  • $\begingroup$ Can I ask how it can help reducing table size? You can build table for such polynomial, I guess that it will be as dense as any other one. $\endgroup$ – Bulat Mar 12 at 12:24
  • $\begingroup$ I tried it with a 32 bit sub8 polynomial. Each table entry only uses the lower 16 bit which reduces memory consumption by 50%. $\endgroup$ – Silicomancer Mar 12 at 12:41
  • $\begingroup$ This sounds like two separate questions. I think it might be better to ask them as two separate questions: how does a low weight speed up computation; and how does a sub8 polynomial speed up computation? $\endgroup$ – D.W. Mar 28 at 22:30
  • $\begingroup$ I am not sure about this. They may be connected. Because sub-width polynomials tend to have a low weight as well. Anyway nobody seems to care or being able to answer yet :( $\endgroup$ – Silicomancer Mar 29 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.