Name= Sakshi Dipak Halge

Subject - Computer Networks Lab

Assignment No.2

OBJECTIVES:

1.To understand CRC and Hamming code

Problem Statement:

Write a program for error detection and correction for 7/8 bits ASCII codes using

Hamming Codes or CRC. Demonstrate the packets captured traces using Wireshark Packet

Analyzer Tool for peer to peer mode .( 50% students will perform Hamming Code and others

will perform CRC)

Theory:

Hamming Distance:

One of the central concepts in coding for error control is the idea of the Hamming distance.

The Hamming distance between two words (of the same size) is the number of differences

between the corresponding bits. We show the Hamming distance between two words x and y

as d(x, y).

The Hamming distance can easily be found if we apply the XOR operation ( ) on the ⊕ two

words and count the number of 1s in the result. Note that the Hamming distance is a value

greater than zero. The Hamming distance between two words is the number of differences

between corresponding bits.

Let us find the Hamming distance between two pairs of words.

1.The Hamming distance d(000, 011) is 2 because 000 011 is 011 (two 1s). ⊕

2.The Hamming distance d(10101, 11110) is 3 because 10101 11110 is 01011 (three ⊕ 1s).

Minimum Hamming Distance:

Although the concept of the Hamming distance is the central point in dealing with

error detection and correction codes, the measurement that is used for designing a code is the

minimum Hamming distance. In a set of words, the minimum Hamming distance is the

smallest Hamming distance between all possible pairs. We use d min to define the minimum

Hamming distance in a coding scheme. To find this value, we find the Hamming distances

between all words and select the smallest one. The minimum Hamming distance is the

smallest Hamming distance between all possible pairs in a set of words.

Find the minimum Hamming distance of the coding scheme in Table. Solution We first find

all the Hamming distances.

d(00000, 01011) = 3

d(01011, 10101) = 4

d(00000, 10101) = 3

d(01011, 11110) = 3

d(00000, 11110) = 4

d(10101, 11110) = 3
The d min in this case is 3.

Hamming Distance and Error:

Before we explore the criteria for error detection or correction, let us discuss the relationship

between the Hamming distance and errors occurring during transmission. When a codeword

is corrupted during transmission, the Hamming distance between the sent and received

codewords is the number of bits affected by the error. In other words, the Hamming distance

between the received codeword and the sent codeword is the number of bits that are

corrupted during transmission. For example, if the codeword 00000 is sent and 01101 is

received, 3 bits are in error and the Hamming distance between the two is d(00000, 01101) =

3.

Minimum Distance for Error Detection:

Now let us find the minimum Hamming distance in a code if we want to be able to

detect up to s errors. If s errors occur during transmission, the Hamming distance between the

sent codeword and received codeword is s. If our code is to detect up to s errors, the

minimum distance between the valid codes must be s + 1, so that the received codeword does

not match a valid codeword. In other words, if the minimum distance between all valid

codewords is s + 1, the received codeword cannot be erroneously mistaken for another

codeword. The distances are not enough (s + 1) for the receiver to accept it as valid. The

error will be detected. We need to clarify a point here: Although a code with d min = s + 1

may be able to detect more than s errors in some special cases, only s or fewer errors are

guaranteed to be detected. To guarantee the detection of up to s errors in all cases, the

minimum Hamming distance in a block code must be d min = s + 1.

CRC:
 A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital

networks and storage devices to detect accidental changes to raw data. Blocks of data

entering these systems get a short check value attached, based on the remainder of a

polynomial division of their contents.

On retrieval, the calculation is repeated and, in the event the check values do not match,

corrective action can be taken against data corruption. CRCs can be used for error correction,

see bitfilters.

CRCs are so called because the check (data verification) value is a redundancy (it expands

the message without adding information) and the algorithm is based on cyclic codes.

CRCs are popular because they are simple to implement in binary hardware, easy to analyze

mathematically, and particularly good at detecting common errors caused by noise in

transmission channels.

Because the check value has a fixed length, the function that generates it is occasionally used

as a hash function.

The CRC was invented by W. Wesley Peterson in 1961; the 32-bit CRC function of Ethernet

and many other standards is the work of several researchers and was published in 1975.

CRCs are based on the theory of cyclic error-correcting codes. The use of systematic cyclic

codes, which encode messages by adding a fixed-length check value, for the purpose of error

detection in communication networks, was first proposed by W. Wesley Peterson in 1961.

Cyclic codes are not only simple to implement but have the benefit of being particularly well

suited for the detection of burst errors: contiguous sequences of erroneous data symbols in

messages. This is important because burst errors are common transmission errors in many

communication channels, including magnetic and optical storage devices. Typically an nbit

CRC applied to a data block of arbitrary length will detect any single error burst not longer
than n bits and will detect a fraction 1/(1 − 2−n) of all longer error bursts. Specification of a

CRC code requires definition of a so-called generator polynomial. This polynomial becomes

the divisor in a polynomial long division, which takes the message as the dividend and in

which the quotient is discarded and the remainder becomes the result.

The important caveat is that the polynomial coefficients are calculated

according to the arithmetic of a finite field, so the addition operation can always be

performed bitwise parallel (there is no carry between digits). The length of the remainder is

always less than the length of the generator polynomial, which therefore determines how long

the result can be. In practice, all commonly used CRCs employ the Galois field of two

elements, GF(2). The two elements are usually called 0 and 1, comfortably matching

computer architecture. A CRC is called an n-bit CRC when its check value is n bits long. For

a given n, multiple CRCs are possible, each with a different polynomial. Such a polynomial

has highest degree n, which means it has n + 1 terms.

In other words, the polynomial has a length of n + 1; its encoding requires n +

1 bits. Note that most polynomial specifications either drop the MSB or LSB, since they are

always 1. The CRC and associated polynomial typically have a name of the form CRC-n-

XXX as in the table below. The simplest error-detection system, the parity bit, is in fact a

trivial 1-bit CRC: it uses the generator polynomial x + 1 (two terms), and has the name CRC-

1.

Application:

A CRC-enabled device calculates a short, fixed-length binary sequence, known as the check

value or CRC, for each block of data to be sent or stored and appends it to the data, forming a

codeword. When a codeword is received or read, the device either compares its check value

with one freshly calculated from the data block, or equivalently, performs a CRC on the
whole codeword and compares the resulting check value with an expected residue constant. If

the CRC check values do not match, then the block contains a data error. The device may

take corrective action, such as rereading the block or requesting that it be sent again.

Otherwise, the data is assumed to be error-free (though, with some small probability, it may

contain undetected errors; this is the fundamental nature of error checking)

Data integrity:

CRCs are specifically designed to protect against common types of errors on communication

channels, where they can provide quick and reasonable assurance of the integrity of messages

delivered. However, they are not suitable for protecting against intentional alteration of data.

Firstly, as there is no authentication, an attacker can edit a message and recompute the CRC

without the substitution being detected. When stored alongside the data, CRCs and

cryptographic hash functions by themselves do not protect against intentional modification of

data. Any application that requires protection against such attacks must use cryptographic

authentication mechanisms, such as message authentication codes or digital signatures (which

are commonly based on cryptographic hash functions).

Secondly, unlike cryptographic hash functions, CRC is an easily reversible function, which

makes it unsuitable for use in digital signatures

Thirdly, CRC is a linear function with a property that ; as a result, even if the CRC is

encrypted with a stream cipher that uses XOR as its combining operation (or mode of block

cipher which effectively turns it into a stream cipher, such as OFB or CFB), both the message

and the associated CRC can be manipulated without knowledge of the encryption key; this

was one of the well-known design flaws of the Wired Equivalent Privacy (WEP) protocol.[5]

To compute an n-bit binary CRC, line the bits representing the input in a row, and position
the (n + 1)-bit pattern representing the CRC's divisor (called a "polynomial") underneath

the left-hand end of the row

Example: In this example, we shall encode 14 bits of message with a 3-bit CRC, with a

polynomial x 3 + x + 1. The polynomial is written in binary as the coefficients; a 3rd-order

polynomial has 4 coefficients (1x 3 + 0x 2 + 1x + 1). In this case, the coefficients are 1, 0, 1

and 1. The result of the calculation is 3 bits long.

Start with the message to be encoded:

11010011101100

This is first padded with zeros corresponding to the bit length n of the CRC. Here is the first

calculation for computing a 3-bit CRC:

11010011101100 000 <--- input right padded by 3 bits

1011 <--- divisor (4 bits) = x³ + x + 1

01100011101100 000 <--- result

The algorithm acts on the bits directly above the divisor in each step. The result for that

iteration is the bitwise XOR of the polynomial divisor with the bits above it.

The bits not above the divisor are simply copied directly below for that step. The divisor is

then shifted one bit to the right, and the process is repeated until the divisor reaches the right-

hand end of the input row. Here is the entire calculation:

11010011101100 000 <--- input right padded by 3 bits

1011 <--- divisor

beneath, the rest of the bits are unchanged)

1011 <--- divisor ...

00111011101100 000

1011

00010111101100 000

1011

00000001101100 000 <--- note that the divisor moves over to align with the next 1 in the

dividend (since quotient for that step was zero)

1011 (in other words, it doesn't necessarily move one bit per iteration)

00000000110100 000

1011

00000000011000 000

1011

00000000001110 000

1011 00000000000101 000

1011

00000000000000 100 <--- remainder (3 bits). Division algorithm stops here as dividend is

equal to zero.
Since the leftmost divisor bit zeroed every input bit it touched, when this process ends the

only bits in the input row that can be nonzero are the n bits at the right-hand end of the row.

These n bits are the remainder of the division step, and will also be the value of the CRC

function (unless the chosen CRC specification calls for some postprocessing). The validity of

a received message can easily be verified by performing the above calculation again, this

time with the check value added instead of zeroes. The remainder should equal zero if there

are no detectable errors.

11010011101100 100 <--- input with check value

1011 <--- divisor

01100011101100 100 <--- result

1011 <--- divisor ...

00111011101100 100 ......

00000000001110 100

1011

00000000000101 100

1011

0 <--- remainder

Conclusion: Thus we have studied Hamming and CRC Code.

1. CRC

#include <iostream>

using namespace std;

int main()

int i,j,k,l;

//Get Frame

int fs;

cout<<"\n Enter Frame size: ";

cin>>fs;

int f[20];

cout<<"\n Enter Frame:";

for(i=0;i<fs;i++)

cin>>f[i];

//Get Generator

int gs;

cout<<"\n Enter Generator size: ";

int g[20];

cout<<"\n Enter Generator:";

for(i=0;i<gs;i++)

cin>>g[i];

cout<<"\n Sender Side:";

cout<<"\n Frame: ";

for(i=0;i<fs;i++)

cout<<f[i];

cout<<"\n Generator :";

for(i=0;i<gs;i++)

cout<<g[i];

//Append 0's

int rs=gs-1;

cout<<"\n Number of 0's to be appended: "<<rs;

{ f[i]=

0;

int temp[20];

for(i=0;i<20;i++)

temp[i]=f[i];

cout<<"\n Message after appending 0's :";

for(i=0; i<fs+rs;i++)

cout<<temp[i];

//Division

for(i=0;i<fs;i++)

{ j=

0;

k=i;

//check whether it is divisible or not

if (temp[k]>=g[j])

{
 for(j=0,k=i;j<gs;j++,k++)

if((temp[k]==1 && g[j]==1) || (temp[k]==0 && g[j]==0))

temp[k]=0;

else

temp[k]=1;

//CRC

int crc[15];

for(i=0,j=fs;i<rs;i++,j++)

crc[i]=temp[j];

cout<<"\n CRC bits: ";

for(i=0;i<rs;i++)

cout<<crc[i];
}

cout<<"\n Transmitted Frame: ";

int tf[15];

for(i=0;i<fs;i++)

tf[i]=f[i];

for(i=fs,j=0;i<fs+rs;i++,j++)

tf[i]=crc[j];

for(i=0;i<fs+rs;i++)

cout<<tf[i];

cout<<"\n Receiver side : ";

cout<<"\n Received Frame: ";

for(i=0;i<fs+rs;i++)

cout<<tf[i];

for(i=0;i<fs+rs;i++)
{

temp[i]=tf[i];

//Division

for(i=0;i<fs+rs;i++)

{ j=

0;

k=i;

if (temp[k]>=g[j])

for(j=0,k=i;j<gs;j++,k++)

if((temp[k]==1 && g[j]==1) || (temp[k]==0 && g[j]==0))

temp[k]=0;

else

temp[k]=1;

}
 cout<<"\n Reaminder: ";

int rrem[15];

for (i=fs,j=0;i<fs+rs;i++,j++)

rrem[j]= temp[i];

for(i=0;i<rs;i++)

cout<<rrem[i];

int flag=0;

for(i=0;i<rs;i++)

if(rrem[i]!=0)

flag=1;

if(flag==0)

cout<<"\n Since Remainder Is 0 Hence Message Transmitted From Sender To Receriver

Is Correct";

}
 else

cout<<"\n Since Remainder Is Not 0 Hence Message Transmitted From Sender To

Receriver Contains Error";

return 0;

/* OUTPUT

iotlab@iotlab-Veriton-M200-B360:~$ g++ crc1.cpp

iotlab@iotlab-Veriton-M200-B360:~$ ./a.out

Enter Frame size: 8

Enter Frame:1

Enter Generator size: 4

Sender Side:

Frame: 10110111

Generator :1010

Number of 0's to be appended: 3

Message after appending 0's :10110111000

CRC bits: 110

Transmitted Frame: 10110111110

Receiver side :

Received Frame: 10110111110

Reminder: 000

Since Remainder Is 0 Hence Message Transmitted From Sender To Receriver Is Correct

*/

2. Hamming Code:

#include<iostream>

using namespace std;

int main()

int data[10];
int dataatrec[10],c,c1,c2,c3,i;

cout<<"Enter 4 bits of data one by one\n";

cin>>data[7];

cin>>data[6]

cin>>data[5]

cin>>data[3]

//Calculation of even parity

data[4]=data[5]^data[6]^data[7];

data[2]=data[3]^data[6]^data[7];

data[1]=data[3]^data[5]^data[7];

cout<<"\nEncoded data is\n";

for(i=1;i<=7;i++)

cout<<data[i];

cout<<"\n\nEnter received data bits one by one\n";

for(i=1;i<=7;i++)

cin>>dataatrec[i];

c1=dataatrec[1]^dataatrec[3]^dataatrec[5]^dataatrec[7]

c2=dataatrec[2]^dataatrec[3]^dataatrec[6]^dataatrec[7]
;

c3=dataatrec[4]^dataatrec[5]^dataatrec[6]^dataatrec[7]

; c=c3*4+c2*2+c1;
 if(c==0)

cout<<"\ncongratulations there is no error: ";

else

cout<<"\nerror on the postion:"<<c;

cout<<"\nCorrect message is:";

if(dataatrec[c]==0)

dataatrec[c]=1;

else

dataatrec[c]=0;

for (i=1;i<=7;i++)

cout<<dataatrec[i];

return 0;

/*OUTPUT

iotlab@iotlab-Veriton-M200-B360:~$ g++ Ham.cpp

iotlab@iotlab-Veriton-M200-B360:~$ ./a.out

Enter 4 bits of data one by one

Encoded data is

1000011

Enter received data bits one by one

error on the postion:2

Correct message is:1000011