Phương pháp mã đa thức CRC (Cyclic Redundancy Check)

CRC (Cyclic Redundancy Check) là một phương pháp để kiểm tra lỗi trong các hệ thống truyền thông. Nó còn được gọi là phương pháp mã đa thức hoặc mã vòng. Để tính toán thông tin kiểm lỗi, người ta sử dụng một "đa thức phát" G, có dạng nhị phân và các hệ số chỉ có giá trị 1 hoặc 0. G sẽ được sử dụng để tính toán một số đặc biệt, tên là "mã kiểm lỗi" (error-checking code), và số này sẽ được gắn thêm vào cuối dữ liệu gửi đi. Khi dữ liệu nhận được, người nhận sẽ sử dụng cùng đa thức phát G để tính toán lại mã kiểm lỗi và so sánh với mã kiểm lỗi được gắn thêm vào dữ liệu. Nếu hai mã này không giống nhau, tức là dữ liệu gửi đi đã bị lỗi trong quá trình truyền, người nhận sẽ yêu cầu gửi lại dữ liệu hoặc thông báo lỗi cho người gửi. Phương pháp này giúp đảm bảo rằng dữ liệu gửi đi luôn đảm bảo chính xác và không bị sai sót trong quá trình truyền.

Ví dụ:

Dạng đa thức: G = x2 + x + x5 + (0x2 + 0x3) + x2 + (0x1) + 1

Dạng nhị phân: G =

Dạng octal: G =

Nguyên tắc cơ bản của phương pháp CRC

Giả sử đa thức G có bậc n, ví dụ x^3+x+1 tương ứng với dãy bit . Dãy bit mang thông tin nguồn I được thêm vào n bit 0 và coi như một đa thức nhị phân P. Ví dụ thông tin nguồn là thì sau khi thêm 3 bit 0, ta có dãy bit tương ứng với đa thức P = x^8+x^7+x^5+x^3.

・Đa thức P được chia cho đa thức G, dựa vào các quy tắc đơn giản của phép trừ không có nhớ như sau:

1 – 1 = 0

0- 0 = 0

1 – 0 = 1

0 – 1 = 0

・Không cần quan tâm tới kết quả của phép chia, phần dư R (lấy n chữ số) của phép chia được thay thế vào chỗ của n chữ 0 bổ sung trong P, tức là ta có D = P + R. Theo tính chất của phép chia đa thức nhị phân, nếu D-R chia hết cho G thì D = P+R cũng vậy. R được gọi là checksum và D chính là dãy bit được gửi đi thay cho I.

・Giả sử dãy bit nhận được là D' không chia hết cho G thì tức là D khác D', ta có thể khẳng định được rằng bức điện chắc chắn bị lỗi. Ngược lại, nếu D' chia hết cho G, thì xác suất rất cao là bức điện nhận được không có lỗi. Ta nói "xác suất cao", bởi mỗi bit trong thông tin nguồn tham gia nhiều vòng (cyclic) vào tính toán thông tin bổ trợ nên khả năng "dữ kiện sai mà kết quả đúng" là rất ít.

Một điều đáng chú ý là tuy phương pháp CRC có vẻ như phức tạp, nhưng thực sự việc thực hiện nó lại rất đơn giản. Phép chia đa thức nhị phân ở đây được thực hiện thuần túy bởi các phép trừ không có nhớ – hay chính là các phép logic XOR. Bên cạnh đó chỉ cần các phép sao chép và so sánh bit thông thường.

Như ta thấy, khả năng phát hiện lỗi được đặc trưng qua khoảng cách Hamming phụ thuộc hoàn toàn vào cách chọn đa thức quy ước G. Tuy nhiên, để phương pháp này đạt được hiệu quả tối ưu, cần cân nhắc cả tới quan hệ giữa chiều dài của dãy bit mang thông tin nguồn và bậc của đa thức G. Một cách ký hiệu thường được dùng để chỉ quan hệ này được gọi là mã (m, n), trong đó m là tổng số bit và n là số bit mạng dữ liệu. Một cấu trúc bức điện theo tiêu chuẩn DIN 19 244:

Tên gọi: Mã (8i+8, 8i), với i = 1…15 là số byte (octet) của dữ liệu

Lớp cấu trúc (format class): FT2

Khoảng cách Hamming: HD = 4

Ví dụ với i = 7, ta sẽ có mã (64, 56), tức bức điện dài 8 byte chứa 7 byte dữ liệu. Trong 8 bit kiểm lỗi có 7 bit là phần dư R được tính theo phương pháp CRC, bit còn lại chính là parity bit chắn của R, sau đó giá trị mỗi bit lại được đảo lại.