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):
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?
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:
<math.h>
by changing pow(2, k)
with 1 << k
b[n]
), since you are fixing the maximum number of parity bits and all other arrays are fixed to 50 or 70.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.