Cyclic Redundancy Check

The cyclic redundancy check (CRC) is a method for error detection in digital data transmission and storage. The so-called CRC-code checksum is calculated from the transmitted data and sent together with this data. Based off this checksum, the recipient can verify if data was changed during the transmission.

Functionality

The algorithm is based on polynomial division over a finite body. The data is interpreted as bit sequence of a certain length. This bit sequence is divided through a firmly defined generator polynomial and the residual value of this division is the checksum that is attached to the data.

The generator polynomial is statically defined and must be known to the sender as well as to the recipient.

Binary polynomial division

Both data and generator are represented as a sequence of ones and zeros, but are treated as polynomials:

bit sequence: 1 1 1 0 0 0 1

polynomial: 1*x^6 + 1*x^5 + 1*x^4 + 0*x^3 + 0*x^2 + 0*x^1 + 1*x^0

The bits are the coefficients of a polynomial. When dividing a bit sequence by the generator polynomial, it should be noted that the calculation is based on an XOR gate:

XOR	0	1
0	0	1
1	1	0

Example calculation

bit sequence:  1 1 1 0 0 1 0 0 0 0
generator: 1 0 0 1

1 1 1 0 0 0 1 0 0 0 0 % 1 0 0 1
1 0 0 1 | | | | | | |
------- | | | | | | |
0 1 1 1 0 | | | | | |
  1 0 0 1 | | | | | |
  ------- | | | | | |
  0 1 1 1 0 | | | | |
    1 0 0 1 | | | | |
    ------- | | | | |
    0 1 1 1 1 | | | |
      1 0 0 1 | | | |
      ------- | | | |
      0 1 1 0 0 | | |
        1 0 0 1 | | |
        ------- | | |
        0 1 0 1 0 | |
          1 0 0 1 | |
          ------- | |
          0 0 1 1 0 |
            0 0 0 0 |
            ------- |
            0 1 1 0 0
              1 0 0 1
              -------
              0 1 0 1

The rest "0 1 0 1" is the checksum and is attached to the data for transmission. The recipient receives the following data package:

1 1 1 0 0 0 | 0 1 0 1

The recipient now checks for errors in the same way using the generator:

bit sequence:  1 1 1 0 0 1 0 1 0 1
generator: 1 0 0 1

1 1 1 0 0 0 1 0 1 0 1 % 1 0 0 1
1 0 0 1 | | | | | | |
------- | | | | | | |
0 1 1 1 0 | | | | | |
  1 0 0 1 | | | | | |
  ------- | | | | | |
  0 1 1 1 0 | | | | |
    1 0 0 1 | | | | |
    ------- | | | | |
    0 1 1 1 1 | | | |
      1 0 0 1 | | | |
      ------- | | | |
      0 1 1 0 0 | | |
        1 0 0 1 | | |
        ------- | | |
        0 1 0 1 1 | |
          1 0 0 1 | |
          ------- | |
          0 0 1 0 0 |
            0 0 0 0 |
            ------- |
            0 1 0 0 1
              1 0 0 1
              -------
              0 0 0 0

When the transmission was correct, the rest of the division is a sequence of zeros.

References

Author: Stefan Bohn Stefan Bohn has been employed at Thomas-Krenn.AG since 2020. Originally based in PreSales as a consultant for IT solutions, he moved to Product Management in 2022. There he dedicates himself to knowledge transfer and also drives the Thomas-Krenn Wiki.

Translator: Alina Ranzinger Alina has been working at Thomas-Krenn.AG since 2024. After her training as multilingual business assistant, she got her job as assistant of the Product Management and is responsible for the translation of texts and for the organisation of the department.