# Cyclic Redundancy Checks (CRC)

Updated on November 29, 2012

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

1

5

7

working