cnetwork-programming

Wrong parity bit generated on the sender side on the hamming code


The following code is for hamming code error calculation:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

void main()
{
    int maxp=6;
    int a[50],temp[70],temp2[70];
    int t,i,j,k,nd,n,nh,sum=0,pos=0;

    printf("Enter Length of Data String: ");
    scanf("%d",&nd);
    printf("Enter Data String: ");
    for(i=0;i<nd;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("-----------------------------------\n",nd);
    for(i=0,j=0;i<nd;i++)
    {
        for(k=0;k<maxp;k++)
        {
            t=pow(2,k)-1;
            if(j==t)
            {
                temp[j]=0;
                j++;
            }
        }
        temp[j]=a[i];
        j++;
    }
    nh=j;
    printf("Length of Hamming code: %d bits\n",nh);
    n=nh-nd;
    printf("Number of Parity Bits: %d \n",n);

    int b[n];
    int m=n-1;
    for(k=0;k<n;k++)
    {
        t=pow(2,k)-1;

        for(i=t;i<nh;)
        {
            for(j=0;j<=t;j++)
            {
                sum=sum+temp[i];
                i++;
                if(i>=nh)
                    break;
            }

            if(i>=nh)
                break;

            for(j=0;j<=t;j++)
            {
                i++;
                if(i>=nh)
                    break;
            }

            if(i>=nh)
                break;
        }
        temp[t]=sum%2;
        sum=0;
        printf("P%d: %d\n",t+1,temp[t]);
    }


    printf("\nHamming code: Sender side:   ");
    for(i=0;i<nh;i++)
    {
        printf("%d ",temp[i]);
    }


    printf("\nHamming code: Receiver side: ");
    for(i=0;i<nh;i++)
    {
        scanf("%d",&temp2[i]);
    }
    sum=0;
    for(k=0;k<n;k++)
    {
        t=pow(2,k)-1;

        for(i=t;i<nh;)
        {
            for(j=0;j<=t;j++)
            {
                sum=sum+temp2[i];
                i++;
                if(i>=nh)
                    break;
            }

            if(i>=nh)
                break;

            for(j=0;j<=t;j++)
            {
                i++;
                if(i>=nh)
                    break;
            }

            if(i>=nh)
                break;
        }
        b[m]=sum%2;
        sum=0;
        printf("P%d: %d\n",t+1,b[m]);
        m--;
    }
    for(m=0;m<n;m++)
    {
        pos=pos+b[n-m-1]*pow(2,m);
    }
    printf("Position of Error: %d\n",pos);
    if(temp2[pos-1]==0)
        temp2[pos-1]=1;
    else
        temp2[pos-1]=0;

    printf("\nHamming code: Receiver side: Error Corrected:  ");
    for(i=0;i<nh;i++)
    {
        printf("%d ",temp2[i]);
    }

    printf("\n-----------------------------------\n",nd);
}

If I run this code I get this:

Enter Length of Data String: 4
Enter Data String: 1
0
1
0
-----------------------------------
Length of Hamming code: 7 bits
Number of Parity Bits: 3 
P1: 1
P2: 0
P4: 1

Hamming code: Sender side:   1 0 1 1 0 1 0 
Hamming code: Receiver side: 1
0
0
1
0
1
0
P1: 1
P2: 1
P4: 0
Position of Error: 3

Hamming code: Receiver side: Error Corrected:  1 0 1 1 0 1 0 

I have the doubt about the 1st parity bits

    P1: 1
    P2: 0
    P4: 1

To implement the hamming code for this logic (for even parity Hamming codeword):

  1. Set a parity bit to 1 if the total number of ones in the positions it checks is odd.
  2. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

Then the 1st generated parity bit should be

p1 = 0
p2= 1
p4= 0

instead of

    P1: 1
    P2: 0
    P4: 1

Can anyone explain what I missed in the above code?


Solution

  • Your code is working correctly and in fact it is correcting the error. What is wrong are your expected parity values. You say that the parity should have been:

    p1 = 0
    p2 = 1
    p4 = 0
    

    Lets make a table with the Hamming's code parity positions:

    0 1 2 3 4 5 6
    P1 P2 D1 P4 D2 D3 D4
    ? ? 1 ? 0 1 0

    P1 is computed starting from position 0 and is computed using 1 value and then skipping 1: positions: 0,2,4,6 that is values ?,1,0,0 so P1 must be 1.

    P2 is computed starting from position 1 and is computed using 2 values and then skipping 2: positions: 1,2,4,5 that is values ?,1,1,0 so P2 must be 0.

    P4 is computed starting from position 3 and is computed using 4 values and then skipping 4: positions: 3,4,5,6 that is values ?,0,1,0 so P4 must be 1.

    That is exactly what your code is doing. And it works!

    The bits which should be used to compute the parities are highlighted here.

    0 1 2 3 4 5 6
    P1 * * * *
    P2 * * * *
    P4 * * * *

    Of course this could go beyond the 4 bits example and your code is capable of doing it. As mentioned in the comments the code could be better:

    1. remove the dependency from <math.h> by changing pow(2, k) with 1 << k
    2. remove the use of VLAs (b[n]), since you are fixing the maximum number of parity bits and all other arrays are fixed to 50 or 70.
    3. remove the spurious argument passed to printf.

    This code could use a good rewriting to avoid so much copy and paste and allow for better testing moving most of the code into functions.