How do I calculate the binary form of a polynomial?

Question

The 4 bytes used in CDROM sectors is just a usual 32 bit CRC. It uses the polynomial

P(x) = (x^16 + x^15 + x^2 + 1).(x^16 + x^2 + x + 1) 

which expands to

x^32 + x^31 + 2x^18 + 2x^17 + 3x^16 + x^15 + x^4 + x^3 + 2x^2 + x + 1

The CRC process reverses the bits of the input bytes and the final CRC value. It is stored in big endian format in the sector.

So I have to pass a polynomial prime into crc32 algorithm.

How do I convert this polynomial expression into binary form. any explanation will be appreciated.

Answer 1

For a CRC32 algorithm with the polynomial $$x^{32} + x^{31} + 2x^{18} + 2x^{17} + 3x^{16} + x^{15} + x^4 + x^3 + 2x^2 + x + 1$$ you first omit the $x^{32}$ term and reduce the remaining coefficients mod 2. This gives $$x^{31} + x^{16} + x^{15} + x^4 + x^3 + x + 1$$ Now simply substitute $x=2\;$ and evaluate, this gives the 32 bit number for the CRC polynomial:

$$10000000000000011000000000011011_2 = 8001801B_{16} = 2147581979_{10} $$

But note that for an actual implementation there more design subtleties: Are you using big-endian or little endian? There are different reflections modes, initial values, final xoring etc.

Answer 2

This boils down to a sequence of shift and xor operations, see for example here for an explanation, including an example calculation.