This post is to explain in common language what is CRC when it comes to data transfer across networks. This is a Networking related term but everyone can get a little understand about how error detection and correction occurs in data communication systems by reading what I’m about to say. We all know data has to move through different media or devices when it is transferred from one location to another. There are possibilities the data might get corrupted or lost all together when it moves from one hop to another. The lost or corruption of data can occur due to many causes such as noise or other waves radiated from other devices. With this in mind, Network engineers has come out with some smart ways to make sure that when a data is corrupted or lost, it can be detected and corrected. One technique is the CRC approach. In CRC, additional stuff is added to the data being sent, that’s why it’s Redundancy. The general idea behind this approach is that, when a data is to be sent to another device, the sending device will perform some mathematical calculations on the data and get an outcome called a CRC, then send the data together with the CRC to the receiver. When the receiver receives the data and CRC together, it will perform the same mathematical calculation and based on what the result is, the data will be accepted or discarded. This is a general view of the mathematics that is performed at the sender site. First, the data to be sent is converted into binary or hex, normally called a dataword. This dataword has length k, the sender and receiver in advance agrees on what is called a divisor to use in the calculation. At the sender site, the dataword is augmented with some number of zeroes which can be calculated from the length of the codeword minus the length of the dataword. A codeword is the outcome of a dataword concatenated with a CRC. That means, in the first place, the sender site will get the length of the codeword just be observing the divisor agreed upon. The length of the divisor is length of Codeword minus length of dataword plus 1. So if you know the length of dataword and the length of dataword, you can easily know the length of codeword.
Size of divisor = n – k + 1, where n = length of codeword, k = length of dataword.
length of codeword = size of divisor + K – 1.
Number of zeroes to augment the dataword before performing the division is at sender site = n – k.
So to make this more clearly, let’s assume we have converted our data into binary and is 1011110, and we agree to use the divisor 1011. Then we have,
dataword = 1011110
divisor = 1011
length of dataword = k = 7
size of divisor = 4
length of codeword = n=4+ 7 – 1 = 10.
number of zeros to augment the dataword = n-k = 10-7 = 3
so the augmented dataword = 1011110000 ( three zeroes added to the end of the original dataword)
Now, We divide the augmented dataword with the divisor and get a remainder which is the CRC.
Let’s do the binary division, its simple but tricky, I get it done with this technique. Write the augmented dataword on a line and write the divisor below it, with leftmost digits of the divisor and dataword aligned vertically. Then you are going to XOR the digits in the divisor and the dividend. The simplest way to remeber XORing is, if the two digits are the same, then it’s a 0, if they are different, then it’s a 1. After each step of Xoring, you shift the divisor to the right by one digit. You continue until you can’t divide no more. Remember, when there are bunch of zeroes on the left of the dividend before a 1, you can move straight and align your divisor with the first digit that is 1 and continue dividing if the value of the dividend from that point is still bigger than the divisor. It easy to see if you have a number smaller than the divisor by counting the length from the first significant 1 to the least significant digit in the dividend and compare this with the length of the divisor. if the divisor’s length is bigger, then you can no more divide. The remainder is what is left where there is no more divisions to be made.
1011110000 -> dividend(dataword augmented with 3 zeroes)
1011 -> divisor
____________
0000110000 -> dividend
1011 ->divisor (moved to align with the first digit that is 1 in dividend)
_____________________
011100 -> dividend
1011 ->divisor (moved to align with the first digit that is 1 in dividend)
______________________
01010 -> dividend
1011 -> divisor
————————————
0001
remainder = 001.
Therefore crc = 001.
The last thing we got is 0001 but we need only three digits in the remainder, remainder the codeword is of length 10 and the dataword is already of length 7. so we need only 3 digits and those zeroes before the one are all insignificant. who chose 001 as the remainder.
now, the codeword is dataword concatenate with remainder
codeword = 1011110111
This codeword will be sent to the receiver site and the crc will also be sent.
So the receive will receive the codeword and the crc and begin it’s mathematics to make sure the data is not corrupted.
At the receiver site, instead of augment with zeroes before the division, the codeword is augmented with the crc. but the divisor is the same, it’s agreed upon and can not be changed.
So let’s see how the binary division goes on at the receiver site,
Codeword received = 1011110111
crc received = 001
divisor = 1011
augmented codeword = 1011110111 001
here goes the division at the receiver site.
1011110111 001 -> dividend
1011 ->divisor
——————————-
0000110111001 -> dividend
1011 ->divisor
———————————
011011001
1011
———————————-
01101001
1011
———————————–
0110001
1011
———————————-
011101
1011
———————————-
01011
1011
———————————–
0000
Now the receiver can accept the codeword received, drop off the last 3 digits in the codeword received to get the dataword sent from the receiver. The receiver knows to drop off the 3 digits because it knows the codeword received was augmented with the crc before sent from the sender.
The last 0000 or the remainder at the receiver site is called a syndrome. If the syndrome is zero or zeroes, then there is no problem with the data, otherwise, the data is corrupted and everything will be discarded and the receiver has to resend it.
Another approach for solving this same problem is polynomial division. That’s more standard and l hope l’ll get some time to write on that also. Just to conclude, there are some standard CRC available which you can use in whatever you want to do but l think it’s a good idea to understand the general concept behind the working of a CRC. With this simple discussion above, you can write a program to implement error detection and correction using CRC.
