# 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

John Smith 4 years ago

What meaning: -

Highest order bit is set to 1

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