# 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 +RG 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-RG G G

But we know that:

M << r= Q +RG 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= 100100110000G 10011

Now for the division:

10001010remainder 1110 10011|10010011000010011101101001110100100111110

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

M << r 100100110000 R1110- T100100111110

We can see that this divides exactly by G:

10001010remainder 0 10011|100100111110100111011110011100111001100

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

10111111remainder 1111 10011|101000111110100111110110011111011001111101100111110110011111011001111100100111111

## References

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

## See Also:

## Comments

What meaning: -

Highest order bit is set to 1

M shift left by r = Q + R

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

G G

Why R divide G on right side ?