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