hamming code in C++

In this tutorial, we will learn how to find the Hamming code of binary data with a solved example and C++ program.

Hamming code is error-detection and error-correction code which is used to find and correct errors in a code while transmission in data communication. The original data bits are mixed with some bits called redundant bits from the sender sides. Then on the receiver side, the Hamming codes are decoded to find the errors while communication.

Hamming code can only detect 2-bit error and can correct a single bit error only.

Before going into the Hamming code, we need to understand two keywords:

  1. Parity Bits
    It is a bit which is added to data if the total number of 1’s is odd or even depending on odd parity or even parity.
    In the case of odd parity, if the total number of 1’s in data is even then ‘1’ will be added to that data as a parity bit to make the total number of 1’s odd. Else, ‘0’ will be added if the total number of  1’s in data is odd.
    In the case of even parity, if the total number of 1’s in a data is odd then ‘1’ will be added to that data as a parity bit, to make the total number of 1’s even. Else, ‘0’ will be added if the total number of  1’s in data is even.
  2. Redundant bit
    A redundant bit is an extra bit which is added to the data bit. This is to make Hamming code or we can say, to detect errors in the data while transmission.
The number of Redundant bits 'r' for 'm' number of data bits is given by:
2^r >= m + r + 1

Let’s find the Hamming code of data bits, theoretically, to understand it in a better way:

Finding the Hamming Code

Consider a data of 4 bits 1011. 
let the 1st, 2nd, 3rd and a 4th bit from the left side of data be m1, m2, m3, and m4 
respectively.

The number of Redundant bits for 4 bits of data:
2^r >= 4 + r + 1

for r = 3 : 
           2^3 >= 4 + 3 + 1 
        => 8 >= 8                    (true)

Therefore, total number of redundant bits will be 3.And The length of Hamming 
will be 4 + 3 = 11. 
Let the redundant bits be r0, r1 and r2

position of r0 = 2^0 = 1
position of r1 = 2^1 = 2
position of r2 = 2^2 = 4

The Hamming code will look like:

find the hamming code of binary data in C++

and After putting data bits we will get:

solution of hamming code in C++

Now, we need to find the values of r0, r1, and r2. which we will find in the complete C++ program.

Click here ( hamming code in pdf ) for the complete manual solution.  

C++ program to generate Hamming code

#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char** argv) {

    int data_bits[20],m,r = 0,parity;    //m = no. of data bits, r = no. of redundant bits
    
    cout<<"Enter the size of data bits: ";
    cin>>m;
    
    //finding no. of redundant bits
    while(pow (2,r) < m + r + 1){
        r++;
    }
    
    cout<<"Enter the data bit: ";
    for(int i = 1; i <= m; i++)
        cin>>data_bits[i];
    
    int hamming[m + r],j = 0,k = 1;    
    
    //finding positions of redundant bits.
    for(int i = 1; i <= m + r; i++){
        
        if( i == pow( 2, j )){
            hamming[i] = -1;    //-1 is initial value of redundant bits
            j++;
        }
        else{
            hamming[i] = data_bits[k];
            k++;
        }
    }
    
    k = 0;
    int x, min, max = 0;
    //finding parity bit
    for (int i = 1; i <= m + r; i = pow (2, k)){
      k++;
      parity = 0;
      j = i;
      x = i;
      min = 1;
      max = i;
       while ( j <= m + r){
          for (x = j; max >= min && x <= m + r; min++, x++){
              if (hamming[x] == 1)
                  parity = parity + 1;;
          }
          j = x + i;
          min = 1;
      }
      
      //checking for even parity
      if (parity % 2 == 0){ 
         hamming[i] = 0;
      }
      else{
        hamming[i] = 1;
      }
  }
    
    cout<<"\nHamming code is: ";
    for(int i = 1; i <= m + r; i++)
        cout<<hamming[i]<<" ";
    
    return 0;
}

Output: 

Enter the size of data bits: 4
Enter the data bit: 1
0
1
1

Hamming code is: 0 1 1 0 0 1 1

you may also read: 

How to find Hamming distance between two strings in C++

Leave a Reply

Your email address will not be published. Required fields are marked *