[導讀]之前在做學校項目的環冗時候用到了CRC原理，但在網上查找的余校驗的原理過程中，發現講解CRC知識的實現資源很多，但是環冗對新手比較友好的、講的余校驗的原理十分清楚的又很少，很多資料也不完善，實現讀起來心中常常不由自主地奔騰過上千個“為什么”“為什么”，環冗本文盡可能的余校驗的原理對新手友好、解答CRC里面的實現一些知識點，而不是環冗簡單的應用。 依據學習目的余校驗的原理不同，如果大家只想簡單應用，實現不求原理，環冗那么直接復制--粘貼最后的余校驗的原理代碼即可。
之前在做學校項目的實現時候用到了CRC 原理，但在網上查找的過程中，發現講解CRC知識的資源很多，但是對新手比較友好的、講的十分清楚的又很少，很多資料也不完善，讀起來心中常常不由自主地奔騰過上千個“為什么”“為什么”， 本文盡可能的對新手友好、解答CRC里面的一些知識點，而不是簡單的應用。 依據學習目的不同，如果大家只想簡單應用，不求原理，那么直接復制--粘貼最后的代碼即可。 1. CRC 算法原理
在對信息的處理過程中，我們可以將要被處理的數據塊M看成一個n階的二進制多項式，其形式如下： CRC校驗就是基于這種多項式進行的運算，以GF(2)(The integers modulo 2)多項式算術為數學基礎，即 (模-2)除法的余數運算（其實說白了就是異或Xor（見2.2）），使用的除數不同，CRC的類型也就不一樣。CRC傳輸實際上就是在長度為?k?的數據后面添加供差錯檢測(Frame Check Sequence)?用的?r?位冗余碼（Redundant code 沒錯CRC里面的R就是這個），使原數據構成?n = k + r?位并發送出去,?此方式又叫（n, k）碼?？梢宰C明存在一個最高次冪為n-k=r的多項式G(x),??根據G(x)可以生成k位信息的校驗碼，而?G(x)?叫做這個CRC碼的生成多項式( Poly )。而根據?k?值的不同，就形成了不同的CRC碼的生成多項式，以下為各種常用的多項表達式：
這些多項表達式的值便是(模-2)除法的除數，本博客這里選取CRC-32多項式（即為對應除數）格式，通過取余做操，獲取CRC檢驗碼。 2. CRC?傳輸過程
2.1 傳輸原理
按?1. CRC?算法原理?所述，將長度為?k?位的數據塊對應一個GF(2)多項式M，以?8?位數據塊11100110舉例，如果先傳輸MSB（Most Significant Bit），則它對應的多項式為x^7 + x^6 + x^5 + x^2 + x （8位對應x的7次冪，因為從x0?開始計數，2進制為1時有效）。發送端和接收端約定一個次數為?r?的CRC多項式，取CRC-4?為例：x^4 + x + 1，r = 4。在數據塊后面加上r個0對應的多項式為M'，顯然有M' = Mx^r?。用?M'?除以CRC-4?將得到一個次數等于或小于?r-1?的余數多項式?R，其對應的?r?位數值則為校驗碼。發送方通過指定的CRC多項式產生r位的CRC校驗碼，接收方則通過該CRC多項式來驗證收到的報文碼的CRC校驗碼是否為0。 假設發送信息用信息多項式C(x)表示，將C(x)左移?r?位，則可表示成C(x)x^r，這樣C(x)的右邊就會空出r位校驗碼的位置，使用GF(2) （模2除法），得到的余數R就是校驗碼。發送的CRC編碼是, 至于驗證接收到的報文編碼是否至正確，方法依然是做模2除：，若余數為0則正確。 2.2?邏輯異或運算
CRC校驗是基于多項式進行的運算，其加減法運算以2為模GF(2)?，加減時不進（借）位，實際上與邏輯異或（XOR）運算是一致, XOR是將參加運算的兩個數據，按二進制位進行“異或”運算。 異或運算規則（^）規則如下：
0^0=0；??0^1=1；? 1^0=1；?? 1^1=0； 即：參加運算的兩個對象，如果兩個相應位為“異”（值不同），則該位結果為1，否則為0。 2.3 傳輸計算示例
以G(X)=X4+X3+1為例，設原數據為10110011。 ?（1）G(X)=X4+X3+1,?二進制比特串為11001。（在?X?的n?次方不為0處2的n次方的位=1?) ?（2）因為校驗碼4位，所以10110011后面需加4個0，得到101100110000，用“模2除法”?(即邏輯亦或^)?即可得出結果： （3）即CRC^101100110000得到101100110100，并發送到接收端。 （4）接收端收到101100110100后除以11001(以“模2除法”方式去除),余數為0則無差錯。 3. CRC?的實現（Reversed 反向校驗模式）
一般來說CRC有多種實現方式，在本文中我們以C語言為例，并給出?直接生成法?和?查表法?兩個例子。 直接生成法?適用于 CRC 次冪較小的格式，當CRC 次冪逐漸增高時，因為其復雜的Xor 邏輯運算會拖累系統運行速度，不再建議使用直接生成法，取而代之的是查表法——將數據塊M 的一部分提前運算好，并將結果存入數組中，系統開始執行運算時，相當于省去了之前的操作，直接從類似中間的位置開始計算，所以會提高效率。 在計算CRC時也可以選擇正向校驗（Normal）?或者反向校驗（Reversed），由于 Normal 和 Reversed 是鏡像關系，兩種方法會影響到最后的校驗碼，使得兩種方式最后得到的校驗碼呈現鏡像關系。但這對CRC 本身的成功率并沒有影響，只不過是：正向走一遍，還是鏡像走一遍罷了。 那為什么還會有Reversed格式呢？是因為在大多數硬件系統的傳輸中，普遍先發送LSB，而Reversed 的CRC 正是滿足于這種LSB First 的格式，因此適用。 設數據塊為Mx, CRC校驗式為G(x) FCS位數為?r。 如下表所示，當采取反向校驗設計時, 需進行以下操作：
| Polynomial Representations |
| | | |
| | | | |
| | | | |
| | | | |
| | | | |
（1）將翻轉后的Mx^r的后r位放入一個長度為r的寄存器中； （2）如果寄存器的首位為1，將寄存器右移1位(將Mx^r剩下部分的MSB移入寄存器的MSB（高八位）)，再與G(x)?的后r位異或，否則僅將寄存器右移1位(將Mx^r剩下部分的LSB（低八位）移入寄存器的LSB)； （3）重復第2步，直到M全部?Mx^r?移入寄存器； unsigned int CRC;//int的大小是32位，作32位CRC寄存器unsigned int CRC_32_Table[256];//用來保存CRC碼表void GenerateCRC32_Table(){ for(int i=0;i<256;++i)//用++i以提高效率{ CRC=i;for(int j=0;j<8;++j){ if(CRC&1)// LSM為1CRC=(CRC>>1)^0xEDB88320;//采取反向校驗else //0xEDB88320就是CRC-32多項表達式的reversed值CRC>>=1;}CRC_32_Table[i]=CRC;}}
4.?生成多項式的選擇
不同的CRC生成多項式，其檢錯能力是不同的。要使用R位校驗碼，生成多項式的次冪應為R。同時生成多項式應該包含項"1"，否則校驗碼的LSB(Least Significant Bit)將始終為0。如果數據塊M (包括校驗碼)?在傳輸過程中產生了差錯，則接收端收到的消息可以表示為M +R’。若R’?不能被CRC?生成多項式G?除盡，則該差錯可以被檢測出?？紤]以下幾種情況： 1) 1位差錯，即R’?= x^n = 100...00，n >= 0。只要G至少有2位1，R'就不能被G除盡。這是因為G x^k相當于將G左移k位，對任意多項式Q，QG相當于將多個不同的G的左移相加。如果G至少有兩位1，它的多個不同的左移相加結果至少有兩位1。 2)奇數位差錯，只要G含有因子F = x + 1, ?R'?就不能被G除盡。這是因為QG = Q'F，由1)的分析，F的多個不同的左移相加結果1的位數必然是偶數。 3)爆炸性差錯，即R' = (x^n + ... + 1)x^m = 1...100...00，n >= 1，m >= 0，顯然只要G包含項"1"，且次數大于n，就不能除盡R'。 4)2位差錯，即R' = (x^n + 1)x^m = 100...00100...00，n >= 0。設x^n + 1 = QG + R，則R' = QGx^m + Rx^m，由3)可知R'能被G除盡當且僅當R為0。因此只需分析x^n + 1，對于次數R，總存在一個生成多項式G，使得n最小為2^R - 1時，才能除盡x^n + 1。稱該生成多項式是原始的(primitive)，它提供了在該次數上檢測2位差錯的最高能力，因為當n = 2^R - 1時，x^n + 1能被任何R次多項式除盡。 5.?Q & A
Q: 為什么寄存器初始化置0？
A:?寄存器的初始值不為 0，那么寄存器中的值就相當于是待測數據，這樣算出的 CRC 結果并不正確。再考慮CRC32 模型的 Init=0xFFFFFFFF，待測數據的內容和長度為隨機，如果寄存器初始值為 0，那么待測字節則為 1 字節?0x00，計算出來的 CRC32 值也就為 0。寄存器用0xFFFFFFFF 進行初始化，就可以避免這個問題
Q：為什么先移位再XOR？
A:?0xEDB88320已經是Gx 去掉最高項的簡寫，為了確保運算無誤，所以需要先移位再XOR。這不會影響最后的結果，因為在做XOR運算時，gx 的最高位都會被消掉（因為在除法運算中每次循環都是從1 開始除， 而gx 的最高項就是1，所以每次都會被消掉）
Q: 查表法的index 是什么，而內容又是什么？
A:?Index 為數據塊M 的前8位，內容是前8位與CRC XOR后的值，用時需再與gx異或。
Q: 查表法為什么會有256個字符？
A:?在CRC-16和32中，一次移出的待測數據為 8 位 bits，即一次進行一個字節的計算，則表格有 2^8＝256 個表值。一個字節有8位二進制數，每一位都有2種選擇。
文章整理自網絡
關注微信公眾號『玩轉嵌入式』，后臺回復“128”獲取干貨資料匯總，回復“256”加入技術交流群。
|
｜單片機編程如何查看版本之間代碼的不同：代碼比較工具 |
|
|
免責聲明：本文內容由21ic獲得授權后發布，版權歸原作者所有，本平臺僅提供信息存儲服務。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯系我們，謝謝！
