C program to implement Cyclic Redundancy Check CRC

# C program to implement Cyclic Redundancy Check CRC

87459
10
SHARE

C program to implement Cyclic Redundancy Check 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 corrective action can be taken against presumed data corruption if the check values do not match.

How to Compute CRC Cyclic Redundancy Check ?

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.

`11010011101100`

This is first padded with zeroes 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```

If the input bit above the leftmost divisor bit is 0, do nothing. If the input bit above the leftmost divisor bit is 1, the divisor is XORed 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 entire calculation:

```11010011101100 000 <--- input right padded by 3 bits
1011               <--- divisor
01100011101100 000 <--- result
1011              <--- divisor ...
00111011101100 000
1011
00010111101100 000
1011
00000001101100 000
1011
00000000110100 000
1011
00000000011000 000
1011
00000000001110 000
1011
00000000000101 000
101 1
-----------------
00000000000000 100 <---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).

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
101 1
------------------
0 <--- remainder```

Let see how to write a CRC.

# C program to implement Cyclic Redundancy Check CRC :

```#include<stdio.h>
#include<string.h>
#define N strlen(g)

char t[28],cs[28],g[]="10001000000100001";
int a,e,c;

void xor(){
for(c = 1;c < N; c++)
cs[c] = (( cs[c] == g[c])?'0':'1');
}

void crc(){
for(e=0;e<N;e++)
cs[e]=t[e];
do{
if(cs[0]=='1')
xor();
for(c=0;c<N-1;c++)
cs[c]=cs[c+1];
cs[c]=t[e++];
}while(e<=a+N-1);
}

int main()
{
printf("\nEnter data : ");
scanf("%s",t);
printf("\n----------------------------------------");
printf("\nGeneratng polynomial : %s",g);
a=strlen(t);
for(e=a;e<a+N-1;e++)
t[e]='0';
printf("\n----------------------------------------");
printf("\nModified data is : %s",t);
printf("\n----------------------------------------");
crc();
printf("\nChecksum is : %s",cs);
for(e=a;e<a+N-1;e++)
t[e]=cs[e-a];
printf("\n----------------------------------------");
printf("\nFinal codeword is : %s",t);
printf("\n----------------------------------------");
printf("\nTest error detection 0(yes) 1(no)? : ");
scanf("%d",&e);
if(e==0)
{
do{
printf("\nEnter the position where error is to be inserted : ");
scanf("%d",&e);
}while(e==0 || e>a+N-1);
t[e-1]=(t[e-1]=='0')?'1':'0';
printf("\n----------------------------------------");
printf("\nErroneous data : %s\n",t);
}
crc();
for(e=0;(e<N-1) && (cs[e]!='1');e++);
if(e<N-1)
printf("\nError detected\n\n");
else
printf("\nNo error detected\n\n");
printf("\n----------------------------------------\n");
return 0;
}```

Sample Output:

Enter data : 1101

—————————————-
Generatng polynomial : 10001000000100001
—————————————-
Modified data is : 11010000000000000000
—————————————-
Checksum is : 1101000110101101
—————————————-
Final codeword is : 11011101000110101101
—————————————-
Test error detection 0(yes) 1(no)? : 0

Enter the position where error is to be inserted : 2

—————————————-
Erroneous data : 10011101000110101101

Error detected

We hope you all have enjoyed the of Cyclic Redundancy check CRC. If you have any doubts ask us in form of comments.

SHARE
Well, I am software programmer and love to code. My hobbies is to do Hacking, Coding, Blogging, Web Designing and playing online games. Feel free to contact me at shiviskingg@gmail.com or lokesh@hackingloops.com