CRC algorithm
WAP in C/C++ to
implement CRC algorithm.
METHOD-:
THEORY & CONCEPT-:
A CRC
is an error-detecting code. Its computation
resembles a long division operation in which the quotient is
discarded and the remainder becomes the result, with the important distinction
that the arithmetic used is the carry-less arithmetic of a finite
field. The length of the remainder is always less than or equal to the
length of the divisor, which therefore determines how long the result can be.
The definition of a particular CRC specifies the divisor to be used, among
other things.
Although CRCs can be
constructed using any finite field, all commonly used CRCs employ the finite
field GF(2),
the field of two elements, usually called 0 and 1, comfortably matching
computer architecture. The rest of this article will discuss only these binary
CRCs, but the principles are more general.
An important reason for the
popularity of CRCs for detecting the accidental alteration of data is their
efficiency guarantee. Typically, an n-bit CRC, applied to a data block of
arbitrary length, will detect any single error burst
not longer than n bits (in other words, any single alteration that spans no
more than n bits of the data), and will detect a fraction 1-2-n of
all longer error bursts. Errors in both data transmission channels and magnetic
storage media tend to be distributed non-randomly (i.e. are
"bursty"), making CRCs' properties more useful than alternative
schemes such as multiple parity checks.
The simplest error-detection
system, the parity
bit, is in fact a trivial CRC: it uses the two-bit-long divisor 11.
CRCs are not, by themselves,
suitable for protecting against intentional alteration of data (for example, in
authentication applications for data security), because their convenient
mathematical properties make it easy to compute the CRC adjustment required to
match any given change to the data.
METHOD-:
The mechanics of computing an
n-bit binary CRC are simple. The bits representing the input are lined up in a
row, and the (n+1)-bit pattern representing the CRC's divisor (called a
"polynomial") is positioned underneath the left-hand end of the row.
Here is the first calculation for computing a 3-bit CRC:
11010011101100 <--- Input
1011 <--- divisor (4 Bits)
--------------
01100011101100 <--- result
If the input bit above the leftmost divisor bit is 0, do nothing and move
the divisor to the right by one bit. If the input bit above the leftmost
divisor bit is 1, the divisor is exclusive-ORed
into the input (in other words, the input bit above each 1-bit in the divisor
is toggled). 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 last calculation:
00000000001110 <--- result of multiplication calculation
1011 <--- divisor
--------------
00000000000101 <--- remainder (3 bits)
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).
IMPLEMENTATION IN C -:
#include<conio.h>
#include<stdio.h>
#include<process.h>
void main()
{
int msg[20],crc[20],n,i,j,p,a,rem[10],quo[10];
clrscr();
printf("Enter Mesage size");
scanf("%d",&n);
printf("Enter message in Binary");
for(i=0;i<n;i++)
{
scanf("%d",&msg[i]);
}
printf("Enter CRC Gen. size");
scanf("%d",&p);
printf("Enter crc bits in Binary");
for(i=0;i<p;i++)
{
scanf("%d",&crc[i]);
}
a=p-1;
for(i=0;i<a;i++)
{
msg[n+i]=0;
}
printf("The Code To be Sent is - ");
for(i=0;i<(n+a);i++)
{
printf("%d",msg[i]);
}
for(i=0;i<p;i++)
{
if (msg[i]==1 && crc[i]==1)
{
rem[i]=0;
}
if( msg[i]==1 && crc[i]==0)
{ rem[i]=1;
}
if(msg[i]==0 && crc[i]==1)
{
rem[i]=1;
}
if( msg[i]==1 && crc[i]==0)
{
rem[i]=0;
}
i=0;
if(rem[i]==0 && rem[i+1]== 0 && rem[i+2]==1)
{
rem[i+4]=msg[i+4];
rem[i+5]=msg[i+5];
if(crc[i]==0)
{
rem[i]=0;
}
if(crc[i]==1)
{
rem[i]=1;
}
if((rem[i+3]==1) && (crc[i+1]==0))
{
rem[i+1]=1;
}
if(rem[i+3]==1 && crc[i+1]==1)
{
rem[i+1]=0;
}
if(rem[i+3]==0 && crc[i+1]==1)
{
rem[i+1]=1;
}
if(rem[i+3]==0 && crc[i+1]==0)
{
rem[i+1]=0;
}
if(rem[i+4]==1 && crc[i+2]==0)
{
rem[i+2]=0;
}
if(rem[i+4]==1 && crc[i+2]==1)
{
rem[i+2]=0;
}
if(rem[i+4]==0 && crc[i+2]==0)
{
rem[i+2]=0;
}
if(rem[i+5]==0 && crc[i+3]==0)
{
rem[i+3]=1;
}
if(rem[i+5]==1 && crc[i+3]==1)
{
rem[i+3]=0;
}
if(rem[i+5]==0 && crc[i+3]==1)
{
rem[i+2]=1;
}
if(rem[i+5]==1 && crc[i+3]==0)
{
rem[i+3]=0;
}
if(rem[i]==0 && rem[i+1]==0 && rem[i+2]==0 &&
rem[i+3]==0)
{
if(crc[i]==0)
{
rem[i]=0;
}
if(crc[i]==1)
{
rem[i]=1;
}
if(crc[i+1]==0)
{
rem[i+1]=0;
}
if(crc[i+1]==1)
{
rem[i+1]=1;
}
if(crc[i+2]==0)
{
rem[i+2]=0;
}
if(crc[i+2]==1)
{
rem[i+2]=1;}
if(crc[i+3]==1)
{
rem[i+3]=0;
}
}
printf("The code to be sent is
" );
for(j=0;j<n;j++)
{
printf("%d", msg[j]);
for(i=0;i<n;i++)
{
printf("%d",rem[i]);
}
}}}
getch();
}
0 comments