寫給嵌入式程序員的循環(huán)冗余校驗(yàn)（CRC）算法入門引導(dǎo)前言CRC校驗(yàn)（循環(huán)冗余校驗(yàn)）是數(shù)據(jù)通訊中最常采用的校驗(yàn)方式。在嵌入式軟件開發(fā)中，經(jīng)常要用到CRC 算法對(duì)各種數(shù)據(jù)進(jìn)行校驗(yàn)。因此，掌握基本的CRC算法應(yīng)是嵌入式程序員的基本技能。可是，我認(rèn)識(shí)的嵌入式程序員中能真正掌握CRC算法的人卻很少，平常在項(xiàng)目中見到的CRC的代碼多數(shù)都是那種效率非常低下的實(shí)現(xiàn)方式。
其實(shí)，在網(wǎng)上有一篇介紹CRC 算法的非常好的文章，作者是Ross Williams，題目叫：“A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS”。我常將這篇文章推薦給向我詢問CRC算法的朋友，但不少朋友向我抱怨原文太長(zhǎng)了，而且是英文的。希望我能寫篇短點(diǎn)的文章，因此就有了本文。不過，我的水平比不了Ross Williams，我的文章肯定也沒Ross Williams的寫的好。因此，閱讀英文沒有障礙的朋友還是去讀Ross Williams的原文吧。
本文的讀者群設(shè)定為軟件開發(fā)人員，尤其是從事嵌入式軟件開發(fā)的程序員，而不是專業(yè)從事數(shù)學(xué)或通訊領(lǐng)域研究的學(xué)者（我也沒有這個(gè)水平寫的這么高深）。因此，本文的目標(biāo)是介紹CRC算法的基本原理和實(shí)現(xiàn)方式，用到的數(shù)學(xué)盡量控制在高中生可以理解的深度。
另外，鑒于大多數(shù)嵌入式程序員都是半路出家轉(zhuǎn)行過來的，不少人只會(huì)C語(yǔ)言。因此，文中的示例代碼全部采用C語(yǔ)言來實(shí)現(xiàn)。作為一篇入門短文，文中給出的代碼更注重于示范性，盡可能的保持易讀性。因此，文中的代碼并不追求最高效的實(shí)現(xiàn)，但對(duì)于一般的應(yīng)用卻也足夠快速了。
從奇偶校驗(yàn)說起所謂通訊過程的校驗(yàn)是指在通訊數(shù)據(jù)后加上一些附加信息，通過這些附加信息來判斷接收到的數(shù)據(jù)是否和發(fā)送出的數(shù)據(jù)相同。比如說RS232串行通訊可以設(shè)置奇偶校驗(yàn)位，所謂奇偶校驗(yàn)就是在發(fā)送的每一個(gè)字節(jié)后都加上一位，使得每個(gè)字節(jié)中1的個(gè)數(shù)為奇數(shù)個(gè)或偶數(shù)個(gè)。比如我們要發(fā)送的字節(jié)是0x1a，二進(jìn)制表示為0001 1010。
采用奇校驗(yàn)，則在數(shù)據(jù)后補(bǔ)上個(gè)0，數(shù)據(jù)變?yōu)?001 1010 0，數(shù)據(jù)中1的個(gè)數(shù)為奇數(shù)個(gè)（3個(gè)）
采用奇校驗(yàn)，則在數(shù)據(jù)后補(bǔ)上個(gè)1，數(shù)據(jù)變?yōu)?001 1010 1，數(shù)據(jù)中1的個(gè)數(shù)為偶數(shù)個(gè)（4個(gè)）
接收方通過計(jì)算數(shù)據(jù)中1個(gè)數(shù)是否滿足奇偶性來確定數(shù)據(jù)是否有錯(cuò)。
奇偶校驗(yàn)的缺點(diǎn)也很明顯，首先，它對(duì)錯(cuò)誤的檢測(cè)概率大約只有50%。也就是只有一半的錯(cuò)誤它能夠檢測(cè)出來。另外，每傳輸一個(gè)字節(jié)都要附加一位校驗(yàn)位，對(duì)傳輸效率的影響很大。因此，在高速數(shù)據(jù)通訊中很少采用奇偶校驗(yàn)。奇偶校驗(yàn)優(yōu)點(diǎn)也很明顯，它很簡(jiǎn)單，因此可以用硬件來實(shí)現(xiàn)，這樣可以減少軟件的負(fù)擔(dān)。因此，奇偶校驗(yàn)也被廣泛的應(yīng)用著。
奇偶校驗(yàn)就先介紹到這來，之所以從奇偶校驗(yàn)說起，是因?yàn)檫@種校驗(yàn)方式最簡(jiǎn)單，而且后面將會(huì)知道奇偶校驗(yàn)其實(shí)就是CRC 校驗(yàn)的一種(CRC-1)。
累加和校驗(yàn)
另一種常見的校驗(yàn)方式是累加和校驗(yàn)。所謂累加和校驗(yàn)實(shí)現(xiàn)方式有很多種，最常用的一種是在一次通訊數(shù)據(jù)包的最后加入一個(gè)字節(jié)的校驗(yàn)數(shù)據(jù)。這個(gè)字節(jié)內(nèi)容為前面數(shù)據(jù)包中全部數(shù)據(jù)的忽略進(jìn)位的按字節(jié)累加和。比如下面的例子：
我們要傳輸?shù)男畔椋?6、23、4
加上校驗(yàn)和后的數(shù)據(jù)包：6、23、4、33
這里 33 為前三個(gè)字節(jié)的校驗(yàn)和。接收方收到全部數(shù)據(jù)后對(duì)前三個(gè)數(shù)據(jù)進(jìn)行同樣的累加計(jì)算，如果累加和與最后一個(gè)字節(jié)相同的話就認(rèn)為傳輸?shù)臄?shù)據(jù)沒有錯(cuò)誤。
累加和校驗(yàn)由于實(shí)現(xiàn)起來非常簡(jiǎn)單，也被廣泛的采用。但是這種校驗(yàn)方式的檢錯(cuò)能力也比較一般，對(duì)于單字節(jié)的校驗(yàn)和大概有1/256 的概率將原本是錯(cuò)誤的通訊數(shù)據(jù)誤判為正確數(shù)據(jù)。之所以這里介紹這種校驗(yàn)，是因?yàn)镃RC校驗(yàn)在傳輸數(shù)據(jù)的形式上與累加和校驗(yàn)是相同的，都可以表示為：通訊數(shù)據(jù) 校驗(yàn)字節(jié)（也可能是多個(gè)字節(jié)）
初識(shí) CRC 算法CRC 算法的基本思想是將傳輸?shù)臄?shù)據(jù)當(dāng)做一個(gè)位數(shù)很長(zhǎng)的數(shù)。將這個(gè)數(shù)除以另一個(gè)數(shù)。得到的余數(shù)作為校驗(yàn)數(shù)據(jù)附加到原數(shù)據(jù)后面。還以上面例子中的數(shù)據(jù)為例：
6、23、4 可以看做一個(gè)2進(jìn)制數(shù)： 0000011000010111 00000010
假如被除數(shù)選9，二進(jìn)制表示為：1001
則除法運(yùn)算可以表示為：
可以看到，最后的余數(shù)為1。如果我們將這個(gè)余數(shù)作為校驗(yàn)和的話，傳輸?shù)臄?shù)據(jù)則是：6、23、4、1
CRC 算法和這個(gè)過程有點(diǎn)類似，不過采用的不是上面例子中的通常的這種除法。在CRC算法中，將二進(jìn)制數(shù)據(jù)流作為多項(xiàng)式的系數(shù)，然后進(jìn)行的是多項(xiàng)式的乘除法。還是舉個(gè)例子吧。
比如說我們有兩個(gè)二進(jìn)制數(shù)，分別為：1101 和1011。
1101 與如下的多項(xiàng)式相聯(lián)系：1x3+1x2+0x1+1x0=x3+x2+x0
1011與如下的多項(xiàng)式相聯(lián)系：1x3+0x2+1x1+1x0=x3+x1+x0
兩個(gè)多項(xiàng)式的乘法：(x3+x2+x0)(x3+x1+x0)=x6+x5+x4+x3+x3+x3+x2+x1+x0
得到結(jié)果后，合并同類項(xiàng)時(shí)采用模2運(yùn)算。也就是說乘除法采用正常的多項(xiàng)式乘除法，而加減法都采用模2運(yùn)算。所謂模2運(yùn)算就是結(jié)果除以2后取余數(shù)。比如3 mod 2 = 1。因此，上面最終得到的多項(xiàng)式為：x6+x5+x4+x3+x2+x1+x0，對(duì)應(yīng)的二進(jìn)制數(shù):111111
加減法采用模2運(yùn)算后其實(shí)就成了一種運(yùn)算了，就是我們通常所說的異或運(yùn)算：
0+0=0
0+1=1
1+0=1
1+1=0
| 0-0=0
1-0=1
0-1=1
1-1=0
|
除法運(yùn)算與上面給出的乘法概念類似，還是遇到加減的地方都用異或運(yùn)算來代替。下面是一個(gè)例子：
要傳輸?shù)臄?shù)據(jù)為：1101011011
除數(shù)設(shè)為：10011
在計(jì)算前先將原始數(shù)據(jù)后面填上4個(gè)0：11010110110000，之所以要補(bǔ)0，后面再做解釋。
從這個(gè)例子可以看出，采用了模2的加減法后，不需要考慮借位的問題，所以除法變簡(jiǎn)單了。最后得到的余數(shù)就是CRC 校驗(yàn)字。為了進(jìn)行CRC運(yùn)算，也就是這種特殊的除法運(yùn)算，必須要指定個(gè)被除數(shù)，在CRC算法中，這個(gè)被除數(shù)有一個(gè)專有名稱叫做“生成多項(xiàng)式”。生成多項(xiàng)式的選取是個(gè)很有難度的問題，如果選的不好，那么檢出錯(cuò)誤的概率就會(huì)低很多。好在這個(gè)問題已經(jīng)被專家們研究了很長(zhǎng)一段時(shí)間了，對(duì)于我們這些使用者來說，只要把現(xiàn)成的成果拿來用就行了。
最常用的幾種生成多項(xiàng)式如下：
CRC8=X8+X5+X4+X0
CRC-CCITT=X16+X12+X5+X0
CRC16=X16+X15+X2+X0
CRC12=X12+X11+X3+X2+X0
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0
有一點(diǎn)要特別注意，文獻(xiàn)中提到的生成多項(xiàng)式經(jīng)常會(huì)說到多項(xiàng)式的位寬（Width，簡(jiǎn)記為W），這個(gè)位寬不是多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)的位數(shù)，而是位數(shù)減1。比如CRC8中用到的位寬為8的生成多項(xiàng)式，其實(shí)對(duì)應(yīng)得二進(jìn)制數(shù)有九位：100110001。另外一點(diǎn)，多項(xiàng)式表示和二進(jìn)制表示都很繁瑣，交流起來不方便，因此，文獻(xiàn)中多用16進(jìn)制簡(jiǎn)寫法來表示，因?yàn)樯啥囗?xiàng)式的最高位肯定為1，最高位的位置由位寬可知，故在簡(jiǎn)記式中，將最高的1統(tǒng)一去掉了，如CRC32的生成多項(xiàng)式簡(jiǎn)記為04C11DB7實(shí)際上表示的是104C11DB7。當(dāng)然，這樣簡(jiǎn)記除了方便外，在編程計(jì)算時(shí)也有它的用處。
對(duì)于上面的例子，位寬為4（W=4），按照CRC算法的要求，計(jì)算前要在原始數(shù)據(jù)后填上W個(gè)0，也就是4個(gè)0。
位寬W=1的生成多項(xiàng)式(CRC1)有兩種，分別是X1和X1+X0，讀者可以自己證明10 對(duì)應(yīng)的就是奇偶校驗(yàn)中的奇校驗(yàn)，而11對(duì)應(yīng)則是偶校驗(yàn)。因此，寫到這里我們知道了奇偶校驗(yàn)其實(shí)就是CRC校驗(yàn)的一種特例，這也是我要以奇偶校驗(yàn)作為開篇介紹的原因了。
CRC算法的編程實(shí)現(xiàn)說了這么多總算到了核心部分了。從前面的介紹我們知道CRC校驗(yàn)核心就是實(shí)現(xiàn)無借位的除法運(yùn)算。下面還是通過一個(gè)例子來說明如何實(shí)現(xiàn)CRC校驗(yàn)。
假設(shè)我們的生成多項(xiàng)式為：100110001（簡(jiǎn)記為0x31），也就是CRC-8
則計(jì)算步驟如下：
（1） 將CRC寄存器（8-bits，比生成多項(xiàng)式少1bit）賦初值0
（2） 在待傳輸信息流后面加入8個(gè)0
（3） While (數(shù)據(jù)未處理完)
（4） Begin
（5） If (CRC寄存器首位是1)
（6） reg = reg XOR 0x31
（7） CRC寄存器左移一位，讀入一個(gè)新的數(shù)據(jù)于CRC寄存器的0 bit的位置。
（8） End
（9） CRC寄存器就是我們所要求的余數(shù)。
實(shí)際上，真正的CRC 計(jì)算通常與上面描述的還有些出入。這是因?yàn)檫@種最基本的CRC除法有個(gè)很明顯的缺陷，就是數(shù)據(jù)流的開頭添加一些0并不影響最后校驗(yàn)字的結(jié)果。這個(gè)問題很讓人惱火啊，因此真正應(yīng)用的CRC 算法基本都在原始的CRC算法的基礎(chǔ)上做了些小的改動(dòng)。
所謂的改動(dòng)，也就是增加了兩個(gè)概念，第一個(gè)是“余數(shù)初始值”，第二個(gè)是“結(jié)果異或值”。
所謂的“余數(shù)初始值”就是在計(jì)算CRC值的開始，給CRC寄存器一個(gè)初始值。“結(jié)果異或值”是在其余計(jì)算完成后將CRC寄存器的值在與這個(gè)值進(jìn)行一下異或操作作為最后的校驗(yàn)值。
常見的三種CRC 標(biāo)準(zhǔn)用到個(gè)各個(gè)參數(shù)如下表。
| CCITT
| CRC16
| CRC32
| 校驗(yàn)和位寬W
| 16
| 16
| 32
| 生成多項(xiàng)式
| x16+x12+x5+1
| x16+x15+x2+1
| x32+x26+x23+x22+x16+
x12+x11+x10+x8+x7+x5+
x4+x2+x1+1
| 除數(shù)（多項(xiàng)式）
| 0x1021
| 0x8005
| 0x04C11DB7
| 余數(shù)初始值
| 0xFFFF
| 0x0000
| 0xFFFFFFFF
| 結(jié)果異或值
| 0x0000
| 0x0000
| 0xFFFFFFFF
|
加入這些變形后，常見的算法描述形式就成了這個(gè)樣子了：
（1） 設(shè)置CRC寄存器，并給其賦值為“余數(shù)初始值”。
（2） 將數(shù)據(jù)的第一個(gè)8-bit字符與CRC寄存器進(jìn)行異或，并把結(jié)果存入CRC寄存器。
（3） CRC寄存器向右移一位，MSB補(bǔ)零，移出并檢查L(zhǎng)SB。
（4） 如果LSB為0，重復(fù)第三步；若LSB為1，CRC寄存器與0x31相異或。
（5） 重復(fù)第3與第4步直到8次移位全部完成。此時(shí)一個(gè)8-bit數(shù)據(jù)處理完畢。
（6） 重復(fù)第2至第5步直到所有數(shù)據(jù)全部處理完成。
（7） 最終CRC寄存器的內(nèi)容與“結(jié)果異或值”進(jìn)行或非操作后即為CRC值。
示例性的C代碼如下所示，因?yàn)樾屎艿停?xiàng)目中如對(duì)計(jì)算時(shí)間有要求應(yīng)該避免采用這樣的代碼。不過這個(gè)代碼已經(jīng)比網(wǎng)上常見的計(jì)算代碼要好了，因?yàn)檫@個(gè)代碼有一個(gè)crc的參數(shù)，可以將上次計(jì)算的crc結(jié)果傳入函數(shù)中作為這次計(jì)算的初始值，這對(duì)大數(shù)據(jù)塊的CRC計(jì)算是很有用的，不需要一次將所有數(shù)據(jù)讀入內(nèi)存，而是讀一部分算一次，全讀完后就計(jì)算完了。這對(duì)內(nèi)存受限系統(tǒng)還是很有用的。 - #define POLY 0x1021
- /**
- * Calculating CRC-16 in 'C'
- * @para addr, start of data
- * @para num, length of data
- * @para crc, incoming CRC
- */
- uint16_t crc16(unsigned char *addr, int num, uint16_t crc)
- {
- int i;
- for (; num > 0; num--) /* Step through bytes in memory */
- {
- crc = crc ^ (*addr++ << 8); /* Fetch byte from memory, XOR into CRC top byte*/
- for (i = 0; i < 8; i++) /* Prepare to rotate 8 bits */
- {
- if (crc & 0x8000) /* b15 is set... */
- crc = (crc << 1) ^ POLY; /* rotate and XOR with polynomic */
- else /* b15 is clear... */
- crc <<= 1; /* just rotate */
- } /* Loop for 8 bits */
- crc &= 0xFFFF; /* Ensure CRC remains 16-bit value */
- } /* Loop until num=0 */
- return(crc); /* Return updated CRC */
- }
下面對(duì)這個(gè)函數(shù)給出個(gè)例子片段代碼：
- unsigned char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
- unsigned char data2[] = {'5', '6', '7', '8', '9'};
- unsigned short c1, c2;
- c1 = crc16(data1, 9, 0xffff);
- c2 = crc16(data1, 4, 0xffff);
- c2 = crc16(data2, 5, c2);
- printf("%04x", c1);
- printf("%04x", c2);
讀者可以驗(yàn)算，c1、c2 的結(jié)果都為 29b1。上面代碼中crc 的初始值之所以為0xffff，是因?yàn)镃CITT標(biāo)準(zhǔn)要求的除數(shù)初始值就是0xffff。
上面的算法對(duì)數(shù)據(jù)流逐位進(jìn)行計(jì)算，效率很低。實(shí)際上仔細(xì)分析CRC計(jì)算的數(shù)學(xué)性質(zhì)后我們可以多位多位計(jì)算，最常用的是一種按字節(jié)查表的快速算法。該算法基于這樣一個(gè)事實(shí)：計(jì)算本字節(jié)后的CRC碼，等于上一字節(jié)余式CRC碼的低8位左移8位，加上上一字節(jié)CRC右移 8位和本字節(jié)之和后所求得的CRC碼。如果我們把8位二進(jìn)制序列數(shù)的CRC(共256個(gè))全部計(jì)算出來，放在一個(gè)表里，編碼時(shí)只要從表中查找對(duì)應(yīng)的值進(jìn)行處理即可。
按照這個(gè)方法，可以有如下的代碼（這個(gè)代碼也不是我寫的，是我在Micbael Barr的書“Programming Embedded Systems in C and C++” 中找到的，同樣，我做了點(diǎn)小小的改動(dòng)。）：
- /*
- crc.h
- */
-
- #ifndef CRC_H_INCLUDED
- #define CRC_H_INCLUDED
-
- /*
- * The CRC parameters. Currently configured for CCITT.
- * Simply modify these to switch to another CRC Standard.
- */
- /*
- #define POLYNOMIAL 0x8005
- #define INITIAL_REMAINDER 0x0000
- #define FINAL_XOR_VALUE 0x0000
- */
- #define POLYNOMIAL 0x1021
- #define INITIAL_REMAINDER 0xFFFF
- #define FINAL_XOR_VALUE 0x0000
-
- /*
- #define POLYNOMIAL 0x1021
- #define POLYNOMIAL 0xA001
- #define INITIAL_REMAINDER 0xFFFF
- #define FINAL_XOR_VALUE 0x0000
- */
-
- /*
- * The width of the CRC calculation and result.
- * Modify the typedef for an 8 or 32-bit CRC standard.
- */
- typedef unsigned short width_t;
- #define WIDTH (8 * sizeof(width_t))
- #define TOPBIT (1 << (WIDTH - 1))
-
- /**
- * Initialize the CRC lookup table.
- * This table is used by crcCompute() to make CRC computation faster.
- */
- void crcInit(void);
-
- /**
- * Compute the CRC checksum of a binary message block.
- * @para message, 用來計(jì)算的數(shù)據(jù)
- * @para nBytes, 數(shù)據(jù)的長(zhǎng)度
- * @note This function expects that crcInit() has been called
- * first to initialize the CRC lookup table.
- */
- width_t crcCompute(unsigned char * message, unsigned int nBytes);
-
- #endif // CRC_H_INCLUDED
- /*
- *crc.c
- */
-
- #include "crc.h"
- /*
- * An array containing the pre-computed intermediate result for each
- * possible byte of input. This is used to speed up the computation.
- */
- static width_t crcTable[256];
-
- /**
- * Initialize the CRC lookup table.
- * This table is used by crcCompute() to make CRC computation faster.
- */
- void crcInit(void)
- {
- width_t remainder;
- width_t dividend;
- int bit;
- /* Perform binary long division, a bit at a time. */
- for(dividend = 0; dividend < 256; dividend++)
- {
- /* Initialize the remainder. */
- remainder = dividend << (WIDTH - 8);
- /* Shift and XOR with the polynomial. */
- for(bit = 0; bit < 8; bit++)
- {
- /* Try to divide the current data bit. */
- if(remainder & TOPBIT)
- {
- remainder = (remainder << 1) ^ POLYNOMIAL;
- }
- else
- {
- remainder = remainder << 1;
- }
- }
- /* Save the result in the table. */
- crcTable[dividend] = remainder;
- }
- } /* crcInit() */
-
- /**
- * Compute the CRC checksum of a binary message block.
- * @para message, 用來計(jì)算的數(shù)據(jù)
- * @para nBytes, 數(shù)據(jù)的長(zhǎng)度
- * @note This function expects that crcInit() has been called
- * first to initialize the CRC lookup table.
- */
- width_t crcCompute(unsigned char * message, unsigned int nBytes)
- {
- unsigned int offset;
- unsigned char byte;
- width_t remainder = INITIAL_REMAINDER;
- /* Divide the message by the polynomial, a byte at a time. */
- for( offset = 0; offset < nBytes; offset++)
- {
- byte = (remainder >> (WIDTH - 8)) ^ message[offset];
- remainder = crcTable[byte] ^ (remainder << 8);
- }
- /* The final remainder is the CRC result. */
- return (remainder ^ FINAL_XOR_VALUE);
- } /* crcCompute() */
上面代碼中crcInit() 函數(shù)用來計(jì)算crcTable，因此在調(diào)用 crcCompute 前必須先調(diào)用 crcInit()。不過，對(duì)于嵌入式系統(tǒng)，RAM是很緊張的，最好將 crcTable 提前算好，作為常量數(shù)據(jù)存到程序存儲(chǔ)區(qū)而不占用RAM空間。CRC 計(jì)算實(shí)際上還有很多內(nèi)容可以介紹，不過對(duì)于一般的程序員來說，知道這些也就差不多了。余下的部分以后有時(shí)間了我再寫篇文章來介紹吧。
|
