天天看點

【Linux】詳解CRC校驗

 1. CRC校驗概念      CRC即循環備援校驗碼:是資料通信領域中最常用的一種查錯校驗碼,其特征是資訊字段和校驗字段的長度可以任意標明。循環備援檢查(CRC)是一種資料傳輸檢錯功能,對資料進行多項式計算,并将得到的結果附在幀的後面,接收裝置也執行類似的算法,以保證資料傳輸的正确性和完整性。

2.CRC校驗原理

     CRC校驗原理看起來比較複雜,好難懂,因為大多數書上基本上是以二進制的多項式形式來說明的。其實很簡單的問題,其根本思想就是先在要發送的幀後面附加一個數(這個就是用來校驗的校驗碼,它是二進制序列),進而生成一個新幀發送給接收端。當然,這個附加的數不是随意的,它要使所生成的新幀能與發送端和接收端共同標明的某個特定數整除(注意,這裡不是直接采用二進制除法,而是采用一種稱之為“模2除法”)。到達接收端後,再把接收到的新幀除以(同樣采用“模2除法”)這個標明的除數。因為之前在發送端發送資料幀時就已認證附加一個數(校驗碼),做了“去餘”處理(也就已經能整除了),是以結果應該是沒有餘數。如果有餘數,則表明該幀在傳輸過程中出現了差錯。

【關于模2除法的說明】 模2除法與算術除法類似,但其對每一位除的結果不會影響其他位,相當于二進制中的邏輯異或運算。當也就是比較後,兩者對應位相同則結果為“0”,不同則結果為“1”。如圖所示。當餘數位數與除數的位數相同時,商為1,并進行異或運算;當餘數的位數與除數位數不相同時,進行補位,補位的位置商為0,還不相同繼續補位,商為0,直至相同時,就進行商1,還有異或運算。如此反複。

【Linux】詳解CRC校驗

3. CRC校驗的步驟

  (1)先選擇一個用于在接收端進行校驗時,對接收的幀進行除法運算的除數(是二進制比較特串,通常是以多項方式表示,是以CRC又稱多項式編碼方法,這個多項式也稱之為“生成多項式”)。

  (2)看所標明的除數二進制位數(假設為k位),然後在要發送的資料幀(假設為m位)後面加上k-1位“0”,然後以這個加了k-1個“0“的新幀(一共是m+k-1位)以“模2除法”方式除以上面這個除數,所得到的餘數(也是二進制的比特串)就是該幀的CRC校驗碼,也稱之為FCS(幀校驗序列)。但要注意的是,餘數的位數一定要是比除數位數隻能少一位,哪怕前面位是0,甚至是全為0(附帶好整除時)也都不能省略。

  (3)再把這個校驗碼附加在原資料幀(就是m位的幀,注意不是在後面形成的m+k-1位的幀)後面,建構一個新幀發送到接收端;最後在接收端再把這個新幀以“模2除法”方式除以前面選擇的除數,如果沒有餘數,則表明該幀在傳輸過程中沒出錯,否則出現了差錯。

  通過以上介紹,大家一定可以了解CRC校驗的原理,并且不再認為很複雜吧。

4.  CRC校驗碼的計算示例

  CRC校驗的關鍵是如何求出餘數,也就是CRC校驗碼。

  以一個例子來具體說明整個過程。現假設選擇的CRC生成多項式為G(X) = X^4 + X^3 + 1,要求出二進制序列10110011的CRC校驗碼。下面是具體的計算過程:

  (1)首先把生成多項式轉換成二進制數,由G(X) = X^4 + X^3 + 1可以知道(它一共是5位(總位數等于最高位的幂次加1,即4+1=5),然後根據多項式各項的含義(多項式隻列出二進制值為1的位,也就是這個二進制的第4位、第3位、第0位的二進制均為1,其它位均為0)很快就可得到它的二進制比特串為11001。

  (2)因為生成多項式的位數為5,根據前面的介紹,得知CRC校驗碼的位數為4(校驗碼的位數比生成多項式的位數少1)。因為原資料幀10110011,在它後面再加4個0,得到101100110000,然後把這個數以“模2除法”方式除以生成多項式11001,得到的餘數(即CRC校驗碼)為0100,如圖。

【Linux】詳解CRC校驗

    (3)把上步計算得到的CRC校驗0100替換原始幀101100110000後面的四個“0”,得到新幀101100110100。再把這個新幀發送到接收端。

  (4)當以上新幀到達接收端後,接收端會把這個新幀再用上面標明的除數11001以“模2除法”方式去除,驗證餘數是否為0,如果為0,則證明該幀資料在傳輸過程中沒有出現差錯,否則出現了差錯。

繼續閱讀