Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Checksum
2.1.
Operation at senders’ side
2.2.
Operation at receiver’s side
2.3.
Example
3.
Hamming Code
3.1.
Procedure
3.2.
Example
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Error Detection and Correction Code: Part 2

Author Hari Sapna Nair
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The bits 0 and 1 correspond to the two different ranges of analog voltages. So, during the transmission of binary data from one system to the other, the noise also gets added. Due to this, errors might be there in the received data at the other system.

This means that a bit 0 may change to 1, or a bit 1 may change to 0. It is impossible to avoid noise interference. But, we can definitely get back the original data first by various error detection and correction code techniques. 

In this article, we will extensively discuss the need for error detection and correction code techniques and the various techniques like checksum and hamming code.

Recommended Topic, Microinstruction in Computer Architecture

Checksum

The checksum is a block code method. Here a checksum is created based on the data values in the sender's data blocks to be transmitted using an algorithm and appended to the sender's data. When the receiver receives this data, a new checksum is calculated and compared with the previous checksum. If the result obtained is zero, there is no error.

Operation at senders’ side

The following steps are performed at the sender's end:-

Step 1: Break the original message into 'k' numbers of blocks with 'n' bits in each block.

Step 2: Sum all the 'k' data blocks.

Step 3: Add the carry to the sum, if any.

Step 4: Do 1's complement to the sum

 

The result so obtained here is called the checksum.

Operation at receiver’s side

The following steps are performed at the receiver’s end:-

Step 1: Collect all the data blocks, including the checksum.

Step 2: Sum all the data blocks and checksum.

Step 3: The sum obtained is complemented, and the result is checked. 

Step 4: If the result obtained is zero, there is no error.

Example

Consider the data block to be sent is: 10011001111000100010010010000100

In this case, let's consider an 8-bit checksum.

Sender's end

The given data block is divided into segments of 8 bits as follows:

Sum the data blocks

The result 1000100011 has 10 bits, so the two extra bits must be wrapped around.

1's complement is taken:

Checksum = 11011010
 

The data block and the checksum value are transmitted to the receiver.


Receiver's end

The received data unit is divided into segments of 8 bits on the receiver side.

The sum of the segments and the checksum value are added.

Sum of segments = 00100101

Checksum = 11011010

1's complement is taken:


 

Since the result is 0, no error occurred in the data, and the receiver accepts it

Recommended Topic - Shift Registers in Digital Electronics and what is middleware

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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: 

2r >= 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,.....2k-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 20, 21, 22.

r1 = 1st position

r2 = 2nd position

r4 = 4th 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 4th 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 4th 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!

Previous article
Error Detection and Correction Code: Part 1
Next article
Addition and Subtraction
Live masterclass