CRC (Cyclic Redundancy Check)

Định Nghĩa của Wikipedia: CRC (cyclic redundancy check) là một loại hàm băm, được dùng để sinh ra giá trị kiểm thử, của một chuỗi bit có chiều dài ngắn và cố định, của các gói tin vận chuyển qua mạng hay một khối nhỏ của tệp dữ liệu. Giá trị kiểm thử được dùng để dò lỗi khi dữ liệu được truyền hay lưu vào thiết bị lưu trữ. Giá trị của CRC sẽ được tính toán và đính kèm vào dữ liệu trước khi dữ liệu được truyền đi hay lưu trữ. Khi dữ liệu được sử dụng, nó sẽ được kiểm thử bằng cách sinh ra mã CRC và so khớp với mã CRC trong dữ liệu.

CRC rất phổ biến, vì nó rất đơn giản để lắp đặt trong các máy tính sử dụng hệ cơ số nhị phân, dễ dàng phân tích tính đúng, và rất phù hợp để dò các lỗi gây ra bởi nhiễu trong khi truyền dữ liệu.

---

Trong quá trình sử dụng máy tính, chắc hẳn bạn đã không ít lần cảm thấy khó chịu (đặc biệt là khi bạn đã tốn hàng giờ để download một tập tin quan trọng) khi gặp phải thông báo lỗi của WinZip từ chối xả nén một tập tin vì phép kiểm CRC thấy bại. Tại sao các phần mềm nén lại phải thực hiện phép kiểm tra CRC mỗi khi nó xả nén một tập tin? Thực ra, CRC là một phương pháp nhằm kiểm tra xem nội dung một tập tin có bị thay đổi hay không (đặc biệt là khi tập tin này được truyền đi trên mạng). Điều này cực kỳ quan trọng đối với các phần mềm nén vì chỉ cần sai lệch một byte cũng đủ để làm sai lệch hoàn toàn nội dung các tập tin bị nén.

Ý tưởng về CRC cũng không quá phức tạp. Trong bài viết này, chúng ta sẽ xem xét qua một thuật toán phát sinh CRC đơn giản.

Trước tiên, để đơn giản hóa bài toán mà không làm mất tính tổng quát, ta sẽ xem nội dung tập tin F cần kiểm tra như là một con số nguyên khổng lồ trong đó, byte có nghĩa nhất là byte đầu tiên của tập tin, byte tiếp theo là byte có nghĩa kế tiếp và cứ thế cho đến byte cuối cùng của tập tin là byte ít có nghĩa nhất. Hay nói một cách khác, tập tin cần được kiểm tra F sẽ được đại diện bởi một con số nguyên S_F mà giá trị của nó là :

(1)

trong đó b[i] là byte thứ i của tập tin.

Chẳng hạn, giả sử tập tin cần kiểm tra có nội dung là TEST thì giá trị S_F của nó sẽ là :

S_F = 84´256³ + 69´256² + 83´256¹ + 84 = 1 413 829 716

(trong đó mã ASCII của ký tự các T, E và S lần lượt là 84, 69, 83)

Giá trị CRC của một tập tin F là một số nguyên 2 byte sao cho với một hằng số nguyên cho trước G, đẳng thức sau được thỏa mãn (MOD là toán tử chia lấy phần dư, giống toán tử % của C, chẳng hạn 5 mod 2 = 1 vì 5 chia cho 2 còn dư 1 )

(S_F ´ 256² + CRC) MOD G = 0 (2)

Người ta thường chọn G là một số nguyên tố.

Giá trị CRC thỏa (2) có thể được xác định bằng công thức sau :

CRC = G – ( (S_F ´ 256²) MOD G ) (3)

Khi truyền tập tin F sang nơi khác, ta đồng thời truyền cả giá trị CRC sang nơi nhận. Nơi nhận sẽ nhận được một tập tin có nội dung là F_nhận­ và giá trị
CRC­_nhận. Áp dụng công thức (1) với F_{nhận ­} để tính ra giá trị số nguyên đại diện cho F_nhận là S’_F

Tại nơi nhận, phép kiểm tra CRC được thực hiện bằng cách áp dụng công thức (2) đối với S’_F và giá trị CRC_nhận, nghĩa là kiểm tra đẳng thức:

(S’_F ´ 256² + CRC_nhận) MOD G = 0 (4)

Nếu (4) sai thì chắc chắn F_nhận ¹ F. Ngược lại, nếu (4) đúng thì không chắc chắn F_nhận ¹ F nhưng cũng không chắc chắn là F_nhận = F !!!

Điều này mới nghe có vẻ rất ngạc nhiên vì nếu đúng như vậy thì phương pháp này chẳng có giá trị gì cả ! Nhưng may mắn là, trong điều kiện thực tế, khi (3) đúng thì khả năng xảy ra trường F_nhận ¹ F là cực kỳ thấp, thấp đến mức mà ta có thể yên tâm là nó không thể xảy ra. Cơ sở cho khẳng định này là các sai sót trong quá trình truyền tập tin thường xảy ra ngẫu nhiên và số bit bị sai sót thường ít (1-2 bit). Trong khi đó, để xảy ra trường hợp F_nhận ¹ F và đẳng thức (3) được thỏa mãn cùng lúc, nội dung của F_nhận phải tuân theo một quy luật khá đặc biệt và số bit bị thay đổi giá trị cũng thường nhiều. Sự ngẫu nhiên khó có thể tạo ra một sai sót đặc biệt như vậy.

Cách cài đặt thuật toán phát sinh và kiểm tra CRC cho một tập tin cũng khá rõ ràng. Tuy nhiên, bạn đọc nên lưu ý đến vấn đề tràn số khi tính tổng S_F. Để tránh điều này, bạn có thể sử dụng tính chất sau của toán tử mod : (A + B) MOD C = ( (A MOD C) + B ) MOD C

Đoạn chương trình minh họa sau dùng để phát sinh giá trị CRC của một chuỗi ký tự F (biến value sẽ giữ giá trị CRC khi đoạn chương trình kết thúc).

len = strlen(F);

value = 0;

// Tính giá trị số nguyên đại diện cho F dùng công thức (1)

for (i = 0; i <>

value = value <<>

value += F[i];

value = value % G;

}

// Tính giá trị CRC dùng công thức (3)

value = value <<>

value = value % G;

if (value) value = G - value;

...

=== Sưu Tầm từ Internet