Cyclic Redundancy Check thường viết tắt là CRC, là thuật ngữ tiếng Anh trong kỹ thuật số (tạm dịch “Kiểm dư chu trình”), là phương pháp kiểm tra và phát hiện lỗi, được sử dụng trong các mạng số và thiết bị lưu trữ để phát hiện sự thay đổi tình cờ đối với dữ liệu được truyền đi hay lưu trữ.
CRC là một loại hàm băm dùng để phát sinh giá trị kiểm thử cho chuỗi bit, những gói tin luân chuyển qua mạng hay một khối nhỏ của tệp tài liệu. Giá trị của CRC được đo lường và thống kê và đính kèm vào tài liệu trước khi tài liệu được truyền đi hay tàng trữ. Khi tài 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 tài liệu. CRC rất thông dụng, vì nó rất đơn thuần để lắp ráp trong những máy tính sử dụng hệ cơ số nhị phân, thuận tiện nghiên cứu và phân tích tính đúng, và rất tương thích để dò những lỗi gây ra bởi nhiễu trong khi truyền tài liệu .CRC do W. Wesley Peterson tăng trưởng năm 1961. [ 1 ] Thời kỳ đó phương tiện đi lại lưu dữ liệu hầu hết là băng ghi 9 đường ( 9 track tape ) với 8 đường cho 8 bit tài liệu của 1 byte và 1 cho bit chẵn lẻ. Dữ liệu ghi được chia khối ( block ) với kết thúc khối là byte CRC ( CRC 8 bit ). Ngày nay CRC hoàn toàn có thể lập với 8, 16 hay 32 bit cho khối, và được luân chuyển cùng với bit chẵn lẻ để kiểm tra và phát hiện lỗi .
CRC là một loại mã phát hiện lỗi. Cách tính toán của nó giống như phép toán chia số dài trong đó thương số được loại bỏ và số dư là kết quả, điểm khác biệt ở đây là sử dụng cách tính không nhớ (carry-less arithmetic) của một trường hữu hạn. Độ dài của số dư luôn nhỏ hơn hoặc bằng độ dài của số chia, do đó số chia sẽ quyết định độ dài có thể của kết quả trả về. Định nghĩa đối với từng loại CRC đặc thù quyết định số chia nào được sử dụng, cũng như nhiều ràng buộc khác.
Mặc dù những mã CRC hoàn toàn có thể thiết kế xây dựng được bằng cách sử dụng bất kể trường hữu hạn nào, nhưng tổng thể những mã CRC thường dùng đều sử dụng trường hữu hạn GF ( 2 ). Đây là trường hai thành phần, thường được ký hiệu là 0 và 1, tương thích với kiến trúc máy tính. Phần còn lại của bài viết sẽ chỉ đề cập đến những mã CRC thuộc dạng này, nhưng nguyên tắc thì khái quát hơn .
Một lý do quan trọng lý giải sự phổ biến của mã CRC trong phát hiện sự thay đổi ngẫu nhiên của dữ liệu là hiệu suất đảm bảo. Điển hình, một mã CRC n bit, được áp dụng cho một đoạn dữ liệu có độ dài tùy ý, sẽ phát hiện được bất kỳ lỗi tín hiệu đơn nào có độ dài không quá n bit (nói cách khác, bất kỳ sự biến đổi đơn lẻ nào có chiều dài không quá n bit của dữ liệu), và sẽ phát hiện một phần 1-2-n của tất cả các lỗi tín hiệu có độ dài dài hơn thế. Các lỗi trong cả các kênh truyền dữ liệu và phương tiện bộ nhớ từ dẫn đến phân bố không ngẫu nhiên (v.d, “bursty”), làm cho các đặc tính của CRC trở nên hữu dụng hơn những mã khác như Multiple Parity checks.
Hệ thống tìm lỗi đơn thuần nhất, bit parity ( xét chẵn lẻ ), thực ra là một mã CRC ở dạng tầm thường : sử dụng số chia độ dài 2 bit là 11 .
Tính toán CRC[sửa|sửa mã nguồn]
Để đo lường và thống kê một mã nhị phân n bit CRC, xếp những bit trình diễn đầu vào thành một hàng, và đặt mẫu ( n + 1 ) bit màn biểu diễn số chia của CRC ( gọi là một ” đa thức ” ) vào bên dưới bên trái ở cuối hàng .Sau đây ví dụ encode 14 bits của message với CRC 3 – bit với đa thức như sau
- Đa thức (polynomial) làx3 + x + 1
đa thức được viết dưới dạng nhị phân khi thực thiện phép tính - Đa thức này là đa thức bậc ba nên sẽ có 4 hệ số (1x3 + 0x2 + 1x + 1
). Trong trường hợp này, 4 hệ số sẽ là 1, 0, 1 và 1.
Dãy số đầu vào:
11010011101100
11010011101100 000 Lại đưa vào đầu vào của phép tính tiếp theo) Ánh đã chia thử: 010011001111101
Nếu dãy nhị phân đầu vào bên trên có bít cực tả ( tiên phong bên trái ) là 0, không làm gì hết và dịch số chia sang phải một bít. Nếu dãy nhị phân đầu vào bên trên có bít cực tả là 1, lấy dãy số đầu vào trừ đi số chia ( hay nói cách khác, lấy từng bít ở dãy số nguồn vào trên trừ đi từng bít ở số chia ). Số chia sau đó dịch vị trí 1 bít sang phải, quy trình cứ tiếp nối như vậy đến khi số chia chạm tới tận cùng bên phải của dãy số nguồn vào. Đây là phép tính sau cuối :
00000000000101 000Do cực tả của số san sẻ làm những bít tương ứng của dãy số đầu vào quay trở lại 0 qua mỗi lần dịch, khi quy trình này kết thúc, chỉ còn những bít ở dãy nguồn vào hoàn toàn có thể không là 0 trở thành n bit cuối bên phải của dãy số. n bit này là số dư của bước chia, và cũng sẽ là giá trị hàm CRC ( trừ khi hàm CRC được chọn đặc biệt quan trọng được gọi cho 1 số ít quy trình tiền giải quyết và xử lý ) .
Những hàm CRC thường dùng và được tiêu chuẩn hóa[sửa|sửa mã nguồn]
Các dạng mã kiểm soát lỗi CRC (cyclic redundancy check) được chia thành nhiều tiêu chuẩn, chúng không được tiêu chuẩn hóa thống nhất cho 1 thuật toán nào ở mỗi mức độ trên toàn cầu: có 3 đa thức CRC-12[2], ít nhất 8 biến thể có trong tài liệu của CRC-16, và 3 biến thể của CRC-32[3] được biết đến. Các đa thức thường được xem như không phải là tối ưu có thể. Trong những năm từ 1993 đến 2004, Koopman, Castagnoli và một số nhà khoa học đã tiến hành tìm kiếm trong không gian các đa thức lên đến 16,[4] và không gian 24 và 32 bit,[5][6] tìm các ví dụ có hiệu suất tốt hơn nữa (trong các điều kiện quãng cách Hamming cho một bức tin có kích thước cho trước) so với các đã thức trong các giao thức trước đó, và xuất bản những kết quả tốt nhất trong số chúng với mục đích cải thiện năng lực tìm lỗi cho cac tiêu chuẩn trong tương lai.[6]
Không phải ngẫu nhiên mà đa thức phổ biển CRC-32, được IEEE ra mắt và được dùng trong V. 42, Ethernet, FDDI và ZIP và những file PNG cũng như nhiều ứng dụng khác, là một đa thức sinh ra từ mã Hamming và được chọn để tìm lỗi [ 7 ] trong những kênh tiếp thị quảng cáo. Dù vậy, nó còn có hiệu suất tốt hơn với đa thức Castagnoli CRC-32C sử dụng ở iSCSI [ 6 ] trong những thiên nhiên và môi trường Internet SCSI .Bảng dưới đây chỉ liệt kê những đa thức của những thuật toán phong phú đang được sử dụng .
Tên
Đa thức
Các biểu diễn: thông thường hoặc nghịch đảo (đảo của đảo)CRC-1
x + 1 { displaystyle x + 1 }parity bit)
0x1 hoặc 0x1 (0x1)CRC-4-ITU
x 4 + x + 1 { displaystyle x ^ { 4 } + x + 1 }ITU G.704, p. 12)
0x3 hoặc 0xC (0x9)CRC-5-ITU
x 5 + x 4 + x 2 + 1 { displaystyle x ^ { 5 } + x ^ { 4 } + x ^ { 2 } + 1 }ITU G.704, p. 9)
0x15 hoặc 0x15 (0x1A)CRC-5-USB
x 5 + x 2 + 1 { displaystyle x ^ { 5 } + x ^ { 2 } + 1 }USB token packets)
0x05 hoặc 0x14 (0x12)CRC-6-ITU
x 6 + x + 1 { displaystyle x ^ { 6 } + x + 1 }ITU G.704, p. 3)
0x03 hoặc 0x30 (0x21)CRC-7
x
7
+
x
3
+
1{displaystyle x^{7}+x^{3}+1}
MMC,SD)
0x09 hoặc 0x48 (0x44)CRC-8-ATM
x 8 + x 2 + x + 1 { displaystyle x ^ { 8 } + x ^ { 2 } + x + 1 }HEC)
0x07 hoặc 0xE0 (0x83)CRC-8-CCITT
x 8 + x 7 + x 3 + x 2 + 1 { displaystyle x ^ { 8 } + x ^ { 7 } + x ^ { 3 } + x ^ { 2 } + 1 }1-Wire bus)
0x8D hoặc 0xB1 (0xC6)CRC-8-Dallas/Maxim
x 8 + x 5 + x 4 + 1 { displaystyle x ^ { 8 } + x ^ { 5 } + x ^ { 4 } + 1 }1-Wire bus)
0x31 hoặc 0x8C (0x98)CRC-8
x 8 + x 7 + x 6 + x 4 + x 2 + 1 { displaystyle x ^ { 8 } + x ^ { 7 } + x ^ { 6 } + x ^ { 4 } + x ^ { 2 } + 1 }
0xD5 hoặc 0xAB (0xEA [4])CRC-8-SAE J1850
x 8 + x 4 + x 3 + x 2 + 1 { displaystyle x ^ { 8 } + x ^ { 4 } + x ^ { 3 } + x ^ { 2 } + 1 }
0x1D hoặc 0xB8 (0x8E)CRC-10
x 10 + x 9 + x 5 + x 4 + x + 1 { displaystyle x ^ { 10 } + x ^ { 9 } + x ^ { 5 } + x ^ { 4 } + x + 1 }
0x233 hoặc 0x331 (0x319)CRC-11
x 11 + x 9 + x 8 + x 7 + x 2 + 1 { displaystyle x ^ { 11 } + x ^ { 9 } + x ^ { 8 } + x ^ { 7 } + x ^ { 2 } + 1 }FlexRay)
0x385 hoặc 0x50E (0x5C2)CRC-12
x 12 + x 11 + x 3 + x 2 + x + 1 { displaystyle x ^ { 12 } + x ^ { 11 } + x ^ { 3 } + x ^ { 2 } + x + 1 }[8][9])
0x80F or 0xF01 (0xC07)
CRC-15-CAN
x 15 + x 14 + x 10 + x 8 + x 7 + x 4 + x 3 + 1 { displaystyle x ^ { 15 } + x ^ { 14 } + x ^ { 10 } + x ^ { 8 } + x ^ { 7 } + x ^ { 4 } + x ^ { 3 } + 1 }
0x4599 hoặc 0x4CD1 (0x62CC)CRC-16-Fletcher
Không phải một CRC; xem Fletcher's checksum
Sử dụng trong Adler-32 A & B CRCCRC-16-CCITT
x 16 + x 12 + x 5 + 1 { displaystyle x ^ { 16 } + x ^ { 12 } + x ^ { 5 } + 1 }X.25, V.41, CDMA, Bluetooth, XMODEM, HDLC,PPP, IrDA, BACnet; được gọi là CRC-CCITT, MMC,SD)
0x1021 hoặc 0x8408 (0x8810 [4])CRC-16-DNP
x 16 + x 13 + x 12 + x 11 + x 10 + x 8 + x 6 + x 5 + x 2 + 1 { displaystyle x ^ { 16 } + x ^ { 13 } + x ^ { 12 } + x ^ { 11 } + x ^ { 10 } + x ^ { 8 } + x ^ { 6 } + x ^ { 5 } + x ^ { 2 } + 1 }IEC 870, M-Bus)
0x3D65 hoặc 0xA6BC (0x9EB2)CRC-16-IBM
x 16 + x 15 + x 2 + 1 { displaystyle x ^ { 16 } + x ^ { 15 } + x ^ { 2 } + 1 }SDLC, USB, khác; còn được biết là CRC-16)
0x8005 hoặc 0xA001 (0xC002)CRC-24-Radix-64
x 24 + x 23 + x 18 + x 17 + x 14 + x 11 + x 10 + x 7 + x 6 + x 5 + x 4 + x 3 + x + 1 { displaystyle x ^ { 24 } + x ^ { 23 } + x ^ { 18 } + x ^ { 17 } + x ^ { 14 } + x ^ { 11 } + x ^ { 10 } + x ^ { 7 } + x ^ { 6 } + x ^ { 5 } + x ^ { 4 } + x ^ { 3 } + x + 1 }FlexRay)
0x864CFB hoặc 0xDF3261 (0xC3267D)CRC-30
x 30 + x 29 + x 21 + x 20 + x 15 + x 13 + x 12 + x 11 + x 8 + x 7 + x 6 + x 2 + x + 1 { displaystyle x ^ { 30 } + x ^ { 29 } + x ^ { 21 } + x ^ { 20 } + x ^ { 15 } + x ^ { 13 } + x ^ { 12 } + x ^ { 11 } + x ^ { 8 } + x ^ { 7 } + x ^ { 6 } + x ^ { 2 } + x + 1 }CDMA)
0x2030B9C7 hoặc 0x38E74301 (0x30185CE3)CRC-32-Adler
Không phải một CRC; xem Adler-32
xem Adler-32CRC-32-IEEE 802.3
x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1 { displaystyle x ^ { 32 } + x ^ { 26 } + x ^ { 23 } + x ^ { 22 } + x ^ { 16 } + x ^ { 12 } + x ^ { 11 } + x ^ { 10 } + x ^ { 8 } + x ^ { 7 } + x ^ { 5 } + x ^ { 4 } + x ^ { 2 } + x + 1 }V.42, MPEG-2, PNG [10])
0x04C11DB7 hoặc 0xEDB88320 (0x82608EDB [6])
CRC-32C (Castagnoli)
x 32 + x 28 + x 27 + x 26 + x 25 + x 23 + x 22 + x 20 + x 19 + x 18 + x 14 + x 13 + x 11 + x 10 + x 9 + x 8 + x 6 + 1 { displaystyle x ^ { 32 } + x ^ { 28 } + x ^ { 27 } + x ^ { 26 } + x ^ { 25 } + x ^ { 23 } + x ^ { 22 } + x ^ { 20 } + x ^ { 19 } + x ^ { 18 } + x ^ { 14 } + x ^ { 13 } + x ^ { 11 } + x ^ { 10 } + x ^ { 9 } + x ^ { 8 } + x ^ { 6 } + 1 }
0x1EDC6F41 hoặc 0x82F63B78 (0x8F6E37A0 [6])CRC-32K (Koopman)
x 32 + x 30 + x 29 + x 28 + x 26 + x 20 + x 19 + x 17 + x 16 + x 15 + x 11 + x 10 + x 7 + x 6 + x 4 + x 2 + x + 1 { displaystyle x ^ { 32 } + x ^ { 30 } + x ^ { 29 } + x ^ { 28 } + x ^ { 26 } + x ^ { 20 } + x ^ { 19 } + x ^ { 17 } + x ^ { 16 } + x ^ { 15 } + x ^ { 11 } + x ^ { 10 } + x ^ { 7 } + x ^ { 6 } + x ^ { 4 } + x ^ { 2 } + x + 1 }
0x741B8CD7 hoặc 0xEB31D82E (0xBA0DC66B [6])CRC-64-ISO
x
64
+
x
4
+
x
3
+
x
+
1{displaystyle x^{64}+x^{4}+x^{3}+x+1}
HDLC — ISO 3309)
0x000000000000001B hoặc 0xD800000000000000 (0x800000000000000D)CRC-64-ECMA-182
x 64 + x 62 + x 57 + x 55 + x 54 + x 53 + x 52 + x 47 + x 46 + x 45 + x 40 + x 39 + x 38 + x 37 + x 35 + x 33 + { displaystyle x ^ { 64 } + x ^ { 62 } + x ^ { 57 } + x ^ { 55 } + x ^ { 54 } + x ^ { 53 } + x ^ { 52 } + x ^ { 47 } + x ^ { 46 } + x ^ { 45 } + x ^ { 40 } + x ^ { 39 } + x ^ { 38 } + x ^ { 37 } + x ^ { 35 } + x ^ { 33 } + }x 32 + x 31 + x 29 + x 27 + x 24 + x 23 + x 22 + x 21 + x 19 + x 17 + x 13 + x 12 + x 10 + x 9 + x 7 + x 4 + x + 1 { displaystyle x ^ { 32 } + x ^ { 31 } + x ^ { 29 } + x ^ { 27 } + x ^ { 24 } + x ^ { 23 } + x ^ { 22 } + x ^ { 21 } + x ^ { 19 } + x ^ { 17 } + x ^ { 13 } + x ^ { 12 } + x ^ { 10 } + x ^ { 9 } + x ^ { 7 } + x ^ { 4 } + x + 1 }
ECMA-182 p. 63)
0x42F0E1EBA9EA3693 hoặc 0xC96C5795D7870F42 (0xA17870F5D4F51B49)Đã từng tồn tại, nhưng không còn sử dụng trong công nghệ—hầu hết được thay thế bằng các hàm mật mã băm (cryptographic hash functions):
- CRC-128 (IEEE)
- CRC-256 (IEEE)
