CRC (Cyclic Redundancy Check)

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 SF 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ị SF của nó sẽ là :

SF = 84´2563 + 69´2562 + 83´2561 + 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 )

(SF ´ 2562 + 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 – ( (SF ´ 2562) 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à Fnhận­ và giá trị
CRC­nhận. Áp dụng công thức (1) với Fnhận ­ để tính ra giá trị số nguyên đại diện cho Fnhậ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ị CRCnhận, nghĩa là kiểm tra đẳng thức:

(S’F ´ 2562 + CRCnhận) MOD G = 0 (4)

Nếu (4) sai thì chắc chắn Fnhận ¹ F. Ngược lại, nếu (4) đúng thì không chắc chắn Fnhận ¹ F nhưng cũng không chắc chắn là Fnhậ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 Fnhậ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 Fnhận ¹ F và đẳng thức (3) được thỏa mãn cùng lúc, nội dung của Fnhậ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 SF. Để 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 < len; i++) {

value = value << 8;

value += F[i];

value = value % G;

}

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

value = value << 16;

value = value % G;

if (value) value = G - value;

...

Posted in: lap trinh vien, Lap trinh vien Java