Error Detection and Correction Code: Part 2

Hamming Code

Hamming code is an error-correction code used to detect and correct errors that occur when the data is transmitted from the sender end to the receiver end.

In this method, the sender encodes the message by adding redundant bits within the message. These redundant bits are the extra bits that are generated and inserted at specific positions in the message itself. When the receiver receives this message, it performs recalculations to detect errors and find the bit position that has an error.

Procedure

• A data block of 'd' bits is added to the redundant bits 'r'. Here r should follow the following equation: 

2^r >= d+r+1

• The location of each of the (d+r) digits is assigned with a decimal value.
• The 'r' bits are placed at bit positions of powers of 2 like 1,2,.....2^k-1.
• At the receiver's end, the parity bits are recalculated. The decimal value of the parity bits gives the position of an error.

Example

Let's understand Hamming code through an example.

Suppose the original message to be transmitted is 1010.

d = 4

2r >= d+r+1

2r >= 4+r+1

Therefore, r should be 3 to satisfy the above relation.

Total number of bits = d+r = 4+3 = 7
 

Position of redundant bits

Let's represent the three bits by r1, r2, r4. The position of the redundant bits is calculated corresponding to the raised power of 2. Therefore, their corresponding positions of the redundant bits are 2⁰, 2¹, 2².

r1 = 1^st position

r2 = 2^nd position

r4 = 4^th position

 

Determining R1 bit

To find the r1 bit, we perform a parity check on the bit positions whose binary representation includes 1 in the first position. The bit positions that include 1 in the first position are 1, 3, 5, 7. 

Now, an even-parity check is performed at these bit positions. The total number of 1’s at these bit positions corresponding to r1 is even. Hence, the value of the r1 bit is 0.

 

Determining R2 bit

To find the r2 bit, we perform a parity check on the bit positions whose binary representation includes 1 in the second position. The bit positions that include 1 in the first position are 2, 3, 6, 7. 

Now, an even-parity check is performed at these bit positions. The total number of 1's at these bit positions corresponding to r1 is odd. Hence, the value of the r2 bit is 1.

 

Determining R4 bit

To find the r4 bit, we perform a parity check on the bit positions whose binary representation includes 1 in the third position. The bit positions that include 1 in the first position are 4, 5, 6, 7. 

Now, an even-parity check is performed at these bit positions. The total number of 1's at these bit positions corresponding to r1 is even. Hence, the value of the r4 bit is 0.

 

Data Transferred

Suppose the 4^th bit changes from 0 to 1 at the receiver's end; then parity bits are recalculated.

 

Data Received

 

Error Correction

Let’s see how to correct the error when the above data bit is received at the receiver’s end.

 

Binary Representation of r1

The bit positions of the r1 bit are 1,3,5,7. The binary representation of r1 is 1100. On performing an even-parity check, the total number of 1s appearing in the r1 bit is even. Therefore, the value of r1 is 0.

Binary Representation of r2

The bit positions of the r2 bit are 2,3,6,7. The binary representation of r2 is 1001. On performing an even-parity check, the total number of 1s appearing in the r2 bit is even. Therefore, the value of r2 is 0.

Binary Representation of r4

The bit positions of the r4 bit are 4,5,6,7. The binary representation of r4 is 1011. On performing an even-parity check, the total number of 1s appearing in the r4 bit is odd. Therefore, the value of r4 is 1.

 

Binary Representation of the Redundant Bits 

The binary representation of the redundant bits (r4r2r1) is 100 which corresponds to decimal value 4. Therefore, the error occurs in at the 4^th bit position. To correct the error, the bit value must be changed from 1 to 0.

Check out this problem - Two Sum Problem

FAQs

1. Is hamming code an example of block codes or convolutional codes?
   Hamming code comes under the category of block code. Here, the two simultaneous bit errors are detected, and this code corrects single-bit errors. In this mechanism, the sender encodes the message by appending the unessential bits in the data. The bits are added to the specific position in the message because they are the extra bits for correction.
    
2. What is the difference between single-bit error and burst error?
   In a single-bit error, only one bit of a data block is changed from 1 to 0 or 0 to 1.
   In burst error, two or more bits of a data block are changed from 0 to 1 or 1 to 0.
    
3. What are the two ways of handling error correction?
   Error correction is handled in two ways:
   Forward error correction: The receiver uses the error-correcting code, automatically correcting the errors.
   Backward error correction: Once the error is detected, the receiver requests the sender to retransmit the entire data unit.
    
4. Mention differences between the checksum and Cyclic Redundancy Check (CRC) techniques.
   Some differences between the checksum and Cyclic Redundancy Check (CRC) techniques are as follows:-

• The checksum can detect a single-bit change in the data, while the CRC can detect double digits errors.
• The checksum method quickly computes the error, while the CRC follows a complex computation method.
• The CRC is based on the hash approach, while checksum is based on the addition approach.
• The checksum method is widely used in data validation during software implementation, while the CRC is commonly used in analog transmission for data validation.
• The checksum can compute fewer number errors than CRC. While the CRC is too complex to compute, it can detect more errors.

Key Takeaways

In this article, we have extensively discussed the need for error detection and correction code techniques and the various techniques like checksum and hamming code. Error detection and correction code play an essential role in transmitting data from one source to another. And it is vital to have proper knowledge of this to avoid receiving erroneous data.

We hope that this blog has helped you enhance your knowledge regarding error detection and correction code techniques and if you would like to learn more, check out our articles on Error Detection and Correction Code: Part 1. Do upvote our blog to help other ninjas grow. Happy Coding!