Error Detection and Correction

Data can be corrupted during transmission. For reliable communication, errors must be detected and corrected.

Types of Errors

Single-bit error

The term Single-bit error means that only one bit of a given data unit (such as byte, character, data unit or packet) is changed from 1 to 0 or from 0 to 1.

Burst Error

The term Burst Error means that two or more bits in the data unit have changed from 1 to 0 or from 0 to 1.

Redundancy

             One method is to send every data twice, so that receiver checks every bit of two copies and detect error.

Drawbacks

Ø  Sends n-redundant bits for n-bit message.

Ø  Many errors are undetected if both the copies are corrupted.

Instead of adding entire data, some bits are appended to each unit.

             This is called redundant bit because the bits added will not give any new information. These bits are called error detecting codes.

The three error detecting techniques are:

Ø  Parity check

Ø  Check sum algorithm

Ø  Cyclic Redundancy Check

Parity Check

Simple parity check

             Only one redundant bit, called parity bit is added to every data unit so that the total number of 1’s in unit become even (or odd)

Two Dimensional Parity

Ø  It is based on simple parity.

Ø  It performs calculation for each bit position across each byte in the frame.

Ø 

This adds extra parity byte for entire frame, in addition to a parity bit for each byte.

            For example frame containing 6 bytes of data. In this third bit of the parity byte is 1 since there are an odd number of 1’s is in the third bit across the 6 bytes in the frame.

            In this case, 14 bits of redundant information are added with original information.

Check sum algorithm

Ø  In the sender side all the words are added and then transmit the result of sum called checksum with the data.

Ø  The receiver performs the same calculation on the received data and compares the result with the received checksum.

Ø  If any transmitted data, including the checksum itself, is corrupted, then the results will not match, so the receiver knows that an error occurred.

 Ø  Instead of sending the checksum as such, one’s complement of that sum will be send to the receiver. If the receiver gets the result as zero then it will be the correct one.

Ø  In this, we can represent unsigned number from 0 to 2ⁿ using n bits.

Ø  If the number has more than n bits, the extra leftmost bits need to be added to the n rightmost bits.

Ø  Data can be divided in to 16 bit word and the Checksum is initialized to zero.