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