NAME: S.R.
PRAVEEN
REG NO: 19BCE0363
CSE1004 – Network and Communication
LAB ASSESSMENT-4
HAMMING CODE CASE STUDY
ALGORITHM:
Encoding a message by Hamming Code
• If the message contains m number of data bits, r number of redundant bits
are added to it so that m is able to indicate at least (m + r+ 1) different
states.
• The r redundant bits placed at bit positions of powers of 2, i.e. 1, 2, 4, 8, 16
etc. They are referred in the rest of this text as r1 (at position 1), r2 (at
position 2), r3 (at position 4), r4 (at position 8) and so on.
• Each redundant bit, ri, is calculated as the parity, generally even parity, based
upon its bit position. It covers all bit positions whose binary representation
includes a 1 in the ith position except the position of ri.
• r1 is the parity bit for all data bits in positions whose binary representation
includes a 1 in the least significant position excluding 1 (3, 5, 7, 9, 11 and so
on)
• r2 is the parity bit for all data bits in positions whose binary representation
includes a 1 in the position 2 from right except 2 (3, 6, 7, 10, 11 and so on)
• r3 is the parity bit for all data bits in positions whose binary representation
includes a 1 in the position 3 from right except 4 (5-7, 12-15, 20-23 and so
on)
Decoding a message in Hamming Code
• Using the same formula as in encoding, the number of redundant bits are
ascertained. 2r ≥ m + r + 1 where m is the number of data bits and r is the
number of redundant bits.
• The r redundant bits placed at bit positions of powers of 2, i.e. 1, 2, 4, 8, 16
etc.
• Parity bits are calculated based upon the data bits and the redundant bits
using the same rule as during generation of c1,c2 ,c3 ,c4 etc. Thus
c1 = parity(1, 3, 5, 7, 9, 11 and so on)
c2 = parity(2, 3, 6, 7, 10, 11 and so on)
c3 = parity(4-7, 12-15, 20-23 and so on)
• The decimal equivalent of the parity bits binary values is calculated. If it is 0,
there is no error. Otherwise, the decimal value gives the bit position which
has error. For example, if c1c2c3c4 = 1001, it implies that the data bit at
position 9, decimal equivalent of 1001, has error. The bit is flipped to get the
correct message.
CASE STUDY:
A physics teacher has conducted a quiz in which the maximum mark
a student can score is 15. Student ‘A’ wants to know how much marks he has
scored in the quiz so he asks his teacher to send his marks. His teacher decides
to send his marks and informs him that he will send his marks in binary form.
The receiver that is the student will now receive seven binary bits (4 data bits
(his mark) embedded with 3 parity bits). Now the student will enter the code
he has received and then he will obtain the original message (his marks) sent
by his teacher. Then he can know his marks. Only one bit error detection and
correction is possible here.
CODE:
#include<stdio.h>
#include<math.h>
int main()
{
int d[10];
int dt[10],c,c1,c2,c3,i;
int m[10];
printf("Enter the marks obtained by the student (binary) :\n");
scanf("%d",&d[0]);
scanf("%d",&d[1]);
scanf("%d",&d[2]);
scanf("%d",&d[4]);
d[6]=d[0]^d[2]^d[4];
d[5]=d[0]^d[1]^d[4];
d[3]=d[0]^d[1]^d[2];
printf("\nEncoded data is\n");
for(i=0;i<7;i++)
printf("%d",d[i]);
printf("\n\nEnter the message that the student has received :\n");
for(i=0;i<7;i++)
scanf("%d",&dt[i]);
c1= dt[6]^dt[4]^dt[2]^dt[0];
c2= dt[5]^dt[4]^dt[1]^dt[0];
c3= dt[3]^dt[2]^dt[1]^dt[0];
c=c3*4+c2*2+c1 ;
if(c==0 && dt[6]==d[6] && dt[5]==d[5] && dt[3]==d[3] ) {
printf("\nThe received message has no error in it\n");
printf("\nThe original marks as sent by his teacher(binary) :");
printf("%d",d[0]);
printf("%d",d[1]);
printf("%d",d[2]);
printf("%d",d[4]);
}
else
printf("\nError on position %d",c);
printf("\nData sent : ");
for(i=0;i<7;i++)
printf("%d",d[i]);
printf("\nData received : ");
for(i=0;i<7;i++)
printf("%d",dt[i]);
printf("\nThe original marks as sent by his teacher(binary) :\n");
if(dt[7-c]==0)
dt[7-c]=1;
else
dt[7-c]=0;
printf("%d",d[0]);
printf("%d",d[1]);
printf("%d",d[2]);
printf("%d",d[4]);
m[0]=d[4];
m[1]=d[2];
m[2]=d[1];
m[3]=d[0];
int mark=0;
for(i=0;i<=3;i++)
{
mark=mark+m[i]*pow(2,i);
printf("\nStudent A mark in the quiz: ");
printf("%d",mark);
OUTPUT SCREENSHOT:
Message sent by physics teacher to the student: 1011
Encoded data: 1010101
Message the student received (entered by the student) : 1010001
Error position: 3
Message after correction: 1011
Student A mark : 11
Message sent by physics teacher to the student: 1111
Encoded data: 1111111
Message the student received (entered by the student) : 1111111
No error detected
Student A mark: 15
