Apr 18 2014
CRC Implementation in C
CRC Implementation in C with efficient algorithm. CRC Implementation with bitwise operators and example.
Best error detection algorithm which used for data transmission.
Modulo-2 binary division
CRC Modulo 2 Division
The modulo-2 division process is defined as follows:
Call the uppermost c+1 bits of the message the remainder
- Beginning with the most significant bit in the original message and for each bit position that follows, look at the c+1 bit remainder:
- If the most significant bit of the remainder is a one, the divisor is said to divide into it. If that happens (just as in any other long division) it is necessary to indicate a successful division in the appropriate bit position in the quotient and to compute the new remainder. In the case of modulo-2 binary division, we simply:
- Set the appropriate bit in the quotient to a one, and
- XOR the remainder with the divisor and store the result back into the remainder
- Otherwise (if the first bit is not a one):
- Set the appropriate bit in the quotient to a zero, and
- XOR the remainder with zero (no effect)
- Left-shift the remainder, shifting in the next bit of the message. The bit that’s shifted out will always be a zero, so no information is lost.
- If the most significant bit of the remainder is a one, the divisor is said to divide into it. If that happens (just as in any other long division) it is necessary to indicate a successful division in the appropriate bit position in the quotient and to compute the new remainder. In the case of modulo-2 binary division, we simply:
The final value of the remainder is the CRC of the given message.
CRC Implementation in C
Common file for Both and Reciever
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | //CRC Common File for Both Sender and Receiver #include<stdio.h> //Standard Input Functions #include<sys/types.h> //Named Pipes (FIFO) Types #include<sys/stat.h> // Named Pipes (FIFO) Functions #include<fcntl.h> //File Control Unix Functions #include<unistd.h> //Unix Standard Functions #define MAX 100 //Buffer Size for Writing Message unsigned short POLYNOMIAL;//Divisor int spoly=0,sdata=0; //Size of bits in divisor and actual data struct codeword { unsigned short data; unsigned short rem; }; //Power function for generating power unsigned long power(unsigned long no,unsigned long len) { unsigned long pow=1,i; for(i=1;i<=len;i++) pow *= no; return pow; } //Actual CRC logic which will return remainder unsigned short crcCalc(unsigned short const message) { unsigned short remainder,fdigit,bit; /* Initially, the dividend is the remainder. */ remainder = message; //Generating number which will return first bit from left side fdigit = power(2,sdata-1); //For each bit position in the message.... for (bit = 0; bit < sdata; bit++) { //If the uppermost bit is a 1... if (remainder & fdigit ) { //XOR the previous remainder with the divisor. remainder ^= POLYNOMIAL; } //Shift the next bit of the message into the remainder. remainder = (remainder << 1); } //Return only the relevant bits of the remainder as CRC. return (remainder >> (sdata-spoly+1)); } |
CRC Sender Code
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | //CRC Sender Example #include "crccom.c" //Common Function of CRC int main() { char *myfifo = "myfifo"; //FIFO File Path int fp; //Open Pipe Return Value char msg[MAX]; //Original Message to be sent unsigned short tpoly; //temp poly for checking no of bits in poly struct codeword ch; POLYNOMIAL=19; printf("Polynomial (Divisor) : %d",POLYNOMIAL); printf("\nEnter Data Character : "); scanf("%d",&tpoly); ch.data = tpoly; printf("Creating Pipe...Waiting for receiver for Process...\n"); //Creating Named Pipe //mkfifo(<filepath>,<permission>) if(mkfifo(myfifo,0666) < 0) { perror("FIFO (Named Pipe) could not be created.\n"); exit(-1); } else printf("FIFO (Named Pipe) Created...\n"); //Opening Named Pipe //open(<filepath>,<openingmode>); fp = open(myfifo,O_WRONLY); if(fp < 0) { perror("FIFO (Named Pipe) could not be opened.\n"); exit(-2); } else printf("FIFO (Named Pipe) Opened...\n"); //Calculate number of bits in divisor. tpoly = POLYNOMIAL; while(tpoly > 0) { tpoly /= 2; spoly++; } //Total bits for storing data sdata = sizeof(ch.data)*8; //Move all bits in divisor to the start position POLYNOMIAL <<= (sdata-spoly); //Calculate acutal CRC ch.rem = crcCalc(ch.data); printf("Data=> %d, Remainder => %d\n",ch.data,ch.rem); //Writing to Named Pipe //write(<open_pipe_return_value>,<message>,<msgsize>); if(write(fp,&ch,sizeof(struct codeword)) < 0) { perror("Error writing to FIFO (Named Pipe)\n"); exit(-3); } else printf("Message has been sent to FIFO (Named Pipe)\n"); //Closing Named Pipe //close(<open_pipe_return_value>); if(close(fp) < 0) { perror("Error closing FIFO (Named Pipe)\n"); exit(-4); } return 0; } |
CRC Receiver Code
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | //CRC Receiver Example #include "crccom.c" //CRC Common Functions int main() { char *myfifo = "myfifo"; //FIFO File Path int fp; //Open Pipe Return Value struct codeword ch; unsigned short rem,tpoly; //Opening Named Pipe //open(<filepath>,<openingmode>); fp = open(myfifo,O_RDONLY); if(fp < 0) { perror("FIFO (Named Pipe) could not be opened for reading.\n"); exit(-1); } else printf("FIFO (Named Pipe) Opened... Trying to read from\n"); //Reading From Named Pipe //read(<open_pipe_return_value>,<message>,<msgsize>); if(read(fp,&ch,sizeof(struct codeword)) < 0) { perror("Error reading from FIFO (Named Pipe)\n"); exit(-2); } else printf("Message Received from FIFO (Named Pipe)\n"); //CRC Logic Starts POLYNOMIAL = 19; printf("\nPolynomial (Divisor) : %d\n",POLYNOMIAL); tpoly = POLYNOMIAL; while(tpoly > 0) { tpoly /= 2; spoly++; } //Total bits for storing data sdata = sizeof(ch.data)*8; //Move all bits in divisor to the start position POLYNOMIAL <<= (sdata-spoly); rem = crcCalc(ch.data); if(rem != ch.rem){ printf("Error in Transmission"); exit(-5); } printf("\nSuccessfull Trasmission Original Message : %d",ch.data); //CRC Logic Ends //Closing Named Pipe //close(<open_pipe_return_value>); if(close(fp) < 0) { perror("Error closing FIFO (Named Pipe)\b"); exit(-3); } if(unlink(myfifo) < 0) { perror("Error deleting FIFO (Named Pipe)\b"); exit(-4); } return 0; } |
