CRCs (Cyclic Redundancy Checks)

CRCs (Cyclic Redundancy Checks) are a type of checksum that is used to detect errors in data transmission. It is based on modulo-2 polynomial (GF(2)) division.

“Everything you wanted to know about CRC algorithms, but were afraid to ask for fear that errors in your understanding might be detected.” - Ross N. Williams.¹

How They Work

The general idea behind a CRC is to treat the input data as one huge number, divide it by another fixed number, and make the remainder from this division the checksum. It turns out that division (as long as the divisor is about as big as the checksum) is good at creating “chaos” in the checksum, meaning that small changes in the input data will result in a large change in the checksum.

Imagine the data [0x05, 0xB8]. Pretend our divider is 0x05. We can treat the data as the single number 0x05B8 (concatenating the bytes together). We can then divide 0x05B8 by 0x05 and get a remainder of 0x04. This is our checksum. This is obviously easy to do with simple CPU arithmetic when the data is just two bytes. However, when the data is much larger, it becomes more difficult to do this in a single operation. Instead, we can use long division to “iterate” through the data one bit at a time.

Doing it the long division way on our data [0x05, 0xB8] with our divider 0x05 would look like this:

          0b100100100
        _____________
0b101 ) 0b10110111000
        0b10100000000   (0b101 << 8 = 1280)
        -------------
        0b00010111000   (= 184)
        0b00010100000   (0b101 << 5 = 160)
        -------------
        0b00000011000   (= 24)
        0b00000010100   (0b101 << 2 = 20, also note a borrow happens here)
        -------------
        0b00000000100   (= 4 = remainder)

Instead of the numbers being treated as positive integers, CRCs treat them as polynomials (this includes the dividend (data), divisor, and remainder). This is done by treating the bit string whose bits are the coefficients of the polynomial. For example, our divisor of 0xFA is 0b11111010, which in polynomial form is $1x^7 + 1x^6 + 1x^5 + 1x^4 + 1x^3 + 0x^2 + 1x^1 + 0x^0$ which simplifies to $x^7 + x^6 + x^5 + x^4 + x^3 + x$.

But how does division work with polynomials rather than numbers? This is where it gets a bit weird, and the $GF(2)$ field (Galois field of two elements) comes into play. The rule is decided that the polynomial arithmetic will be all modulo 2. This is essentially the same as binary arithmetic with no carry.

Addition and Subtraction

Addition without carry is the same as XOR. For example:

 1001
+1010
-----
 0011

Subtraction is the same as addition.

Multiplication

For multiplication, the cleanest way to see what’s going on is to do it on the polynomials first. As an example, 1011 is $x^3 + x + 1$ and 1010 is $x^3 + x$. Multiplying them out the ordinary way:

$$\begin{aligned} (x^3 + x + 1)(x^3 + x) &= x^6 + x^4 + x^4 + x^2 + x^3 + x \\ &= x^6 + 2x^4 + x^3 + x^2 + x \end{aligned}$$

The $2x^4$ term has a coefficient of 2, but coefficients live in GF(2) where $2 \equiv 0$, so that whole term vanishes:

$$x^6 + x^3 + x^2 + x$$

Reading off the coefficients gives the bit string 1001110.

Doing the same thing directly on the binary representation, multiplication becomes “for every set bit at position $i$ in the multiplier, XOR a copy of the multiplicand shifted left by $i$.” Laid out as long multiplication:

   1011
 x 1010
 ------
   0000   (bit 0 of 1010 = 0)
  1011    (bit 1 of 1010 = 1, shifted left 1)
 0000     (bit 2 of 1010 = 0)
1011      (bit 3 of 1010 = 1, shifted left 3)
-------
1021110   (column-wise sums — the 2 at bit position 4 is the same 2 as in the $2x^4$ coefficient above)
1001110   (after mod 2 collapses the 2 to 0)

The column-overlap at bit position 4 (where the shift-by-1 and shift-by-3 partials both contribute a 1) is exactly the source of the $2x^4$ term in the polynomial form. The mod-2 rule kills it in either representation, so the two methods agree on the final answer 1001110.

Division

Now let’s explore division. We’ll do it as polynomials first, then binary. As a small example, let’s divide 1101001 by 1001 — that is, $x^6 + x^5 + x^3 + 1$ by $x^3 + 1$.

In polynomial form, long division works just like ordinary algebra. The leading term of the quotient is whatever cancels the leading term of the dividend.

Step 1: $\frac{x^6}{x^3} = x^3$, so the first quotient term is $x^3$. Multiply back: $x^3 \cdot (x^3 + 1) = x^6 + x^3$. Subtract from the dividend:

$$(x^6 + x^5 + x^3 + 1) - (x^6 + x^3) = x^5 + 1$$

Remember that subtraction in GF(2) is the same as addition, so the $x^6$ and $x^3$ terms each cancel against their counterparts.

Step 2: $\frac{x^5}{x^3} = x^2$, so the next quotient term is $x^2$. Multiply: $x^2 \cdot (x^3 + 1) = x^5 + x^2$. Subtract:

$$(x^5 + 1) - (x^5 + x^2) = x^2 + 1$$

The remainder $x^2 + 1$ has degree 2, less than the divisor’s degree 3, so we are done. The quotient is $x^3 + x^2$ and the remainder is $x^2 + 1$.

In binary, the same idea works directly with bit-shifts and XORs. Here’s 1101001 ÷ 1001 laid out in the standard long-division form:

          1100 (quotient)
      ________
1001 ) 1101001 (divider | dividend)
       1001..,
       ----..,
        1000.,
        1001.,
        ----.,
         0010,
         0000,
         ----,
          0101
          0000
          ----
           101 (remainder)

(, represents unprocessed “1“‘s in the dividend, . represents unprocessed “0“‘s in the dividend)

At each step, look at the leftmost bit of the working window: if it’s 1, we subtract the divisor from the dividend by XORing in the divisor (1001); if it’s 0, XOR in 0000 instead (a no-op kept for layout regularity — see iterations 3 and 4, which are the bit-by-bit version’s way of saying “the polynomial division would have already stopped”). Then shift the window one column to the right, bringing in the next bit of the dividend. The , and . placeholders to the right stand for original-dividend bits not yet pulled into the window — , represents a 1, . represents a 0.

Tip

GF(2) polynomial division is a bit weird, 1000 is subtracted by a seemingly bigger 1001 and there is a remainder! There is not really a notion of bigger and smaller numbers in GF(2) except for the position of the leading bit (the degree of the polynomial).

The quotient 1100 ($x^3 + x^2$) and remainder 101 ($x^2 + 1$) match the polynomial result above. For CRC purposes the quotient is discarded — only the remainder matters. Taking the remainder of polynomial division is exactly how a CRC is computed. The dividend is the message with $r$ zero bits appended (where $r$ is the degree of the generator polynomial), and the divisor is the generator.

The Generator Polynomial

Now that we have a basic understanding of CRC maths, what is the generator polynomial? This is the polynomial that is used to divide the data by. For example, it could be $x^3 + x + 1$. It is commonly represented as a hexadecimal number rather than as a traditional polynomial. A really important point to note is that the leading one is dropped from the hex representation by convention. For example:

• Polynomial: $x^3 + x + 1$
• Binary: 0b1011
• Hex: 0x3 (leading one is dropped!)

The width of the polynomial is the position of the leading bit, counting from 0. So the width of the polynomial 0b1011 is 3, not 4. This is one of the most important parts of the polynomial, as it determines the width of the CRC value. This is because the remainder (CRC value) will always be less than the divisor (this should be any obvious truth about any division).

You could choose any polynomial, but some are better than others at detecting errors. The science behind choosing a polynomial is a bit of a dark art, and generally you are advised to pick a standard and use that rather than coming up with your own!

Calculating the CRC is now done by:

1. Appending $w$ zero bits to the data, where $w$ is the width of the generator polynomial.
2. Dividing the data by the generator polynomial to work out the remainder. This is the CRC value!

Example

Calculate the CRC for the data 0b11010011 using the polynomial 0b1011.

First we recognize the width $w$ is 3 bits, so we append 3 zero bits to the data:

11010011000

Now we divide the data by the generator polynomial by using long division. Now remember that we are using mod 2 arithmetic, so we just XOR the bits together.

11010011000 (dividend)
1011        (divisor)
-----------
01100011000
 1011
-----------
00111011000
  1011
-----------
00010111000
   1011
-----------
00000001000
       1011
-----------
00000000011 (remainder)

Done! Our CRC value is 011.

Next, the CRC value is appended to the data (taking the place of those zero bits we appended earlier). So we would send the following to the receiver:

11010011011 (data + crc)

When the receiver gets the data, it needs to check if the message is valid. To do this, it could split the message into the original data and the CRC value and do the same CRC calculation on the original data. If the calculated CRC value matches the CRC value embedded in the message then the message is valid. However, there is a trick which makes things simpler. Rather than splitting the message up, the receiver can just calculate the CRC of the entire message (including the CRC value embedded into it by the sender). If the calculated CRC value is 0, the message is valid. Why does this work? This is because we added the remainder onto the data. Remember in $GF(2)$ arithmetic, addition is the same as subtraction. So it’s the same as subtracting the remainder from the data. If you subtract the remainder, you are left with a number which perfectly divides by the polynomial and gives 0 remainder, hence a CRC value of 0.

Note

This receiver CRC value being 0 is true as long as the XorOut value of the algorithm is 0 (this is explained below). If XorOut is not 0, then the remainder that the receiver calculates (a.k.a. the residual) may be non-zero. In either case, you check that your calculated CRC value matches the residual to make sure the message is valid.

Choosing a Polynomial

So before we talked about how once we add the remainder to the original data, the message is perfectly divisible by the polynomial. This means the transmitted message $T$ is a integer multiple of the polynomial $G$.

If the message is corrupted during transmission, then the received message will be:

$$T + E$$

where $E$ is the error pattern and $+$ is CRC addition (XOR). The receiver divides $T + E$ by $G$. We know that (mod is the same thing as remainder):

$$T \bmod G = 0$$

So thus:

$$(T + E) \bmod G = E \bmod G$$

Any corruption that just so happens to make $E$ a multiple of $G$ will go undetected by the receiver. So we want to choose a polynomial $G$ whose multiples are not anything like the kind of error patterns we are likely to see during transmission.

Single Bit Errors

Single bit errors are where $E$ would be things like 1000, 0100, 0010, and 0001. This means a single bit has been flipped in the message. In polynomial form this would be $E = x^i$ where $i$ is an integer. These are easy to detect, as we just need to make sure that $G$ has at least two bits set to 1. Any non-zero multiple of $G$ will also have at least two bits set to 1, and thus $G$ will never divide $E$ evenly.

For example, if $G$ was 101, then in polynomial form $G = x^2 + 1$. There is no way to divide $E = x^i$ by $G$ and leave no remainder as the only things that divide $E = x^i$ cleanly are $x^j$ where $j \le i$.

Two Bit Errors

This is where the maths and logic starts to get more involved, and I don’t understand exactly how it works. But there are ways to design the polynomial $G$ so that it can detect all two bit errors.

Error With an Odd Number of Bits

All errors with an odd numbers of bits can be detected by making sure the polynomial $G$ has an even number of bits set to 1. This is because:

1. Multiplication in GF(2) is XORing the polynomial bits and various shifted positions against the data.
2. XORing a number with an even number of bits (the polynomial) preserves the “oddness” property of the number.

Burst Errors

All burst errors up to a certain length can be detected by making sure the polynomial $G$ has its lowest bit set to 1.¹

Summary

There is no one “best” polynomial to choose. There are certainly some that are bad choices and there are some which a better choices for certain applications. There are “best” polynomials with regards to specific Hamming distance properties, but these assume the data is affected by low, constant, random, independent bit errors.² This is usually not the case in practice, bit errors tend to occur in bursts and may affect a sequence of bits all in the same direction.

Implementing a CRC Algorithm in Software

The key things we have to do is CRC division. We can’t just use the normal division instruction all CPUs have since:

1. We are using mod 2 arithmetic (a.k.a. GF(2), CRC arithmetic), not regular division.
2. The number we are dividing is the entire message, which could be many bytes, kBs, MBs long. Most CPUs/standard libraries/compilers only support numbers up to 8 or 16 bytes (64 or 128 bits).

So we have to implement our own CRC division algorithm. The simplest way is to repeat in code the long division algorithm we used above. We can do this by:

1. Creating a variable which represents the in-progress remainder. The variable’s width is the degree of the generator polynomial — i.e. one less than the polynomial’s bit-width. For polynomial 1011 (4 bits, degree 3), the variable is 3 bits, starting at 000.
2. Shift the variable left by 1 bit. On the low end, shift in the next bit of the augmented message (the message with the zero bits appended). The MSB of the message is taken first (i.e. the topmost bit of the highest byte). The bit that falls off the high end of the variable is the “popped” bit.
3. If the popped bit was a 1, XOR the variable with the generator polynomial minus its leading 1 (the same form discussed earlier — for 1011, that’s 011).

Example

Calculate the CRC for the data 11010011 using the polynomial 1011 using the simple software implementation described above.

Variable starts as 000. Augmented message is 11010011000 (11 bits remaining).

Shift variable left. Variable is now 001. Augmented message is now 1010011000 (10 bits remaining). 0 popped off, no XOR.

Shift variable left. Variable is now 011. Augmented message is now 010011000 (9 bits remaining). 0 popped off, no XOR.

Shift variable left. Variable is now 110. Augmented message is now 10011000 (8 bits remaining). 0 popped off, no XOR.

Shift variable left. Variable is now 101. Augmented message is now 0011000 (7 bits remaining). 1 popped off, XOR variable with poly 011. Variable is now 110.

Shift variable left. Variable is now 100. Augmented message is now 011000 (6 bits remaining). 1 popped off, XOR variable with poly 011. Variable is now 111.

Shift variable left. Variable is now 110. Augmented message is now 11000 (5 bits remaining). 1 popped off, XOR variable with poly 011. Variable is now 101.

Shift variable left. Variable is now 011. Augmented message is now 1000 (4 bits remaining). 1 popped off, XOR variable with poly 011. Variable is now 000.

Shift variable left. Variable is now 001. Augmented message is now 000 (3 bits remaining). 0 popped off, no XOR.

Shift variable left. Variable is now 010. Augmented message is now 00 (2 bits remaining). 0 popped off, no XOR.

Shift variable left. Variable is now 100. Augmented message is now 0 (1 bit remaining). 0 popped off, no XOR.

Shift variable left. Variable is now 000. Augmented message is now <empty> (0 bits remaining). 1 popped off, XOR variable with poly 011. Variable is now 011.

The final variable is 011, which is the CRC for the data 0b11010011 using the polynomial 0b1011. This matches the long-division remainder computed earlier.

Initial Values

So far we have been assuming that the initial value of the CRC residual variable is initialized to 0. This is not always the case. Many CRC algorithms start with a non-zero initial value. Why? There is quite a problem with CRC algorithms that start with all 0s - the CRC value does not change with any leading zero bits, and thus cannot detect errors if 0 bits are missing/added. This type of error can be quite common in practise, and many CRC algorithm start with a non-zero init value to compensate. I would always prefer to select an algorithm with a non-zero init value unless there is a very good reason to use a 0 init value.

The most popular non-zero initial value is just all f’s, e.g. 0xffff for a 16-bit CRC.

CRC Calculators

NinjaCalc has a CRC calculator which allows you to calculate the CRC value for ASCII or hex data, using either common pre-loaded CRC algorithms or your own custom algorithm.

Example usage of the CRC Calculator within NinjaCalc (https://ninjacalc.mbedded.ninja/calculators/software/crc-calculator).

Processor Support

Some processors have dedicated instructions for CRC calculations. Some Intel processors have the SSE4.2 instruction set (Streaming SIMD Extensions 4.2) which includes the CRC32 instruction. This was first introduced in the Nehalem microarchitecture.³ This accumulates a CRC32C (Castagnoli) value using the polynomial 0x1EDC6F41.⁴ AArch64 architecture provides hardware acceleration for the CRC-32 and CRC-32C algorithms.³

Some Common CRC Algorithms

Note that this does in no way try and be an exhaustive list. Sites like CRC RevEng - Catalogue of parameterized CRC algorithms and Prof. Koopman’s CRC Polynomial Zoo have great detailed lists of CRC algorithms.

The following algorithms are parameterized following the convention used by Dr Ross Williams in his A Painless Guide To CRC Error Detection Algorithms paper:¹

• Name: The name of the CRC algorithm. We use the name specified by Ross Williams if possible.
• Width: The width of the CRC in bits. This is always the same as the degree of the polynomial.
• Poly: The polynomial of the CRC algorithm, expressed as a hexadecimal number. The leading one (the coefficient of the highest power of $x$) is dropped from the hex value.
• Init: The initial value of the CRC algorithm before any input data is processed.
• RefIn: Whether the input is reflected (bits are swapped around their center, e.g. 11001010 reflected becomes 01010011). If false, input bytes are treated as bit 7 being the most significant bit and bit 0 being the least significant bit. If true the input is reflected first so that all the bits are reversed in order.
• RefOut: Whether the output is reflected. If false, the output is fed directly into the XOR function after running through input data. If true, the output is reflected first so that all the bits are reversed in order (similar to RefIn).
• XorOut: This is the value that the result is finally XORed with before being returned as the final CRC value. This affects the residue and can make it non-zero.
• Check: The check value of the CRC algorithm. This is not strictly part of the CRC algorithm definition, but is included to make it easier to verify the CRC algorithm. It is the resulting CRC value from feeding in the ASCII string "123456789".
• Residue: The value you get when the receiver runs the CRC algorithm over the entire message including the appended CRC value. This would normally be 0, but algorithms with a non-zero XorOut produce a non-zero residue (a constant determined by the XorOut and polynomial). If the XorOut is 0, the residue is 0. The residue is what the receiver checks its calculated CRC value against to confirm the message is valid.

CRC-8/BLUETOOTH

Property	Value
Name	CRC-8/BLUETOOTH
Width	8
Poly	0xa7
Init	0x00
RefIn	True
RefOut	True
XorOut	0x00
Check	0x26
Residue	0x00

The CRC-8/BLUETOOTH CRC is used in the Bluetooth header error check (HEC).⁵

CRC-8/I-432-1

Property	Value
Name	CRC-8/I-432-1
Width	8
Poly	0x07
Init	0x00
RefIn	False
RefOut	False
XorOut	0x55
Check	0xa1
Residue	0xac

Also called CRC-8-CCITT. Used by SMBus for packet error checking (PEC).³

CRC-8/MAXIM-DOW

Property	Value
Name	CRC-8/MAXIM-DOW
Width	8
Poly	0x31
Init	0x00
RefIn	True
RefOut	True
XorOut	0x00
Check	0xa1
Residue	0x00

This checksum is used in Maxim 1-Wire device registration numbers.⁵

CRC-16 (CCITT-FALSE)

Property	Value
Name	CRC-16/IBM-3740
Width	16
Poly	0x1021
Init	0xffff
RefIn	False
RefOut	False
XorOut	0x0000
Check	0x29b1
Residue	0x0000

CRC-16-CCITT was first used by IBM in its SDLC data link protocol. It is also known as just CRC-CCITT (it always uses a 16-bit CRC checksum).

However, CRC-16-CCITT are not all the same. There are a few common variants of the CRC-16-CCITT in use:

• XModem
• 0xFFFF. This is an adaptation of the CRC-CCITT algorithm but with a starting CRC value of 0xFFFF rather than 0x0000.
• 0x1D0F
• Kermit. This is in fact the “true” CRC-CCITT CRC algorithm.

All of the CRC-CCITT variants use the following generator polynomial:

$x^{16} + x^{12} + x^{5} + 1$

It can be represented by the following hexadecimal numbers:

Normal: 0x1021
Reverse: 0x8408
Koopman: 0x8810

CRC-32/ISO-HDLC

Property	Value
Name	CRC-32/ISO-HDLC
Width	32
Poly	0x04c11db7
Init	0xffffffff
RefIn	True
RefOut	True
XorOut	0xffffffff
Check	0xcbf43926
Residue	0xdebb20e3

CRC-32/ISO-HDLC is one of the most common 32-bit CRC algorithms. It is also known as CRC-32, CRC-32/ADCCP, CRC-32/V-42, CRC-32/XZ and PKZIP. HDLC is defined in ISO/IEC 13239. Ethernet uses this in its frame check sequence (FCS).³

External Resources

http://reveng.sourceforge.net/crc-catalogue/16.htm is a great webpage catalogue of many 16-bit CRC algorithms.

A Painless Guide To CRC Error Detection Algorithms is an old (1993), sore-on-the eyes (pure text article) but great in-depth introduction to CRC algorithms.¹

Footnotes

1. Ross N. Williams (1993, Aug 19). A Painless Guide To CRC Error Detection Algorithms. Rocksoft Pty Ltd. Retrieved 2026-04-29, from http://www.ross.net/crc/download/crc_v3.txt. ↩ ↩² ↩³ ↩⁴

2. Philip Koopman (2024, Feb 25). Best CRC Polynomials. Carnegie Mellon University. Retrieved 2026-04-30, from https://users.ece.cmu.edu/~koopman/crc/. ↩

3. Wikipedia (2026, Apr 13). Cyclic redundancy check [wiki]. Retrieved 2026-04-30, from https://en.wikipedia.org/wiki/Cyclic_redundancy_check. ↩ ↩² ↩³ ↩⁴

4. Wikipedia (2026, Jan 16). SSE4 [wiki]. Retrieved 2026-04-30, from https://en.wikipedia.org/wiki/SSE4. ↩

5. Greg Cook (2024, Dec 11). Catalogue of parametrised CRC algorithms. CRC RevEng. Retrieved 2026-04-30, from https://reveng.sourceforge.io/crc-catalogue/all.htm. ↩ ↩²