Cyclic Redundancy Checks

Introduction

Cyclic Redundancy Checks (CRCs) are used to detect errors in transmitted data. A CRC is calculated from the message contents and transmitted with the message. On receipt, a further calculation is performed on the message and CRC to determine whether either has been corrupted.

Here we show the basic method without going into a lot of detail. CRC calculations are performed using modulo 2 arithmetic.

CRC Calculation

Consider the message as a binary number, M. The CRC is also a binary number, R. Typically, CRCs are 16 or 32 bits wide. Here, we will say that they are r bits wide. M and R are combined to form the transmitted message, T.

The number G is known to both the transmitter and receiver. G is (r + 1) bits wide and the highest order bit is set to 1. This means that dividing a binary number by G will give a remainder between 0 and (G - 1), that is it will be between 1 and r bits wide.

The CRC is calculated as the remainder when M is shifted left by r bits and then divided by G. That is:

    M << r = Q + R
      G          G

where Q is the quotient and R is the remainder.

As G is (r + 1) bits wide, R is no more than r bits wide.

The Transmitted Message

The transmitted message, T, is formed by shifting M left by r bits and then subtracting the CRC as follows:

    T = (M << r) – R

There are a few points to note here:

This operation means that T is a multiple of G.
As we are using modulo 2 arithmetic, we can replace the minus sign with a plus sign.
Modulo 2 addition is the xor operation.
R is no more than r bits wide and the shifting process leaves r zeros at the insignificant end of M.

CRC Checking

Given that T is a multiple of G, checking the CRC is a simple process. Divide T by G. If there is no remainder then the message has not been modified. This is proved below:

    T = (M << r) – R

so:

    T = M << r   R
    G     G      G

But we know that:

    M << r = Q + R
      G          G

so:

    T = Q + R   R = Q
    G       G   G

i.e. there is no remainder.

If we find that T divided by Q does give a remainder then the received message is not as transmitted.

Example

Suppose we have:

    M = 10010011
    G = 10011
    r = 4

Then:

    M << r = 100100110000
      G          10011

Now for the division:

                 10001010 remainder 1110
       10011|100100110000 
             10011
                 10110 
                 10011
                   10100 
                   10011
                     1110

Subtracting the remainder from the shifted message we get the transmitted message:

    M << r  100100110000
      R             1110-
      T     100100111110

We can see that this divides exactly by G:

                 10001010 remainder 0
       10011|100100111110 
             10011
                 10111 
                 10011
                   10011 
                   10011
                       00

But if the message had been corrupted then it is unlikely to be exactly divisible by G. For example:

                 10111111 remainder 1111
       10011|101000111110
             10011 
               11101
               10011 
                11101
                10011 
                 11101
                 10011 
                  11101
                  10011 
                   11101
                   10011 
                    11100
                    10011 
                     1111

References

F Halsall (1992). Data Communications, Computer Networks and Open Systems. Addison-Wesley ISBN 0-201-56506-4. See section 3.5.3

Home