Crc Program In C

• ✅ The Cyclic Redundancy Check algorithm's guiding concepts are explained in this article with examples.
• ✅ Provides two distinct approaches for implementing the CRC program.
• ✅ Explains the two distinct ways to build the CRC program in C and their respective algorithms and time complexity.

Introduction

The Cyclic Redundancy Check (CRC) algorithm is responsible for error detection and validation of transmitted data by the sender. This process involves the utilization of a generator polynomial for calculating the check value through binary division, alongside the actual data being transmitted. Including the CRC value along with the data ensures data integrity during transfer.

The polynomial's degree serves as markers for the positions of bits to encode the information being transmitted in polynomial format. For example, the binary sequence 1010101 with a length of 7 can be depicted as,

x7+x5+x3+1

Since the numerical value of that particular representation is likewise zero, the binary value of zero remains unexpressed.

Binary information can also serve as a representation of the generating polynomial. The data polynomial's degree needs to be lower than that of the generator polynomial and greater than zero. Different standards for CRC can be established depending on the generator polynomial's degree. For instance, a degree of 8 is employed for the CRC-8 standard, while a degree of 16 is utilized for the CRC-16 standard. This serves as a clear example of the generator polynomial.

x5+x4+x2

It is worth mentioning that Cyclic Redundancy Check can also serve as a hashing function. However, due to its limitation, CRC-8 can only produce a maximum of 256 (2^8).

The following are the CRC's steps: the sender's side,

• ✅ The generating polynomial of length l and the data of length n are ready.
• ✅ The data that has to be delivered has (l-1) zeros attached to it.
• ✅ The binary version of the generating polynomial is used as the divisor in binary division, with the data acting as the dividend. The check value is the remainder of the binary division.
• ✅ The check value is added to the end of the data before sending the signal.

Verify the value, also known as CRC, is expressed in a mathematical form as follows,

The 'n' in this scenario represents the number of bits in the generator polynomial. Moving towards the recipient,

• ✅ The incoming data undergoes another round of division through binary manipulations, where the data acts as the dividend and the binary equivalent of the generator polynomial acts as the divisor.
• ✅ The data transmitted by the sender remains error-free when the remainder of the binary division equals zero. In case the remainder is not zero, it signifies the presence of an error affecting the transmission.

The stages in binary division are identical to those in regular polynomial division and are as follows:

• ✅ Dividend and divisor must be XOR at every stage of division. Just the first n bits of the divisor, where n is the number of bits in the dividend, are used for this operation.
• ✅ Based on the n-bit data, the quotient will either be 1 or 0. The quotient is determined by the final piece of the data. If it is 1, it is 1, and if it is 0, it is 0.
• ✅ After the remainder of the aforementioned action, the bit at position n+1 is extracted from the data and added. This leftover amount serves as the next operation's divisor.
• ✅ Up until all the data bits are utilized in the calculation, the action is repeated.

One fascinating aspect of the Cyclic Redundancy Check is the unique process it follows: CRC(x^y^z) equals crc(x) XOR crc(y) XOR crc(z).

When we perform the XOR operation, it is denoted by the symbol ^. If we XOR three data elements first and then calculate the CRC of the outcome, the resulting CRC value will be identical to the scenario where we calculate the CRC for each data piece individually and then XOR the CRC results together.

NOTE: When both inputs are the same, the XOR operator returns 0, and while in all other circumstances it returns 1.

CRC implementation in C

The CRC algorithm can be implemented in C through two different methods. The initial method involves utilizing a character array, while the alternative method involves employing bitwise manipulation techniques.

Algorithm

The CRC program's implementation algorithm is as follows:

• ✅ Get the data and the polynomial generator.
• ✅ Let n represent the generator polynomial's length.
• ✅ Add n-1 zeros after the data.
• ✅ Invoke the CRC function.

The CRC function's algorithm is as follows:

• ✅ Get the data's first n bits.
• ✅ If the first bit is 1, then combine the generator polynomial with the first n bits of the data in a XOR operation.
• ✅ To retain the first bit, move the bits one place.
• ✅ Add a little portion of the data. Continue until all of the data's bits have been inserted.

The truth table below for the XOR operator forms the basis for the approach utilized in the XOR function:

• ✅ When the first and second bits are compared, the result is 0 if the two bits are the same.
• ✅ If the bits vary, the result is 1, otherwise.

The following is the algorithm used to check for faults on the receiver side:

• ✅ A Cyclic Redundancy Check is performed on the newly received data to identify the remaining data.
• ✅ The criteria that the remainder must not include a 1 and that its length must be smaller than the generator polynomial are iterated.
• ✅ We can be certain that there is no mistake if all the items are iterated; otherwise, there is error.
• ✅ In order to determine the size of a character array, utilize the strlen method. To use this method, the string.h header must be included.

CODE:

// Include headers
#include<stdio.h>
#include<string.h>
// length of the generator polynomial
#define N strlen(gen_poly)
// data to be transmitted and received
char data[28];
// CRC value
char check_value[28];
// generator polynomial
char gen_poly[10];
// variables 
int data_length,i,j;
// function that performs XOR operation
void XOR(){
    // if both bits are the same, the output is 0
    // if the bits are different the output is 1
    for(j = 1;j < N; j++)
    check_value[j] = (( check_value[j] == gen_poly[j])?'0':'1');
    
}
// Function to check for errors on the receiver side
void receiver(){
// get the received data
    printf("Enter the received data: ");
    scanf("%s", data);
    printf("\n-----------------------------\n");
    printf("Data received: %s", data);
// Cyclic Redundancy Check
    crc();
// Check if the remainder is zero to find the error
    for(i=0;(i<N-1) && (check_value[i]!='1');i++);
        if(i<N-1)
            printf("\nError detected\n\n");
        else
            printf("\nNo error detected\n\n");
}

void crc(){
    // initializing check_value
    for(i=0;i<N;i++)
        check_value[i]=data[i];
    do{
    // check if the first bit is 1 and calls XOR function
        if(check_value[0]=='1')
            XOR();
// Move the bits by 1 position for the next computation
        for(j=0;j<N-1;j++)
            check_value[j]=check_value[j+1];
        // appending a bit from data
        check_value[j]=data[i++];
    }while(i<=data_length+N-1);
// loop until the data ends
}

int main()
{
    // get the data to be transmitted
    printf("\nEnter data to be transmitted: ");
    scanf("%s",data);
    printf("\n Enter the Generating polynomial: ");
    // get the generator polynomial
    scanf("%s",gen_poly);
    // find the length of data
    data_length=strlen(data);
    // appending n-1 zeros to the data
    for(i=data_length;i<data_length+N-1;i++)
        data[i]='0';
    printf("\n----------------------------------------");
// print the data with padded zeros
    printf("\n Data padded with n-1 zeros : %s",data);
    printf("\n----------------------------------------");
// Cyclic Redundancy Check
    crc();
// print the computed check value
    printf("\nCRC or Check value is : %s",check_value);
// Append data with check_value(CRC)  
    for(i=data_length;i<data_length+N-1;i++)
        data[i]=check_value[i-data_length];
    printf("\n----------------------------------------");
// printing the final data to be sent
    printf("\n Final data to be sent : %s",data);
    printf("\n----------------------------------------\n");
// Calling the receiver function to check errors
    receiver();
        return 0;
}

OUTPUT:

Enter data to be transmitted: 1001101
Enter the Generating polynomial: 1011
----------------------------------------
Data padded with n-1 zeros : 1001101000
----------------------------------------
CRC or Check value is : 101
----------------------------------------
Final data to be sent : 1001101101
----------------------------------------
Enter the received data: 1001101101
-----------------------------
Data received: 1001101101
No error detected

Explanation

There are no signal errors as the data being transmitted and received are identical.

Enter the received data: 1001001101
-----------------------------
Data received: 1001001101
Error detected

There is a signal discrepancy due to the disparity between the transmitted and received data.

The time and space requirements of the program are denoted by the time complexity and space complexity correspondingly. The Big-O notation is employed to symbolize the time and space complexity. As a consequence of the simultaneous iteration of two for loops, the time complexity of the program is O(n^2).

Due to the utilization of a one-dimensional character array to store n characters, the program exhibits an O(n) space complexity.

CRC Implementation using Bit Manipulation

The CRC algorithm is executed by applying bit manipulation methods in this manner.

Algorithm

The bit manipulation technique used to implement CRC in C is as follows:

• ✅ Get the data and the polynomial generator.
• ✅ Decimalize the generating polynomial and the input data.
• ✅ To append zeros to the end of the data, shift the bits in the data by n-1 places, where n is the length of the generating polynomial.
• ✅ With the help of the logarithmic function, determine how many bits need to be moved.
• ✅ Shift the data by the calculated number of bits and use a generator polynomial to conduct an XOR operation.
• ✅ Identify the remaining part of the procedure, and then add some information to it so that it may be processed further.
• ✅ Continue until every data bit has been used in the calculation.

The algorithm used to translate numbers from decimal to binary is as follows:

• ✅ Use the number and 2 in a modulo operation to determine the residual.
• ✅ Determine the value of 10 raised to the power of the remaining number, and then multiply it by that.
• ✅ Add up the value that was discovered in the previous step.
• ✅ Increase the counter after dividing the decimal by two. Continue doing so until the decimal is no longer equal to 0.
Example

Copy

#include<stdio.h>
#include<math.h>
#include<string.h>
#define ull unsigned lli
#define lli long long int
int Decimal_to_Binary(int decimal)
{
// binary value
    ull binary = 0;
// counter
    int count = 0;
// remainder variable
    int rem=0; 
    while (decimal != 0) {
// perform modulo operation
        rem = decimal % 2;
// compute power of 10
        ull tmp = pow(10, count);
// add result to compute the binary number
        binary += rem * tmp;
// divide the decimal by 2
        decimal /= 2;
// increment count
        count++;
    }
    return binary;
}
 
lli Binary_to_Decimal(char binary[]){
    lli decimal = 0;
// Use bit shifting with 1 to compute the number
// sum the numbers to get the decimal equivalent
    for (int i=0; i<strlen(binary); i++){
        if (binary[i]=='1')
            decimal += 1 << (strlen(binary) - i - 1);
    }
    return decimal;
}
 
// function to compute CRC and codeword
void CRC(char data[], char gen_poly[]){
// length of the generator polynomial
    int length_gen = strlen(gen_poly);
// convert generator polynomial from binary to decimal
    lli generator_dec = Binary_to_Decimal(gen_poly);
// Convert data from binary to decimal
    lli data_dec = Binary_to_Decimal(data);
// Shift n-1 bits to the left in data to append zeros
    lli dividend = data_dec << (length_gen-1); 
// find the number of bits to shift for further computation.
    int shift_bits = (int) ceill(log2l(dividend+1)) - length_gen; 
// initialize variable for CRC or check value
    lli check_value;
// loop to find the check_value or CRC
    while ((dividend >= generator_dec) || (shift_bits >= 0)){
 // take the first four bits of the data 
 // perform XOR with the generator polynomial
        check_value = (dividend >> shift_bits) ^ generator_dec;               
// find the remainder of the operation
        dividend = (dividend & ((1 << shift_bits) - 1)) | (check_value << shift_bits);
// compute the number of bits to shift again
        shift_bits = (int) ceill(log2l(dividend + 1)) - length_gen;
    }
 // append the check value with the data
    lli final_data = (data_dec << (length_gen - 1)) | dividend;
// convert the decimal value to binary 
    printf("Check value or CRC: %d\n",Decimal_to_Binary(dividend));
// print the data to be transmitted
    printf("Data to be sent:  %d",Decimal_to_Binary(final_data));
}
 
int main(){
// Get the data
    char dataword[20];
    printf("Enter the data to be transmitted: ");
    scanf("%s", dataword);
// Get the generator polynomial
    char generator[20];
    printf("\nEnter the generator polynomial: ");    
    scanf("%s",generator);
// Calling the CRC function
    CRC(dataword, generator);
    return 0;
}

OUTPUT:

Enter the data to be transmitted: 1001101
Enter the generator polynomial: 1011
Check value or CRC: 101
Data to be sent:  1001101101
......................................
Process executed in 1.11 seconds.

Explanation:

The time complexity of a program indicates the execution time required, while the space complexity refers to the memory space needed. The complexity of a program is commonly denoted using Big-O notation. In this case, the time complexity is O(n) due to the presence of a single for loop at a time, and the space complexity is also O(n) as characters are stored in a one-dimensional character array.

Conclusion:

• ✅ An error validation procedure called Cyclic Redundancy Check is used to determine whether the signal being sent by the sender has any errors.
• ✅ The data's CRC value is calculated using a generator polynomial, and both the data and CRC are communicated.
• ✅ At every stage of the procedure, the XOR operation is used to determine the CRC value.
• ✅ The receiver side validates itself by determining whether the CRC computed there equals zero.
• ✅ Both the character array and the bit manipulation approach may be used to create the CRC program in C.
• ✅ Both methods have the same level of temporal and spatial complexity.