Hamming Code Implementation in C++

What is Hamming Code ?

Hamming code is an error detection and correction technique used in computer networks to detect and correct the error which are introduced during the transmission of data over a communication channel. Hamming code algorithm can detect maximum two errors and can correct only one error per word.

Hamming Code Generation with example

Hamming code is a linear block of code which consist of parity bits inserted in between the data bits. The parity bits are inserted at each 2ⁿ bit position where n=0,1,2,3…….

For n=0, P0 parity bit will be inserted at 2⁰ = 1 , i.e at first bit position

For n=1, P1 parity bit will be inserted at 2¹ = 2, i.e at second position

For n=2, P2 parity bit will be inserted at 2² = 4, i.e at forth position

so on,

The number of parity bits r to be inserted for a given m number of data bits is given by the following equation

                    2^r ≥ m+r+1,    where m = number of bits in data  &  r = number of parity bits

For a bit word  1011, m=4   find r which satisfy the above equation 

For r=1,   2¹ ≥ 4+1+1, which is not true similar for r=2

For r=3, 2³ ≥ 4+3+1  à 8 ≥ 8 which is true

Hence bit word 1011 needs 3 parity bits to be inserted to form a hamming code.

The 3 parity bits P0, P1 and P2 will be inserted at 1^st, 2^nd and 4^th explained earlier.

The hamming code format for bit word 1011 is shown below

So, now lets obtain the parity bits, for this you may consider even parity or odd parity.

Even parity means the number of 1’s in the given word including the parity bit should be even i.e 2,4,6…

Od parity means the number of 1’s in the given word including the parity bit should be odd i.e 1,3,5…

Let consider the even parity for hamming code of bit word 1011.

The following table illustrate the bits to be check to set the parity bits in Hamming code.

 

For P0, consider bits at position 1,3,5,7 i.e P0,1,1,1

Now the bits sequence P0, 1, 1, 1 should have even parity hence, put P0 = 1 so that sequence become 1 1 1 1 which has even parity.

Similarly for P1, consider bits at position 2,3,6,7 I.e P1,1,0,1

Therefore P1 will be 0 so that the sequence P1 1 0 1 will become even parity.

In similar manner we obtain P2 = 0.

Hence the complete code word for word 1011 is shown below.

 

Now, this hamming code is transmitted over a communication channel to the intended receiver.

Hamming Code Error Detection and Correction

At the receiver side the hamming code is checked for any error.

For the 7 bit hamming code received the bit sequences (1,3,5,7), (2,3,6,7) and (4,5,6,7) are checked for even parity.

If all the bit sequences have even parity then the hamming code received is correct else it has some error.

The error can be detected by forming a error code from the three parity check of sequences mentioned before. 

For example, the received hamming code for the earlier example is 1110101.

Check bits at position 1, 3, 5, 7  = 1 1 1 1 ==> Even parity, hence no error  ==>  E1 = 0

Check bits at position 2, 3, 6, 7  = 0 1 1 1 ==> Odd parity, hence error exits  ==>  E2 =1

Check bits at position 4, 5, 6, 7  = 0 1 1 1 ==> even parity, hence no error  ==>  E3 = 1

Error code = E3 E2 E1 ==> 110 ==> (6)₁₀

Hence, the 6th bit in the received hamming code is incorrect.

Here the 6th is 1, hence invert it to obtain the correct hamming code.

Hence the correct hamming code becomes 1010101 which is correct.

Hamming Code Program in C++

#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;

int check_parity(int n,int i,int code[])        
{
    int p=0,k;
    for(int j=i;j<=n;j=k+i)
    {
        for(k=j;k<j+i && k<=n;k++)        //for i=1 ->bits=1,3,5,7,9,11    for i=2 ->bits 2,3,6,7,10,11
        {                    //i is parity bit position
            if(code[k]==1)
            p++;
        }
    }
    if(p%2==0)
        return 0;        //if no. of 1 is even return 0
    else 
        return 1;        //if no. of 1 is odd return 1
}

void hamming_code(int data[], int num)
{
    int r=0,m=0,n,j=1,c,code[50];
    
    while((r+num+1)>(pow(2,r)))            //calculating no. of parity/redundant bits
        r++;

    n=num+r;                    //adding no. of redundant bits to array size
    for(int i=1;i<=n;i++)
    {
        if(i==pow(2,m) && m<=r)
        {
            code[i]=0;            //initializing all the bit position of power 2 to zero
            m++;
        }
        else
        {
            code[i]=data[j];        //assgning data to remaining positions
            j++;
        }
    }

    m=0;
    for(int i=1;i<=n;i++)
    {
        if(i==pow(2,m) && m<=r)            
        {
            c=check_parity(n,i,code);        //assigning parity bit to position of power 2
            code[i]=c;
            m++;
        }
    }

    cout<<"The hamming code for given data is:";
    for(int i=n;i>0;i--)
    cout<<code[i];
    cout<<"\nEnter the received code:";
    for(int i=n;i>0;i--)
    cin>>code[i];
    m=j=c=0;
    for(int i=1;i<=n;i++)
    {
        if(i==pow(2,m) && m<=r)
        {
            c=c+(pow(2,j)*check_parity(n,i,code));    // decimal value of error code
            j++;
            m++;
        }
    }
    if(c==0)
        cout<<"\nReceived word is correct.";
    else
    {
        cout<<"\nThere is error in bit "<<(n-c)+1<<"\nThe corrected code is:";
        if(code[c]==1)
            code[c]=0;
        else
            code[c]=1;
        for(int i=n;i>0;i--)
            cout<<code[i];
    }
}

int main()
{
    int data[50], num;

    cout<<"Enter the size of data";
    cin>>num;
    cout<<"Enter the data:";
    for(int i=num;i>0;i--)
    cin>>data[i];

    hamming_code(data, num);

    return 0;
}

 

Output:

 

•  _{Cyclic Redundancy Check Program in C++}