––––•(-• (Last † Kill) •-)•––––


    Trình bày thuật toán CRC.

    Share

    Admin
    Admin

    Tổng số bài gửi : 58
    Join date : 05/05/2011
    Age : 26

    Trình bày thuật toán CRC.

    Bài gửi  Admin on Sun Jun 05, 2011 10:42 am

    CRC (2 điểm)
    (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.
    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ù 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.
    Tính toán CRC (2 điểm)
    Để tính toán một mã nhị phân n bit CRC, xếp các bít biểu diễn đầu vào thành một hàng, và đặt mẫu (n+1) bit 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 là phép tính đầu tiên để tính một hàm CRC 3 bít:
    11010011101100 <--- Đầu vào
    1011 <--- Số chia (4 bit = 3 + 1 bit)
    --------------
    01100011101100 <--- Kết quả (--> Lại đưa vào đầu vào của phép tính tiếp theo)
    Nếu dãy nhị phân đầu vào bên trên có bít cực tả (đầu tiên 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ố đầu 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, quá trình cứ tiếp diễn như vậy đến khi số chia chạm tới tận cùng bên phải của dãy số đầu vào. Đây là phép tính cuối cùng:
    00000000001110 <--- Kết quả của phép nhân
    1011 <--- Số chia
    --------------
    00000000000101 <--- Số dư (3 bits)
    Do cực tả của số chia sẽ làm các bít tương ứng của dãy số đầu vào trở về 0 qua mỗi lần dịch, khi quá trình này kết thúc, chỉ còn những bít ở dãy đầu vào 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 được gọi cho một số công đoạn tiền xử lý).
    Những hàm CRC thường dùng và được tiêu chuẩn hóa (1 điểm)
    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[1], í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[2] đượ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[3], và không gian 24 và 32 bit,[4][5] 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 cac tiêu chuẩn trong tương lai[5].
    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 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[6] 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[5] trong các môi trường Internet SCSI.

      Hôm nay: Thu Sep 21, 2017 4:47 am