0

I was looking at this page and I saw that the terms of this polynomial:

  1. 0xad0424f3 = x^32 +x^30 +x^28 +x^27 +x^25 +x^19 +x^14 +x^11 +x^8 +x^7 +x^6 +x^5 +x^2 +x +1

which seems not correct since converting the Hex:

0xad0424f3 is 10101101000001000010010011110011

It would become:

  1. x^31+ x^29+ x^27+ x^26+ x^24+ x^18+ x^13+ x^10+ x^7+ x^6+ x^5+ x^4+ x^1+ x^0

Can you help me understand which one is correct? what about 64 bit ECMA polynomial,

0xC96C5795D7870F42

I want to know the number of terms in each polynomial 0xad0424f3 and 0xC96C5795D7870F42.

Arash
  • 225
  • 1
  • 11

1 Answers1

2

That page is on Koopman's web site, where he has his own notation for CRC polynomials. Since all CRC polynomials have a 1 term, he drops that term, divides the polynomial by x, and represents that in binary. That's what you're looking at.

The benefit is that with a 64-bit word, you can then represent all 64-bit and shorter CRC polynomials, with the length of the CRC denoted by the most significant 1 in the word.

The downside is that only Koopman uses that notation, as far as I know, resulting in some confusion by others. Like yourself.

As for your 64-bit CRC, that polynomial that you note is from the Wikipedia page is actually the reversed version, and is not in Koopman's notation. The expansion into a polynomial is shown right there, underneath the hex representation. It has 34 terms.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • Thank you for your answer, This `0xC96C5795D7870F42` is not from Koopman's web site, so how did you know that you need to add an extra 1 to it? – Arash Nov 24 '20 at 18:19
  • 1
    Because it ends in a `2`. As I said, CRC polynomials always have a _1_ term, so it can't be even unless it's using Koopman's notation. – Mark Adler Nov 24 '20 at 19:52
  • 1
    If it's not from Koopman's web site, where is it from? That would be an example of someone other than Koopman using his notation. – Mark Adler Nov 24 '20 at 20:34
  • It is on Wikipedia https://en.wikipedia.org/wiki/Cyclic_redundancy_check – Arash Nov 24 '20 at 21:59
  • Ah! It's not in Koopman notation. You put the _reversed_ polynomial in your question for some reason, so the _1_ is the most significant bit of `0xC96C5795D7870F42`. – Mark Adler Nov 24 '20 at 22:03
  • Thank you for the answer, but I don't understand why the 64bit notation is different? Is it just because people don't want to put 1 at the end of the binary form? – Arash Nov 24 '20 at 22:14
  • 1
    It's not different. You just picked the wrong entry in the table. The actual polynomial in the usual representation in `0x42F0E1EBA9EA3693`, to the left of the one you picked. The one you picked is just for convenience when implementing the reflected version of the CRC, where the bits of data come in starting from the _least_ significant bits of the bytes, instead of coming in starting from the _most_ significant bits of the bytes. – Mark Adler Nov 24 '20 at 22:19