Hamming Code For Error Correction

When a sender sends data to the receiver, then errors may occur. Error correction codes are used to detect and correct these errors.

There are two methods to handle the error Correction.

1. Backward error correction: After error detection, retransmission of the entire data unit is called backward error correction.

2. Forward error correction: In forward correction, after error detection, the receiver uses the error-correcting code, which corrects the errors automatically.

Hamming Code is the best method, which uses the forward error correction technique to correct the data. It was developed by R.W. Hamming.

Hamming code

According to the hamming code, some redundant bits are added with actual data bits and transmitted. At receiver side these bits are checked, if any there exist any bit error then it is also corrected.

In the Hamming code, Redundant bits are not fixed. If data bits are increased, then redundancy bits are also increased. At the time of sending data, we don’t know the number of redundancy bits.

There are various steps to understand hamming code.

Step 1: No. of Redundancy Bits “r”

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

2^r>=d+r+1

Keep in Mind: consider the smallest value of “r,” which satisfies the above formula.

Understand With Example

Consider the data (1010) which needs to be sent.

• Total number of data bits “d” = 4
• The number of redundant bits “r” will be 2^r >= 4+r+1  

Hence, the value of “r” is 3 because 3 is the smallest value of “r” that satisfies the above equation.

• Total number of bits (data + redundancy) = d+r = 4+3 = 7;

Step 2: Position for each Redundancy bit “r”

The position of the redundancy bit will be calculated through the formula of 2n. If there are three redundancy bits, r1, r2, and r3, then their corresponding positions are 1, 21, and 22.

• The first position of redundancy bit (r1) = 2⁰= 1
• The second position of  redundancy bit (r2) = 2¹= 2  
• Third position of redundancy bit (r3)  = 2²= 4   and so on

As we have 4 data bits (1010), put them in their positions below

Step 3: Determining The Value Of Each Redundancy bit “r”

Each redundancy bit holds its fixed position data bits. As given below

• , r1 fixed positions of data bits are all odd positions, such as 1, 3, 5, 7, and so on.
• r2 fix positions of data bits are 2,3 and then skip 4,5 and then consider 6,7.
• r3 fix positions of data bits are 4,5,6,7 and then 4-skip (8,9,10,11) and then 4 consider and so on.

For the purpose of even parity, count the number of 1s for each r1,r2, and r3 through its fixed positions. If the number of 1s is even, then that redundancy bit (r) will be 0; otherwise, it is 1.

So value of r1,r2 and r3 is given below

• r1 Value = all odd positions as 1,3,5,7 = 011 = 0
• r2 Value = positions of 2,3,6,7 = 011 = 1
• r3 Value = position of 4,5,6,7 =  101 = 0

Step 4: Put The Values Of Redundancy Bits To Their Positions

There are 4 data bits (1010) and 3 redundancy bits (010) as given under

Suppose the 6^th bit is changed from 0 to 1 at the receiving end as given below

Now again, calculate the redundancy value for r1,r2,3  to correct the error.

• r1 Value = all odd positions as 1,3,5,7 = 1100 = 0
• r2 Value = positions of 2,3,6,7 = 1101 = 1
• r3 Value = position of 4,5,6,7 =  1110 = 1

The binary representation of redundant bits, i.e., r3r2r1, is 110, and its corresponding decimal value is 6. Therefore, the error occurs in a 6th-bit position. The data-bit value must be changed from 1 to 0 to correct the error.