- HubPages»
- Technology»
- Computers & Software»
- Computer How-Tos & Tutorials
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:
- 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 - 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.