Error detection and error correction

Data-link layer uses some error control mechanism to ensure that frames (data bit streams) are transmitted with certain level of accuracy.

Types of Errors

• There are three types of errors:

1. Single bit error : Only one bit is corrupt anywhere in a frame,
2. Multiple bits error : More than one bits in corrupted  in a frame.
3. Burst error : Frame contains more than1 consecutive bits corrupted.

• 
  

• Error control mechanism involve two possible ways:

1. Error detection
2. Error correction

Error Detection

Error detection is the process of detecting the errors in the data transmitted from transmitter to receiver, in a communication system.

Errors in the received frames are detected by means of Parity Check and Cyclic Redundancy Check (CRC). In both cases, few extra bits are sent along with actual data to confirm that bits received at other end are same as they were sent. If the counter-check at receiver’ end fails, the bits are considered corrupted.

Parity Check

A parity check is the process that ensures accurate data transmission between nodes during  communication. 

Process:

• One extra bit is sent along with the original bits to make number of 1s either even in case of even parity, or odd in case of odd parity.
• The sender while creating a frame counts the number of 1s in it.
• The receiver simply counts the number of 1s in a frame. If the count of 1s is even and even parity is used, the frame is considered to be not-corrupted and is accepted. If the count of 1s is odd and odd parity is used, the frame is still not corrupted.
• If a single bit flips in transit, the receiver can detect it by counting the number of 1s. But when more than one bits are erro neous, then it is very hard for the receiver to detect the error.

Cyclic Redundancy Check (CRC)

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. This technique involves binary division of the data bits being sent. The divisor is generated using polynomials. 

Process:

• The sender performs a division operation on the bits being sent and calculates the remainder. 
• Before sending the actual bits, the sender adds the remainder at the end of the actual bits. 
• Actual data bits plus the remainder is called a codeword. 
• The sender transmits data bits as codewords.
• At the other end, the receiver performs division operation on codewords using the same CRC divisor. 
• If the remainder contains all zeros the data bits are accepted, otherwise it is considered as there some data corruption occurred in transit.

Block Coding 

• We need redundancy to ensure synchronization and to provide some kind of inherent error detecting. Block coding can give us this redundancy and improve the performance of line coding. In general, block coding changes a block of m bits into a block of n bits, where n is larger than m. Block coding is referred to as an mB/nB encoding technique. Block coding is normally referred to as mBlnB coding; it replaces each m-bit group with an n-bit group. 

• The slash in block encoding for example, 4B/5B, distinguishes block encoding from multilevel encoding for example, 8B6T, which is written without a slash. 

• Block coding normally involves three steps: division, substitution, and combination. In the division step, a sequence of bits is divided into groups of m bits. 

• For example, in 4B/5B encoding, the original bit sequence is divided into 4- bit groups. 

• The heart of block coding is the substitution step. In this step, we substitute an m-bit group for an n-bit group.

• For example, in 4B/5B encoding we substitute a 4-bit code for 127 a 5-bit group. 

• Finally, the n-bit groups are combined together to form a stream. The new stream has more bits than the original bits. 

Error Correction

Error Correction codes are used to correct the errors when data is transmitted from the sender to the receiver.

Error correction can be done in two ways:

• Backward Error Correction: When the receiver detects an error in the data received, it requests back the sender to retransmit the data unit.

• Forward Error Correction: When the receiver detects some error in the data received, it executes error-correcting code, which helps it to auto-recover and to correct some kinds of errors.

Backward Error Correction: It is simple and can only be efficiently used where retransmitting is not expensive. 

For example: fiber optics. 

But in case of wireless transmission retransmitting may cost too much. In the latter case, Forward Error Correction is used.

Process:

• To correct the error in data frame, the receiver must know exactly which bit in the frame is corrupted. To locate the bit in error, redundant bits are used as parity bits for error detection.

• For example, we take ASCII words (7 bits data), then there could be 8 kind of information we need: first seven bits to tell us which bit is error and one more bit to tell that there is no error.

• For m data bits, r redundant bits are used. r bits can provide 2r combinations of information. 

• In m+r bit codeword, there is possibility that the r bits themselves may get corrupted. 

• So the number of r bits used must inform about m+r bit locations plus no-error information, i.e. m+r+1.

Hamming Distance

Hamming distance is a metric for comparing two binary data strings. 

While comparing two binary strings of equal length, Hamming distance is the number of bit positions in which the two bits are different.

The Hamming distance between two strings, a and b is denoted as d(a,b).

It is used for error detection or error correction when data is transmitted over computer networks. It is also using in coding theory for comparing equal length data words

Next page