# How do I calculate CRC32 mathematically?

I want to calcuate the CRC32 (algorithm http://www.libpng.org/pub/png/spec/1.2/PNG-CRCAppendix.html ) using polynomials directly but I don't know how. I found the generating polynomial listed here https://en.wikipedia.org/wiki/Cyclic_redundancy_check (this corresponds to 0xedb88320 in the example code).

So please can someone define a mathematical specification that calculates the same result as this algorithm?

-

1
– Thomas Jul 29 '12 at 11:04
@Thomas, yes but this does not help, thank you though. – user2558 Jul 29 '12 at 11:09

2
– David Cary Jul 30 '12 at 16:28

## 1 Answer

I guess that CRC is borrowed from the $32$-bit Frame Check Sequence in the 1988 edition of CCITT V.42, section 8.1.1.6.2, available here, which gives a mathematical definition (note: remove the obviously spurious $1$ after $x^{30}$ in the English edition).

I prefer this alternate definition with some of the math on polynomial replaced by equivalent operations on bits:

1. Consider the message as a sequence of $n$ bits in chronological order (if the message is structured in words or bytes: with low-order bit first unless otherwise specified).
2. Append $32$ one bits, forming a sequence of $n+32$ bits.
3. Complement the first $32$ bits of that sequence.
4. Form the binary polynomial of degree (at most) $n+31$, with term $x^{n+32-j}$ present (resp. absent) when the $j$th bit in the result of the previous step is one (resp. zero), for $j$ with $0<j\le n+32$.
5. Compute the remainder of the polynomial division of that polynomial by the binary polynomial $x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$, forming a binary polynomial of degree (at most) $31$.
6. Form the $32$-bit sequence with the $j$th bit one (resp. zero) when the term $x^{32-j}$ is present (resp. absent) in that polynomial, for $j$ with $0<j\le 32$.
7. Append that $32$-bit sequence to the ORIGINAL message (if it is to be converted to bytes: the first bit of that sequence shall be the low-order bit of the first byte unless otherwise specified).

Note: Inserting $32$ bits at step 2 allows a receiver to process bits of the message and $32$-bit sequence uniformly as they are being received, without knowing the frontier between the message and the final 32-bit sequence until after the end of that sequence. Step 3 makes it likely that suppression of bits in the message is detected including for zero bits at the beginning of the message.

Note: In term of binary polynomials (according to the conventions in steps 4 and 6), the combination of steps 2 and 3 changes $M(x)$ to $M(x)\cdot x^{32}+\Sigma_{i=n}^{n+31}{x^i}+\Sigma_{i=0}^{31}{x^i}$.

Note: Steps 4, 5 and 6 can be replaced by:

• repeat until the sequence has exactly 32 bits:
• if the first bit is one:
• complement the 7th, 10th, 11th, 17th, 21th, 22th, 23th, 25th, 26th, 28th, 29th, 31th, 32th and 33th bit.
• remove the first bit.
-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.882468581199646, "perplexity_flag": "middle"}