1. Các khái niệm cơ bản

CRC hoạt động dựa trên nguyên tắc phép chia đa thức (polynomial division) trong trường hữu hạn GF(2) (trường hai phần tử, chỉ gồm 0 và 1).

• CRC Code là gì? Nó là một chuỗi bit được tính từ dữ liệu gốc, và được thêm vào bên cuối của chuỗi dữ liệu. Chuỗi bit này chính là phần dư của phép chia.
• Mục đích: Khi bên nhận tính toán lại CRC và so sánh với dữ liệu được gửi, bên nhận có thể xác định có lỗi xảy ra trong quá trình truyền hay không.

2. Cơ chế hoạt động (Phép chia Modulo-2)

Quá trình tính toán CRC được thực hiện qua ba bước chính, sử dụng phép toán số học không nhớ (carry-less arithmetic), tức là phép cộng và phép trừ được thay thế bằng phép toán XOR (Exclusive OR) ở mức bit.

a. Đa thức sinh (Generator Polynomial) - G(x)

• Đây là "số chia" cố định và được thống nhất giữa bên gửi và bên nhận.
• G(x) được biểu diễn dưới dạng một chuỗi bit nhị phân. Độ dài của đa thức sinh (r+1 bit) sẽ quyết định độ dài của mã CRC (r bit).

Ví dụ: Đa thức sinh G(x) = x^3 + x + 1 tương ứng với chuỗi bit 1011 (vì x^3.1 + x^2.0 + x^1.1 + 1). Độ dài của chuỗi CRC sẽ là r = 3 bit.

b. Quá trình tại bên gửi

• Mở rộng Dữ liệu: Lấy dữ liệu cần truyền (D) và thêm r bit 0 vào cuối, trong đó r là số bit của mã CRC mong muốn. Chuỗi mới này được gọi là T
• Thực hiện Phép chia Modulo-2: Chia chuỗi T cho chuỗi bit của Đa thức sinh G.
  • Phép chia Modulo-2 sử dụng XOR thay vì phép trừ thông thường.
• Lấy Phần dư: Phần dư của phép chia này chính là mã CRC (R). Mã CRC này luôn có độ dài là r bit.
• Tạo Khung Dữ liệu: Bên gửi thay thế r bit 0 đã thêm vào ban đầu bằng mã CRC (R). Khung dữ liệu mới này (gồm Dữ liệu gốc + CRC) được truyền đi.

c. Quá trình tại bên nhận

• Nhận Dữ liệu: Bên nhận nhận được khung dữ liệu truyền (Dữ liệu + CRC).
• Kiểm tra CRC: Bên nhận thực hiện phép chia toàn bộ khung dữ liệu nhận được cho đa thức sinh G đã biết. (bên gửi và nhận đã thống nhất với nhau về G, nó giống như một "code" để 2 bên có thể nhận ra nhau).
• Xác định Lỗi:
  • Nếu phần dư bằng 0, dữ liệu được coi là hợp lệ (không bị lỗi).
  • Nếu phần dư khác 0, dữ liệu được coi là bị lỗi trong quá trình truyền và sẽ bị loại bỏ hoặc yêu cầu gửi lại.

Thực hành

Để có thể hiểu hơn về cách CRC hoạt động, nên đọc kỹ lý thuyết phía trên + làm một số ví dụ trong đường link này: https://nguyenquanicd.blogspot.com/2017/10/basic-knowledgecrc-bai-1-ly-thuyet-ve.html

📌 Lưu ý

• Chuỗi CRC được thêm vào phía bên phải điều này đồng nghĩa với việc khi code ta cần phải dịch dữ liệu ban đầu về phía bên trái

Mã nguồn tham khảo: https://github.com/hdtodd/CRC8-Library/blob/main/libcrc8.c

Code mẫu

#include <stdio.h>
#include <stdint.h>
// #include "packetCRC_8.h"

// Cách 1: Tính CRC8 bit-by-bit
uint8_t crc8_bitwise(uint8_t *data, uint8_t len, uint8_t poly) {
    uint8_t crc8 = 0; 
    for(int i = 0; i < len; i++) {
        crc8 = crc8 ^ data[i];
        for(int j = 0; j < 8; j++) {
            if(crc8 & 0x80) { // MSB = 1
                crc8 = crc8 << 1;   // Shift right
                crc8 = crc8 ^ poly; // XOR vs polynomial
            } 
            else { // MSB = 0
                crc8 = crc8 << 1;   // Shift right
            }
        }
    }

    return crc8;
}

// Cách 2: Dùng bảng tra CRC Table
uint8_t crc8_table[256];

void build_crc8_table(uint8_t poly)
{
    for (int i = 0; i < 256; i++) {
        uint8_t crc = i;
        for (int j = 0; j < 8; j++) {
            if (crc & 0x80)
                crc = (crc << 1) ^ poly;
            else
                crc <<= 1;
        }
        crc8_table[i] = crc;
    }
}

uint8_t crc8_lookup(uint8_t *data, int len)
{
    /**
     * Bảng chất CRC là trạng thái liên tục - nghĩa là sau khi xử lí xong byte1, "CRC kết quả" trở thành
     * điểm khởi đầu cho byte2, và cứ tiếp tục như thế nếu ta có nhiều byte.
     */
    uint8_t crc = 0;
    for (int i = 0; i < len; i++) {
        crc = crc8_table[crc ^ data[i]];
    }
    return crc;
}

int main() {
    uint8_t msg[] = {0b10101101};
    uint8_t poly = 0x97; // Polynomial 1001 0111 (CRC-8)

    // Cách 1
    uint8_t crc1 = crc8_bitwise(msg, sizeof(msg), poly);

    // Cách 2
    build_crc8_table(poly);
    uint8_t crc2 = crc8_lookup(msg, sizeof(msg));

    printf("CRC bit-by-bit  = 0x%02X\n", crc1);
    printf("CRC lookup table = 0x%02X\n", crc2);

    return 0;
}****