Error Correction in Computer Networks
In this tutorial, we will be covering the Error Correction by Data link layer in Computer Networks.
In Error Detection, the receiver only needs to know that the received codeword is invalid; But in Error Correction the receiver needs to guess the Original codeword that is sent. In this way, error Correction is much more difficult than Error Detection.
The need for redundant bits is more during error correction rather than for error detection.
Let us take a look at the Structure of the encoder and decoder in the Error Correction:
Figure: Structure of the Encoder and Decoder in the Error Correction
In order to detect or correct the errors, there is a need to send some extra bits along with the data. These extra bits are commonly known as Redundant bits.
As we had learned in the previous tutorial that original data is divided into segments of k bits; it is referred to as dataword. When we add r redundant bits to each block in order to make the length;n=k+r then it is referred to as Codeword.
There are two ways to handle the error correction:
-
Whenever an error discovered, the receiver can have the sender in order to retransmit the entire data unit. This technique is known as the Backward Error correction technique. This technique is simple and inexpensive in the case of wired transmission like fiber optics; there is no expense in retransmitting the data. In the case of wireless transmission, retransmission costs too much thus forward error correction technique is used then.
-
The receiver can use an error-correcting code that automatically contains certain errors. This technique is known as the Forward Error Correction technique.
In order to correct the errors, one has to know the exact position of the error. For example, In case if we want to calculate a single-bit error, the error correction code then mainly determines which one of seven bits is in the error.
In order to achieve this, we have to add some additional redundant bits.
Suppose r (as the redundant bits) and d indicates the total number of data bits. In order to calculate the redundant bits(r), the given formula is used;
2r= d+r+1
Error correction is mainly done with the help of the Hamming code.
Hamming Code
It is a technique developed by R.W. hamming. This can be applied to data units of any length. This code mainly uses the relationship between data and redundancy bits.
The hamming code technique, which is an error-detection and error-correction technique, was proposed by R.W. Hamming. Whenever a data packet is transmitted over a network, there are possibilities that the data bits may get lost or damaged during transmission.
Let's understand the Hamming code concept with an example:
Let's say you have received a 7-bit Hamming code which is 1011011.
First, let us talk about the redundant bits.
The redundant bits are some extra binary bits that are not part of the original data, but they are generated & added to the original data bit. All this is done to ensure that the data bits don't get damaged and if they do, we can recover them.
Now the question arises, how do we determine the number of redundant bits to be added?
We use the formula, 2r >= m+r+1; where r = redundant bit & m = data bit.
From the formula we can make out that there are 4 data bits and 3 redundancy bits, referring to the received 7-bit hamming code.
What is Parity Bit?
To proceed further we need to know about parity bit, which is a bit appended to the data bits which ensures that the total number of 1's are even (even parity) or odd (odd parity).
While checking the parity, if the total number of 1's are odd then write the value of parity bit P1(or P2 etc.) as 1 (which means the error is there ) and if it is even then the value of parity bit is 0 (which means no error).
Hamming Code in Error Detection
As we go through the example, the first step is to identify the bit position of the data & all the bit positions which are powers of 2 are marked as parity bits (e.g. 1, 2, 4, 8, etc.). The following image will help in visualizing the received hamming code of 7 bits.
First, we need to detect whether there are any errors in this received hamming code.
Step 1: For checking parity bit P1, use check one and skip one method, which means, starting from P1 and then skip P2, take D3 then skip P4 then take D5, and then skip D6 and take D7, this way we will have the following bits,
As we can observe the total number of bits is odd so we will write the value of parity bit as P1 = 1. This means the error is there.
Step 2: Check for P2 but while checking for P2, we will use the check two and skip two methods, which will give us the following data bits. But remember since we are checking for P2, so we have to start our count from P2 (P1 should not be considered).
As we can observe that the number of 1's are even, then we will write the value of P2 = 0. This means there is no error.
Step 3: Check for P4 but while checking for P4, we will use the check four and skip four methods, which will give us the following data bits. But remember since we are checking for P4, so we have started our count from P4(P1 & P2 should not be considered).
As we can observe that the number of 1's is odd, then we will write the value of P4 = 1. This means the error is there.
So, from the above parity analysis, P1 & P4 are not equal to 0, so we can clearly say that the received hamming code has errors.
Hamming Code: Error Correction
Since we found that the received code has an error, so now we must correct them. To correct the errors, use the following steps:
Now the error word E will be:
Now we have to determine the decimal value of this error word 101 which is 5 (22 *1 + 21 * 0 + 20 *1 = 5).
We get E = 5, which states that the error is in the fifth data bit. To correct it, just invert the fifth data bit.
So the correct data will be:
