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. Error coding is used for fault tolerant computing in computer memory, magnetic and optical data storage media, satellite and deep space communications, network communications, cellular telephone networks, and almost any other form of digital data communication. Error coding uses mathematical formulas to encode expected, the communication medium's expected error rate, and whether or not data retransmission is possible. Faster processors and better communications technology make more complex coding schemes, With better error detecting and correcting capabilities, possible for smaller embedded systems, allowing for more robust Communications. However, tradeoffs between bandwidth and coding overhead, coding complexity and allowable coding delay between transmissions, must be considered for each application
So, we insert some error detection & correction codes in the transmitted data to check whether the received data is error prone or not & if yes then to correct the received data.
Error detection & correction code are methods of providing reliable digital data transmission and storage when the communication medium used has an unacceptable bit error rate (BER) and a low signal-to-noise ratio (SNR). Error coding is used in many digital applications like computer memory, magnetic and optical data storage media, satellite and deep space.
This project is to address the full spectrum of the use and implementation of Error detection & correcting codes using C programming. The project presents each module in detail. To introduce the more formal aspects of programming the presentation slides have been designed which give the overview of this mini project.
The Project deals with various features of error detection & correction methods such as transmitted data stream, detections & correction codes, received stream, error detection & correction etc. This Project takes transmitted data stream as input from user, calculate the codes to be transmitted along data to introduce error detection & correction , selects a random received data stream with one or no error , at last checks whether the data is correct or not & also correct it , if necessary.
Requirements for the project:-
Operating system used: Windows 98/2000/NT/XP Software used: Turbo C++
Salient features of the project:-
Standard C++ library files
User friendly approach
HISTORY
The history of coding theory is inextricably bound to the development of transmission technology. For instance, the telegraph required an encoding scheme to transform English words into dots and dashes (the reason for Morse code). However, until around the 1940's, error detection (rather than correction) was sought after. Only with the advent of digital computing technology did the decoding of error-correcting codes become practical.
Error-correcting codes were first discovered abstractly in 1945 when Claude Shannon proved a theorem (described later) which states that, even with a noisy channel, there exist ways to encode messages in such a way that they have an arbitrarily good chance of being transmitted safely, provided that one does not exceed the "capacity" of the channel by trying to transmit too much information too quickly.
INPUT & OUTPUT SPECIFICATION
error detection and correction-encoding scheme is used on networks to account for single bit transmission errors. This Shockwave program successfully reverse-engineers the encoding scheme, to be able to do the following:
Accept binary input
Find the error detection or correction Code
Display transmitted stream
Assume a received data stream with one or no error
Detect or Correct the error as asked
Display the final result
DIAGRAM
CODING
// PROGRAM TO RUN ERROR DETECTION & CORRECTION METHODS
// A LIST HEADER FILES USED
#include
#include
#include
#include
// MACRO DEFINTIONS
# define limit 100
// GLOBAL DATA DECLARATION
long m,r;
int is[limit],h[limit],rb[limit],eb[limit],hc[limit],bin[limit], os[limit], ss[limit],cs[8];
//############################################################
// START OF HAMMING CODE
//############################################################
// FUNCTION TO FIND THE BINARY EQUIVALENT OF ANY DECIMAL NUMBER
void binary(long x,int n)
{
int rim,y;
long div=x;
while(div!=0)
{
rim=(int)div%2;
bin[n--]=rim;
div=div/2;
}
if(n>=0)
{
for(y=n;y>0;y--)
bin[y]=0;
}
}
// END OF FUNCTION
//############################################################
//FUNCTION TO FIND THE DECIMAL EQUIVALENT OF ANY BINARY NUMBER
int decimal(int *t,int l)
{
int s=0,i,j;
for(i=0,j=l;j>0;i++,j--)
{
s+=t[j]*pow(2,i);
}
return s;
}
// END OF FUNCTION
//############################################################
// FUNCTION TO CALCULATE THE NUMBER OF REDUNDENCY BITS REQUIRED
void count_r()
{
while(pow(2,r)<(m+r+1))
{
r++;
}
printf("\n No. of redundent bits are ====>> %d ",r);
}
// END OF FUNCTION
//############################################################
// FUNCTION TO CALCULATE THE VALUE OF REDUNDANCY BITS
void red_b()
{
int i,j;
for(j=r;j>0;j--)
{
int sum=0;
for(i=1;i<(m+r+1);i++)
{
binary(i,r);
if(bin[j]==1)
sum=sum+h[i];
}
rb[r-j+1]=sum%2;
}
}
// END OF FUNCTION
//############################################################
// FUNCTION TO ARRANGE THE DATA BITS IN THE HAMMING CODE
void code()
{
int i,j,t;
for(t=1,j=1;t<(m+r+1);t++,j++)
{
for(i=0;i
{
if(pow(2,i)==t)
{
h[t++]=0;
}
}
h[t]=is[j];
}
}
//END OF FUNCTION
//############################################################
// FUNCTION TO ARRANGE THE REDUNDANCY BITS IN THE HAMMING CODE
void h_code()
{
int i,t;
red_b();
printf("\n\n\n\n\n hamming code is====>>");
for(t=1;t<(m+r+1);t++)
{
for(i=0;i
{
if(pow(2,i)==t)
{
hc[t++]=rb[i+1];
}
}
hc[t]=h[t];
}
for(i=1;i<(r+m+1);i++)
printf("%d",hc[i]);
}
// END OF PROGRAM
//############################################################
//FUNCTION TO FIND THE POSITION OF ERROR OCCURANCE
void err_b()
{
int i,j;
for(j=1;j<=r;j++)
{
int sum=0;
for(i=1;i<(m+r+1);i++)
{
binary(i,r);
if(bin[j]==1)
sum=sum+os[i];
}
eb[j]=sum%2;
}
}
// END OF FUNCTION
//############################################################
// FUNCTION TO GUESS THE RECIEVED STREAM
void r_s(int *a,int x)
{
int d=0,t,j;
randomize();
printf("\n The recieved stream is ====>>");
for(j=1;j<=x;)
{
t=rand()%2;
if(t==a[j]||d==0)
{
os[j]=t;
printf("%d",os[j]);
if(t!=a[j])
d++;
j++;
}
}
}
// END OF FUNCTION
//############################################################
// FUNCTION TO FIND HAMMING CODE
void h_c()
{
int c,f,i,s,t;
clrscr();
do
{
printf("\n<<************************** HAMMING CODE METHOD **************************>>");
printf("\n_______________________________________________________________________________\n");
printf("\n\t\t 1. ENTER DATA STREAM");
printf("\n\t\t 2. VIEW DATA STREAM");
printf("\n\t\t 3. FIND HAMMING CODE");
printf("\n\t\t 4. GUESS RECIEVED STREAM");
printf("\n\t\t 5. FIND THE ERROR");
printf("\n\t\t 6. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: printf("\n Enter the no. of bits in the message ((less than %d))====>> ",limit);
scanf("%d",&m);
count_r();
printf("\n Enter the message bit stream ((only in form of 0's and 1's))====>> ");
fflush(stdin);
for(i=1;i<=m;i++)
scanf("%d",&is[i]);
break;
case 2: printf("\n Bit stream is ====>> ");
fflush(stdin);
for(i=1;i<=m;i++)
printf("%d",is[i]);
break;
case 3: code();
h_code();
break;
case 4: r_s(hc,m+r);
break;
case 5: err_b();
printf("\n The error is at the position ====>>");
s=decimal(eb,r);
printf("\t %d ",s);
printf("\n The correct data stream transferred is ====>>");
for(i=1;i<(m+r+1);i++)
{
if(i==s)
{
if(os[i]==0)
os[i]=1;
else
os[i]=0;
}
}
for(t=1;t<(m+r+1);t++)
{
f=0;
for(i=0;i
{
if(pow(2,i)==t)
{
f++;
}
}
if(f==0)
{
printf("%d",os[t]);
}
}
break;
case 6: break;
default:printf("\n Wrong choice");
}
}while(c!=6);
clrscr();
}
//END OF FUNCTION
// END OF HAMMING CODE METHOD
//############################################################
//START OF PARITY BIT METHOD
void p_b()
{
int c,l,i,sum=0;
clrscr();
do
{
printf("\n<<**************************** PARITY BIT METHOD ****************************>>");
printf("\n_______________________________________________________________________________\n");
printf("\n\t\t 1. ENTER DATA STREAM");
printf("\n\t\t 2. VIEW DATA STREAM");
printf("\n\t\t 3. FINDING SENDING STREAM");
printf("\n\t\t 4. GUESS RECIEVED STREAM");
printf("\n\t\t 5. FIND THE ERROR");
printf("\n\t\t 6. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: printf("\n Enter the no. of data bits to be transmitted====>>");
scanf("%d",&l);
printf("\n Enter the message bit stream ((only in form of 0's and 1's))====>> ");
for(i=1;i<=l;i++)
scanf("%d",&is[i]);
break;
case 2: printf("\n Bit stream is ====>> ");
for(i=1;i<=l;i++)
printf("%d",is[i]);
break;
case 3: sum=0;
for(i=1;i<=l;i++)
{
sum=sum+is[i];
}
is[l+1]=sum%2;
printf("\n The sending data stream is====>>");
for(i=1;i<=(l+1);i++)
{
printf("%d",is[i]);
}
break;
case 4: r_s(is,l+1);
break;
case 5: for(i=1;i<=(l+1);i++)
{
if(is[i]==os[i])
continue;
else
{
printf("\n The recieved stream consists of an error.");
break;
}
}
if(i==(l+2))
printf("\n The recieved stream is without any error.");
break;
case 6: break;
default: printf("\n Wrong Choice");
}
}while(c!=6);
clrscr();
}
// END OF PARITY BIT METHOD
//############################################################
// START OF CYCLIC REDUNDANCY CHECK METHOD
void fu(int *as,int *t,int l)
{
int i,j,bs[5],ds[]={0,1,0,1,1};
for(i=1;i<=l;i++)
{
fflush(stdin);
if(as[1]==1)
{
for(j=4;j>0;j--)
{
fflush(stdin);
if(as[j]==ds[j])
{
bs[j-1]=0;
}
else
bs[j-1]=1;
}
for(j=1;j<=4;j++)
{
fflush(stdin);
if(j==4)
{
as[j]=t[i+4];
}
else
as[j]=bs[j];
}
}
else
{
for(j=1;j<=4;j++)
{
if(j==4)
bs[j]=t[i+4];
else
bs[j]=as[j+1];
}
for(j=1;j<=4;j++)
{
as[j]=bs[j];
}
}
}
for(i=1;i<4;i++)
{
cs[i]=as[i];
}
}
void b_divison(int *t,int l)
{
int i,j,as[5];
for(i=1;i<=4;i++)
{
as[i]=t[i];
}
fu(as,t,l);
}
//###########################################################################
void c_r_c()
{
int c,l,i,j,sum,f=0;
int *p;
clrscr();
do
{
printf("\n<<**************************** CHECKSUM METHOD ****************************>>");
printf("\n_______________________________________________________________________________\n");
printf("\n\t\t 1. ENTER DATA STREAM");
printf("\n\t\t 2. VIEW DATA STREAM");
printf("\n\t\t 3. FIND SENDING STREAM");
printf("\n\t\t 4. GUESS RECIEVED STREAM");
printf("\n\t\t 5. FIND THE ERROR");
printf("\n\t\t 6. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: printf("\n Enter the no. of data bits to be transmitted ((multiple of 8))====>> ");
scanf("%d",&l);
printf("\n Enter the message bit stream ((only in form of 0's and 1's))====>> ");
for(i=1;i<=l;i++)
scanf("%d",&is[i]);
break;
case 2: printf("\n Bit stream is ====>> ");
for(i=1;i<=l;i++)
printf("%d",is[i]);
break;
case 3: for(i=l+1;i<=l+3;i++)
is[i]=0;
b_divison(is,l);
printf("\n The sending stream is ====>>");
j=1;
for(i=1;i<=(l+3);)
{
while(i<=l)
{
ss[i]=is[i];
i++;
}
if(i>l)
{
ss[i++]=cs[j++];
}
}
for(i=1;i<=(l+3);i++)
{
printf("%d",ss[i]);
}
break;
case 4: r_s(ss,l+3);
break;
case 5: b_divison(os,l);
for(i=1;i<4;i++)
{
if(cs[i]==1)
f++;
}
if(f==0)
{
printf("\n The recieved stream is without an error.");
}
else
printf("\n The recieved stream consist of an error.");
break;
case 6: break;
default: printf("\n Wrong Choice");
}
}while(c!=6);
clrscr();
}
// END OF CYCLIC REDUNDANCY CHECK METHOD
//############################################################
// START OF CHECKSUM METHOD
//############################################################
// FUNCTION TO CALCULATE THE CHECKSUM
void binarysum(int *it,int l)
{
int i,j,k=1,sum,t[8],s[20];
for(i=1;i<=l;)
{
j=1;
while(j<=8)
{
t[j++]=it[i++];
}
s[k++]=decimal(t,8);
}
k--;
sum=0;
for(i=1;i<=k;i++)
sum=sum+s[i];
binary(sum,8+k);
j=1;
for(i=k+1;i<=(8+k);)
{
cs[j++]=bin[i++];
}
for(i=1;i<=8;i++)
{
if(cs[i]==1)
cs[i]=0;
else
cs[i]=1;
}
printf("\n Checksum is ===>>");
for(i=1;i<=8;i++)
{
printf("%d",cs[i]);
}
}
// END OF FUNCTION
//############################################################
// FUNCTION FOR CHECKSUM METHOD
void c_s()
{
int c,l,i,j,sum,f=0;
clrscr();
do
{
printf("\n<<**************************** CHECKSUM METHOD ****************************>>");
printf("\n_______________________________________________________________________________\n");
printf("\n\t\t 1. ENTER DATA STREAM");
printf("\n\t\t 2. VIEW DATA STREAM");
printf("\n\t\t 3. FIND SENDING STREAM");
printf("\n\t\t 4. GUESS RECIEVED STREAM");
printf("\n\t\t 5. FIND THE ERROR");
printf("\n\t\t 6. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: printf("\n Enter the no. of data bits to be transmitted ((multiple of 8))====>> ");
scanf("%d",&l);
printf("\n Enter the message bit stream ((only in form of 0's and 1's))====>> ");
for(i=1;i<=l;i++)
scanf("%d",&is[i]);
break;
case 2: printf("\n Bit stream is ====>> ");
for(i=1;i<=l;i++)
printf("%d",is[i]);
break;
case 3: binarysum(is,l);
printf("\n The sending stream is ====>>");
j=1;
for(i=1;i<=(l+8);)
{
while(i<=l)
{
ss[i]=is[i];
i++;
}
if(i>l)
{
ss[i++]=cs[j++];
}
}
for(i=1;i<=(l+8);i++)
{
printf("%d",ss[i]);
}
break;
case 4: r_s(ss,l+8);
break;
case 5: binarysum(os,l+8);
for(i=1;i<8;i++)
{
if(cs[i]==1)
f++;
}
if(f==0)
{
printf("\n The recieved stream is without an error.");
}
else
printf("\n The recieved stream consist of an error.");
break;
case 6: break;
default: printf("\n Wrong Choice");
}
}while(c!=6);
clrscr();
}
// END OF FUNCTION
// END OF CHECKSUM METHOD
//############################################################
// START OF ERROR CORRECTION METHODS
void e_c_m()
{
int c;
clrscr();
do
{
printf("\n<<************************ ERROR CORRECTION METHODS ************************>>");
printf("\n________________________________________________________________________________\n");
printf("\n\t\t 1. HAMMING CODE METHOD");
printf("\n\t\t 2. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: h_c();
break;
case 2: break;
default: printf("\n Wrong Choice");
}
}while(c!=2);
clrscr();
}
// END OF ERROR CORRECTION METHODS
//############################################################
// START OF ERROR DETECTION METHODS
void e_d_m()
{
int c;
clrscr();
do
{
printf("\n<<************************ ERROR DETECTION METHODS ************************>>");
printf("\n________________________________________________\n");
printf("\n\t\t 1. PARITY BIT METHOD");
printf("\n\t\t 2. CHECK SUM METHOD");
printf("\n\t\t 3. CYCLIC REDUNDANCY CHECK METHOD");
printf("\n\t\t 4. HAMMING CODE METHOD");
printf("\n\t\t 5. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: p_b();
break;
case 2: c_s();
break;
case 3: c_r_c();
break;
case 4: h_c();
break;
case 5: break;
default: printf("\n Wrong Choice");
}
}while(c!=5);
clrscr();
}
// END OF ERROR DETECTION METHODS
//############################################################
// START OF MAIN FUNCTION
void main()
{
int c;
clrscr();
do
{
printf("\n <<****************** ERROR DETECTION & CORRECTION METHODS ******************>>");
printf("\n________________________________________________\n");
printf("\n\t\t 1. ERROR DETECTION METHOD");
printf("\n\t\t 2. ERROR CORRECTION METHODS");
printf("\n\t\t 3. EXIT");
printf("\n\t\t Enter Choice");
scanf("%d",&c);
switch(c)
{
case 1: e_d_m();
break;
case 2: e_c_m();
break;
case 3: break;
default: printf("\n Wrong Choice");
}
}while(c!=3);
getch();
}
//END OF PROGRAM
OUTPUT
CONCLUSION
Error detection & correction methods are product with easy look and feel to manage errors generated during transmission of data from one electronic device to another. This system provides various features such as detection of error , request to send the data again or correction of data.
This project is just a demo of actual working system where the data is actually transmitted and & handled. So it requires further enhancements which are now its limitations.
GLOSSARY
BIT:-
Binary digit. The smallest unit of data (0,1).
BINARY VALUE:-
Binary value of a character or alphabet is the value containing 0,1 i.e in bit form.
CHECKSUM:-
The value used for error detection. It is formed by adding data units using one’s complement arithmetic & then complementing the result.
CYCLIC REDUNDANCY CHECK:-
A highly accurate error- detection method based on interpreting a pattern of bits as a polynomial.
HAMMING CODE:-
A method that adds redundant bits to a data unit to detect & correct bit error.
PARITY CHECK:-
An error detection method using a parity bit.
REDUNDANCY:-
The addition of bits to a message for error control.
BIBLIOGRAPHY
While working on our project including the help of our guide I referred some books and sum Internet sites. Thus listing all the books here:
Data communication and networking by Behrouza A Forouzan.
Modern Digital Electronics (Edition 3) by R.P Jain
Let us C by Yashwant Kanetkar
Fundamentals of C Programming by V.Rajaram.
sites referred
http://www.sims.berkeley.edu/~rosario/error_correcting.html
http://guest.engelschall.com/~sb/hamming/
http://dict.die.net/error%20detection%20and%20correction/
http://www.mdstud.chalmers.se/~md7sharo/coding/main/node2.html
No comments:
Post a Comment