Understanding and implementing CRC (Cyclic Redundancy Check) calculation

Table of Contents


View Online CRC Silverlight application now!
View Online CRC Javascript application now!
Download C# source code (25 kb)

Article updated November 2016.


[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 orientied note to all general explanations on the web.

Here's the outline:

[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 (divident) 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 (divident and divisor) are not treated as normal integer values, but as binary polyonimals where the actual bits are used as coefficients.

For example, the input data 0x25 = 0010 0101 is taken as 0*x7 + 0*x6 + 1*x5 + 0*x4 + 0*x3 + 1*x2 + 0*x1 + 1*x0.

XOR 0 1
0 0 1
1 1 0

XOR truth table

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 divident 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 divident % 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:

Example:


Input data is the byte 0xC2 = b11000010.
As generator polynomial (=divisor), let's use b100011101.
The divisor has 9 bits (therefore this is a CRC-8 polynomial), so append 8 zero bits to the input pattern .
Align the leading '1' of the divisor with the first '1' of the divident and perform a step-by-step school-like division, using XOR operation for each bit:

ABCDEFGHIJKLMNOP 1100001000000000 100011101 --------- 010011001 100011101 ---------- 000101111 100011101 (*) --------- 001100101 100011101 --------- 010001001 100011101 --------- 000001111 = 0x0F ABCDEFGHIJKLMNOP

The actual CRC value is 0x0F.

Useful observations:


[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:

Example verification:


The actual transmission data (input data + CRC) would be b1100001000001111 Note that we have used an 8bit CRC, so the actual CRC value is also 8bit long. The generator polynomial is statically defined by the used CRC algorithm and so it's known by the receiver.

ABCDEFGHIJKLMNOP 1100001000001111 100011101....... ---------....... 010011001....... 100011101..... ---------...... 000101111...... 100011101.. ---------... 001100100... 100011101 ---------. 010001110. 100011101 --------- 000000000 -> Remainder is 0, data ok! ABCDEFGHIJKLMNOP


[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.
  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

CRC-8 Shift Register Example: Input data = 0xC2 = b11000010 (with 8 zero bits appended: b1100001000000000), Polynomial = b100011101


1. CRC-8 register initialized with 0. --- --- --- --- --- --- --- --- | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <-- b1100001000000000 --- --- --- --- --- --- --- --- 2. Left-Shift register by one position. MSB is 0, so nothing do happen, shift in next byte of input stream. --- --- --- --- --- --- --- --- | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | <-- b100001000000000 --- --- --- --- --- --- --- --- 3. Repeat those steps. All steps are left out until there is a 1 in the MSB (nothing interesting happens), then the state looks like: --- --- --- --- --- --- --- --- | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | <-- b00000000 --- --- --- --- --- --- --- --- 4. Left-Shift register. MSB 1 pops out: --- --- --- --- --- --- --- --- 1 <- | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | <-- b0000000 --- --- --- --- --- --- --- --- So XOR the CRC register (with popped out MSB) b110000100 with polynomial b100011101 = b010011001 = 0x99. The MSB is discarded, so the new CRC register value is 010011001: --- --- --- --- --- --- --- --- | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | <-- b0000000 --- --- --- --- --- --- --- --- 5. Left-Shift register. MSB 1 pops out: b100110010 ^ b100011101 = b000101111 = 0x2F: --- --- --- --- --- --- --- --- | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | <-- b000000 --- --- --- --- --- --- --- --- 6. Left-shift register until a 1 is in the MSB position: --- --- --- --- --- --- --- --- | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | <-- b0000 --- --- --- --- --- --- --- --- 7. Left-Shift register. MSB 1 pops out: b101111000 ^ b100011101 = b001100101 = 0x65: --- --- --- --- --- --- --- --- | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | <-- b000 --- --- --- --- --- --- --- --- 8. Left-shift register until a 1 is in the MSB position: --- --- --- --- --- --- --- --- | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | <-- b00 --- --- --- --- --- --- --- --- 9. Left-Shift register. MSB 1 pops out: b110010100 ^ b100011101 = b010001001 = 0x89: --- --- --- --- --- --- --- --- | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | <-- b0 --- --- --- --- --- --- --- --- 10. Left-Shift register. MSB 1 pops out: b10001001 ^ b100011101 = b000001111 = 0x0F: --- --- --- --- --- --- --- --- | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | <-- <empty> --- --- --- --- --- --- --- --- All input bits are processed, the algorithm stops. The shift register contains now the CRC value which is 0x0F.


[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 polynom, 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 divident, the XOR result for this bit is always 0.
This means we leave out the MSB '1', so we can use the generator polyonimal 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:

public static byte Compute_CRC8_Simple_OneByte_ShiftReg(byte byteVal)
{
    const byte generator = 0x1D;
    byte crc = 0; /* init crc register with 0 */
    /* append 8 zero bits to the input byte */
    byte[] inputstream = new byte[] { byteVal, 0x00 };
    /* handle each bit of input stream by iterating over each bit of each input byte */
    foreach (byte b in inputstream)
    {
        for (int i = 7; i >= 0; i--)
        {
            /* check if MSB is set */
            if ((crc & 0x80) != 0)
            {   /* MSB set, shift it out of the register */
                crc = (byte)(crc << 1);
                /* shift in next bit of input stream:
                 * If it's 1, set LSB of crc to 1.
                 * If it's 0, set LSB of crc to 0. */

                crc = ((byte)(b & (1 << i)) != 0) ? (byte)(crc | 0x01) : (byte)(crc & 0xFE);
                /* Perform the 'division' by XORing the crc register with the generator polynomial */
                crc = (byte)(crc ^ generator);
            }
            else
            {   /* MSB not set, shift it out and shift in next bit of input stream. Same as above, just no division */
                crc = (byte)(crc << 1);
                crc = ((byte)(b & (1 << i)) != 0) ? (byte)(crc | 0x01) : (byte)(crc & 0xFE);
            }
        }
    }
    return crc;
}

[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?

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

public static byte Compute_CRC8_Simple_OneByte(byte byteVal)
{
    const byte generator = 0x1D;
    byte crc = byteVal; /* init crc directly with input byte instead of 0, avoid useless 8 bitshifts until input byte is in crc register */

    for (int i = 0; i < 8; i++)
    {
        if ((crc & 0x80) != 0)
        { /* most significant bit set, shift crc register and perform XOR operation, taking not-saved 9th set bit into account */
            crc = (byte)((crc << 1) ^ generator);
        }
        else
        { /* most significant bit not set, go to next bit */
            crc <<= 1;
        }
    }

    return crc;
}

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.

Step-by-step visualization of simple CRC-8 algorithmus:


1100001000000000crc = 0xC2
100011101i = 0: 0xC2 = b11000010 -> MSB set:
---------
010011001 i = 0: crc = (crc << 1) ^ generator = (0xC2 << 1) ^ 0x1D = 0x184 ^ 0x1D = 0x99.
 100011101 i = 1: 0x99 = b10011001 -> MSB set:
 ---------
 0000101111 i = 1: crc = (0x99 << 1) ^ 0x1D = 0x132 ^ 0x1D = 0x2F
   100011101 i = 2: 0x2F = b00101111 -> MSB not set: crc = (0x2F << 1) = 0x5E
    100011101 i = 3: 0x5E = b01011110 -> MSB not set: crc = (0x5E << 1) = 0xBC
     100011101 i = 4: 0xBC = b10111100 -> MSB set:
     ---------
     001100101 i = 4: crc = (0xBC << 1) ^ 0x1D = 0x178 ^ 0x1D = 0x65
      100011101 i = 5: 0x65 = b01100101 -> MSB not set: crc = (0x65 << 1) = 0xCA
       100011101 i = 6: 0xCA = b11001010 -> MSB set:
       ---------
       010001001 i = 6: crc = (0xCA << 1) ^ 0x1D = 0x194 ^ 0x1D = 0x89
        100011101 i = 7: 0x89 = b10001001 -> MSB set:
        ---------
        000001111 i = 7: crc = (0x89 << 1) ^ 0x1D = 0x112 ^ 0x1D = 0x0F

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!):

Example for two byte input data {0x01, 0x02} with polynomial 0x1D


000000010000001000000000 100011101 --------- 0000111110000 100011101 --------- 0111011010 100011101 --------- 0110001110 100011101 --------- 0100100110 100011101 --------- 0001110110 = 0x76

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:

public static byte Compute_CRC8_Simple(byte[] bytes)
{
    const byte generator = 0x1D;
    byte crc = 0; /* start with 0 so first byte can be 'xored' in */

    foreach (byte currByte in bytes)
    {
        crc ^= currByte; /* XOR-in the next input byte */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x80) != 0)
            {
                crc = (byte)((crc << 1) ^ generator);
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

[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 divident 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 divident 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:

Process for bytewise CRC-8 using input data {0x01, 0x02} and polynomial 0x1D


1. Init crc = 0x00.
2. 'Xor-in' next input byte 0x01: 0x00 ^ 0x01 = 0x01.
3. Calculate CRC-8 of 0x01 using precomputed lookup table: table[0x01] = crc = 0x1D.
4. 'Xor-in' next input byte 0x02: 0x1D ^ 0x02 = 0x1F.
5. Calculate CRC-8 of 0x1F: using precomputed lookup table: table[0x1F] = crc = 0x76.

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:

public static void CalulateTable_CRC8()
{
    const byte generator = 0x1D;
    crctable = new byte[256];
    /* iterate over all byte values 0 - 255 */
    for (int divident = 0; divident < 256; divident++)
    {
        byte currByte = (byte)divident;
        /* calculate the CRC-8 value for current byte */
        for (byte bit = 0; bit < 8; bit++)
        {
            if ((currByte & 0x80) != 0)
            {
                currByte <<= 1;
                currByte ^= generator;
            }
            else
            {
                currByte <<= 1;
            }
        }
        /* store CRC value in lookup table */
        crctable[divident] = currByte;
    }
}

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

public static byte Compute_CRC8(byte[] bytes)
{
    byte crc = 0;
    foreach (byte b in bytes)
    {
        /* XOR-in next input byte */
        byte data = (byte)(b ^ crc);
        /* get current CRC value = remainder */
        crc = (byte)(crctable[data]);
    }

    return crc;
}

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 :-)!


[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?

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

Example for two byte input data {0x01, 0x02} with polynomial 0x1021 (1 0001 0000 0010 0001)


ABCDEFGHIJKLMNOPQRSTUVWXYZ 00000001000000100000000000000000 10001000000100001 ----------------- 00001001000100001 = 0x1221 (intermediate CRC value after completing first byte) 10001000000100001 ----------------- 00011001000110001 10001000000100001 ----------------- 01000000110101001 10001000000100001 ----------------- 00001001101110011 = 0x1373 (final CRC value after both bytes) ABCDEFGHIJKLMNOPQRSTUVWXYZ

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.

Therefore the CRC-16 simple implementation looks like:

public static ushort Compute_CRC16_Simple(byte[] bytes)
{
    const ushort generator = 0x1021; /* divisor is 16bit */
    ushort crc = 0; /* CRC value is 16bit */

    foreach (byte b in bytes)
    {
        crc ^= (ushort(b << 8); /* move byte into MSB of 16bit CRC */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x8000) != 0) /* test for MSB = bit 15 */
            {
                crc = (ushort((crc << 1) ^ generator);
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

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

public static void CalculateTable_CRC16()
{
    const ushort generator = 0x1021;
    crctable16 = new ushort[256];

    for (int divident = 0; divident < 256; divident++) /* iterate over all possible input byte values 0 - 255 */
    {
        ushort curByte = (ushort(divident << 8); /* move divident byte into MSB of 16Bit CRC */

        for (byte bit = 0; bit < 8; bit++)
        {
            if ((curByte & 0x8000) != 0)
            {
                curByte <<= 1;
                curByte ^= generator;
            }
            else
            {
                curByte <<= 1;
            }
        }

        crctable16[divident] = curByte;
    }
}

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

Process for bytewise CRC-16 using input data {0x01, 0x02} and polynomial 0x1021


1. Init crc = 0
2. Handle first input byte 0x01:
 2.1 'Xor-in' first input byte 0x01 into MSB(!) of crc:
   0000 0000 0000 0000 (crc)
   0000 0001 0000 0000 (input byte 0x01 left-shifted by 8)
   -------------------
   0000 0001 0000 0000 = 0x0100
   The MSB of this result is our current divident: MSB(0x100) = 0x01.
 2.2 So 0x01 is the divident. Get the remainder for divident from our table: crctable16[0x01] = 0x1021. (Well this value is famila from the manual computation above.)
   Remember the current crc value is 0x0000. Shift out the MSB of current crc and xor it with the current remainder to get the new CRC:
   0001 0000 0010 0001 (0x1021)
   0000 0000 0000 0000 (CRC 0x0000 left-shifted by 8 = 0x0000)
   -------------------
   0001 0000 0010 0001 = 0x1021 = intermediate crc.
3. Handle next input byte 0x02:
 Currently we have intermediate crc = 0x1021 = 0001 0000 0010 0001.
 3.1 'Xor-in' input byte 0x02 into MSB(!) of crc:
   0001 0000 0010 0001 (crc 0x1021)
   0000 0010 0000 0000 (input byte 0x02 left-shifted by 8)
   -------------------
   0001 0010 0010 0001 = 0x1221
   The MSB of this result is our current divident: MSB(0x1221) = 0x12.
 3.2 So 0x12 is the divident. Get the remainder for divident from our table: crctable16[0x12] = 0x3273.
   Remember the current crc value is 0x1021. Shift out the MSB of current crc and xor it with the current remainder to get the new CRC:
   0011 0010 0111 0011 (0x3273)
   0010 0001 0000 0000 (CRC 0x1021 left-shifted by 8 = 0x2100)
   -------------------
   0001 0011 0111 0011 = 0x1373 = final crc.

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:

public static ushort Compute_CRC16(byte[] bytes)
{
    ushort crc = 0;
    foreach (byte b in bytes)
    {
        /* XOR-in next input byte into MSB of crc, that's our new intermediate divident */
        byte pos = (byte)( (crc >> 8) ^ b); /* equal: ((crc ^ (b << 8)) >> 8) */
        /* Shift out the MSB used for division per lookuptable and XOR with the remainder */
        crc = (ushort)((crc << 8) ^ (ushort)(crctable16[pos]));

    }

    return crc;
}

[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:

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

public uint Compute_CRC32_Simple(byte[] bytes)
{
    const uint polynomial = 0x04C11DB7; /* divisor is 32bit */
    uint crc = 0; /* CRC value is 32bit */

    foreach (byte b in bytes)
    {
        crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x80000000) != 0) /* test for MSB = bit 31 */
            {
                crc = (uint)((crc << 1) ^ polynomial);
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

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

private void CalculateCrcTable_CRC32()
{
    const uint polynomial = 0x04C11DB7;
    crcTable = new uint[256];

    for (int divident = 0; divident < 256; divident++) /* iterate over all possible input byte values 0 - 255 */
    {
        uint curByte = (uint)(divident << 24); /* move divident byte into MSB of 32Bit CRC */
        for (byte bit = 0; bit < 8; bit++)
        {
            if ((curByte & 0x80000000) != 0)
            {
                curByte <<= 1;
                curByte ^= polynomial;
            }
            else
            {
                curByte <<= 1;
            }
        }

        crcTable[divident] = curByte;
    }
}

public uint Compute_CRC32(byte[] bytes)
{
    uint crc = 0;
    foreach (byte b in bytes)
    {
        /* XOR-in next input byte into MSB of crc and get this MSB, that's our new intermediate divident */
        byte pos = (byte)((crc ^ (b << 24)) >> 24);
        /* Shift out the MSB used for division per lookuptable and XOR with the remainder */
        crc = (uint)((crc << 8) ^ (uint)(crcTable[pos]));
    }

    return crc;
}

[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 favourite 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:

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:

public uint Compute_CRC32(byte[] bytes)
{
    uint crc = crcModel.Initial; /* CRC is set to specified initial value */
    foreach (byte b in bytes)
    {
        /* reflect input byte if specified, otherwise input byte is taken as it is */
        byte curByte = (crcModel.InputReflected ? CrcUtil.Reflect8(b) : b);

        /* XOR-in next input byte into MSB of crc and get this MSB, that's our new intermediate divident */
        byte pos = (byte)((crc ^ (curByte << 24)) >> 24);
        /* Shift out the MSB used for division per lookuptable and XOR with the remainder */
        crc = (uint)((crc << 8) ^ (uint)(crcTable[pos]));
    }
    /* reflect result crc if specified, otherwise calculated crc value is taken as it is */
    crc = (crcModel.ResultReflected ? CrcUtil.Reflect32(crc) : crc);
    /* Xor the crc value with specified final XOR value before returning */
    return (uint)(crc ^ crcModel.FinalXor);
}

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

public static ushort Reflect16(ushort val)
{
    ushort resVal = 0;

    for (int i = 0; i < 16; i++)
    {
        if ((val & (1 << i)) != 0)
        {
            resVal |= (ushort)(1 << (15 - i));
        }
    }

    return resVal;
}

[Back to top]

7.2 Representation of generator polyonomials

It is worth to know that there are different ways to represent a generator polynomial in hexadecimal.


INFO:


Please note that this only affects the representation of the polynomial. But the key point is that in each case the SAME polynomial is used for calculation.
Consider the often used CRC-16 polynomial x^16 + x^12 + x^5 + 1. In binary, that's 1 0001 0000 0010 0001.
Here the three different representations for this example:

1 0001 0000 0010 0001 0001 0000 0010 0001 = 0x1021 - Normal Representation 0001 0000 0010 0001 -> reversed : 1000 0100 0000 1000 = 0x8408 - Reversed representation 1 0001 0000 0010 000 -> rearranged: 1000 1000 0001 0000 = 0x8810 - Koopman representation


[Back to top]

7.2.1 Choosing a generator polyonomial

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 Reversed or reciprocal polyonomials

Reversed or reciprocal polyonomials are polynomials that are reflected. So the least significant coefficient becomes the most significant and the other way.

Example: Keep with the CRC-16 polynomial 0x1021 which has binary respresentation 1 0001 0000 0010 0001.
Reversing (or reflecting) the polynomial results in 1 0000 1000 0001 0001 = 0x0811

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 polyonomial 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]

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: xn + xn-1 + ... + x1 + x0.
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).

Example: A CRC-8 with polynomial 0x07 is actually the value 100000111 = 1*x8 + 0*x7 + 0*x6 + 0*x5 + 0*x4 + 0*x3 + 1*x2 + 1*x1 + 1*x0.

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) * xn = G(x) * Q(x) + R(x) where:


[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.

Assume the input data M(x) * xn is the number 195 and the divisor G(x) is 29. We would calculate:
195 / 29 = 6 remainder 21(side note 1). This is the same as 195 = 29 * 6 + 21 (which corresponds to M(x) * x^n = G(x) * Q(x) + R(x)). So the CRC value R(x) is 21.

First verification approch (CRC is transmitted separately to the input data):
The sender sends the input data 195 along with the CRC value 21. The receiver then would take the input data and perform the same calculation (remember the generator polynomial is fixed and statically known by transmitter and receiver): 195 % 29 = 21. The calculated remainder is the same as the received one, so the data transmission was faultless.

Second verification approach (CRC is appended to the input data):
The CRC value is appended to the input data which corresponds in school arithemtic to subtraction. So the CRC value 21 is subtracted from input data 195 resulting in 174 ( = M(x) * x^n - R(x)). The receiver would perform 174 % 29 = 0, so the remainder is zero and the data transmission was faultless.

We know that M(x) * xn 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^n - R(x).
Rearrange the formula: M(x) * x^n = G(x) * Q(x) + R(x)  ===>  M(x) * x^n - R(x) = G(x) * Q(x)
Here we see that M(x) * x^n - 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^n - R(x) divided by G(x) results in 0.

Side note 1: M(x) * x^n = G(x) * Q(x) + R(x) can also be written using the modulo operator mod as R(x) = (M(x) * x^n) 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.

Example: The value 0x34 = 0011 0100 has three '1' bits. Because three is odd, the parity bit is 1.

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.

Here an example for the value 0x34:

001101000 11 --------- 0001000 11 ------- 0100 11 --- 010 11 -- 01 = CRC = 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^n - R(x) and M(x) * x^n + R(x) are the same in CRC arithmetic.


[Back to top]

8.5 Why does multiplication with xn 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 xn + xn-1 + ... + x1 + x0. Multiply it with x:
x* (xn + xn-1 + ... + x1 + x0) = xn+1 + xn + ... + x1
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:

Example:


Assume the polynomial 01010010 = x^6 + x^4 + x and add a zero:
010100100 = x^7 + x^5 + x^2 = x * (x^6 + x^4 + x). So each factor of x appends a zero.



[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).

Example: If that would be true than e.g. following two CRC instances should calculate the same CRC:


Instance a: Initial value = 0x00, polynomial = 0x9B, input message data = [0xFF, 0x01].
Instance b: Initial value = 0xFF, polynomial = 0x9B, input message data = [0x01].

Assumption: Because in CRC instance a), the initial value is zero, nothing will happen (meaning no xor operation will be computed), until the first data byte 0xFF is completely shifted into the register, because 0x00 has no bit set. Then we have actually the same state as CRC instance b), so the processing of the remaining byte 0x11 should result the in the same CRC value for both cases. Right?

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:

public byte Compute_Simple(byte[] bytes)
{
  byte crc = crcModel.Initial;

  foreach (byte b in bytes)
  {
    byte curByte = (crcModel.InputReflected ? CrcUtil.Reflect8(b) : b);
    crc ^= curByte; /* XOR-in the next input byte */

    for (int i = 0; i < 8; i++)
    {
      if ((crc & 0x80) != 0)
      {
          crc = (byte)((crc << 1) ^ crcModel.Polynomial);
      }
      else
      {
          crc <<= 1;
      }
    }
  }

  crc = (crcModel.ResultReflected ? CrcUtil.Reflect8(crc) : crc);
  return (byte)(crc ^ crcModel.FinalXor);
}

> 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:

private uint GetInitialShiftRegister(byte[] bytes)
{
  byte b1 = 0, b2 = 0, b3 = 0, b4 = 0;
  if (bytes.Length >= 1)
  {
    b1 = crcModel.InputReflected ? CrcUtil.Reflect8(bytes[0]) : bytes[0];
  }
  if (bytes.Length >= 2)
  {
    b2 = crcModel.InputReflected ? CrcUtil.Reflect8(bytes[1]) : bytes[1];
  }
  if (bytes.Length >= 3)
  {
    b3 = crcModel.InputReflected ? CrcUtil.Reflect8(bytes[2]) : bytes[2];
  }
  if (bytes.Length >= 4)
  {
    b4 = crcModel.InputReflected ? CrcUtil.Reflect8(bytes[3]) : bytes[3];
  }
  return (uint)(crcModel.Initial ^ (uint)((uint)b4 << 24 | (uint)b3 << 16 | (uint)b2 << 8 | b1));
}

public uint Compute_Simple_ShiftReg(byte[] bytes)
{
    uint crc = GetInitialShiftRegister(bytes);
    /* skip first four bytes, already inside crc register */
    for (int byteIndex = 4; byteIndex < bytes.Length + 4; byteIndex++)
    {
      byte curByte = (byteIndex < bytes.Length) ? (crcModel.InputReflected ? CrcUtil.Reflect8(bytes[byteIndex]) : bytes[byteIndex]) : (byte)0;

      for (int i = 0; i <= 7; i++)
      {
        if ((crc & LOWBIT_MASK) != 0)
        {
          crc = (uint)(crc >> 1);
          crc = ((uint)(curByte & (1 << i)) != 0) ? (uint)(crc | 0x80000000) : (uint)(crc & 0x7FFFFFFF);
          crc = (uint)(crc ^ crcModel.Polynomial);
        }
        else
        {
          crc = (uint)(crc >> 1);
          crc = ((uint)(curByte & (1 << i)) != 0) ? (uint)(crc | 0x80000000) : (uint)(crc & 0x7FFFFFFF);
        }
      }
    }
    crc = (crcModel.ResultReflected ? CrcUtil.Reflect32(crc) : crc);
    return (uint)(crc ^ crcModel.FinalXor);
}


[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 (updated August 2016)

References

[1] Cyclic redundancy check @ Wikipedia
[2] "Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks". The International Conference on Dependable Systems and Networks: 145–154. Retrieved 29 December 2014.
[3] Mathematics of cyclic redundancy checks @ Wikipedia
[4] A Painless Guide to CRC Error Detection Algorithms
[5] CRC RevEng - Catalogue of parametrised CRC algorithms
[6] Finite field @ Wikipedia

Updates