Cyclic Redundancy Check

=> A Generator is shared between the Sender and the Receiver.  
=> Sender will convert Dataword into Codeword using the Generator and send it 
 to the Receiver.  
=> Receiver upon receiving the Codeword, will check for errors in the received 
 Codeword with the help of the Generator. 
=> If no error is found, receiver can extract Dataword from the Codeword.  
 
Sender Side:

 Generator/Divisor: 1100000001011 (Total 13-bits)  
 Dataword: 10101 (5-bits)  
 Extended Dataword: 10101000000000000 (17-bits: Dataword + 12 0's)  
 
1100000001011 ) 10101000000000000 ( 11001  
                1100000001011  
                _____________  
                x1101000010110  
                 1100000001011  
                 _____________  
                 x0010000111010  
                  0000000000000  
                  _____________  
                  x0100001110100  
                   0000000000000  
                   _____________  
                   x1000011101000  
                    1100000001011  
                    _____________  
                    x100011100011  
 
=> So, CRC Bits are: 100011100011  
=> Now Codeword is 10101100001110100 (17-bits: Dataword + CRC bits)  
=> Sender will send this Codeword to the Receiver.  

 Receiver Side:  

 Codeword: 10101100011100011  
 Generator/Divisor: 1100000001011 
 
  1100000001011)   10101100011100011 ( 11001  
                  1100000001011  
                  _____________  
                  x1101100001010  
                   1100000001011  
                   _____________  
                   x0011000000010  
                    0000000000000  
                    _____________  
                    x0110000000101  
                     0000000000000  
                     _____________  
                     x1100000001011  
                      1100000001011  
                      _____________  
                      0000000000000  
 
 => Reached Codeword contain no errors and now extract Dataword from Codeword  
 => Dataword is 10101 [[by removing (Generator_Size - 1) bits from Codeword from Right]]  

 // PROGRAM FOR CYCLIC REDUNDANCY CHECK  
 #include<stdio.h>  
 int main()  
 {  
   int ds, dws, i, j, k, c=0; // ds-DivisorSize: dws-DataWordSize:  
   int div[100], dw[100], ta[100]; // div-Divisor: dw-DataWord: ta-TemporaryArray  
   //TAKING INPUT - DIVISOR  
   printf("Enter the size of divisor: ");  
   scanf("%d", &ds);  
   printf("Enter the divisor in bit pattern: ");  
   for(i=0; i<ds ; i++)  
     scanf("%d", &div[i]);  
   //TAKING INPUT - DATAWORD  
   printf("Enter the size of the DataWord: ");  
   scanf("%d",&dws);  
   printf("Enter the DATAWORD in bit pattern: ");  
   for(i=0; i<dws; i++)  
     scanf("%d",&dw[i]);  
   //ADDING ZEROS TO THE DATAWORD i.e., WE GOT EXTENDED DATAWORD HERE  
   for(i=dws; i<(dws+ds-1); i++)  
     dw[i] = 0;  
   //PRINTING THE EXTENDED DATAWORD  
   printf("Data after inserting zeros or <EXTENDED DATAWORD> : ");  
   for(i=0; i<(dws+ds-1); i++)  
     printf("%d", dw[i]);  
   //COPYING DATAWORD INTO TEMPORARY ARRAY  
   for(i=0; i<(dws+ds-1); i++)  
     ta[i] = dw[i];  
   //GENERATING THE REDUNDANT BITS  
   for(i=0; i!= dws; i++)  
   {  
     if(ta[i]==1)  
       for(j=0, k=i; j<ds; j++, k++)  
          ta[k] = ta[k]^div[j];   
   }  
   //ADDING REDUNDANT BITS TO THE DATAWORD  
   for(i=dws; i<(dws+ds-1); i++)  
     dw[i] = ta[i];  
   //PRINTING THE CODEWORD  
   printf("\n\nThe Generated CODEWORD is: ");  
   for(i=0; i<(dws+ds-1); i++)  
     printf("%d", dw[i]);  
   //COPYING CODEWORD INTO TEMPORARY ARRAY  
   for(i=0; i<(dws+ds-1); i++)  
     ta[i] = dw[i];  
   //DIVIDING CODEWORD WITH DIVISOR AT RECEIVERS END  
   for(i=0; i!= dws; i++)  
   {  
     if(ta[i]==1)  
       for(j=0, k=i; j<ds; j++, k++)  
         ta[k] = ta[k]^div[j];   
   }  
   printf("\nThe Remainder @ receiver's End is: ");  
   for(i=dws; i<(dws+ds-1); i++)  
       printf("%d",ta[i]);  
 //CHECKING IF THERE ARE ANY 1s IN THE REMAINDER  
   for(i=dws; i<(dws+ds-1); i++)  
   {  
     if(ta[i]!=0)  
       c++;  
   }  
   if(c==0)  
     printf("\nThe Codeword hasn't been altered::Message sent SUCCESSFULLY :)");  
   else  
     printf("\nThe Codeword has been altered :(");  
   return 0; 
 }  
 /* EXAMPLE OUTPUT  
 Enter the size of divisor: 4  
 Enter the divisor in bit pattern: 1 0 1 1  
 Enter the size of the DataWord: 5  
 Enter the DataWord in bit pattern: 1 0 1 1 1  
 Data after inserting zeros or <EXTENDED DATAWORD> : 10111000  
 The Generated CODEWORD is: 10111011  
 The Remainder @ receiver's End is: 000  
 The Codeword hasn't been altered::Message sent SUCCESSFULLY :)  
 */