Cyclic Redundancy Checks (CRC)
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.
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.
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
T = M << r - R G G G
But we know that:
M << r = Q + R G G
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.
Suppose we have:
M = 10010011 G = 10011 r = 4
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
- 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
Branch testing and decision testing are closely related. We will treat them same. When 100% coverage is concerned, the two techniques are the same. Branch and decision testing require examination of the source code...
Statement testing is a whitebox, dynamic testing technique. It requires examination of the source code and the creation of tests that will exercise individual statements. The project plan should indicate the proportion...
Introduction These notes describe how to go about modulo 2 addition, subtraction and division. Modulo 2 Arithmetic Modulo 2 arithmetic is performed digit by digit on binary numbers. Each digit is considered...