Error Detection

Error detection techniques are responsible for checking whether any error has occurred or not in the frame that has been transmitted via network. It does not take into account the number of error bits and the type of error.

For error detection, the sender needs to send some additional bits along with the data bits. The receiver performs necessary checks based upon the additional redundant bits. If it finds that the data is free from errors, it removes the redundant bits before passing the message to the upper layers.

The most popular Error Detecting Techniques are:

• Single parity check (Vertical Redundancy Check)
• Two-dimensional parity check (Longitudinal Redundancy Check)
• Checksum
• Cyclic redundancy check

 Single Parity Check

 Single Parity checking is the simple mechanism and inexpensive to detect the errors. In this technique, a redundant bit is also known as a parity bit which is appended at the end of the data unit so that the number of 1s becomes even. Therefore, the total number of transmitted bits would be 9 bits.

 If the number of 1s bits is odd, then parity bit 1 is appended and if the number of 1s bits is even, then parity bit 0 is appended at the end of the data unit. At the receiving end, the parity bit is calculated from the received data bits and compared with the received parity bit. This technique generates the total number of 1s even, so it is known as even-parity checking.

Drawbacks of Single Parity Checking

• It can only detect single-bit errors which are very rare.
• If two bits are interchanged, then it cannot detect the errors.

Two-Dimensional Parity Check

Performance can be improved by using Two-Dimensional Parity Check which organizes the data in the form of a table.

Parity check bits are computed for each row, which is equivalent to the single-parity check.

In Two-Dimensional Parity check, a block of bits is divided into rows, and the redundant row of bits is added to the whole block.

At the receiving end, the parity bits are compared with the parity bits computed from the received data.

Drawbacks of 2D Parity Check

 If two bits in one data unit are corrupted and two bits exactly the same position in another data unit is also corrupted, then 2D Parity checker will not be able to detect the error.

Checksums

 This is a block code method where a checksum is created based on the data values in the data blocks to be transmitted using some algorithm and appended to the data. When the receiver gets this data, a new checksum is calculated and compared with the existing checksum. A non-match indicates an error.

 Error Detection by Checksums

For error detection by checksums, data is divided into fixed sized frames or segments.

 

• Sender’s End − The sender adds the segments using 1’s complement arithmetic to get the sum. It then complements the sum to get the checksum and sends it along with the data frames.
• Receiver’s End − The receiver adds the incoming segments along with the checksum using 1’s complement arithmetic to get the sum and then complements it.

If the result is zero, the received frames are accepted; otherwise they are discarded.

 Suppose that the sender wants to send 4 frames each of 8 bits, where the frames are 11001100, 10101010, 11110000 and 11000011.

 The sender adds the bits using 1s complement arithmetic. While adding two numbers using 1s complement arithmetic, if there is a carry over, it is added to the sum.

After adding all the 4 frames, the sender complements the sum to get the checksum, 11010011, and sends it along with the data frames.

The receiver performs 1s complement arithmetic sum of all the frames including the checksum. 

The result is complemented and found to be 0. Hence, the receiver assumes that no error has occurred.

Cyclic Redundancy Check (CRC)

Cyclic Redundancy Check (CRC) is a block code invented by W. Wesley Peterson in 1961.

CRC involves binary division of the data bits being sent by a predetermined divisor agreed upon by the communicating system. The divisor is generated using polynomials. So, CRC is also called polynomial code checksum.

Given a k-bit frame or message, the transmitter generates an n-bit sequence, known as a frame check sequence (FCS), so that the resulting frame, consisting of (k+n) bits, is exactly divisible by some predetermined number.

Encoding using CRC

The communicating parties agree upon the size of message block and the CRC divisor. The sender performs binary division of the data segment by the divisor.

Sender then appends the remainder called CRC bits to the end of data segment. This makes the resulting data unit exactly divisible by the divisor.

Decoding

The receiver divides the incoming data unit by the divisor. If there is no remainder, the data unit is assumed to be correct and is accepted.

Otherwise, it is understood that the data is corrupted and is therefore rejected. The receiver may then send an erroneous acknowledgement back to the sender for retransmission.

Suppose the original data is 11100 and divisor is 1001.

CRC Generator

A CRC generator uses a modulo-2 division. Firstly, three zeroes are appended at the end of the data as the length of the divisor is 4 and we know that the length of the string 0s to be appended is always one less than the length of the divisor.

Now, the string becomes 11100000, and the resultant string is divided by the divisor 1001.

The remainder generated from the binary division is known as CRC remainder. The generated value of the CRC remainder is 111. CRC remainder replaces the appended string of 0s at the end of the data unit, and the final string would be 11100111 which is sent across the network.

CRC Checker

The functionality of the CRC checker is similar to the CRC generator.

When the string 11100111 is received at the receiving end, then CRC checker performs the modulo-2 division. A string is divided by the same divisor, i.e., 1001.

In this case, CRC checker generates the remainder of zero. Therefore, the data is accepted.