CRC Program in C++
Introduction:
An error-detecting code called a cyclic redundancy check (CRC) is frequently employed in computer networks and storage media to identify unintentional modifications to digital data. A brief check result is appended to the data blocks accessing such systems, which is determined by dividing the data inside of the unit by a polynomial fraction. Corrective measures concerning data corruption can be conducted if the computation happens again upon retrieval and the verification numbers fail to meet. Correction of errors can be achieved via CRCs (see bitfilters).
CRCs get their name since the procedure depends on cyclic codes, and the check (data verification) value is a redundancy (expanding the message without adding information). CRCs are widely used due to their ease of implementation in binary equipment and ease of mathematical analysis and are especially adept in identifying typical faults brought on by broadcast channel congestion. The algorithm that creates the check result can be utilized as a hashing function since it has a defined duration.
Generator Polynomial, which is present both on the sender and the recipient side, is used by CRC. A machine that generates a polynomial of the type x3 + x + 1 is a prime instance. In this generator polynomial, key 1011 is represented. The representation of key 101 by x2 + 1 is a further instance.
When a CRC's check output is n bits a while, it is called an n-bit CRC. Several potential CRCs exist for an integer n, each with a distinct polynomial. A polynomial contains n + 1 terms, or the greatest degree n. Put differently, the polynomial is n + 1 in size and needs n + 1 bits to encode. Many polynomial definitions omit or leave these out because the MSB and LSB always equal 1. The numerical value of the CRC and related polynomials is usually of the shape CRC-n-XXX, as shown in the data table beneath.
Sender Side (Data and Generator Polynomial (or Key) Creation of Encoded Data):
- The binary data is initially enhanced by appending k-1 zeros to its conclusion.
- To split binary data using the key and retain the remaining section, use modulo-2 binary division.
- To create the encoded data, attach the remaining information at the very end of the information and then transmit it.
Sides of the receiver (verify if any faults were introduced during transmission):
If the remaining number is zero after redividing by modulo-2, then there are no mistakes.
Modulo 2 Division:
- The familiar division procedure we apply to decimal integers is identical to the modulo-2 binary division procedure. Note that in this case, XOR is used in place of reduction.
- A duplicate of the divisor (or data) and the k bits of a dividend (or key) are XORed in each step.
- One additional bit is taken out to render it n bits lengthy, and the XOR procedure (remainder) output (n-1) bits are utilized for the following step.
- We get a result whenever we have no more bits to draw down. The rest of the (n-1) bits are attached to the sender side.
Illustration:
Example 1 (transmission error-free):
Data word to be sent - 100100
Key - 1101 [ Or generator polynomial x3 + x2 + 1]
From the sender side:
As a result, the data encoded and provided is 100100001, and the remainder is 001.
On the receiving end:
100100001 is the code phrase that the recipient obtained.
All zeros make up the remainder as a result. The data that was received is error-free.
Example 2: (Transmission error)
What needs to be transmitted is the data byte 100100.
1101 is the key.
From the sender's side:
As a result, the word sent is 100100001, while the remainder is 001.
Receiver's Side:
Let the communication medium contain a mistake.
100000001 is the code word that the recipient acquired.
The issue is discovered at the receiving end since the rest of the number does not consist entirely of zeros.
Example Code:
#include <bits/stdc++.h>
using namespace std;
string xor1(string x, string y)
{
string result = "";
int n = y.length();
for (int i = 1; i < n; i++) {
if (x[i] == y[i])
result += "0";
else
result += "1";
}
return result;
}
string mod2div(string dividend, string divisor)
{
int pick = divisor.length();
string tmp = dividend.substr(0, pick);
int n = dividend.length();
while (pick < n) {
if (tmp[0] == '1')
tmp = xor1(divisor, tmp) + dividend[pick];
else
tmp = xor1(std::string(pick, '0'), tmp)
+ dividend[pick];
pick += 1;
}
if (tmp[0] == '1')
tmp = xor1(divisor, tmp);
else
tmp = xor1(std::string(pick, '0'), tmp);
return tmp;
}
void encodeData(string data, string key)
{
int l_key = key.length();
string appended_data
= (data + std::string(l_key - 1, '0'));
string remainder = mod2div(appended_data, key);
string codeword = data + remainder;
cout << "Remainder : " << remainder << "\n";
cout << "Encoded Data is(Data + Remainder) :" << codeword
<< "\n";
}
void receiver(string data, string key)
{
string currxor
= mod2div(data.substr(0, key.size()), key);
int curr = key.size();
while (curr != data.size()) {
if (currxor.size() != key.size()) {
currxor.push_back(data[curr++]);
}
else {
currxor = mod2div(currxor, key);
}
}
if (currxor.size() == key.size()) {
currxor = mod2div(currxor, key);
}
if (currxor.find('1') != string::npos) {
cout << "there is some error in data" << endl;
}
else {
cout << "the correct message is received" << endl;
}
}
int main()
{
string data = "100101";
string key = "1100";
cout << "Sender side..." << endl;
encodeData(data, key);
cout << "\nReceiver side..." << endl;
receiver(data+mod2div(data+std::string(key.size() - 1, '0'),key), key);
return 0;
}
Output:
Example Code:
CRC program using Bit Manipulation
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
string toBin(long long int number)
{
string bin = "";
while (number) {
if (number & 1)
bin = "1" + bin;
else
bin = "0" + bin;
number = number >> 1;
}
return bin;
}
long long int toDec(string bin)
{
long long int number = 0;
for (int i = 0; i < bin.length(); i++) {
if (bin.at(i) == '1')
number += 1 << (bin.length() - i - 1);
}
return number;
}
void CRC(string dataword, string generator)
{
int l_gen = generator.length();
long long int gen = toDec(generator);
long long int dword = toDec(data word);
long long int dividend = dword << (l_gen - 1);
int shift = (int)ceill(log2l(dividend + 1)) - l_gen;
long long int rem;
while ((dividend >= gen) || (shft >= 0)) {
rem = (dividend >> shft) ^ gen;
dividend = (dividend & ((1 << shft) - 1))
| (rem << shift);
shift = (int)ceill(log2l(dividend + 1)) - l_gen;
}
long long int codeword
= (dword << (l_gen - 1)) | dividend;
cout << "Remainder: " << toBin(dividend) << endl;
cout << "Codeword : " << toBin(codeword) << endl;
}
int main()
{
string data word, generator;
dataword = "10011111";
generator = "1111";
CRC(data word, generator);
return 0;
}
Output:
Implementation
- With each data file to be transferred or saved, a CRC-enabled gadget computes a brief, fixed-length decimal series referred to as the verification result or CRC and includes it in the information, creating a secret word.
- The gadget typically conducts a CRC on the entire codeword then analyzes the resultant checking result to the predicted residual steady, or checks the verification value of a transmitted or scanned codeword to a single recently determined using the information block.
- An information mistake exists in the region if the CRC parameters aren't met.
- The gadget may ask that the segment be transmitted repeatedly or examined again as an act of correction. Alternatively, the information is considered to be free of mistakes. (However, there's a slight chance that it has errors that weren't noticed; error-checking is prone to this.)
Data consistency
CRCs are specially made to guard against typical kinds of mistakes on channels of communication, where they can offer prompt and adequate confidence regarding the delivery of high-quality information. They're not, however, appropriate for safeguarding versus purposeful data tampering.
First, because there isn't any authorization, a hacker can change an email and recalculate the CRC without anybody noticing. Cryptographic hashes and CRCs do not provide safeguards against deliberate data alteration if stored with the information. Cryptographic verification measures, like digital certificates or authentication codes for messages, must be used to protect any program from attacks like this.