Error Detection and Correction Techniques

Aim: a. Write a program for Error Detection usinng CRC.

b. Write a program for Error Correction using Hamming Code.

Apparatus (Software): Eclipse/ Netbeans

Procedure: Following should be studied to understand this practical

Introduction

Environmental interference and physical defects in the communication medium can cause random bit errors during data transmission. Error coding is a method of detecting and correcting these errors to ensure information is transferred intact from its source to its destination.

Types of errors

These interferences can change the timing and shape of the signal. If the signal is carrying binary encoded data, such changes can alter the meaning of the data. These errors can be divided into two types: Single-bit error and Burst error.

Single-bit Error

The term single-bit error means that only one bit of given data unit (such as a byte,

character, or data unit) is changed from 1 to 0 or from 0 to 1 as shown:

Burst Error

The term burst error means that two or more bits in the data unit have changed from 0 to 1 or vice-versa. Note that burst error doesn’t necessary means that error occurs in consecutive bits. The length of the burst error is measured from the first corrupted bit to the last corrupted bit. Some bits in between may not be corrupted.

Detecting Codes

Basic approach used for error detection is the use of redundancy, where additional bits are added to facilitate detection and correction of errors. Popular techniques are:

Simple Parity check
Two-dimensional Parity check
Checksum
Cyclic redundancy check

A. Cyclic Redundancy Checks (CRC)

This Cyclic Redundancy Check is the most powerful and easy to implement technique. Unlike checksum scheme, which is based on addition, CRC is based on binary division. In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are appended to the end of data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number. At the destination, the incoming data unit is divided by the same number. If at this step there is no remainder, the data unit is assumed to be correct and is therefore accepted. A remainder indicates that the data unit has been damaged in transit and therefore must be rejected. The generalized technique can be explained as follows:

If a k bit message is to be transmitted, the transmitter generates an r-bit sequence, known as Frame Check Sequence (FCS) so that the (k+r) bits are actually being transmitted. Now this r-bit FCS is generated by dividing the original number, appended by r zeros, by a predetermined number. This number, which is (r+1) bit in length, can also be considered as the coefficients of a polynomial, called Generator Polynomial. The remainder of this division process generates the r-bit FCS. On receiving the packet, the receiver divides the (k+r) bit frame by the same predetermined number and if it produces no remainder, it can be assumed that no error has occurred during the transmission.

Operations at both the sender and receiver end are shown below:

This mathematical operation performed is illustrated in Fig. 3.2.7 by dividing a sample 4- bit number by the coefficient of the generator polynomial x 3 +x+1, which is 1011, using the modulo-2 arithmetic. Modulo-2 arithmetic is a binary addition process without any carry over, which is just the Exclusive-OR operation. Consider the case where k=1101. Hence we have to divide 1101000 (i.e. k appended by 3 zeros) by 1011, which produces the remainder r=001, so that the bit frame (k+r) =1101001 is actually being transmitted through the communication channel. At the receiving end, if the received number, i.e., 1101001 is divided by the same generator polynomial 1011 to get the remainder as 000, it can be assumed that the data is free of errors.

Program

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class crc

{

public static void main(String args[]) throws IOException

{

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

int[] data;

int[] div;

int[] divisor;

int[] rem;

int[] crc;

int data_bits, divisor_bits, tot_length;

System.out.println("Enter number of data bits : ");

data_bits=Integer.parseInt(br.readLine());

data=new int[data_bits];

System.out.println("Enter data bits : ");

for(int i=0; i<data_bits; i++)

data[i]=Integer.parseInt(br.readLine());

System.out.println("Enter number of bits in divisor : ");

divisor_bits=Integer.parseInt(br.readLine());

divisor=new int[divisor_bits];

System.out.println("Enter Divisor bits : ");

for(int i=0; i<divisor_bits; i++)

divisor[i]=Integer.parseInt(br.readLine());

// Display the Data and Divisor Bits

System.out.print("\n Data bits are : ");

for(int i=0; i< data_bits; i++)

System.out.print(data[i]);

System.out.print("\n Divisor bits are : ");

for(int i=0; i< divisor_bits; i++)

System.out.print(divisor[i]);

tot_length=data_bits+divisor_bits-1;

// Declaration

div=new int[tot_length];

rem=new int[tot_length];

crc=new int[tot_length];

/*------------------ CRC GENERATION-----------------------*/

for(int i=0;i<data.length;i++)

div[i]=data[i];

System.out.print("\n Dividend (after appending 0's) are : ");

for(int i=0; i< div.length; i++)

System.out.print(div[i]);

System.out.println();

for(int j=0; j<div.length; j++)

{

rem[j] = div[j];

}

rem=divide(div, divisor, rem);

for(int i=0;i<div.length;i++) //append dividend and ramainder

{

crc[i]=(div[i]^rem[i]);

}

System.out.println();

System.out.println("CRC code : ");

for(int i=0;i<crc.length;i++)

System.out.print(crc[i]);

/*-------------------ERROR DETECTION---------------------*/

System.out.println();

System.out.println("Enter CRC code of "+tot_length+" bits : ");

for(int i=0; i<crc.length; i++)

crc[i]=Integer.parseInt(br.readLine());

for(int j=0; j<crc.length; j++)

{

rem[j] = crc[j];

}

rem=divide(crc, divisor, rem);

for(int i=0; i< rem.length; i++)

{

if(rem[i]!=0)

{

System.out.println("Error");

break;

}

if(i==rem.length-1)

System.out.println("No Error");

}

static int[] divide(int div[],int divisor[], int rem[])

{

int cur=0;

while(true)

{

for(int i=0;i<divisor.length;i++)

rem[cur+i]=(rem[cur+i]^divisor[i]);

while(rem[cur]==0 && cur!=rem.length-1)

cur++;

if((rem.length-cur)<divisor.length)

break;

}

return rem;

}

Output

CRC WITH ERROR

Enter number of data bits :

Enter data bits :

Enter number of bits in divisor :

Enter Divisor bits :

Data bits are : 11001

Divisor bits are : 110

Dividend (after appending 0's) are : 1100100

CRC code :

1100110

Enter CRC code of 7 bits :

Error

CRC WITHOUT ERROR

Enter number of data bits :

Enter data bits :

Enter number of bits in divisor :

Enter Divisor bits :

Data bits are : 11001

Divisor bits are : 110

Dividend (after appending 0's) are : 1100100

CRC code :

1100110

Enter CRC code of 7 bits :

No Error

B.Hamming Code (Error Correcting Code)

The techniques that we have discussed so far can detect errors, but do not correct them.

Error Correction can be handled in two ways.

One is when an error is discovered; the receiver can have the sender retransmit the entire data unit. This is known as backward error correction.
In the other, receiver can use an error-correcting code, which automatically corrects certain errors. This is known as forward error correction.

In theory it is possible to correct any number of errors atomically. Error-correcting codes are more sophisticated than error detecting codes and require more redundant bits. The number of bits required to correct multiple-bit or burst error is so high that in most of the cases it is inefficient to do so. For this reason, most error correction is limited to one, two or at the most three-bit errors.

Single-bit error correction

Concept of error-correction can be easily understood by examining the simplest case of single-bit errors. As we have already seen that a single-bit error can be detected by addition of a parity bit (VRC) with the data, which needed to be send. A single additional bit can detect error, but it’s not sufficient enough to correct that error too. For correcting an error one has to know the exact position of error, i.e. exactly which bit is in error (to locate the invalid bits). For example, to correct a single-bit error in an ASCII character, the error correction must determine which one of the seven bits is in error. To this, we have to add some additional redundant bits.

To calculate the numbers of redundant bits (r) required to correct d data bits, let us find out the relationship between the two. So we have (d+r) as the total number of bits, which are to be transmitted; then r must be able to indicate at least d+r+1 different values. Of these, one value means no error, and remaining d+r values indicate error location of error in each of d+r locations. So, d+r+1 states must be distinguishable by r bits, and r bits can indicates 2 r states. Hence, 2 r must be greater than d+r+1.

2 r >= d+r+1

The value of r must be determined by putting in the value of d in the relation. For example, if d is 7, then the smallest value of r that satisfies the above relation is 4. So the total bits, which are to be transmitted is 11 bits (d+r = 7+4 =11).

Now let us examine how we can manipulate these bits to discover which bit is in error. A technique developed by R.W.Hamming provides a practical solution. The solution or coding scheme he developed is commonly known as Hamming Code. Hamming code can be applied to data units of any length and uses the relationship between the data bits and redundant bits as discussed.

Basic approach for error detection by using Hamming code is as follows:

• To each group of m information bits k parity bits are added to form (m+k) bit code as shown above:

• Location of each of the (m+k) digits is assigned a decimal value.

• The k parity bits are placed in positions 1, 2, ..., 2k-1 positions.–K parity checks are performed on selected digits of each codeword.

• At the receiving end the parity bits are recalculated. The decimal value of the k parity bits provides the bit-position in error, if any.

Above figure shows how hamming code is used for correction for 4-bit numbers (d 4 d 3 d 2 d 1 ) with the help of three redundant bits (r 3 r 2 r 1 ). For the example data 1010, first r 1 (0) is calculated considering the parity of the bit positions, 1, 3, 5 and 7. Then the parity bits r 2 is calculated considering bit positions 2, 3, 6 and 7. Finally, the parity bits r 4 is calculated considering bit positions 4, 5, 6 and 7 as shown. If any corruption occurs in any of the transmitted code 1010010, the bit position in error can be found out by calculating r 3 r 2 r 1 at the receiving end. For example, if the received code word is 1110010, the recalculated value of r 3 r 2 r 1 is 110, which indicates that bit position in error is 6, the decimal value of 110.

Example:

Let us consider an example for 5-bit data. Here 4 parity bits are required. Assume that during transmission bit 5 has been changed from 1 to 0 as shown in Fig. 3.2.11. The receiver receives the code word and recalculates the four new parity bits using the same set of bits used by the sender plus the relevant parity (r) bit for each set (as shown in Fig. 3.2.11). Then it assembles the new parity values into a binary number in order of r positions (r8, r4, r2, r1).

Calculations:

Parity recalculated (r8, r4, r2, r1) = 01012 = 510. Hence, bit 5 th is in error i.e. d5 is in error. So, correct code-word which was transmitted is:

Program

//HAMMING CODE

import java.util.*;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.lang.*;

class HammingCode

{

public static void main(String args[])

{

Scanner scr=new Scanner(System.in);

System.out.println("This is hamming code error detection and correction using EVEN parity");

System.out.println();

System.out.println("Enter 4 data bits.D4 D3 D2 D1");

int n=4;

int d[]=new int[4]; //..........Array to accept data bits

for(int i=n-1;i>=0;--i)

{

System.out.println("Enter the value of D"+(i+1));

d[i]=scr.nextInt();

}

/*.............. Formula for calculating 2^k>=n+k+1 ...............*/

int k=0;

while(Math.pow(2,k)<(n+k+1))

{

++k;

}

System.out.println();

System.out.println(k+" parity bits are required for the transmission of data bits.");

int p[]=new int[k]; //..........Array to store parity bits

int h[]=new int[n+k+1];//.........Array to hold the hamming code.(n+k+1) as we start from pos 1.

/********** Initializing array h[] to -1 ************/

for(int i=0;i<7;++i)

h[i]=-1;

int count=0;

int c=2;

while(count<4)

{

++c;

if(c==4)

continue;

h[c]=d[count];

++count;

}

int p1[]={h[1],h[3],h[5],h[7]};

int p2[]={h[2],h[3],h[6],h[7]};

int p3[]={h[4],h[5],h[6],h[7]};

int parity[]=new int[3];

/************Setting the value of parity bit*************/

parity[0]=set_parity_bit(p1);

parity[1]=set_parity_bit(p2);

parity[2]=set_parity_bit(p3);

/************Inserting the parity bits in the hamming code**********/

h[1]=parity[0];

h[2]=parity[1];

h[4]=parity[2];

System.out.println("\nSENDER:");

System.out.print("\nThe data bits entered are: ");

for(int i=3;i>=0;--i)

System.out.print(d[i]+" ");

System.out.println("\nThe Parity bits are: ");

for(int i=2;i>=0;--i)

System.out.println("Value of P"+(i+1)+" is "+parity[i]+" ");

System.out.print("\nThe Hamming code is as follows :-\nD4 D3 D2 P3 D1 P2 P1 \n");

for(int i=(n+k);i>0;--i)

System.out.print(h[i]+" ");

System.out.println();

System.out.println("\nEnter the hamming code with error at any position of your choice.");

for(int i=7;i>0;--i)

h[i]=scr.nextInt();

int p4[]={h[1],h[3],h[5],h[7]};

int p5[]={h[2],h[3],h[6],h[7]};

int p6[]={h[4],h[5],h[6],h[7]};

parity[0]=set_parity_bit(p4);

parity[1]=set_parity_bit(p5);

parity[2]=set_parity_bit(p6);

int position=(int)(parity[2]*Math.pow(2,2)+parity[1]*Math.pow(2,1)+parity[0]*Math.pow(2,0));

System.out.println("\nRECEIVER:");

System.out.println("Error is detected at position "+position+" at the receiving end.");

System.out.println("Correcting the error.... ");

if(h[position]==1)

h[position]=0;

else

h[position]=1;

System.out.print("The correct code is ");

for(int i=7;i>0;--i)

System.out.print(h[i]+" ");

}

static int set_parity_bit(int a[])

{

int count=0;

int l=a.length;

for(int i=0;i<l;++i)

if(a[i]==1)

++count;

if((count%2)==0)

return 0;

else

return 1;

}

OUTPUT

This is hamming code error detection and correction using EVEN parity

Enter 4 data bits.D4 D3 D2 D1

Enter the value of D4

Enter the value of D3

Enter the value of D2

Enter the value of D1

3 parity bits are required for the transmission of data bits.

SENDER:

The data bits entered are: 1 0 1 1

The Parity bits are:

Value of P3 is 0

Value of P2 is 0

Value of P1 is 1

The Hamming code is as follows :-

D4 D3 D2 P3 D1 P2 P1

1 0 1 0 1 0 1

Enter the hamming code with error at any position of your choice.

RECEIVER:

Error is detected at position 4 at the receiving end.

Correcting the error....

The correct code is 1 0 1 0 1 0 1

Search This Blog

Brinda's Blog

Error Detection and Correction Techniques

Comments

Post a Comment

Popular posts from this blog

Study of Differenet Network Types and Different Types of Network Cables and Practically Implement the Cross-Wired cable using Clamping Tool.

Challenges in e-governance