Cyclic Redundancy Check (CRC)

Description

Cyclic Redundancy Check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. It operates by appending a fixed number of check bits (CRC bits) to the end of the data stream, computed based on the data content. At the receiver end, the CRC is recalculated and compared with the transmitted CRC. If they match, the data is considered intact; otherwise, an error is detected.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

int crc(vector<int>& data, vector<int>& generator) {
    int dataLength = data.size();
    int generatorLength = generator.size();

    vector<int> appendedData(data.begin(), data.end());
    appendedData.resize(dataLength + generatorLength - 1, 0);

    for (int i = 0; i < dataLength; ++i) {
        if (appendedData[i] == 1) {
            for (int j = 0; j < generatorLength; ++j) {
                appendedData[i + j] ^= generator[j];
            }
        }
    }

    return stoi(string(appendedData.end() - generatorLength + 1, appendedData.end()), nullptr, 2);
}

int main() {
    // Example usage
    vector<int> data = {1, 0, 1, 0, 1};
    vector<int> generator = {1, 0, 1};

    int crcChecksum = crc(data, generator);
    cout << "CRC checksum: " << crcChecksum << endl;

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
CRC Calculation	O(n * m)	O(n + m)

Where:

• n: Length of the data bits.
• m: Length of the generator polynomial.

← Back to Homepage