Description
Objective
Write a program for error detection using Cyclic redundancy check(CRC). Demonstrate
the packets captured traces using Wireshark Packet Analyzer Tool for peer to peer
mode.
Cyclic redundancy check(CRC)
An error detection mechanism in which a special number is appended to a block of data
in order to detect any changes introduced during storage (or transmission). The CRC is
recalculated on retrieval (or reception) and compared to the value originally transmitted,
which can reveal certain types of error. For example, a single corrupted bit in the data
results in a one-bit change in the calculated CRC, but multiple corrupt bits may cancel
each other out.
A CRC is derived using a more complex algorithm than the simple CHECKSUM,
involving MODULO ARITHMETIC (hence the ‘cyclic’ name) and treating each input
word as a set of coefficients for a polynomial.
● CRC is more powerful than Vertical redundancy check(VRC) and Longitudinal
redundancy check(LRC) in detecting errors.
● It is not based on binary addition like VRC and LRC. Rather it is based on binary
division.
● At the sender side, the data unit to be transmitted IS divided by a predetermined
divisor (binary number) in order to obtain the remainder. This remainder is called CRC.
● The CRC has one bit less than the divisor. It means that if CRC is of n bits, divisor is
of n+ 1 bit.
●The sender appends this CRC to the end of data unit such that the resulting data unit
becomes exactly divisible by predetermined divisor i.e. remainder becomes zero.
● At the destination, the incoming data unit i.e. data + CRC is divided by the same
number (predetermined binary divisor).
● If the remainder after division is zero then there is no error in the data unit & receiver
accepts it.
● If remainder after division is not zero, it indicates that the data unit has been damaged
in transit and therefore it is rejected.
● This technique is more powerful than the parity check and checksum error detection.
● CRC is based on binary division. A sequence of redundant bits called CRC or CRC
remainder is appended at the end of a data unit such as byte.
Requirements of CRC :
A CRC will be valid if and only if it satisfies the following requirements:
1. It should have exactly one less bit than the divisor.
2. Appending the CRC to the end of the data unit should result in the bit sequence
which is exactly divisible by the divisor.
CRC Generator
The various steps followed in the CRC method are
1. A string of n as is appended to the data unit. The length of the predetermined divisor
is n+ 1.
2. The newly formed data unit i.e. original data + string of n as are divided by the divisor
using binary division and remainder is obtained. This remainder is called CRC.
3. Now, the string of n Os appended to the data unit is replaced by the CRC remainder
(which is also of n bit).
4. The data unit + CRC is then transmitted to the receiver.
5. The receiver on receiving it divides data unit + CRC by the same divisor & checks the
remainder.
6. If the remainder of division is zero, receiver assumes that there is no error in data
and
it accepts it.
7. If the remainder is non-zero then there is an error in data and receiver rejects it.
• For example, if data to be transmitted is 1001 and the predetermined divisor is 1011.
The procedure given below is used:
String of 3 zeroes is appended to 1011 as a divisor is of 4 bits. Now newly formed data
is 1011000
CRC Checker
1. Data unit 1011000 is divided by 1011.
2. During this process of division, whenever the leftmost bit of dividend or remainder
is 0, we use a string of Os of same length as divisor. Thus in this case divisor
1011 is replaced
by 0000.
3. At the receiver side, data received is 1001110.
4. This data is again divided by a divisor 1011.
5. The remainder obtained is 000; it means there is no error.
Performance
CRC is a very effective error detection technique. If the divisor is chosen
according to the previously mentioned rules, its performance can be summarized
as follows:
● CRC can detect all single-bit errors
● CRC can detect all double-bit errors (three 1’s)
● CRC can detect any odd number of errors.
● CRC can detect all burst errors of less than the degree of the polynomial.
● CRC detects most of the larger burst errors with a high probability.
