Menu

Aim: write a c-program for implement the Cyclic Redundancy Check(CRC).

Cyclic redundancy check (CRC):

Error:

A condition when the receiver’s information does not matches with the sender’sinformation. During transmission, digital signals suffer from noise that can introduce errors in the binary bits travelling from sender to receiver. That means a 0 bit may change to 1 or a 1 bit may change to 0.

Error Detecting Codes (Implemented either at Data link layer or Transport Layer of OSI Model):

Whenever a message is transmitted, it may get scrambled by noise or data may get corrupted. To avoid this, we use error-detecting codes which are additional data added to a given digital message to help us detect if any error has occurred during transmission of the message.

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

Cyclic redundancy check (CRC)

  • Unlike checksum scheme, which is based on addition, CRC is based on binary
  • 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
  • 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
  • A remainder indicates that the data unit has been damaged in transit and therefore must be

Cyclic redundancy check (CRC

EXAMPLE

ALGORITHM FOR CRC

BEGIN

step 1: declare i,j,keylen,mesglen and char arrays input[100],temp[30],quot[100],rem[30],key[30],key1[30];

step 2: enter the data and scan the data into input[]

step 3: enter the key and scan the data into key[]

step 4: save the length of input in msglen and length of key in keylen

step 5: copy key[] to key1[]

step 6: initialize i=0 and repeat step 7 until i<keylen-1

step 7: input[msglen+i]=0 and inc i

step 8: initialize i=0 and repeat step 9 until i<keylen

step 9: temp[i]=input[i] and inc i

step 10: initialize i=0 and repeat step 11-22 until i<msglen

step 11: quot[i]=temp[0] and inc i

step 12: if quot[i] equal to 0 then goto step 13 else step 15

step 13: initialize j=0 and repeat step 14 until j<keylen and goto step 17

step 14: key[j]=0 and inc j

step 15: initialize j=0 and repeat step 16 until j<keylen step 16: key[j]=key1[j] and inc j

step 17: initialize j=keylen-1 and repeat step 18-20 until j>0

step 18: if temp[j] equal to key[j] goto step 19 else step 20

step 19: rem[j-1]=’0′ and dec j and goto step 21

step 20: rem[j-1]=’1′ and dec j

step 21: rem[keylen-1]=input[i+keylen] step 22: copy rem to temp[]

step 23: copy temp[] to rem[]

step 24: print the final data from input[] and rem[]

step 25: enter the frame and save in input

step 26: initialize j=0 and repeat step 27 until j<=msglen and then k=0

step 27: rem[j]=input[j] and inc j

step 28: initialize i=msglen and repeat step 29 until i<=keylen

step 29: if i>msglen then initialize j=0 and repeat step 30 until j<msglen

step 30: rem[j]=rem[j+1] and rem[j]=input[j] and inc j

step 31: if rem[0] then quot[k++]=1 else quot[k++]=0

step 32: initialize j=0 and repeat step 32 until j<=msglen

step 33: rem[j]=rem[j]^input[j]

step 34: print quotient and reminder

step 35: initialize i=1 repeat step 36 until i<=msglen

step 36: if rem[i] then flag=0

step 37: if flag is positive print “no error” else print “error”

END
Program:

 

#include<stdio.h>

#include<stdlib.h>

int main()

{

int i,j,k=0;

int flag=1,a[16],g[16],r[20],div[16],n,m;

system(“clear”);

printf(“Enter degree of generator:”);

scanf(“%d”,&n);

printf(“\n Enter the generator:\n”); 

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

scanf(“%d”,&g[i]);

printf(“\nEnter the degree of the frame:”); 

scanf(“%d”,&m);

printf(“Enter the frame:\n”); 

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

scanf(“%d”,&a[i]);

if(m<n || g[0]==0)

{

printf(“Not a proper generator:\n”);

exit(0);

}

for(i=m+1;i<=m+n;i++) a[i]=0;

for(j=0;j<=n;j++) r[j]=a[j];

 for(i=n;i<=m+n;i++)

{

if(i>n)

{

for(j=0;j<n;j++) r[j]=r[j+1];

r[j]=a[i];

}

if(r[0]) div[k++]=1; else

{

div[k++]=0; continue;

}

for(j=0;j<=n;j++) r[j]=r[j]^g[j];

}

printf(“\n Quotient is:”); 

for(j=0;j<k;j++) 

printf(“%d”,div[j]); 

printf(“\n Remainder is:”); 

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

 printf(“%d”,r[i]);

printf(“\n Transmitted frame is:”);

for(i=m+1,j=1;i<=m+n;i++) 

printf(“%d”,a[i]);

printf(“\n”);

printf(“\n Enter the degree of     

frame:”); 

scanf(“%d”,&m);

printf(“Enter the frame:\n”); 

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

scanf(“%d”,&a[i]);

for(j=0;j<=n;j++) r[j]=a[j];

k=0;

for(i=n;i<=m;i++)

{

if(i>n)

{

for(j=0;j<n;j++) r[j]=r[j+1];

r[j]=a[i];

}

if(r[0]) div[k++]=1; else

{

div[k++]=0; continue;

}

for(j=0;j<=n;j++) r[j]=r[j]^g[j];

}

printf(“\n Quotient is:”);

 for(j=0;j<k;j++)

 printf(“%d”,div[j]);

 printf(“\n Remainder is:”);

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

 printf(“%d”,r[i]);

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

{

if(r[i]) flag=0;

}

if(flag)

printf(“\n No Error \n”);

 else

printf(“\n Error”); return 0;

}

Output:

Enter the degree of the generator: 3 

Enter the generator: 1 0 0 1

Enter the degree of the frame: 7

Enter the frame :

1

1

1

1

1

1

1

1

Quotient is : 11100011 

Remainder is: 011

Transmitted frame is: 11111111011

Enter the degree of the frame:10 

Enter the frame:

1

1

1

1

1

1

1

1

0

1

1

Quotient is: 11100011 

Remainder is:000

No Error