Cyclic Redundancy Checks (CRC)

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:

  1. This operation means that T is a multiple of G.
  2. As we are using modulo 2 arithmetic, we can replace the minus sign with a plus sign.
  3. Modulo 2 addition is the xor operation.
  4. 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.

More by this Author


Comments 4 comments

John Smith 4 years ago

What meaning: -

Highest order bit is set to 1


Booster911 profile image

Booster911 4 years ago from UK Author

The "highest order bit" is the binary digit with the highest numerical value. That is the one on the left when it is written down.


John Smith 4 years ago

M shift left by r = Q + R

------------------- ---

G G

Why R divide G on right side ?


Booster911 profile image

Booster911 4 years ago from UK Author

I'm afraid that two equations had lost their minus sign. I've fixed that now so I hope that makes more sense.

    Sign in or sign up and post using a HubPages Network account.

    0 of 8192 characters used
    Post Comment

    No HTML is allowed in comments, but URLs will be hyperlinked. Comments are not for promoting your articles or other sites.


    Click to Rate This Article
    working