循環(huán)冗余校驗(yàn)CRC的算法分析和程序?qū)崿F(xiàn)

1、循環(huán)冗余校驗(yàn)CRC的算法分析和程序?qū)崿F(xiàn)西南交通大學(xué)計(jì)算機(jī)與通信工程學(xué)院劉東摘要通信的目的是要把信息及時(shí)可靠地傳送給對(duì)方，因此要求一個(gè)通信系統(tǒng)傳輸消息必須可靠與快速，在數(shù)字通信系統(tǒng)中可靠與快速往往是一對(duì)矛盾。為了解決可靠性，通信系統(tǒng)都采用了差錯(cuò) 控制。本文詳細(xì)介紹了循環(huán)冗余校驗(yàn)CRC( Cyclic Redundancy Check )的差錯(cuò)控制原理及其算法實(shí)現(xiàn)。關(guān)鍵字通信循環(huán)冗余校驗(yàn)CRC-32 CRC-16 CRC-4概述在數(shù)字通信系統(tǒng)中可靠與快速往往是一對(duì)矛盾。若要求快速，則必然使得每個(gè)數(shù)據(jù)碼元所占地 時(shí)間縮短、波形變窄、能量減少，從而在受到干擾后產(chǎn)生錯(cuò)誤地可能性增加，傳送信息地可靠性下

2、降。若是要求可靠，則使得傳送消息地速率變慢。因此，如何合理地解決可靠性也速度這一對(duì)矛盾，是正確設(shè)計(jì)一個(gè)通信系統(tǒng)地關(guān)鍵問(wèn)題之一。為保證傳輸過(guò)程的正確性，需要對(duì)通信過(guò)程進(jìn)行差錯(cuò)控 制。差錯(cuò)控制最常用的方法是自動(dòng)請(qǐng)求重發(fā)方式(ARQ)、向前糾錯(cuò)方式(FEC)和混合糾錯(cuò)(HEC)。在傳輸過(guò)程誤碼率比較低時(shí)，用FEC方式比較理想。在傳輸過(guò)程誤碼率較高時(shí)，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象。HEC方式則式ARQ和FEC的結(jié)合。在許多數(shù)字通信中，廣泛采用ARQ方式，此時(shí)的差錯(cuò)控制只需要檢錯(cuò)功能。實(shí)現(xiàn)檢錯(cuò)功能的差錯(cuò)控制方法很多，傳統(tǒng)的有：奇偶校驗(yàn)、校驗(yàn) 和檢測(cè)、重復(fù)碼校驗(yàn)、恒比碼校驗(yàn)、行列冗余碼校驗(yàn)等，這些方法都

3、是增加數(shù)據(jù)的冗余量，將校驗(yàn) 碼和數(shù)據(jù)一起發(fā)送到接受端。接受端對(duì)接受到的數(shù)據(jù)進(jìn)行相同校驗(yàn)，再將得到的校驗(yàn)碼和接受到的 校驗(yàn)碼比較，如果二者一致則認(rèn)為傳輸正確。但這些方法都有各自的缺點(diǎn)，誤判的概率比較高。循環(huán)冗余校驗(yàn) CRC ( Cyclic Redundancy Check )是由分組線性碼的分支而來(lái)，其主要應(yīng)用是二元碼組。編碼簡(jiǎn)單且誤判概率很低，在通信系統(tǒng)中得到了廣泛的應(yīng)用。下面重點(diǎn)介紹了CRC校驗(yàn)的原理及其算法實(shí)現(xiàn)。一、循環(huán)冗余校驗(yàn)碼(CRC)CRC校驗(yàn)采用多項(xiàng)式編碼方法。被處理的數(shù)據(jù)塊可以看作是一個(gè)n階的二進(jìn)制多項(xiàng)式，由anixnJL anxx -a,x - a0。如一個(gè)8位二進(jìn)制數(shù)101

4、10101可以表示為：7654321x 0x 1x 1x 0x 1x 0x 1 o多項(xiàng)式乘除法運(yùn)算過(guò)程與普通代數(shù)多項(xiàng)式的乘除法相同。多項(xiàng)式的加減法運(yùn)算以2為模，加減時(shí)不進(jìn)，錯(cuò)位，和邏輯異或運(yùn)算一致。采用CRC校驗(yàn)時(shí)，發(fā)送方和接收方用同一個(gè)生成多項(xiàng)式g (x)，并且g (x)的首位和最后一位的系數(shù)必須為1o CRC的處理方法是：發(fā)送方以 g ( x)去除t (x)，得到余數(shù)作為 CRC校驗(yàn)碼。 校驗(yàn)時(shí)，以計(jì)算的校正結(jié)果是否為 0為據(jù)，判斷數(shù)據(jù)幀是否出錯(cuò)。CRC校驗(yàn)可以100 %地檢測(cè)出所有奇數(shù)個(gè)隨機(jī)錯(cuò)誤和長(zhǎng)度小于等于k ( k為g (x)的階數(shù))的突發(fā)錯(cuò)誤。所以 CRC的生成多項(xiàng)式的階數(shù)越高，那

5、么誤判的概率就越小。CCITT建議：2048 kbit/s2。在IBM的同步數(shù)據(jù)鏈的PCM基群設(shè)備采用 CRC-4方案，使用的CRC校驗(yàn)碼生成多項(xiàng)式 g (x) =x4 x T。采用16 位CRC校驗(yàn)，可以保證在1014 bit碼元中只含有一位未被檢測(cè)出的錯(cuò)誤路控制規(guī)程SDLC的幀校驗(yàn)序列FCS中，使用CRC-16，其生成多項(xiàng)式g (x) =x16 x15 x2 1 ;而在CCITT推薦的高級(jí)數(shù)據(jù)鏈路控制規(guī)程 HDLC的幀校驗(yàn)序列FCS中，使用CCITT-16 ,其生成多 項(xiàng)式 g ( x )= x16 x15 x51。 CRC-32 的生成多項(xiàng)式 g ( x )322623221612111

6、087542=x x x x x x x x x x x x x x 1 o CRC-32 出錯(cuò)的概率比CRC-16低10-倍。由于CRC-32的可靠性，把 CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以 在通信、計(jì)算機(jī)等領(lǐng)域運(yùn)用十分廣泛。 在一些UART通信控制芯片（如MC6582、lntel8273和Z80-SIO） 內(nèi)，都采用了 CRC校驗(yàn)碼進(jìn)行差錯(cuò)控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用 CRC-32進(jìn)行差錯(cuò)控制。二、CRC校驗(yàn)碼的算法分析CRC校驗(yàn)碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)t（x）除以生成多項(xiàng)式 g（ x），將最后的余數(shù)作為CRC校驗(yàn)碼。其實(shí)現(xiàn)步驟如下：（1） 設(shè)待發(fā)送的數(shù)

7、據(jù)塊是 m位的二進(jìn)制多項(xiàng)式t（x），生成多項(xiàng)式為r階的g（ x）o在數(shù)據(jù)塊 的末尾添加r個(gè)0，數(shù)據(jù)塊的長(zhǎng)度增加到 m+r位，對(duì)應(yīng)的二進(jìn)制多項(xiàng)式為 xrt（x）。（2）用生成多項(xiàng)式g（ x）去除xrt（x），求得余數(shù)為階數(shù)為 r-1的二進(jìn)制多項(xiàng)式y(tǒng) （x）o此二進(jìn) 制多項(xiàng)式y(tǒng)（ x）就是t（ x）經(jīng)過(guò)生成多項(xiàng)式 g（ x）編碼的CRC校驗(yàn)碼。（3） 用xrt（x）以模2的方式減去y（x）,得到二進(jìn)制多項(xiàng)式 xrt'（x）。xrt'（x）就是包含了 CRC 校驗(yàn)碼的待發(fā)送字符串。從CRC的編碼規(guī)則可以看出，CRC編碼實(shí)際上是將代發(fā)送的m位二進(jìn)制多項(xiàng)式t（x）轉(zhuǎn)換成了可以被g（x）除

8、盡的m+r位二進(jìn)制多項(xiàng)式xrt'（x），所以解碼時(shí)可以用接受到的數(shù)據(jù)去除g（x），如果余數(shù)位零，則表示傳輸過(guò)程沒(méi)有錯(cuò)誤；如果余數(shù)不為零，則在傳輸過(guò)程中肯定存在錯(cuò)誤。許多 CRC的硬件解碼電路就是按這種方式進(jìn)行檢錯(cuò)的。同時(shí)xrt'（x）可以看做是由t（x）和CRC校驗(yàn)碼的組合，所以解碼時(shí)將接收到的二進(jìn)制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。為了更清楚的了解 CRC校驗(yàn)碼的編碼過(guò)程， 下面用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明CRC校驗(yàn)碼的編碼過(guò)程。由于 CRC-32、CRC-16、CCITT和CRC-4的編碼過(guò)程基本一致，只有位數(shù)和生成多項(xiàng)式不 一樣。為了敘述簡(jiǎn)單，用一個(gè)CRC-4編碼的例

9、子來(lái)說(shuō)明 CRC的編碼過(guò)程。設(shè)待發(fā)送的數(shù)據(jù)t（x）為12位的二進(jìn)制數(shù)據(jù) 100100011100； CRC-4的生成多項(xiàng)式為 g（ x） =x4 x 7,階數(shù)r為4,即10011o首先在t（ x）的末尾添加4個(gè)0構(gòu)成x4t（x），數(shù)據(jù)塊就成了 1001000111000000。然后用g（ x）去除x4t（x），不用管商是多少，只需要求得余數(shù) y（x）。下表為 給出了除法過(guò)程。除數(shù)次數(shù)被除數(shù)/ g（ x） /結(jié)果余數(shù)01 0010001110000001001110000001 0011000010011100000011 0011100000010000001 0011000001000000

10、21 00000011001 00110001100從上面表中可以看出， CRC編碼實(shí)際上是一個(gè)循環(huán)移位的模2運(yùn)算。對(duì)CRC-4，我們假設(shè)有 一個(gè) 5 bits 的寄存器， 通過(guò)反復(fù)的移位和進(jìn)行 CRC 的除法， 那么最終該寄存器中的值去掉最高一位 就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述：/reg 是一個(gè) 5 bits 的寄存器把 reg 中的值置 0.把原始的數(shù)據(jù)后添加 r 個(gè) 0.While （ 數(shù)據(jù)未處理完 ）BeginIf （reg 首位是 1）reg = reg XOR 0011.把 reg 中的值左移一位，讀入一個(gè)新的數(shù)據(jù)并置于 register 的 0 bit

11、的位置。Endreg 的后四位就是我們所要求的余數(shù)。這種算法簡(jiǎn)單，容易實(shí)現(xiàn)，對(duì)任意長(zhǎng)度生成多項(xiàng)式的G （x）都適用。在發(fā)送的數(shù)據(jù)不長(zhǎng)的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長(zhǎng)的話，這種方法就不太適合了。它一次只能處理一位數(shù) 據(jù)，效率太低。為了提高處理效率，可以一次處理 4位、8 位、16位、32位。由于處理器的結(jié)構(gòu)基 本上都支持 8位數(shù)據(jù)的處理，所以一次處理 8 位比較合適。為了對(duì)優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個(gè)角度理解一下。在上面例子中， 可以將編碼過(guò)程看作如下過(guò)程：由于最后只需要余數(shù)，所以我們只看后四位。構(gòu)造一個(gè)四位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg0（ reg的

12、0位），同時(shí)reg3的數(shù)據(jù)移出reg。有上面的算法可以知道，只有當(dāng)移出的數(shù)據(jù) 為1時(shí)，reg才和g（ x）進(jìn)行XOR運(yùn)算；移出的數(shù)據(jù)為 0時(shí)，reg不與g（x）進(jìn)行XOR運(yùn)算，相 當(dāng)與和0000進(jìn)行XOR運(yùn)算。就是說(shuō)，reg和什么樣的數(shù)據(jù)進(jìn)行 XOR移出的數(shù)據(jù)決定。由于只有一 個(gè)bit，所以有21種選擇。上述算法可以描述如下，/reg 是一個(gè) 4 bits 的寄存器初始化 t=0011,0000把 reg 中的值置 0.把原始的數(shù)據(jù)后添加 r 個(gè) 0.While （ 數(shù)據(jù)未處理完 ）Begin把 reg 中的值左移一位，讀入一個(gè)新的數(shù)據(jù)并置于 register 的 0 bit 的位置。reg

13、= reg XOR t 移出的位 End上面算法是以 bit 為單位進(jìn)行處理的， 可以將上述算法擴(kuò)展到 8 位，即以 Byte 為單位進(jìn)行處理， 即CRC-32。構(gòu)造一個(gè)四個(gè) Byte的寄存器reg，初值為0x00000000，數(shù)據(jù)依次移入 reg0（ reg的0 字節(jié)，以下類(lèi)似），同時(shí)reg3的數(shù)據(jù)移出reg。用上面的算法類(lèi)推可知，移出的數(shù)據(jù)字節(jié)決定reg和什么樣的數(shù)據(jù)進(jìn)行 XOR。由于有8個(gè)bit，所以有28種選擇。上述算法可以描述如下：/reg 是一個(gè) 4 Byte 的寄存器初始化t = 共有28 = 256項(xiàng)把 reg 中的值置 0.把原始的數(shù)據(jù)后添加 r/8 個(gè) 0 字節(jié).While

14、 （ 數(shù)據(jù)未處理完 ）Begin把reg中的值左移一個(gè)字節(jié)，讀入一個(gè)新的字節(jié)并置于reg的第0個(gè)byte的位置。reg = reg XOR t 移出的字節(jié) End算法的依據(jù)和多項(xiàng)式除法性質(zhì)有關(guān)。如果一個(gè)m位的多項(xiàng)式t （x）除以一個(gè)r階的生成多項(xiàng)式g (x), t(x) =amxm+am/Xm，+ +a2x2 十印乂1+a0，將每一位 akxk (0=<k<m )提出來(lái)，在后面不足r個(gè)0后，單獨(dú)去除g(x)，得到的余式位yk(x)。則將ymJ(x) - ym(x)：t:壯y0 (x) 后得到的就是t( x)由生成多項(xiàng)式g( x)得到的余式。對(duì)于 CRC-32，可以將每個(gè)字節(jié)在后面補(bǔ)

15、上 32個(gè)0后與生成多項(xiàng)式進(jìn)行運(yùn)算，得到余式和此字節(jié)唯一對(duì)應(yīng)，這個(gè)余式就是上面算法種t中的值，由于一個(gè)字節(jié)有8位，所以t共有28 = 256項(xiàng)。多項(xiàng)式運(yùn)算性質(zhì)可以參見(jiàn)參考文獻(xiàn)1。這種算法每次處理一個(gè)字節(jié)，通過(guò)查表法進(jìn)行運(yùn)算，大大提高了處理速度，故為大多數(shù)應(yīng)用所采用。三、CRC-32的程序?qū)崿F(xiàn)。為了提高編碼效率，在實(shí)際運(yùn)用中大多采用查表法來(lái)完成CRC-32校驗(yàn)，下面是產(chǎn)生CRC-32校驗(yàn)嗎的子程序。un sig ned long crc_32_tab256=0x00000000,0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,

16、0xe963a535,0x9e6495a3,0x0edb8832, 0x5a05df1b, 0x2d02ef8d；/事先計(jì)算出的參數(shù)表，共有256項(xiàng)，未全部列出。un sig ned long Gen erateCRC32(char xdata * DataBuf,u nsig ned long len)un sig ned long oldcrc32;un sig ned long crc32;un sig ned long oldcrc;un sig ned int charc nt;char c,t;oldcrc32 = 0x00000000; / 初值為 0charc nt=0;whi

17、le (le n-) t= (oldcrc32 >> 24) & 0xFF;要移出的字節(jié)的值oldcrc=crc_32_tabt;/根據(jù)移出的字節(jié)的值查表c=DataBufcharcnt;/新移進(jìn)來(lái)的字節(jié)值oldcrc32= (oldcrc32 << 8) | c;/將新移進(jìn)來(lái)的字節(jié)值添在寄存器末字節(jié)中oldcrc32=oldcrc32Aoldcrc;將寄存器與查出的值進(jìn)行xor運(yùn)算charc nt+;crc32=oldcrc32;return crc32;參數(shù)表可以先在 PC機(jī)上算出來(lái)，也可在程序初始化時(shí)完成。下面是用于計(jì)算參數(shù)表的c語(yǔ)言子程序，在 Visua

18、l C+ 6.0下編譯通過(guò)。#in clude <stdio.h>un sig ned long int crc32_table256;un sig ned long int ulPo lyno mial = 0x04c11db7;un sig ned long int Reflect (un sig ned long int ref, char ch) un sig ned long int value(0);/ 交換 bit0 和 bit7, bitl 和 bit6，類(lèi)推for(int i = 1; i < (ch + 1); i+)if(ref & 1)value |= 1 << (ch - i);ref >>= 1;return value;init_crc32_table() unsigned long int crc,temp;/ 256 個(gè)值for(int i = 0; i <= 0xFF; i+) temp