CRC 校驗的原理及代碼實現
一、CRC 校驗介紹
循環冗餘校驗碼（CRC），是一種常用的、具有檢錯、糾錯能力的校驗碼，在早期的通信中運用廣泛。循環冗餘校驗碼常用於外存儲器和計算機同步通信的數據校驗。循環冗餘校驗是通過某種數學運算來建立數據位和校驗位的約定關係的。
與奇偶校驗、和校驗、異或校驗等校驗方式不同，CRC 校驗的計算過程相對複雜很多。
二、模 2 除法介紹
CRC 校驗原理雖然看起來比較複雜，其實也不難理解，其根本思想就是先在要發送的幀後面附加一個數，生成一個新幀發送給接收端。當然，這個附加的數不是隨意的，它要使所生成的新幀能與發送端和接收端共同選定的某個特定數整除。
這裏不是直接採用二進制除法，而是採用一種稱之爲 “模 2 除法”。到達接收端後，再把接收到的新幀除以（同樣採用“模 2 除法”）這個選定的除數。因爲在發送端發送數據幀之前就已通過附加一個數，做了“去餘” 處理，所以結果應該是沒有餘數，結果能夠被除數整除。如果有餘數，則表明該幀在傳輸過程中出現了差錯。
這裏，爲了能夠對 CRC 校驗有深入瞭解，我們來介紹一下模 2 除法。與 “算術除法” 類似，但它既不向上位借位，也不比較除數和被除數的相同位數值的大小，只要以相同位數進行相除即可。
模 2 減法運算實際上是按位異或運算。也就是比較後，兩者對應位相同則結果爲 “0”，不同則結果爲 “1”。如下圖所示，二進制的數 1010101 除以 1001，結果得到商爲 1011，餘數爲 110。
三、CRC 校驗原理
上面我們對 CRC 校驗進行了簡單介紹，下面我們就來看看 CRC 校驗是如何實現的。
首先，爲了進行 CRC 校驗，發送端和接收端要約定一個除數，這個除數通常是以多項方式表示，這個多項式也稱之爲 “生成多項式”。如常用的多項式 x4 + x + 1，表示的除數爲 10011，多項式 x16 + x15 + x2 + 1 表示的除數爲 11000000000000101，下表列出了常用的除數多項式公式。
選定了除數之後，需要在要發送的數據後面加上 k-1 位 “0”，k 爲除數的位數。然後以這個加了 k-1 個“0“的新數（一共是 m+k-1 位）以“模 2 除法” 方式除以上面這個除數，所得到的餘數就是這個數據的 CRC 校驗碼。但要注意的是，餘數的位數一定要是比除數位數只能少一位，即使前面位是 0，甚至是全爲 0（附帶好整除時）也都不能省略。
最後，再把這個校驗碼附加在原數據後面，構建一個新幀發送到接收端；最後在接收端再把這個新幀以 “模 2 除法” 方式除以前面選擇的除數，如果沒有餘數，則表明該幀在傳輸過程中沒出錯，否則出現了差錯。
下面，我們通過一個例子來說明一下，CRC 校驗的計算過程。
假設我們計算十六進制數 0xBB 的 CRC 校驗碼，我們使用的生成多項式爲 x4 + x + 1。則待計算的數表示爲二進制位 1011 1011，除數爲 10011。由於生成多項式的位數爲 5，根據上面的介紹，得知 CRC 校驗碼的位數爲 4（校驗碼的位數比生成多項式的位數少 1）。因此在原始數據後面再加 4 個 0，得到 1011 1011 0000，然後把這個數以 “模 2 除法” 方式除以生成多項式，得到的餘數（即 CRC 碼）爲 1111，如下圖所示。
把上步計算得到的 CRC 校驗 1111 替換原始幀 1011 1011 0000 後面的四個 “0”，得到新幀 1011 1011 1111。再把這個新幀發送到接收端。當以上新幀到達接收端後，接收端會把這個新幀再用上面選定的除數 10011 以“模 2 除法” 方式去除，驗證餘數是否爲 0，如果爲 0，則證明該幀數據在傳輸過程中沒有出現差錯，否則出現了差錯。
四、CRC 校驗的 c 代碼實現
CRC 校驗的計算過程比較複雜，一般代碼實現採用查表的方法。下面的代碼是 CRC16 校驗實現的代碼，對應的 CRC 算法爲 CRC-16/MODBUS，生成多項式爲 x16 + x15 + x2 + 1。
注意：示例代碼得到的 CRC 結果中，高 8 位在前，低 8 位在後。需要根據具體的應用場景進行調整。
原文： https://blog.csdn.net/bhniunan/article/details/111031467
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/iUlh86Ln4TI6hkFNTp-Uzg