Implementation of Hamming code

• This post gives an idea on how to implement Hamming Code. Hamming code pattern is mainly used for detection of errors in bits.

Objectives:

• The main objective is, detection of single bit error, burst error and to correct by using the suitable methodology (by hamming distance concept).
• The purpose of this project is to overcome unreliable transmission of data during the transmission from the encoder to the decoder.
• It involves block coding, finding the hamming distance between to existing code words, redundancy, error correction, parity check code.

Description:

The theory of error detecting and correcting codes is that branch of engineering and mathematics which deals with the reliable transmission and storage of data. Information media are not 100% reliable in practice, in the sense that noise (any form of interference) frequently causes data to be distorted. To deal with this undesirable but inevitable situation, self-correcting codes are constructed by combining data bits with a number of redundant check-bits, which together are referred to as code words.  By adding a single bit (as in Parity Checking) along with a given number of data-bits, half of the possible code words become valid and half invalid.  This is referred to as a code that has Hamming Distance 2 (two single bit flips are required to get from one calid code to another). This particular approach, using Hamming Distance, is the minimum requirement for self-error correction and is commonly referred to as a Hamming Code.

Preliminaries:

a. Hamming distance H(a,b) = #number of bit positions in which a differs from b, i.e., the number of 1’s in an XOR. Hamming distance of a code is the minimum over all pairs of distinct code words of the Hamming distance between them, i.e.,

H(code) = min {H(a,b) | a<>b and a, b in code}

b. Error correction – enough redundancy is transmitted in the code that errors can be corrected by the receiver without retransmission.

c. Error detection is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver.

d. d-bit error detection requires a code with Hamming distance (d+1).
    d-bit error correction requires a code with Hamming distance (2d+1).

Tools  Required:

• Encoder.
• Decoder.
• cyclic redundancy check (CRC) or polynomial code checksum.
• linear block codes.
• Two single bit Flip-Flop.

Future Scope:

In the field of artificial intelligence, where there is a need to search through large state spaces, there is the notion of using evaluation functions to heuristically search a large space in a hill climbing or the best-first search fashion. Since Hamming distance is an easy-to-define metric, it is used to search the state space for design flaws.

Hamming code is an easy and efficient technique, which can only detect and correct a single bit error. However. it can also be used to detect a burst error (A burst error means that 2 or more bits in the data unit have changed), but by applying the different technique.

The structure of the encoder and decoder for a Hamming code

Suggested Read:

• Java Registration Form using Servlet, MySQL
• Implementation of a simple library management system

Following is the code in C language to implement hamming code:

Program to implement 7-bit hamming code:

#include<stdio.h>

void main() 
{
int data[10];
int dataatrec[10],c,c1,c2,c3,i;

printf(“Enter 4 bits of data one by one\n”);
scanf(“%d”,&data[0]);
scanf(“%d”,&data[1]);
scanf(“%d”,&data[2]);
scanf(“%d”,&data[4]);

data[6]=data[0]^data[2]^data[4];
data[5]=data[0]^data[1]^data[4];
data[3]=data[0]^data[1]^data[2];

printf(“\nEncoded data is\n”);
for(i=0;i<7;i++)
printf("%d",data[i]);

printf("\n\nEnter received data bits one by one\n");
for(i=0;i<7;i++)
scanf("%d",&dataatrec[i]);

c1= dataatrec[6]^dataatrec[4]^dataatrec[2]^dataatrec[0];
c2= dataatrec[5]^dataatrec[4]^dataatrec[1]^dataatrec[0];
c3= dataatrec[3]^dataatrec[2]^dataatrec[1]^dataatrec[0];
c=c3*4+c2*2+c1 ;

	if(c==0 && dataatrec[6]==data[6] && dataatrec[5]==data[5] && dataatrec[3]==data[3] ) {
	printf("\nNo error while transmission of data\n");
	}
    else
	{
		printf("\nError on position %d",c);

		printf("\nData sent : ");
		for(i=0;i<7;i++)
		printf("%d",data[i]);

		printf("\nData received : ");
		for(i=0;i<7;i++)
		printf("%d",dataatrec[i]);

		printf("\nCorrect message is\n");

		if(dataatrec[7-c]==0)
		dataatrec[7-c]=1;
		else
		dataatrec[7-c]=0;

		for (i=0;i<7;i++) 
		{
			printf("%d",data[i]);
		}
	}
}

 

 

//HAMMING CODE for error detection and correction
#include<stdio.h>
int main()
{
int a[4],b[4],r[3], s[3],i,q[3];
printf("\nenter 4 bit data word:\n");
for(i=3;i>=0;i--)
{
scanf("%d",&a[i]);
}
r[0]=(a[2]+a[1]+a[0])%2;
r[1]=(a[2]+a[1]+a[3])%2;
r[2]=(a[0]+a[1]+a[3])%2;

printf("\n\nthe 7bit hamming code word: \n");
for(i=3;i>=0;i--)
{
printf("%d\t",a[i]);
}
for(i=2;i>=0;i--)
{
printf("%d\t",r[i]);
}
printf("\n");
printf("\nenter the 4bit recieved word: ");

for(i=3;i>=0;i--)
scanf("%d",&b[i]);

//calculating syndrome bits
s[0]= (b[2]+b[1]+b[0]+r[0])%2;
s[1]= (b[3]+b[2]+b[1]+r[1])%2;
s[2]= (b[0]+b[1]+b[3]+r[2])%2;
printf("\nsyndrome is: \n");

for(i=2; i>=0;i--)
{
printf("%d",s[i]);
}
if((s[2]==0) && (s[1]==0) && (s[0]==0))
printf("\n RECIEVED WORD IS ERROR FREE\n");
if((s[2]==1) && (s[1]==0) && (s[0]==1))
printf("\nrecieved word is error with error in 1bit(b0) position from right\n");
if((s[2]==1) && (s[1]==1) && (s[0]==1))
printf("\nrecieved word is error with error in 2bit(b1) position from right\n");
if((s[2]==0) && (s[1]==1) && (s[0]==1))
printf("\nrecieved word is error with error in 3bit(b2) position from right\n");
if((s[2]==1) && (s[1]==1) && (s[0]==0))
printf("\nrecieved word is error with error in 4bit(b3) position from right\n");
return(1);
}
//End of Hamming code program