Error Correction Techniques ~ technical guptaji

Error detection techniques is used to find out the exact number of bits that have been corrupted and as well as their locations.

Error correction can be handled in two ways :

1. Backward Error Correction (Retransmission) : If the receiver detects an error in the incoming data unit, it requests the sender to re-transmit the data frame. It is a relatively simple technique. But it can be efficiently used only where retransmitting is not expensive as in fibre optics.

2. Forward Error Correction : If the receiver detects some error in the incoming frame, it executes error correcting code that generates the actual frame. This saves bandwidth required for retransmission.

If there are two many errors, the frames need to be retransmitted.

A single additional bit can detect the error, but cannot correct it.

For correcting the errors, one has to know the exact position of the error. For example, if we want to calculate a single bit error, the error correction code will determine which one of seven bits is in error. To achieve this, we have to add some additional redundant bits.

Redundant bits : Redundant bits are extra binary bits that are generated and added to the information carrying bits of data transfer to ensure that number of bits were lost during the data transfer.

Suppose r is the number of redundant bits and d is the total number of data bits. The number of redundant bits r can be calculated by using the formula:

Number of redundant bits 2^r>=d+r+1

The value of r is calculated by using the above formula. For example, if the value of d is 4, then the possible smallest value that satisfies the above relation would be 3.

To determine the position of the bit which is in error, a technique developed by R.W Hamming is Hamming code which can be applied to any length of the data unit and uses the relationship between data units and redundant units.

Hamming Code

Hamming Code is a set of error correction code that can be used to detect and correct the errors that can occur when the data is moved from sender to the receiver.

Parity Bits : A parity bit is a bit appended to the data of binary bits to ensure that the total number of 1's in the data is even or odd. Parity bits are used for error detection.

There are two types of parity bits :

Even parity: To check for even parity, if the total number of 1's is even, then the value of the parity bit is 0. If the total number of 1's is odd, then the value of the parity bit is 1.

Odd Parity: To check for odd parity, if the total number of 1's is even, then the value of parity bit is 1. If the total number of 1's is odd, then the value of parity bit is 0.

Algorithm of Hamming Code

Step 1 : Calculate the number of redundant bits by using this formula 2^r>=d+r+1.

Step 2 : Find out the positions of redundant bits.

The redundant bits placed at bit positions of powers of 2 like 1,2,4,8,16,32.... and so on.

Step 3 : calculate the values of each redundant bits.

Each redundant bit, r is calculated as the parity, generally even parity, based upon it's bit position.

Step 4 : Placed the redundant bits into the positions of actual data and sent to the receiver.

Step 5 : At the receiver's end the parity bits are also calculated and if the parity bits having non-zero values then the data is said to be corrupted.

Step 6 : Find out the position of the data which is corrupted and correct them by changing the bit to 0 or 1.

Example : Suppose the original data is 1010 which is to be sent.

At the first step we calculate the number of redundant bits

Total number of data bits 'd' = 4

Number of redundant bits r 2^r >= d+r+1

2^r>= 4+r+1

Therefore, the value of r is 3 that satisfies the above relation. So there we will use 3 redundant bits.

At the second step determine the positions of redundant bits.

The three bits are represented by r1, r2, r4. The position of the redundant bits is calculated with corresponds to the raised power of 2. Therefore, their corresponding positions are 1, 2¹, 2².

The position of r1 = 1

The position of r2 = 2

The position of r4 = 4

Representation of Data on the addition of parity bits:

At the third step determine the values of each redundant(parity) bits so now we find the values of r1, r2 and r4 by the help of this binary representation of every position number.

Determining the r1 bit

The r1 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the first position.

We observe from the above figure that the bit positions that includes 1 in the first position are 1, 3, 5, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r1 is even, therefore, the value of the r1 bit is 0.

Determining r2 bit

The r2 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the second position.

We observe from the above figure that the bit positions that includes 1 in the second position are 2, 3, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r2 is odd, therefore, the value of the r2 bit is 1.

Determining r4 bit

The r4 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the third position.

We observe from the above figure that the bit positions that includes 1 in the third position are 4, 5, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r4 is even, therefore, the value of the r4 bit is 0.

At the step 4 placed the redundant bits into the positions of actual data and sent to the receiver.now the the transferred data is :

Suppose the 4^th bit is changed from 0 to 1 at the receiving end, then parity bits are recalculated at the receiver site in the step 5.

R1 bit

The bit positions of the r1 bit are 1,3,5,7.

We observe from the above figure that the binary representation of r1 is 1100. Now, we perform the even-parity check, the total number of 1's appearing in the r1 bit is an even number. Therefore, the value of r1 is 0.

R2 bit

The bit positions of r2 bit are 2,3,6,7.

We observe from the above figure that the binary representation of r2 is 1001. Now, we perform the even-parity check, the total number of 1's appearing in the r2 bit is an even number. Therefore, the value of r2 is 0.

R4 bit

The bit positions of r4 bit are 4,5,6,7.

We observe from the above figure that the binary representation of r4 is 1011. Now, we perform the even-parity check, the total number of 1's appearing in the r4 bit is an odd number. Therefore, the value of r4 is 1.

Note : If we get all the parity bits are 0 at the receiver end then the data is not corrupted.

But here we get the non-zero parity bits so here is an error or the data is said to be corrupted.

The binary representation of redundant bits, i.e., r4 r2 r1 is 100, and its corresponding decimal value is 4. Therefore, the error occurs in a 4^th bit position. The bit value must be changed from 1 to 0 to correct the error.