欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標題: 循環冗余校驗（CRC）算法入門引導 [打印本頁]
作者: 51黑dd    時間: 2016-4-7 03:42
標題: 循環冗余校驗（CRC）算法入門引導
寫給嵌入式程序員的循環冗余校驗（CRC）算法入門引導前言CRC校驗（循環冗余校驗）是數據通訊中最常采用的校驗方式。在嵌入式軟件開發中，經常要用到CRC 算法對各種數據進行校驗。因此，掌握基本的CRC算法應是嵌入式程序員的基本技能。可是，我認識的嵌入式程序員中能真正掌握CRC算法的人卻很少，平常在項目中見到的CRC的代碼多數都是那種效率非常低下的實現方式。
其實，在網上有一篇介紹CRC 算法的非常好的文章，作者是Ross Williams，題目叫：“A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS”。我常將這篇文章推薦給向我詢問CRC算法的朋友，但不少朋友向我抱怨原文太長了，而且是英文的。希望我能寫篇短點的文章，因此就有了本文。不過，我的水平比不了Ross Williams，我的文章肯定也沒Ross Williams的寫的好。因此，閱讀英文沒有障礙的朋友還是去讀Ross Williams的原文吧。
本文的讀者群設定為軟件開發人員，尤其是從事嵌入式軟件開發的程序員，而不是專業從事數學或通訊領域研究的學者（我也沒有這個水平寫的這么高深）。因此，本文的目標是介紹CRC算法的基本原理和實現方式，用到的數學盡量控制在高中生可以理解的深度。
另外，鑒于大多數嵌入式程序員都是半路出家轉行過來的，不少人只會C語言。因此，文中的示例代碼全部采用C語言來實現。作為一篇入門短文，文中給出的代碼更注重于示范性，盡可能的保持易讀性。因此，文中的代碼并不追求最高效的實現，但對于一般的應用卻也足夠快速了。
從奇偶校驗說起所謂通訊過程的校驗是指在通訊數據后加上一些附加信息，通過這些附加信息來判斷接收到的數據是否和發送出的數據相同。比如說RS232串行通訊可以設置奇偶校驗位，所謂奇偶校驗就是在發送的每一個字節后都加上一位，使得每個字節中1的個數為奇數個或偶數個。比如我們要發送的字節是0x1a，二進制表示為0001 1010。
采用奇校驗，則在數據后補上個0，數據變為0001 1010 0，數據中1的個數為奇數個（3個）
采用奇校驗，則在數據后補上個1，數據變為0001 1010 1，數據中1的個數為偶數個（4個）
接收方通過計算數據中1個數是否滿足奇偶性來確定數據是否有錯。
奇偶校驗的缺點也很明顯，首先，它對錯誤的檢測概率大約只有50%。也就是只有一半的錯誤它能夠檢測出來。另外，每傳輸一個字節都要附加一位校驗位，對傳輸效率的影響很大。因此，在高速數據通訊中很少采用奇偶校驗。奇偶校驗優點也很明顯，它很簡單，因此可以用硬件來實現，這樣可以減少軟件的負擔。因此，奇偶校驗也被廣泛的應用著。
奇偶校驗就先介紹到這來，之所以從奇偶校驗說起，是因為這種校驗方式最簡單，而且后面將會知道奇偶校驗其實就是CRC 校驗的一種(CRC-1)。

累加和校驗
另一種常見的校驗方式是累加和校驗。所謂累加和校驗實現方式有很多種，最常用的一種是在一次通訊數據包的最后加入一個字節的校驗數據。這個字節內容為前面數據包中全部數據的忽略進位的按字節累加和。比如下面的例子：
我們要傳輸的信息為： 6、23、4
加上校驗和后的數據包：6、23、4、33
這里 33 為前三個字節的校驗和。接收方收到全部數據后對前三個數據進行同樣的累加計算，如果累加和與最后一個字節相同的話就認為傳輸的數據沒有錯誤。
累加和校驗由于實現起來非常簡單，也被廣泛的采用。但是這種校驗方式的檢錯能力也比較一般，對于單字節的校驗和大概有1/256 的概率將原本是錯誤的通訊數據誤判為正確數據。之所以這里介紹這種校驗，是因為CRC校驗在傳輸數據的形式上與累加和校驗是相同的，都可以表示為：通訊數據 校驗字節（也可能是多個字節）
初識 CRC 算法CRC 算法的基本思想是將傳輸的數據當做一個位數很長的數。將這個數除以另一個數。得到的余數作為校驗數據附加到原數據后面。還以上面例子中的數據為例：
6、23、4 可以看做一個2進制數： 0000011000010111 00000010
假如被除數選9，二進制表示為：1001
則除法運算可以表示為：

可以看到，最后的余數為1。如果我們將這個余數作為校驗和的話，傳輸的數據則是：6、23、4、1
CRC 算法和這個過程有點類似，不過采用的不是上面例子中的通常的這種除法。在CRC算法中，將二進制數據流作為多項式的系數，然后進行的是多項式的乘除法。還是舉個例子吧。
比如說我們有兩個二進制數，分別為：1101 和1011。
1101 與如下的多項式相聯系：1x3+1x2+0x1+1x0=x3+x2+x0
1011與如下的多項式相聯系：1x3+0x2+1x1+1x0=x3+x1+x0
兩個多項式的乘法：(x3+x2+x0)(x3+x1+x0)=x6+x5+x4+x3+x3+x3+x2+x1+x0
得到結果后，合并同類項時采用模2運算。也就是說乘除法采用正常的多項式乘除法，而加減法都采用模2運算。所謂模2運算就是結果除以2后取余數。比如3 mod 2 = 1。因此，上面最終得到的多項式為：x6+x5+x4+x3+x2+x1+x0，對應的二進制數:111111
加減法采用模2運算后其實就成了一種運算了，就是我們通常所說的異或運算：
0+0=0
0+1=1
1+0=1
1+1=0
0-0=0
1-0=1
0-1=1
1-1=0
上面說了半天多項式，其實就算是不引入多項式乘除法的概念也可以說明這些運算的特殊之處。只不過幾乎所有講解 CRC 算法的文獻中都會提到多項式，因此這里也簡單的寫了一點基本的概念。不過總用這種多項式表示也很羅嗦，下面的講解中將盡量采用更簡潔的寫法。
除法運算與上面給出的乘法概念類似，還是遇到加減的地方都用異或運算來代替。下面是一個例子：
要傳輸的數據為：1101011011
除數設為：10011
在計算前先將原始數據后面填上4個0：11010110110000，之所以要補0，后面再做解釋。

從這個例子可以看出，采用了模2的加減法后，不需要考慮借位的問題，所以除法變簡單了。最后得到的余數就是CRC 校驗字。為了進行CRC運算，也就是這種特殊的除法運算，必須要指定個被除數，在CRC算法中，這個被除數有一個專有名稱叫做“生成多項式”。生成多項式的選取是個很有難度的問題，如果選的不好，那么檢出錯誤的概率就會低很多。好在這個問題已經被專家們研究了很長一段時間了，對于我們這些使用者來說，只要把現成的成果拿來用就行了。
最常用的幾種生成多項式如下：
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
有一點要特別注意，文獻中提到的生成多項式經常會說到多項式的位寬（Width，簡記為W），這個位寬不是多項式對應的二進制數的位數，而是位數減1。比如CRC8中用到的位寬為8的生成多項式，其實對應得二進制數有九位：100110001。另外一點，多項式表示和二進制表示都很繁瑣，交流起來不方便，因此，文獻中多用16進制簡寫法來表示，因為生成多項式的最高位肯定為1，最高位的位置由位寬可知，故在簡記式中，將最高的1統一去掉了，如CRC32的生成多項式簡記為04C11DB7實際上表示的是104C11DB7。當然，這樣簡記除了方便外，在編程計算時也有它的用處。
對于上面的例子，位寬為4（W=4），按照CRC算法的要求，計算前要在原始數據后填上W個0，也就是4個0。
位寬W=1的生成多項式(CRC1)有兩種，分別是X1和X1+X0，讀者可以自己證明10 對應的就是奇偶校驗中的奇校驗，而11對應則是偶校驗。因此，寫到這里我們知道了奇偶校驗其實就是CRC校驗的一種特例，這也是我要以奇偶校驗作為開篇介紹的原因了。
CRC算法的編程實現說了這么多總算到了核心部分了。從前面的介紹我們知道CRC校驗核心就是實現無借位的除法運算。下面還是通過一個例子來說明如何實現CRC校驗。
假設我們的生成多項式為：100110001（簡記為0x31），也就是CRC-8
則計算步驟如下：
（1）      將CRC寄存器（8-bits，比生成多項式少1bit）賦初值0
（2）      在待傳輸信息流后面加入8個0
（3）      While (數據未處理完)
（4）      Begin
（5）          If (CRC寄存器首位是1)
（6）              reg = reg XOR 0x31
（7）          CRC寄存器左移一位，讀入一個新的數據于CRC寄存器的0 bit的位置。
（8）      End
（9）      CRC寄存器就是我們所要求的余數。

實際上，真正的CRC 計算通常與上面描述的還有些出入。這是因為這種最基本的CRC除法有個很明顯的缺陷，就是數據流的開頭添加一些0并不影響最后校驗字的結果。這個問題很讓人惱火啊，因此真正應用的CRC 算法基本都在原始的CRC算法的基礎上做了些小的改動。
所謂的改動，也就是增加了兩個概念，第一個是“余數初始值”，第二個是“結果異或值”。
所謂的“余數初始值”就是在計算CRC值的開始，給CRC寄存器一個初始值。“結果異或值”是在其余計算完成后將CRC寄存器的值在與這個值進行一下異或操作作為最后的校驗值。
常見的三種CRC 標準用到個各個參數如下表。

CCITT
CRC16
CRC32
校驗和位寬W
16
16
32
生成多項式
x16+x12+x5+1
x16+x15+x2+1
x32+x26+x23+x22+x16+
x12+x11+x10+x8+x7+x5+
x4+x2+x1+1
除數（多項式）
0x1021
0x8005
0x04C11DB7
余數初始值
0xFFFF
0x0000
0xFFFFFFFF
結果異或值
0x0000
0x0000
0xFFFFFFFF

加入這些變形后，常見的算法描述形式就成了這個樣子了：
（1）      設置CRC寄存器，并給其賦值為“余數初始值”。
（2）      將數據的第一個8-bit字符與CRC寄存器進行異或，并把結果存入CRC寄存器。
（3）      CRC寄存器向右移一位，MSB補零，移出并檢查LSB。
（4）      如果LSB為0，重復第三步；若LSB為1，CRC寄存器與0x31相異或。
（5）      重復第3與第4步直到8次移位全部完成。此時一個8-bit數據處理完畢。
（6）      重復第2至第5步直到所有數據全部處理完成。
（7）      最終CRC寄存器的內容與“結果異或值”進行或非操作后即為CRC值。

示例性的C代碼如下所示，因為效率很低，項目中如對計算時間有要求應該避免采用這樣的代碼。不過這個代碼已經比網上常見的計算代碼要好了，因為這個代碼有一個crc的參數，可以將上次計算的crc結果傳入函數中作為這次計算的初始值，這對大數據塊的CRC計算是很有用的，不需要一次將所有數據讀入內存，而是讀一部分算一次，全讀完后就計算完了。這對內存受限系統還是很有用的。
  1.     #define POLY        0x1021  
  2.     /**
  3.      * Calculating CRC-16 in 'C'
  4.      * @para addr, start of data
  5.      * @para num, length of data
  6.      * @para crc, incoming CRC
  7.      */  
  8.     uint16_t crc16(unsigned char *addr, int num, uint16_t crc)  
  9.     {  
  10.         int i;  
  11.         for (; num > 0; num--)              /* Step through bytes in memory */  
  12.         {  
  13.             crc = crc ^ (*addr++ << 8);     /* Fetch byte from memory, XOR into CRC top byte*/  
  14.             for (i = 0; i < 8; i++)             /* Prepare to rotate 8 bits */  
  15.             {  
  16.                 if (crc & 0x8000)            /* b15 is set... */  
  17.                     crc = (crc << 1) ^ POLY;    /* rotate and XOR with polynomic */  
  18.                 else                          /* b15 is clear... */  
  19.                     crc <<= 1;                  /* just rotate */  
  20.             }                             /* Loop for 8 bits */  
  21.             crc &= 0xFFFF;                  /* Ensure CRC remains 16-bit value */  
  22.         }                               /* Loop until num=0 */  
  23.         return(crc);                    /* Return updated CRC */  
  24.     }  
復制代碼

上面的代碼是我從http://mdfs.net/Info/Comp/Comms/CRC16.htm找到的，不過原始代碼有錯誤，我做了些小的修改。

下面對這個函數給出個例子片段代碼：
  1.     unsigned char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};  
  2.     unsigned char data2[] = {'5', '6', '7', '8', '9'};  
  3.     unsigned short c1, c2;  
  4.     c1 = crc16(data1, 9, 0xffff);  
  5.     c2 = crc16(data1, 4, 0xffff);  
  6.     c2 = crc16(data2, 5, c2);  
  7.     printf("%04x", c1);  
  8.     printf("%04x", c2);  
復制代碼


讀者可以驗算，c1、c2 的結果都為 29b1。上面代碼中crc 的初始值之所以為0xffff，是因為CCITT標準要求的除數初始值就是0xffff。

上面的算法對數據流逐位進行計算，效率很低。實際上仔細分析CRC計算的數學性質后我們可以多位多位計算，最常用的是一種按字節查表的快速算法。該算法基于這樣一個事實：計算本字節后的CRC碼，等于上一字節余式CRC碼的低8位左移8位，加上上一字節CRC右移 8位和本字節之和后所求得的CRC碼。如果我們把8位二進制序列數的CRC(共256個)全部計算出來，放在一個表里，編碼時只要從表中查找對應的值進行處理即可。

按照這個方法，可以有如下的代碼（這個代碼也不是我寫的，是我在Micbael Barr的書“Programming Embedded Systems in C and C++” 中找到的，同樣，我做了點小小的改動。）：
  1.     /*
  2.     crc.h
  3.     */  
  4.       
  5.     #ifndef CRC_H_INCLUDED  
  6.     #define CRC_H_INCLUDED  
  7.       
  8.     /*
  9.     * The CRC parameters. Currently configured for CCITT.
  10.     * Simply modify these to switch to another CRC Standard.
  11.     */  
  12.     /*
  13.     #define POLYNOMIAL          0x8005
  14.     #define INITIAL_REMAINDER   0x0000
  15.     #define FINAL_XOR_VALUE     0x0000
  16.     */  
  17.     #define POLYNOMIAL          0x1021  
  18.     #define INITIAL_REMAINDER   0xFFFF  
  19.     #define FINAL_XOR_VALUE     0x0000  
  20.       
  21.     /*
  22.     #define POLYNOMIAL          0x1021
  23.     #define POLYNOMIAL          0xA001
  24.     #define INITIAL_REMAINDER   0xFFFF
  25.     #define FINAL_XOR_VALUE     0x0000
  26.     */  
  27.       
  28.     /*
  29.     * The width of the CRC calculation and result.
  30.     * Modify the typedef for an 8 or 32-bit CRC standard.
  31.     */  
  32.     typedef unsigned short width_t;  
  33.     #define WIDTH (8 * sizeof(width_t))  
  34.     #define TOPBIT (1 << (WIDTH - 1))  
  35.       
  36.     /**
  37.      * Initialize the CRC lookup table.
  38.      * This table is used by crcCompute() to make CRC computation faster.
  39.      */  
  40.     void crcInit(void);  
  41.       
  42.     /**
  43.      * Compute the CRC checksum of a binary message block.
  44.      * @para message, 用來計算的數據
  45.      * @para nBytes, 數據的長度
  46.      * @note This function expects that crcInit() has been called
  47.      *       first to initialize the CRC lookup table.
  48.      */  
  49.     width_t crcCompute(unsigned char * message, unsigned int nBytes);  
  50.       
  51.     #endif // CRC_H_INCLUDED  
復制代碼
  1.     /*
  2.      *crc.c
  3.      */  
  4.       
  5.     #include "crc.h"  
  6.     /*
  7.     * An array containing the pre-computed intermediate result for each
  8.     * possible byte of input. This is used to speed up the computation.
  9.     */  
  10.     static width_t crcTable[256];  
  11.       
  12.     /**
  13.      * Initialize the CRC lookup table.
  14.      * This table is used by crcCompute() to make CRC computation faster.
  15.      */  
  16.     void crcInit(void)  
  17.     {  
  18.         width_t remainder;  
  19.         width_t dividend;  
  20.         int bit;  
  21.         /* Perform binary long division, a bit at a time. */  
  22.         for(dividend = 0; dividend < 256; dividend++)  
  23.         {  
  24.             /* Initialize the remainder.  */  
  25.             remainder = dividend << (WIDTH - 8);  
  26.             /* Shift and XOR with the polynomial.   */  
  27.             for(bit = 0; bit < 8; bit++)  
  28.             {  
  29.                 /* Try to divide the current data bit.  */  
  30.                 if(remainder & TOPBIT)  
  31.                 {  
  32.                     remainder = (remainder << 1) ^ POLYNOMIAL;  
  33.                 }  
  34.                 else  
  35.                 {  
  36.                     remainder = remainder << 1;  
  37.                 }  
  38.             }  
  39.             /* Save the result in the table. */  
  40.             crcTable[dividend] = remainder;  
  41.         }  
  42.     } /* crcInit() */  
  43.       
  44.     /**
  45.      * Compute the CRC checksum of a binary message block.
  46.      * @para message, 用來計算的數據
  47.      * @para nBytes, 數據的長度
  48.      * @note This function expects that crcInit() has been called
  49.      *       first to initialize the CRC lookup table.
  50.      */  
  51.     width_t crcCompute(unsigned char * message, unsigned int nBytes)  
  52.     {  
  53.         unsigned int offset;  
  54.         unsigned char byte;  
  55.         width_t remainder = INITIAL_REMAINDER;  
  56.         /* Divide the message by the polynomial, a byte at a time. */  
  57.         for( offset = 0; offset < nBytes; offset++)  
  58.         {  
  59.             byte = (remainder >> (WIDTH - 8)) ^ message[offset];  
  60.             remainder = crcTable[byte] ^ (remainder << 8);  
  61.         }  
  62.         /* The final remainder is the CRC result. */  
  63.         return (remainder ^ FINAL_XOR_VALUE);  
  64.     } /* crcCompute() */  
復制代碼

上面代碼中crcInit() 函數用來計算crcTable，因此在調用 crcCompute 前必須先調用 crcInit()。不過，對于嵌入式系統，RAM是很緊張的，最好將 crcTable 提前算好，作為常量數據存到程序存儲區而不占用RAM空間。CRC 計算實際上還有很多內容可以介紹，不過對于一般的程序員來說，知道這些也就差不多了。余下的部分以后有時間了我再寫篇文章來介紹吧。





歡迎光臨 (http://www.raoushi.com/bbs/) Powered by Discuz! X3.1