Tài liệu Cài đặt thuật toán tính crc mạng máy tính và truyền số liệu

0 Đề tài : Cài đặt thuật toán tính CRC TRƯỜNG ĐẠI HỌC KINH TẾ QUỐC DÂN BỘ MÔN CÔNG NGHỆ THÔNG TIN Môn : Mạng máy tính và truyền số liệu Đề tài : Cài đặt thuật toán tính CRC Sinh viên : Vũ Văn Linh Phan Đình Lợi Nguyễn Thị Mai Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 1 Đề tài : Cài đặt thuật toán tính CRC Hà Nội 5/2010 Lời mở đầu Mạng máy tính phát sinh từ nhu cầu muốn chia sẻ, dùng chung tài nguyên và cho phép giao tiếp trực tuyến (online) cũng như các ứng dụng đa phương tiện trên mạng. Tài nguyên gồm có các phần mềm (dữ liệu, chương trình ứng dụng,...) và tài nguyên phần cứng (máy in, máy quét, CD ROM , ...). Giao tiếp trực tuyến bao gồm gửi và nhận thông điệp, thư điện tử. Các ứng dụng đa phương tiện có thể phát là phát thanh, truyền hình, điện thoại qua mạng, hội thảo trực tuyến, nghe nhạc, xem phim trên mạng... Trong giáo trình Mạng máy tính và truyền số liệu mà chúng ta đang nghiên cứu, có một phần rất quan trọng đó là : Các vấn đề liên quan đến mạng máy tính. Và đề tài mà chúng tôi tìm hiểu đó là : " Cài đặt thuật toán tính CRC ", đây là một phần khá quan trọng liên quan đến các vấn đề của mạng. Bài báo cáo của nhóm tôi gồm 3 phần : Phần 1 : Giới thiệu Phần 2 : Nội dung Phần 3 : Chạy chương trình Dù đã tìm hiểu rất kỹ nhưng trong bài báo cáo không tránh khỏi thiếu sót. Chúng tôi xin trân trọng tiếp thu tất cả những ý kiến đóng góp của cô và các bạn để hoàn thiện bản báo cáo này hơn nữa. Xin trân thành cảm ơn ! Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 2 Đề tài : Cài đặt thuật toán tính CRC Mục lục Phần I : Giới thiệu...................................................................................... Phần II : Nội dung...................................................................................... II.1. Định nghĩa.................................................................................. - CRC là gì ?....................................................................... - Giới thiệu chung về CRC .............................................. II.2. Tư tưởng của phương pháp CRC............................................... II.3. Thuật toán................................................................................. II.4. Tính toán CRC.......................................................................... Cách tính CRC-8 trong việc kiểm soát lỗi dữ liệu được truyền............................................................................................ II.4.2.Cách 2: Phương pháp Table-Driven ........................ II.4.1. Cách 1: Phương pháp Direct Calculation ................ II.5. Các hàm CRC thường dùng và được tiêu chuẩn hóa.......... II.6. Chương trình chạy.................................................................. II.7. Ứng dụng thực tế................................................................. Phần III : Tổng kết................................................................................ Phần IV : Tài liệu tham khảo............................................................... Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 3 Đề tài : Cài đặt thuật toán tính CRC Phần I. Giới thiệ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? 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. Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 4 Đề tài : Cài đặt thuật toán tính CRC Phần II : Nội dung II.1. Định nghĩa CRC là gì ? 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. Giới thiệu chung về CRC Mặc dù các mã CRC có thể 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ất cả các mã CRC thường dùng đều sử dụng trường hữu hạn GF(2). Đây là trường hai phần tử, thường được ký hiệu là 0 và 1, phù hợp 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 trong 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 Trường ĐH Kinh Tế Quốc Dân Môn : Mạng máy tính và truyền số liệu 5 Đề tài : Cài đặt thuật toán tính CRC 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 giản nhất, bit parity (xet 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. II.2. Tư tưởng của phương pháp CRC - Cho trước một đa thức (gọi là đa thức sinh) G(x) với hệ số bậc cao nhất và thấp nhất đều bằng 1. - Tìm tập bít kiểm tra Checksum thỏa mãn điều kiện : đa thức tương ứng với xâu ghép (xâu gốc và checksum) phải chia hết (theo modulo 2) cho G(x). - Khi nhận tin, bên nhận kiểm tra lỗ bằng cách lấy xâu bít nhận được chia (modulo 2) cho G(x). Nếu không chia hết thì có nghĩa là đã có lỗi (ngược lại thì cũng chưa thể khẳng định là không có lỗi). - Giả sử G(x) có bậc là r, xâu bít gốc tương ứng với đa thức M(x) có bậc m. Các bước tính Checksum như sau : B1 : Thêm r bít 0 vào cuối xâu bít cần truyền : xâu ghép sẽ gồm có m + r bít tương ứng với đa thức x^r M(x). B2 : Chia (Modulo 2) xâu bít tương ứng cho xâu bít tương ứng với G(x). B3 : Lấy xâu bit bị chia trừ (modulo 2) cho số dư. Kết quả là xâu bit được truyền đi (xâu gốc + checksum). Ký hiệu đa thức tương ứng với nó là T(x), rõ ràng T(x) chia hết (modulo 2) cho G(x). Thí dụ áp dụng : Cho xâu bit 1101010111, đa thức sinh G(x) = x^4+x^3+x+1, hãy tính xâu bít được truyền đi trên mạng. Xâu bít gốc 1101010111 tương ứng với đa thức M(x) = x^9+x^8+x^6+x^4+x^2+x+1. Đa thức sinh G(x) = x^4+x^3+x+1 tương ứng với xâu bit 11011. X^r M(x) = 11010101110000 Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 6 Đề tài : Cài đặt thuật toán tính CRC 1000100001 11011 11010101110000 11011 11011 11011 010000 10011 0011 Checksum Kết quả : Checksum = 0011 Xâu bít được truyền đi trên mạng là : T(x) = 11010101110011. II.3. Thuật toán Bài toán: tìm chuỗi bit đầu ra của chuỗi dữ liệu cần truyền M với đa thức sinh P. Cách làm: Đầu vào: Nhập chuỗi M dưới dạng nhị phân( 0,1) Chuỗi P dưới dạng nhị phân có r+1 bit và ngắn hơn chuỗi M Thao tác: 1. Thêm r số 0 vào sau chuỗi M, tức là ta thực hiện phép toán M.2r 2. Tính FCS là số dư của phép chia M.2r cho P. 3. Ghép số dư vào đuôi của chuỗi M ta được chuỗi mới M|FCS( là chuỗi ra) Đầu ra: In ra chuỗi M|FCS Ví dụ: Chuỗi dữ liệu cần truyền M = 11100011 ( 8 bit) Đa thức sinh P =110011 có 6 bit(  r=5), vậy ta thêm 5 số 0 vào sau của chuỗi M(x) ta được chuỗi M(x).2r có dạng là 1110001100000. Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 7 Đề tài : Cài đặt thuật toán tính CRC Lấy chuỗi này chia cho P bằng cách sau( ở đây phép chia được hiểu là 1 số lần của phép trừ nhưng không có “nhớ” hay “mượn” như các phép toán nhị phân thông thường ): 1110001100000(trừ) 110011 --------------0010111100000, dịch sang trái 2 bit vì 2 số 0 đầu bỏ đi, thành 10111100000(trừ) 110011 ------------01110000000, dịch trái 1 bit, thành 1110000000(trừ) 110011 ----------0010110000, lại dịch trái 2 bit, thành 10110000(trừ) 110011 ------01111100, dịch trái 1 bit, thành 1111100(trừ) 110011 -------0011010, dịch trái 2 bit thành 11010, số này có số chữ số là 5, nhỏ hơn 6 là số chữ số của P, không chia được và là số dư. Vậy FCS( hay số dư của phép chia) sẽ là 11010. Ghép với M ta được M|FCS : 1110001111010 Đây là chuỗi cần tìm. II.4. Tính toán CRC Cách tính CRC-8 trong việc kiểm soát lỗi dữ liệu được truyền II.4.1. Cách 1: Phương pháp Direct Calculation Giả sử ta có chuỗi data như sau: MSB LSB 10000000 00000001 10100011 = Data String (80 01 A3 h) Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 8 Đề tài : Cài đặt thuật toán tính CRC Đa thức sử dụng để tính CRC-8: g(D) = D8 + D2 + D + 1 => 1 0000 0111 (Polynomial) Tư tưởng chính là ta cứ thực hiện phép XOR giữa data string và polynomial. Đối với chuỗi data string, ta thêm 8 bits 0 vào cuối (ở vị trí LSB) 1 lần duy nhất trước khi thực hiện các phép XOR sau đó. Lưu ý là bit đầu tiên trong Polynomial ( 1 0000 0111 ) được align thẳng hàng với bit có giá trị là 1 đầu tiên trong data string tính từ MSB ( 1 0000000 00000001 10100011 00000000 ) Phép XOR có rule như sau: 0 + 0 => 0 1 + 1 => 0 0 + 1 => 1 1 + 0 => 1 Điều kiện dừng của phép lặp XOR là khi ta align polynomial với data string thì tính từ vị trí xuất hiện giá trị 1 đầu tiên của data string đến cuối data string không đủ 8 bit. Nên kết quả data string của phép XOR cuối cùng chính là CRC-8 10000000 00000001 10100011 => data string 10000000 00000001 10100011 00000000 (add 8 bits value 0) 10000011 1 (polynomial) 00000011 10000001 10100011 00000000 (XOR between data string and polynomial) 10 0000111 (move polynomial to the next appear of value 1 in data string) 01 10001111 10100011 00000000 1 00000111 0 10001000 10100011 00000000 10000011 1 00001011 00100011 00000000 1000 00111 0011 00011011 00000000 10 0000111 II.4.2.Cách 2: Phương pháp Table-Driven Giả sử ta có chuỗi data như sau: MSB LSB 10000000 00000001 10100011 00000000 = Data String (80 01 A3 h). 1. Khởi tạo 1 biến 1 byte với giá trị là 0 (8 bits đều là 0). 2. Thực hiện phép XOR giữa data string với byte vừa khởi tạo đó. 3. Giá trị sau khi XOR của byte đầu tiên được sử dụng để tra trong bảng tìm kiếm. Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 9 Đề tài : Cài đặt thuật toán tính CRC Cách tra như sau: - Bảng có giá trị index từ 0->255 (ví dụ tên bảng là tbl) nên khi giá trị cần tra là 00010010b (18 dec) => kết quả trả về là tbl[ 18 ] là 0x7E (01111110b) 4. Dịch chuỗi data string 8 bits về bên trái 5. Tiếp tục thực hiện phép XOR giữa chuỗi data string và kết quả vừa tra được trong bảng tìm kiếm (lưu ý là chúng ta luôn so byte đầu tiên bên MSB) 6. Thực hiện tương tự cho đến byte cuối cùng thì kết quả tra được chính là CRC-8 10000000 00000001 10100011 00000000 (data string) 00000000 (init variable) 10000000 00000001 10100011 00000000 (XOR result) 10001001 (result in lookup table) 00000001 10100011 00000000 (shift 8th bit of data string to left) 10001000 (XOR with above result lookup table) 10110001 (result in lookup table) 10100011 00000000 (shift 8th bit of data string to left) 00010010 (XOR with above result lookup table) 01111110 (result in lookup table) 00000000 (shift 8th bit of data string to left) 01111110 => CRC Cách tạo bảng tham chiếu CRC: Để tạo bảng tham chiếu CRC, ta làm như sau: 1. Tạo 1 mảng 1 chiều 256 phần tử 2. Duyệt từng phần tử trong bảng, gán giá trị của crc bằng index của phần tử đang xét 3. Duyệt từng bit trong crc đang xét, nếu bit đầu của crc là 0x01 thì dịch trái crc 1 bit và thực hiện hiện phép bù bit với 0x07, còn nếu không thì chỉ thực hiện dịch trái 1 bit mà thôi. Thực hiện với tất cả các bit của crc 4. Cập nhật lại giá trị crc mới vào bảng và duyệt tiếp các phần tử còn lại. void CCRC8Dlg::isb_WiMAX_POM_gen_crc8_table() { uint16_t index_ui16;/*table index*/ uint8_t bit_ui8;/*bit counter*/ uint8_t crc_ui8;/* CRC result*/ for ( index_ui16 = 0; index_ui16 < 256; index_ui16++ ) Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 10 Đề tài : Cài đặt thuật toán tính CRC { crc_ui8 = index_ui16; for ( bit_ui8 = 0; bit_ui8 < 8; bit_ui8++ ) { if ( crc_ui8 & 0x80 ) crc_ui8 = ( crc_ui8 << 1 ) ^ ISB_WiMAX_POM_CRC8_POLYNOMIAL_K; else crc_ui8 = ( crc_ui8 << 1 ); } isb_WiMAX_pommgr_info_str_g.crc8Table_ui8[index_ui16] = crc_ui8; } } II.5. Các hàm CRC thường dùng và được tiêu chuẩn hóa 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, í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 được biết đến. Các đa thức thường được xem như không phải là tối ưu nhất 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, và không gian 24 và 32 bit, 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 tực tìm lỗi cho các tiêu chuẩn trong tương lai. Far from being arbitrarily chosen, đa thức phổ biển CRC-32 , được IEEE giới thiệu và được dùng trong V.42, Ethernet, FDDI và ZIP và các filePNG 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 trong các kênh truyền thông. 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 trong các môi trường Internet SCSI. Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 11 Đề tài : Cài đặt thuật toán tính CRC Bảng dưới đây chỉ liệt kê những đa thức của những thuật toán đa dạng đang được sử dụng. Bất kỳ giao thức cá biệt. Tên Các biểu diễn: thông thường hoặc nghịch đảo (đảo của đảo) Đa thức CRC x + 1 (hầu hết phần cứng; còn biết với tên parity bit) -1 0x1 or 0x1 (0x1) CRC -4- x4 + x + 1 (ITU G.704, p. 12) ITU 0x3 or 0xC (0x9) CRC -5- x5 + x4 + x2 + 1 (ITU G.704, p. 9) ITU 0x15 or 0x15 (0x1A) CRC -5- x5 + x2 + 1 (USB token packets) USB 0x05 or 0x14 (0x12) CRC -6- x6 + x + 1 (ITU G.704, p. 3) ITU 0x03 or 0x30 (0x21) CRC x7 + x3 + 1 (Các hệ thống viễn thông, MMC,SD) 0x09 or Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 12 Đề tài : Cài đặt thuật toán tính CRC -7 0x48 (0x44) CRC -8x8 + x2 + x + 1 (ATM HEC) AT M 0x07 or 0xE0 (0x83) CRC -8x8 + x7 + x3 + x2 + 1 (1-Wire bus) CCI TT 0x8D or 0xB1 (0xC6) CRC -8Dall x8 + x5 + x4 + 1 (1-Wire bus) as/M axim 0x31 or 0x8C (0x98) CRC 8 x + x7 + x6 + x4 + x2 + 1 -8 0xD5 or 0xAB (0xEA [3]) CRC -8SAE x8 + x4 + x3 + x2 + 1 J185 0 0x1D or 0xB8 (0x8E) CRC 10 x + x9 + x5 + x4 + x + 1 -10 0x233 or 0x331 (0x319) Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 13 Đề tài : Cài đặt thuật toán tính CRC CRC 11 x + x9 + x8 + x7 + x2 + 1 (FlexRay) -11 0x385 or 0x50E (0x5C2) CRC 12 x + x11 + x3 + x2 + x + 1 (Các hệ thống viễn thông ) -12 0x80F or 0xF01 (0xC07) CRC -15- 15 x + x14 + x10 + x8 + x7 + x4 + x3 + 1 CA N 0x4599 or 0x4CD1 (0x62CC ) CRC -16Không phải một CRC; xem Fletcher's checksum Fletc her Sử dụng trong Adl er-32 A & B CRC CRC 16 x + x12 + x5 +1 (X.25, V.41, CDMA, Bluetooth, XMODEM, -16HDLC,PPP, IrDA, BACnet; known as CRCCCI CCITT, MMC,SD) TT 0x1021 or 0x8408 (0x8810) CRC 16 x + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1 (DNP, IEC -16870, M-Bus) DNP 0x3D65 or 0xA6BC (0x9EB2) CRC x16 + x15 + x2 + 1 (SDLC, USB, khác; còn được biết là CRC- 0x8005 -16- 16) or IBM 0xA001 Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 14 Đề tài : Cài đặt thuật toán tính CRC (0xC002) 0x864CF CRC B or 24 23 18 17 14 11 10 7 6 5 4 3 -24- x + x + x + x + x + x + x + x + x + x + x + x + x 0xDF326 Radi + 1 (FlexRay) 1 x-64 (0xC326 7D) 0x2030B 9C7 or 30 29 21 20 15 13 12 11 8 7 6 2 CRC x + x + x + x + x + x + x + x + x + x + x + x + x 0x38E74 -30 + 1 (CDMA) 301 (0x30185 CE3) CRC -32Không phải một CRC; xem Adler-32 Adle r xem Adle r-32 CRC 0x04C11 -32DB7 or 32 26 23 22 16 12 11 10 8 7 5 4 2 IEE x + x + x + x + x + x + x + x + x + x + x + x + x 0xEDB8 E + x + 1 (V.42, MPEG-2,PNG ) 8320 802. (0x82608 3 EDB) CRC x32 + x28 + x27 + x26 + x25 + x23 + x22 + x20 + x19 + x18 + x14 + x13 -32C + x11 + x10 + x9 + x8 + x6 + 1 (Cas tagn oli) Trường ĐH Kinh Tế Quốc Dân liệu 0x1EDC 6F41 or 0x82F63 B78 (0x8F6E Môn : Mạng máy tính và truyền số 15 Đề tài : Cài đặt thuật toán tính CRC 37A0 ) CRC 32K x32 + x30 + x29 + x28 + x26 + x20 + x19 + x17 + x16 + x15 + x11 + x10 (Ko + x7 + x6 + x4 + x2 + x + 1 opm an) 0x741B8 CD7 or 0xEB31 D82E (0xBA0D C66B) CRC -64- x64 + x4 + x3 + x + 1 (HDLC — ISO 3309) ISO 0x00000 0000000 001B or 0xD8000 0000000 0000 (0x80000 0000000 000D) 0x42F0E 1EBA9E CRC 64 A3693 or x + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 + x40 + x39 -640xC96C5 + x38 + x37 + x35 + x33 + x32+ x31 + x29 + x27 + x24 + x23 + x22 + x21 EC 795D787 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1 (as described MA0F42 in ECMA-182 p.63) 182 (0xA178 70F5D4F 51B49) Trường ĐH Kinh Tế Quốc Dân liệu Môn : Mạng máy tính và truyền số 16 Đề tài : Cài đặt thuật toán tính CRC II.6. Chương trình chạy #include #include #include main() { char m[64], p[32],fcs[32]; int i,j=-1,k; // nhap chuoi nhi phan a1: printf("\n nhap vao chuoi bit: "); gets(m); int b=strlen(m); //do dai chuoi m for(i=0; i - Xem thêm -