Table of Contents

Article updated March 2024 (for details, click here to see the changelog).

[Back to top]

1. Foreword & Outline

This article is the result of the fact that I found finally time to deal with CRC. After reading Wikipedia and some other articles, I had the feeling to not really understand completely in depth.
Therefore I decided to write this article, trying to cover all topics I had difficulties with. And this in exactly the same order I concerned myself with CRC. Please note that this article is not indented to be a full comprehensive CRC guide explaining all details - it should be used as an additional, practical oriented note to all general explanations on the web.

Here's the outline:

• At first, the general idea and functionality of CRC is discussed.
• Subsequently, some examples are calculated by hand to get familiar with the process of CRC calculation.
• Based on those observations, implementations of CRC calculation are presented step by step, from naive ones till more efficient algorithms. Here the emphasis lies on the target to really get the point of the code compared to the manual calculation. Here an exemplary CRC-8 polynomial is used.
• Afterwards, the achieved knowledge is expanded to CRC-16 and CRC-32 calculation, followed by some CRC theory and maybe a FAQ section.

[Back to top]

2. Introduction

CRC (Cyclic Redundancy Check) is a checksum algorithm to detect inconsistency of data, e.g. bit errors during data transmission. A checksum, calculated by CRC, is attached to the data to help the receiver to detect such errors. Refer also to [1] for a short or to [4] for a very detailed CRC introduction.

CRC is based on division. The actual input data is interpreted as one long binary bit stream (dividend) which is divided by another fixed binary number (divisor). The remainder of this division is the checksum value.
However, reality is a bit more complicated. The binary numbers (dividend and divisor) are not treated as normal integer values, but as binary polyonimals where the actual bits are used as coefficients.

Division of polynomials differs from integer division. Without going into detail, the underlying used aritmetic for CRC calculation is based on the XOR (Exclusive-OR) operation (we'll come to an example soon!).
- The dividend is the complete input data (interpreted as binary stream).
- The divisor, also called generator polynomial, is statically defined by the used CRC algorithm. CRC-n using a fixed defined generator polynom with (n+1) bits.
- The CRC checksum value is defined as dividend % divisor.

For manual calculation, n zero bits are appended to the input data before actual CRC calculation (polynomial division) is computed. Let's perform an example CRC computation:

Useful observations:

• In each step, the leading '1' of the divisor is always aligned with the first '1' of the dividend. This implies that the divisor does not move only 1 bit right per step, but sometimes also several steps (e.g. like in line (*).
• The algorithms stops if the divisor zeroed out each bit of the actual input data (without padding bytes): The input data ranges from column A to H including. In the last step, column H and all prior columns contain 0, so the algorithm stops.
• The remainder (= CRC) is the value 'below' the padding zero bits (column I to P). Because we added n padding bytes, the actual CRC value has also n bits.
• Only the remainder in each step is of interest, the actual division result (quotient) is therefore not tracked at all.

[Back to top]

2.1 CRC Verification

The remainder is the CRC value which is transmitted along with the input data to the receiver. The receiver can either verify the received data by computing the CRC and compare the calculated CRC value with the received one. Or, more commonly used, the CRC value is directly appened to the actual data. Then the receiver computes the CRC over the whole data (input with CRC value appended): If the CRC value is 0, then most likely no bit error occured during transmission. Let's do verification according the latter case:

[Back to top]

3. Concept of the CRC shift register

So we have seen how to calculate the CRC checksum value manually, but how can it be implemented?
The input data stream is generally quite long (more than 1 bit) so it's not possible to perform a simple division like "Input data % generator polynomial". The computation has to be performed step-by-step and here the concept of a shift register comes into play.

A shift register has a fixed width and can shift it's content by one bit, removing the bit at the right or left border and shift in a new bit at the freed position. CRC uses a left shift register: When shifted, the most significant bit pops out the register, the bit at position MSB-1 moves one position left to postion MSB, the bit at position MSB-2 to MSB-1 and so on. The bit position of the least significant bit is free: here the next bit of the input stream is shifted in.

MSB LSB --- --- --- -- -- --- <-- | | | |.... | | <-- (shift in input message bits) --- --- --- -- -- ---

The process of CRC calculation using a shift register is as follow:

1. Initialize the register with 0. (Note that initial values != 0 are handled especially, consider chapter 8.6).
2. Shift in the input stream bit by bit. If the popped out MSB is a '1', XOR the register value with the generator polynomial.
3. If all input bits are handled, the CRC shift register contains the CRC value.

Let's visualize the procedure with the example data from above

[Back to top]

4. Implementing CRC-8 algorithms

This chapter handles different algorithms and their implementations in C# for calculating CRC-8 checksum values. It starts with simple algorithms for limited input data and ends with efficient table-based implementations.

[Back to top]

4.1 Simple CRC-8 shift register implementation for one byte input data

Let's start with an implementation of a CRC-8 algorithm for solely one byte input data. The implementation will stay very closely to the shift register process from the example above.

A CRC-8 algorithm uses actually a 9bit generator polynomial, but it would be cumbersome to track such an unaligned value in an algorithm. Fortunately, as described in the previous chapter, the most significant bit can be discarded. First, it is always 1. Second, because the divisor is always aligned in such a manner that this leading '1' alignes with the next '1' of the dividend, the XOR result for this bit is always 0.
This means we leave out the MSB '1', so we can use the generator polynomial b100011101 = 0x1D as the example polynomial from now on.

Let's start with an implementation which is as close as possible to the shift register approach:

[Back to top]

4.2 Modified CRC-8 bitwise implementation for one byte input data

Well, above implementation looks complicated! How can it be simplified?

• The first 8 left-shifts are useless because the CRC value is initialized with 0 so no XOR operation is performed. This means we can initialize the CRC value directly with the input byte.
• So only '0' are left in the input stream (the appended zeros). They do not have to be explicitly shifted-in, as the C# leftshift operator << fills in the LSB with '0' by default.
• This implies that the inputstream array is not required anymore.

Applying these simplifications result in following implementation (much better, isn't it?):

To illustrate how the algorithmus is working, the example from above (input byte 0xC2, generator polynomial 0x1D) is repeated - this time showing the intermediate values of each step of implementation Compute_CRC8_Simple_OneByte.

The fact that the crc value is left-shifted by one _before_ it's 'xored' with the divisor should become clear: it's due to the already discussed reason that the MSB bit of the generator polynomial is not stored / not used by the algorithm as well as it's result.

[Back to top]

4.3 General CRC-8 bitwise implementation

Till now only one byte was used as input data, so let's see what happens if the input data is extended to a byte array.
The first function Compute_CRC8_Simple_OneByte_ShiftReg() could easily be adapted (only the input parameter would be a byte array at which a 0x00 byte is appended), but what about Compute_CRC8_Simple_OneByte()?
The interesting point is at the border between two bytes: If one byte is completely processed, how is the subsequent byte incorporated into the calculation process? Again, let's start with a simple example (even more manual CRC-calculation action!):

Actually the algorithm handles one byte at a time, and does not consider the next byte until the current one is completely processed.
Refering to Compute_CRC8_Simple_OneByte, the value crc is set to 0x01 and the input looks like 0000000100000000... So let's see the state when the first byte is completely processed: 000000010000000000000000 100011101 --------- 000011101 Compare this to our manual approach where we have the second byte 0x02 already 'in range': 000000010000001000000000 100011101 --------- 000011111 So obviously the next byte has to be XORed with the current CRC value: 000011101 ^ 00000010 = 000011111 and the algorithm then continues with the 'new' xored value.
With this knowledge we can easily extend our algorithm to work with an input byte array of arbitrary length:

[Back to top]

4.4 Improved CRC-8 byte-by-byte algorithm (lookup table based)

So far the algorithm is quite inefficient as it works bit by bit. For larger input data, this could be quite slow. But how can our CRC-8 algorithm be accelerated?
The dividend is the current crc byte value - and a byte can only take 256 different values. The polynomial (= divisor) is fixed. Why not precompute the division for each possible byte by the fixed polynomial and store these result in a lookup table? This is possible as the remainder is always the same for the same dividend and divisor! Then the input stream can be processed byte by byte instead of bit by bit.
Let's use our common example to demonstrate the process manually:

For step 3 and 5, the lookup table is used instead of bit by bit processing - that makes the actual speedup.
Here an implementation for calculating the 256-element lookup table:

Then improved CRC-8 algorithm using the lookup table is as follow:

The improvement of speed comes at the cost of processing time to precalculate the table and of higher memory consumption of the 256-byte elements, but that's worth it :-)!
Please note that this is not yet the "full" CRC-8 algorithm implementation because it does not consider initial XOR values, final XOR values and reflection. This will be covered in chapter 7.

[Back to top]

5. Extending to CRC-16

The more bits the CRC value has the less is the probability of a collision: for CRC-8 there are only 256 different CRC values. This means if the data is disturbed or modified between sender and receiver, there is a probability of 1/256 that the modified data stream has the same CRC value as the original data stream, thus the error is not detected. Beside other factors (more on this in the theory part), increasing the CRC width results in better error protection.

This raises the question: What is the impact on the implementation if we want to extend it from CRC-8 to CRC-16?

• 1. Obviously a CRC-16 uses a polynomial of degree 16 with 17 terms, but similar to CRC-8 the most significant bit is implicitly 1. Therefore the generator polynomial as well as the CRC value have now a 16bit data type.
• 2. How to 'Xor-In' the next input byte (8bit) into the CRC value (16bit)? The answer is into the most significant byte of the CRC. Similar to chapter 4.3, let's visualize it with an example:

First, let's make another manual calculation, this time for CRC-16 with polynomial 0x1021:

What happens if the algorithm has handled the first input byte 0x01: 00000001000000000000000000000000 10001000000100001 ----------------- 00001000000100001 Here we see that the next input byte 0x02 = 00000010 has be xored into the MSB of 00001000000100001 to get 00001001000100001 to proceed.

• 3. The check if the most significant bit set changes because bit15 instead of bit7 has to be tested: 0x80 -> 0x8000

Therefore the CRC-16 simple implementation looks like:

The modification of the implementations for calculating the CRC-16 lookup table is now quite easy:

The actual byte by byte is a bit tricky so let's first check our example again:

The important point is here that after xoring the current byte into the MSB of the intermediate CRC, the MSB is the index into the lookup table.
Here the corresponding implementation for the table-based CRC-16 algorithm:

[Back to top]

6. Extending to CRC-32

After having understood the extension process from CRC-8 to CRC-16 in the previous chapter, the modifications to CRC-32 is pretty easy. I discard the detailed steps as they are very similar to the CRC-16 case - just a quick overview of the changes:

• CRC-32 uses a 33-bit polynom, however again the most signficant bit is always '1' and can be discarded. Therefore, the polynomial and the CRC value are represented by 32 bit variables.
• The bit operations change slightly: Moving the input byte into the MSB of CRC requires now a shift by 24. Also the check for the most significant bit uses a different mask of 0x80000000 instead of 0x8000.

Actually that's it, so here is the bitwise CRC-32 algorithm implementation:

Calculating the CRC-32 lookup table and using it for the CRC computation is then straight forward:

[Back to top]

7. CRC algorithm specification

At this point, you (and me hopefully... ;-) ) should know how CRC computation works and how to calculate it manually as well as how to implement it in your favorite programming language.

However, a CRC instance is defined by specific parameters. We have already seen that e.g. the width of the generator polynomial varies, but there are more definition parameters. In order to be able to implement each CRC instance, let's discuss how an CRC algorithm instance is described.

[Back to top]

7.1 CRC parametrization

Following standard parameters are used to define a CRC algorithm instance:

• Name: Well, a CRC instance has to be identified somehow, so each public defined CRC parameter set has a name like e.g. CRC-16/CCITT.
• Width (in bits): Defines the width of the result CRC value (n bits). Simultaneously, also the width of the generator polynomial is defined (n+1 bits). Most common used widths are 8, 16 and 32 bit. But theoretically all widths beginning from 1 are possible. In practice, even quite big (80 bit) or uneven (5 bit or 31 bit) widths are used.
• Polynomial: Used generator polynomial value. Note that different representations exist, see chapter 7.2.
• Initial Value: The value used to initialize the CRC value / register. In the examples above, always zero is used, but it could be any value.
  CAUTION: See chapter 8.6 for the correct handling of initial values not equal to 0.
• Input reflected: If this value is TRUE, each input byte is reflected before being used in the calculation. Reflected means that the bits of the input byte are used in reverse order. So this also means that bit 0 is treated as the most significant bit and bit 7 as least significant.
  Example with byte 0x82 = b10000010: Reflected(0x82) = Reflected(b10000010) = b01000001 = 0x41.
• Result reflected: If this value is TRUE, the final CRC value is reflected before being returned. The reflection is done over the whole CRC value, so e.g. a CRC-32 value is reflected over all 32 bits.
• Final XOR value: The Final XOR value is xored to the final CRC value before being returned. This is done after the 'Result reflected' step. Obviously a Final XOR value of 0 has no impact.
• Check value [Optional]: This value is not required but often specified to help to validate the implementation. This is the CRC value of input string "123456789" or as byte array: [0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39].

For a great overview over standard CRC algorithms, refer to [5].
Here a pseudo-code CRC-32 table-based implementation taking the definition parameters into account:

And finally a possible implementation to reflect a 16bit value:

[Back to top]

7.2 Representation of generator polynomials

It is worth to know that there are different ways to represent a generator polynomial in hexadecimal.
Remember: A CRC-n uses a generator polynomial of degree n of the form xⁿ + x^n-1 + ... + x¹ + x⁰. Note that it has n+1 coefficients.

• Normal representation: The most significant bit (= xⁿ) of the generator polynomial is left out in the hexadecimal representation (as it's always 1). The hexadecimal polynomial contains only the coefficients x^n-1 ... x⁰. We used normal respresentation in this article.
  Example: In the CRC-8 discussion we used polynomial 100011101. Discarding the most significant bit results in 100011101, which is 0x1D.
• Reversed representation: The most significant bit (= xⁿ) of the generator polynomial is left out in the hexadecimal representation (like in the normal representation), but the tail is then reflected ('LSB first'), i.e. each nibble is reversed. So the most-significant bit does not match x^n-1 as in the normal representation, but x⁰.
  Example: Polynomial is 100011101. Discarding the most significant bit results in 10001 1101. Reflection (reverse of each nibble) of 0001 1101 is 1011 1000 = 0xB8.
• Koopman representation: The least(!) significant bit (= x⁰) of the generator polynomial is discarded. The hexadecimal polynomial contains only the coefficients xⁿ ... x¹.
  Example: Polynomial is 100011101. Discarding the least significant bit results in 100011101 = 0x8E.

Note that there are also so-called reciprocal polynomials which have their own representation, see chapter 7.3.

[Back to top]

7.2.1 Choosing a generator polynomial

The length on the generator polynomial depends on the maximum length of the input data and the desired error detection properties. The more likely one or more bit errors shall be detected and/or the longer the input data may be, the longer the generator polynomial has to be. This also decreases the probality of collisions (same CRC value for different input data).
Note that the actual value of the generator polynomial has also major impact on its error detection capabilities and its design is non-trivial and requires serious math knowledge (e.g. see [2] for an expert article.)

[Back to top]

7.3 Reciprocal polynomials

Reciprocal polynomials are polynomials that are reflected. So the least significant coefficient becomes the most significant and the other way. In other words, a reciprocal polynomial is created from a polynomial by assigning coefficient xⁿ to x⁰, x^n-1 to x¹ and so on.
The representation is based on the Koopman representation, but reflected ('LSB first').

CAUTION: Sometimes reciprocal polynomials are called reversed polynomials. This can easily be mixed up with the reversed representation of polynomial as described in chapter 7.2. However these are two different things.

It's a fact that reversed polynomials are 'as good as' the polynomials of which they are the reciprocal ones referring to their error detection properties.
Unfortunately such polynomials make it all a bit more complicated: the calculated CRC value of a polynomial is NOT the same as the calculated CRC value of its reciprocal polynomial for the same message data!

Because the LSB and MSB are exchanged, you can think of the processing of reversed polynomials as they would be shifted from the other side into the CRC shift register: In the example of the CRC shift register in chapter 3 the input data was shifted from the right. If the reversed polynomial is used, you could get the same CRC result when shifting the input data from the left. Actually the whole processing is then just mirrored.
In the C# download package linked at the top, there is a 'reflected' implementation for each CRC class: Such a reflected CRC algorithm produces the same CRC result when using a reversed polynomial like the standard implementation using the non-reversed polynomial by 'mirroring' the processing.

[Back to top]

7.3.1 Reversed CRC lookup table and calculation of reciprocal CRC

The fact that there are the two variants MSB-to-LSB and LSB-to-MSB often causes confusion. For example this is the reason why often two different lookup tables are found in the net for the same CRC instance: For the well-known standard CRC-32 instance (e.g. PKZIP) with polynomial 0x04c11db7, you can find a lookup table starting with the values 0x00000000 and 0x04C11DB7, the other one with 0x00000000 and 0x77073096. The first one correspond to the algorithms described in this article, while the second corresponds to the reciprocal variant where the coefficients are reflected.
Let's recall the calculation for the 'normal' CRC-32 lookup table, compared to the 'reciprocal variant' of the CRC-32 lookup table :

To calculate the reciprocal variant lookup-table, two changes are required to handle the reflected bit-order: At first, the CRC parameter Polynomial has to be reflected, and second the order of bit processing in the algorithm itself needs to be changed from MSB-to-LSB to LSB-to-MSB, resulting in right-shifting instead of left-shifting.
So this results in two different look-up tables. This implies that also the actual CRC calculation needs to adapated for the reciprocal variant in order to retrieve the same CRC result as for the normal variant.

In general, to use the reciprocal variant of a CRC-model, following changes are required for the CRC model: The CRC parameters Polynomial and Initial Value have to be reflected, the parameters Input reflected and Result reflected have to be negated and the parameter Final XOR value remains unchanged. Here some code to change the CRC model to the reciprocal CRC model:

With this information, here the table-based calculation of reciprocal CRC-32 (right) compared to the normal calculation (left):

[Back to top]

7.4 Extending to arbitrary CRC sizes (width of polynomials)

Until now, only CRC widths of 8, 16 and 32 have been considered, thus integer multiples of byte (8 bit) sizes. Of course, there are also CRC algorithms with other widths. What needs to be considered in the implementation to support those kinds of CRC algorithms? This is discussed in this chapter. Note that in the following, still the input values are assumed to be bytes (8 bit values).

It is obvious that the underlying data type must be sufficiently large to hold the values (so e.g. use 32 bit values for CRC-28). Considering the simple bitwise implementation, following values depend on the CRC width and needs to be adapted as follows (Note: At first, only CRC with > 8 are considered):

CRC > 8:

• The number of bits to move the next byte into the MSB of the CRC register depends on the CRC width. E.g. for CRC-11, the input byte needs only be shifted by 3.
  In general: Number of bits to left shift = crcsize - 8.
• The most significant bit of the CRC is checked if it is set. Therefore the needed bit mask depends on the CRC width. E.g. a CRC-11 value has 11 binary digits, so the bit mask is in binary b100 0000 0000 = 0x400.
  In general: topbitmask = 1 << (crcsize - 1).
• For a CRC-x, only the lower x bits are significant. If a larger data type is used, then the upper unused bits shall be cleared, otherwise the result is interpreted incorrectly. So a mask should be applied to the CRC value. E.g for CRC-11, only the 11 lower bits are relevant, thus the mask would be b111 1111 1111 = 0x7FF.
  In general: final mask = (1 << crcsize) - 1.
• The reflection of a value must also be considered.

With this information, a sample CRC implementation for CRC width of 8 or greater might look like the following (Note: due to usage of ushort, actually only up to CRC-16 is supported but this changed by replacing uhsort by a larger data type):

CRC < 8:

For a CRC width smaller than 8, additional points must taken into account because byte values are used as input values. This means the CRC register is actually smaller than an input value. This is no issue when using the initial shift register implementation.
However, it matters for our simple implementation where whole bytes are "xored" into the CRC register. It would be required to only "xor" the relevant bits and handle the remaining bits of the input byte in the next loop which complicates the handling of the inputs bytes significantly.

An alternative approach which results in a simpler implementation is to use always an 8 bit CRC register also for a CRC width smaller than 8. The trick is then to only work the "x" most significant bits of the CRC register for a CRC with width "x". This means:

• The next byte of the input byte stream is just moved into the CRC register, no need to shift the value inside the CRC register.
• The top bit mask is always 0x80.
• The final mask is always 0xFF.
• The initial and polynomial values are shifted to the left so that both are located in the most signficant bits of the 8-bit CRC value.
• At the end of the calculation, the CRC value is shifted back so that it is located in the least signficant bits of the 8-bit CRC register value, otherwise the result is interpreted incorrectly.

Summarized, a possible implementation for CRC-x (where x < 8) might look like following:

[Back to top]

8. Additional remarks (points worth to know)

This last chapter contains interesting (and maybe not completely obvious) topics about CRC calculation. These points are optional and contain just additional information, for those who are interested in same background information.

[Back to top]

8.1 Basic mathematical view of CRC (read it first)

First let's recall some mathematical basics for CRC definition for better understanding of the next points. Please note that the sub chapter actually represents the same information as chapter 2 (don't hesitate to have a quick look back at this introduction chapter):

CRC-n uses a generator polynomial G(x) which has degree n and n+1 terms: xⁿ + x^n-1 + ... + x¹ + x⁰.
The n+1 terms means that the polynomial has a length of n + 1 bits (using normal representation the most significant bit is left out).

The computation of CRC, which we know is based on polynomial division (or more specific on Polynomial arithmetic modulo 2), can be stated as M(x) * xⁿ = G(x) * Q(x) + R(x) where:

• M(x) is the input binary string, so M(x)*xⁿ is the input string with n zero bits appended. (Stop! Why is it like that? Answer: We'll come to this later in chapter 8.5 ).
• G(x) is the generator polynomial with degree n as already stated.
• Q(x) is quotient of the division and not used further.
• R(x) is the remainder = the actual CRC value.

[Back to top]

8.2 Background to CRC verification

Or: "Why is the verification result zero if the CRC is computed over the input data with the actual CRC value appended (in the manual approach)?"

Actually, the XOR arithmetic of CRC division is comparable to school arithmetic in this case, so let's start with an example.

We know that M(x) * xⁿ is the input data bit string with n zero bits appended. As we see later ( in chapters 8.4 and 8.5) appending the bits of R(x) to this input string can be stated as M(x) * xⁿ - R(x).
Rearrange the formula: M(x) * xⁿ = G(x) * Q(x) + R(x)  ===>  M(x) * xⁿ - R(x) = G(x) * Q(x)
Here we see that M(x) * xⁿ - R(x) (which is the input data with the CRC appended) is an integer multiple of the polynomial G(x). And this means that M(x) * xⁿ - R(x) divided by G(x) results in 0.

Side note 1: M(x) * xⁿ = G(x) * Q(x) + R(x) can also be written using the modulo operator mod as R(x) = (M(x) * xⁿ) mod G(x).

[Back to top]

8.3 CRC-1 is the same as a parity bit

This is correct. Here some clarifying words: A parity bit indicates if the number of bits with value 1 is even or odd. In the case of even parity, the number of bits whose value is 1 in a given set are counted. If that total is odd, the parity bit value is set to 1, making the total count of 1's in the set an even number.

CRC-1 has degree 1 and 2 terms: a*x^1 + b*x^0. The most significant bit is always 1. However a polynomial 10 has no sense because the actual CRC value would always be 0. So CRC-1 has polyomial 11 (binary) which is just 0x01 in normal representation. And this is in fact the calculation of an even parity bit. Remember that the actual CRC value has n bits, so for CRC-1 the remainder has 1 bit, either 0 or 1.

[Back to top]

8.4 Why is addition is the same as subtraction in CRC arithmetic?

CRC computation is performed using so-called polynomial arithmetic. This polynomial arithmetic is based on division over the finite field with two elements: 0 and 1. Also called Galois field over two elements.
To define the addition operation, there are only four cases to distinct:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 - note that there is no carry!

Due to the fact that we perform the calculation over a finite field (refer to [6] for more info), there is only one way to define subtraction:
0 - 0 = 0
0 - 1 = 1
1 - 0 = 1
1 - 1 = 0

We see that addition and subtraction are the same: Basically this is the XOR operation we have already used several times above.
That's the reason why we stated above that M(x) * xⁿ - R(x) and M(x) * xⁿ + R(x) are the same in CRC arithmetic.

[Back to top]

8.5 Why does multiplication with xⁿ append n zeros?

This is due to the fact that each trailing zero bit of adds a factor of x. Let's say we have the polynomial xⁿ + x^n-1 + ... + x¹ + x⁰. Multiply it with x:
x* (xⁿ + x^n-1 + ... + x¹ + x⁰) = xⁿ⁺¹ + xⁿ + ... + x¹
So by multiplying with x, we have increased the degree of the polynomial by 1, which equals appending a zero to the right. Maybe this gets clearer with an example:

[Back to top]

8.6 When using an initial value other than zero in the shift register, the result is incorrect.

In chapter 7 initial values were introduced, with the description that it's the value used to initialize the shift register. Well, you can read this statement also in other CRC articles, however there is a trap that is commonly not well described (if at all).

Unfortunately, not. Above examples give the two different CRC values of 0x2A and 0xE0.

Looking at the simple (non-lookup table, but byte-wise handling) CRC-8 implementation, we see the reason:

> Before the actual first xor operation of the CRC calculation is performed, the initial value is xored with the first input byte!

What does that mean for the initial value of the shift register when performing the CRC calculation bit by bit, like the pen and paper approach at the top? Answer: The register must be initialized with the initial value 'xored' with the first input bytes. For CRC-16 the initial value must be xored with the first two input bytes, for CRC-32 with the first four input bytes, and so on.
Here an example implementation how to initialize a CRC-32 shift register and the corresponding shift register algorithm. This is taken from the C# source package linked at the top of the article:

[Back to top]

9. Conclusion & References

This article is my own guide to CRC: very practical and based on many examples - quite different to most of the other articles on the web. I hope you found it interesting and that it supported you in understanding and implementing CRC!
Drop me a line for corrections, hints, criticism, praise ;)

Sunshine, February 2015 (last update: June 2023)

References

Updates

• 2024/03/23:
  • Added a note to chapter 4.4 that the presented algorithm at this location is only an intermediate version to avoid misunderstandings.
• 2023/06/19:
  • Fixed grammar: Replaced divident by dividend.
  • Clarified several locations that CRC-n uses a polynomial of degree n which has n+1 terms.
• 2023/03/11:
  • Added chapter 7.4 (Extending to arbitrary CRC sizes (width of polynomials))
• 2019/03/22:
  • Fixed a bug in chapter 7.3.1 about the final XOR value when using the reciprocal variant: In the reciprocal CRC model, the final XOR value must not be reflected, contrary to my previous statement.
    Note that in the source code, this was already correctly implemented.
• 2018/12/29:
  • Replaced occurrences of x^n by xⁿ for consistent naming.
• 2018/09/29:
  • Fixed a glitch in the "Step-by-step visualization of simple CRC-8 algorithmus" table. Thanks to the careful reader for pointing me to it.
  • Reworked the chapters of representation of polynomials and reciprocal polynomials - hopefully they are more understandable now (chapter 7.2 and 7.3).
  • Fixed a typo in chapter 8.6 (byte 0x01 instead of 0x11). Thanks to the careful reader for pointing me to it.
• 2016/11/11:
  • Added chapters 7.3 (reversed polynomials) and chapter 8.6 (initial value for shift register)
  • Updated C# source package with CRC classes that work in the reversed way.
  • Updated Javascript Online calculator to show optionally the CRC lookup table in the reversed way.
• 2016/08/19: Fixed a typo in chapter 8.4: 1 + 1 = 0 instead of 1 + 1 = 1.
• 2015/05/30: Added chapter 8.