CRC
循環冗余碼（Cyclic Redundancy Code， CRC）是一種用于校驗通信鏈路上數字傳輸準確性的計算方法（通過某種數學運算來建立數據位和校驗位(CRC)的約定關系的）。它是利用除法以及余數的原理來作錯誤偵測。
發送方: 使用某公式計算出被傳送數據所含信息的一個值，并將此值 附在被傳送數據后。
接收方: 對同一數據進行相同的計算，應該得到相同的結果。對比CRC結果。
數學背景
模二運算
模二運算，是一種二進制的四則運算，包括模二加(+)、模二減(-)、模二乘(x)、模二除(/) 四種二進制運算。與四則運算不同的是模二運算不考慮進位和借位.
重點
- 模二加法和模二減法的結果是相同的，并且與異或（XOR）運算的結果是一致的。 異或運算可以代替模二加減運算。可用硬件XOR異或門硬件代替運算。
- 模二乘法可看作兩個步驟， 可用AND與門代替運算。
a. 第一步被乘數的位跟乘數進行與運算，再根據被乘數的階進行左移被乘數的階數位，被乘數的位數對應n個部分積。
b. 部分積進行模二加法運算。 - 模二乘除法與普通乘除法一樣演算，區別是模二除法的被除數部分的階數與除數P的階數相同時，進行部分XOR異或運算，得到商數和余數，將余數的階數與除數P循環計算，直到余數的階數小于R，這個余數就是附加的校驗碼。
關注模二除法，因為它與CRC算法密切相關，它有三個性質： - 當最后余數的位數小于除數位數時，除法停止。
- 當被除數的位數小于除數位數時，則商數為0，被除數就是余數。
- 只要被除數或部分余數的位數與除數一樣多，且最高位為1，不管其他位是什么數，皆可商1。
二進制多項式
對任意的二進制數都構造與其對應的一個二進制系數多項式。
例如：10011B，其對應的二進制系數多項式為P(X) = X^4 +X +1。
CRC算法中，對于二進制數都是以二進制系數多項式去描述的,。
CRC算法
CRC 算法的基本思想是將要傳輸數據后面填充N個0（既是傳輸數據信息左移N位）當做一個包含數據的多項式。將左移后的數據多項式 模二除以另一個生成多項式（Poly），得到的余數作為(CRC)校驗數據附加到原數據后面。（模二除，CRC取余）
g(x)為校驗碼的生成多項式（上文中，除數的二級制多項式poly），不同的位數的CRC多項式，對應生成多項式的次冪不同，其糾錯能力也不同。常見的標準多項式如下。
CRC-8算法為例，該算法生成多項式G(X)為
.除數p(x)為0b10000 0111。
CRC算法參數模型
NAME：參數模型名稱，決定了CRC位寬和POLY生成多項式。
WIDTH：寬度，即CRC位數。
POLY：生成項的簡寫，以16進制表示。例如：CRC-32即是0x04C11DB7，忽略了最高位的"1"，即完整的生成項是0x104C11DB7。
INIT：這是計算CRC循環冗余碼時，在數據后面預填充的預置值，十六進制表示。
REFIN：控制輸入數據是否進行反轉操作，True或False。若False，則輸入數據的比特順序反轉，通常是將最高有效位（MSB）變為最低有效位（LSB）。
REFOUT：控制輸出CRC校驗值是否進行反轉操作。在計算左移后數據多項式模二除以生成多項式后，余數（即CRC校驗值）是否按位反轉，True或False。
XOROUT：計算結果與此參數異或后得到最終的CRC值。
數據m(x)=0x31 ,CRC-8算法為例，該算法生成多項式G(X)為
.除數p(x)為0b10000 0111。數據m(x)左移八位即x8m(x)=0x3100。 p(x) 模二除以x8m(x)的余數為0x97.
以CRC-16/DNP算法為例，
● 多項式公式G(X)為x16 + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1，除數為p(x)=0x13D65= 0b10011 1101 0110 0101。
● 數據m(x)為=0x31=0b0011 0001。由于CRC-16/DNP模型的輸入數據反轉，其值RefIn m(x) =0b1000 1100 =0x8C。數據m(x)左移16位即x16RefInm(x)=0x8C0000。
● x16RefIn m(x) = 0x8C0000模二除以p(x) = 0x13D65 的余數為r(x)=0b0101 1001 1011 0101=0x59b5.輸出數據翻轉RefOut r(x)=0b1010 1101 1001 1010 =0xAD9A。
● 結果異或值XorOut為0xFFFF,CRC-16/DNP算法的CRC值= 結果異或值XorOut 按位異或 輸出數據翻轉RefOut r(x)，即RefOut r(x) ^ XorOut 。其值為0xAD9A ^ 0xFFFF = 0xE265。
傳統CRC算法
實際應用時，發送方和接收方按以下方式通信：
發送方和接收方在通信前，約定好一個預設除數P(X)。P(X)首位和最后一位的系數必須為1. 以上面的CRC-8為例，多項式（poly）為X8 + X2 + X +1,對應除數P(X) = 10011.
發送方在發送前，將原始數據左移 除數P(X)的次冪的位，將其值進行模二除法運算生成余數F(X)（即CRC碼），然后將其附加到原始數據后面一起T(X)發送給接收方。
接收方收到后將其T(X)模二除以約定好的除數P(X)，當且僅當余數為0時接收方認為沒有差錯.
CRC校驗碼的編碼方法是用待發送的二進制數據D(x)昧以生成多項式G(x)，將最后的余數作為CRC校
驗碼。其實現步驟如下：
①沒待發送的數據塊是P位的二進制多項式D(x)．生成多項式為i階的G(x)。在數據塊的末尾掭加i
個0．數據塊的長度增加到m+i位．對應的二進制多項式為xiD(x).
②用生成多項式G(x)去除xiD(x)，求得余數為階數為i-1的二進制多項式R(x)。此二進制多項式R(x)
就是D(x)經過生成多項式G(x)編碼的CRC校驗碼。
③用xiD(x)以模2的方式減去R(x)，得到二進制多項式xiD’(x)。xiD’(x)就是包含了CRC校驗碼的
待發送字符串。
基于查表法的CRC算法
計算機操作單元一般為字節為單位，所以采用一個或者多個字節長度的CRC進行校驗傳遞數據，提高CRC校驗速度。 預先將CRC計算出來，并存到校驗表里，且校驗表存在 該行的首個CRC碼與該列的首個CRC碼的異或值 與他們交集的CRC碼相同，每次調用CRC算法采用查表法替代移位計算發放，可提升計算速度。
以8bit 一個字節長度的CRC為例，有256種情況，對應余數有0~255種，將256種余數分別計算出來，按照順序存放在一個包含256個入口地址的校驗表中，然后對輸入數據流采用查表來實現。
設置數據流為,
數學表達式為
,其中⊕為異或運算符。生成多項式為G(x)17bit,則CRC碼為CRC16,數學表示式為
CRC校驗可以100％地檢測出所有奇數個隨機錯誤和長度小于或等于i(i為g(x)的階數)的突發錯誤。
所以CRC的生成多項式的階數越高，那么誤判的概率就越小。
參考鏈接
【科普向】誰都能看懂的CRC（循環冗余校驗）原理：https://blog.csdn.net/weixin_44256803/article/details/105805628
什么是CRC：https://info.support.huawei.com/info-finder/encyclopedia/zh/CRC.html
CRC校驗查表法原理及實現（CRC-16）： https://blog.csdn.net/AgonyRR/article/details/107810982
CRC循環冗余校驗 查表算法的代碼實現:https://blog.csdn.net/weixin_44256803/article/details/111794445
CRC在線計算： http://www.ip33.com/crc.html
[1]馬群,王會燃.基于查表法的嵌入式系統CRC算法研究[J].軟件導刊,2014,13(10):51-52.
)
