CRC Cycle Redundancy Check

Introduction

In the world of data communication, ensuring that information is transmitted accurately is critical. Enter CRC (Cyclic Redundancy Check)—a powerful method to detect accidental errors during data transfer. Whether you’re a student, developer, or tech enthusiast, this guide will break down CRC in simple terms, complete with examples, code, and FAQs. Let’s dive in!

What is CRC?

CRC (Cyclic Redundancy Check) is a technique used to detect unintentional changes (errors) in raw data transmitted over networks or stored in devices. It works by adding a “checksum” to the data, which helps the receiver verify if the data arrived intact.

Key Features of CRC

Simple & Fast: CRC is computationally efficient.
Widely Used: Found in Ethernet, ZIP files, PNG images, and more.
Error Detection: Detects burst errors (multiple corrupted bits).

Example 1: No Error in Transmission

Sender Side

Data to Send: 100100
Key (Generator Polynomial): 1101 (represents $x^{3} + x^{2} + 1$ )

Step 1: Augment the Data

Add $k - 1$ zeros (here, $k = 4$ , so add 3 zeros).
Augmented Data: 100100 + 000 = 100100000.

Step 2: Modulo-2 Division

Divide 100100000 by 1101 using XOR operations.

Step	Current Bits	XOR with Key (1101)	Result	Bring Down Next Bit
1	`1001`	`1101`	`0100`	`0` → `01000`
2	`01000`	`0000` (leading 0)	`01000`	`0` → `010000`
3	`010000`	`0000`	`010000`	`0` → `0100000`
4	`0100000`	`0000`	`0100000`	`0` → `01000000`
5	`01000000`	`0000`	`01000000`	`1` → `010000001`

Final Remainder: 001
Encoded Data Sent: Original data + remainder = 100100001.

Receiver Side

Received Data: 100100001 (no errors)

Step 1: Modulo-2 Division

Divide 100100001 by 1101.

Step	Current Bits	XOR with Key (1101)	Result	Bring Down Next Bit
1	`1001`	`1101`	`0100`	`0` → `01000`
2	`01000`	`0000`	`01000`	`0` → `010000`
3	`010000`	`0000`	`010000`	`0` → `0100000`
4	`0100000`	`0000`	`0100000`	`0` → `01000000`
5	`01000000`	`0000`	`01000000`	`1` → `010000001`

Final Remainder: 000
Conclusion: No errors detected.

Example 2: Error During Transmission

Sender Side

Data to Send: 100100
Key: 1101
Encoded Data Sent: 100100001 (same as Example 1).

Receiver Side

Received Data: 100000001 (error in the 4th bit: 1 → 0)

Step 1: Modulo-2 Division

Divide 100000001 by 1101.

Step	Current Bits	XOR with Key (1101)	Result	Bring Down Next Bit
1	`1000`	`0000` (leading 1)	`1000`	`0` → `10000`
2	`10000`	`1101`	`0101`	`0` → `01010`
3	`01010`	`0000`	`01010`	`0` → `010100`
4	`010100`	`0000`	`010100`	`0` → `0101000`
5	`0101000`	`0000`	`0101000`	`1` → `01010001`

Final Remainder: 101
Conclusion: Non-zero remainder → Error detected.

Why This Works

Sender appends a checksum derived from the original data.
Receiver recalculates the checksum. If the data is unchanged, the remainder is zero.
Modulo-2 Division uses XOR instead of subtraction, making it efficient for binary data.

Visual Recap

Error-Free Transmission

Data: 100100 → Encoded: 100100001  
Receiver Division: 100100001 ÷ 1101 = 0 remainder ✔️

Corrupted Transmission

Data: 100100 → Encoded: 100100001  
Received: 100000001 (error)  
Receiver Division: 100000001 ÷ 1101 = 101 remainder ❌

Key Takeaways

CRC is Fast: Simple XOR operations make it ideal for real-time systems.
Detects Burst Errors: Can catch multiple consecutive bit flips.
Not for Security: CRC only detects accidental errors, not intentional tampering.

How CRC Works: Sender and Receiver

CRC relies on a generator polynomial (a mathematical expression) known to both sender and receiver. Here’s a step-by-step breakdown:

1. Sender Side: Generating the Encoded Data

Step 1: Augment the Data

Original data: 100100
Add k-1 zeros (where k is the key length).
- Example: If the key is 1101 (k=4), add 3 zeros → 100100000.

Step 2: Perform Modulo-2 Division

Divide the augmented data by the key using XOR operations.
Remainder from this division becomes the checksum.

Step 3: Send Encoded Data

Append the checksum to the original data.
- Example: Data becomes 100100001.

2. Receiver Side: Error Checking

Step 1: Divide Received Data by the Key

Use the same generator polynomial (key).
Perform modulo-2 division again.

Step 2: Check the Remainder

Remainder = 0: No errors detected.
Remainder ≠ 0: Data is corrupted.

The Magic of Modulo-2 Division

Modulo-2 division uses XOR instead of subtraction. Here’s how it works:

Align the divisor (key) with the leftmost 1 of the dividend.
XOR the divisor with the selected bits.
Bring down the next bit and repeat until all bits are processed.
The final remainder is the checksum.

Example: Modulo-2 Division

Data: 100100000 (Augmented)
Key: 1101
Remainder: 001
Encoded Data: 100100001

Real-World Examples

Example 1: No Transmission Error

Sender: Sends 100100001.
Receiver: Divides by 1101.
Remainder: 000 → No error.

Example 2: Error During Transmission

Corrupted Data Received: 100000001.
Receiver’s Division: Remainder = 101 → Error detected.

Implementing CRC in Code

1. String-Based Approach (C++)

This method uses strings to simulate binary division:

#include <bits/stdc++.h>  
using namespace std;  

// XOR function for binary strings  
string xor1(string a, string b) {  
    string result = "";  
    for (int i = 1; i < b.length(); i++) {  
        if (a[i] == b[i]) result += "0";  
        else result += "1";  
    }  
    return result;  
}  

// Modulo-2 division  
string mod2div(string dividend, string divisor) {  
    int pick = divisor.length();  
    string tmp = dividend.substr(0, pick);  
    while (pick < dividend.length()) {  
        if (tmp[0] == '1')  
            tmp = xor1(divisor, tmp) + dividend[pick];  
        else  
            tmp = xor1(string(pick, '0'), tmp) + dividend[pick];  
        pick++;  
    }  
    return tmp;  
}  

// Encode data with CRC  
void encodeData(string data, string key) {  
    string appended_data = data + string(key.length()-1, '0');  
    string remainder = mod2div(appended_data, key);  
    cout << "Encoded Data: " << data + remainder << endl;  
}

2. Bit Manipulation Approach (C++)

A faster method using bitwise operations:

#include <iostream>  
using namespace std;  

// Convert number to binary string  
string toBin(long long num) {  
    string bin = "";  
    while (num) {  
        bin = (num & 1 ? "1" : "0") + bin;  
        num >>= 1;  
    }  
    return bin;  
}  

// CRC using bit manipulation  
void CRC(string dataword, string generator) {  
    long long gen = stoll(generator, 0, 2);  
    long long dword = stoll(dataword, 0, 2);  
    long long dividend = dword << (generator.length() - 1);  
    int shft = ceil(log2(dividend + 1)) - generator.length();  

    while (dividend >= gen || shft >= 0) {  
        long long rem = (dividend >> shft) ^ gen;  
        dividend = (dividend & ((1 << shft) - 1)) | (rem << shft);  
        shft = ceil(log2(dividend + 1)) - generator.length();  
    }  
    cout << "Codeword: " << toBin((dword << (generator.length()-1)) | dividend) << endl;  
}

Why CRC is Not Foolproof

Detects Accidental Errors Only: CRC can’t protect against intentional tampering.
Burst Errors Limit: Effectiveness depends on the polynomial’s degree.

FAQs

1. Why Use CRC Instead of Checksums?

CRC detects more error types, especially burst errors, thanks to polynomial division.

2. How is the Generator Polynomial Chosen?

Polynomials are standardized (e.g., CRC-16, CRC-32) for optimal error detection.

3. Can CRC Correct Errors?

No, CRC only detects errors. Use Forward Error Correction (FEC) for correction.

4. Is CRC Used in 5G Networks?

Yes! CRC is vital in 5G for ensuring data integrity.

5. What’s the Time Complexity of CRC?

O(n), where n is data length. It’s efficient for large datasets.

Conclusion

By 2025, CRC will remain a cornerstone in error detection for communication systems. Its simplicity, speed, and reliability make it indispensable.