循環(huán)冗余校驗(共6頁)

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

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

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

4、+ + + 。如一個8 位二進制數(shù) 可以表示為：1x7 + 0x6 +1x5 +1x4 + 0x3 +1x2 + 0x +1。多項式乘除法運算過程與普通代數(shù)多項式的乘除法相同。多項式的加減法運算以2 為模，加減時不進，錯位，和邏輯異或運算一致。采用 CRC 校驗時，發(fā)送方和接收方用同一個生成多項式g（x）_,并且g（x）的首位和最后一位的系數(shù)必須為1。CRC 的處理方法是：發(fā)送方以g（x）去除t（x），得到余數(shù)作為CRC 校驗碼。校驗時，以計算的校正結(jié)果是否為0 為據(jù)，判斷數(shù)據(jù)幀是否出錯。CRC 校驗可以100地檢測出所有奇數(shù)個隨機錯誤和長度小于等于k（k 為g（x）的階數(shù)）的突發(fā)錯誤。所以C

5、RC 的生成多項式的階數(shù)越高，那么誤判的概率就越小。CCITT 建議：2048 kbit/s的PCM 基群設(shè)備采用CRC-4 方案，使用的CRC 校驗碼生成多項式g（x）= x4 + x +1。采用16位CRC 校驗，可以保證在1014 bit 碼元中只含有一位未被檢測出的錯誤2。在IBM 的同步數(shù)據(jù)鏈路控制規(guī)程SDLC 的幀校驗序列FCS中，使用CRC-16，其生成多項式g（x）= x16 + x15 + x2 +1；而在CCITT 推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC 的幀校驗序列FCS 中，使用CCITT-16，其生成多項式g （ x ） = x16 + x15 + x5 +1 。CRC-

6、32 的生成多項式g （ x ）= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x +1。CRC-32出錯的概率比CRC-16低105 倍4。由于CRC-32 的可靠性，把CRC-32 用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計算機等領(lǐng)域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273 和Z80-SIO）內(nèi)，都采用了CRC 校驗碼進行差錯控制；以太網(wǎng)卡芯片、MPEG 解碼芯片中，也采用CRC-32 進行差錯控制。二、CRC 校驗碼的算法分析CRC 校驗碼的編碼方法是用

7、待發(fā)送的二進制數(shù)據(jù)t（x）除以生成多項式g（x），將最后的余數(shù)作為CRC 校驗碼。其實現(xiàn)步驟如下：（1） 設(shè)待發(fā)送的數(shù)據(jù)塊是m 位的二進制多項式t（x），生成多項式為r 階的g（x）。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m+r位，對應(yīng)的二進制多項式為xr t(x)。（2） 用生成多項式g（x）去除xr t(x)，求得余數(shù)為階數(shù)為r-1 的二進制多項式y(tǒng)（x）。此二進制多項式y(tǒng)（x）就是t（x）經(jīng)過生成多項式g（x）編碼的CRC 校驗碼。（3） 用xr t(x)以模2 的方式減去y（x），得到二進制多項式xr t'(x)。xr t'(x)就是包含了CRC校驗碼的待發(fā)送字符

8、串。從 CRC 的編碼規(guī)則可以看出，CRC 編碼實際上是將代發(fā)送的m 位二進制多項式t（x）轉(zhuǎn)換成了可以被g（x）除盡的m+r位二進制多項式xr t'(x)，所以解碼時可以用接受到的數(shù)據(jù)去除g（x），如果余數(shù)位零，則表示傳輸過程沒有錯誤；如果余數(shù)不為零，則在傳輸過程中肯定存在錯誤。許多CRC 的硬件解碼電路就是按這種方式進行檢錯的。同時xr t'(x)可以看做是由t（x）和CRC校驗碼的組合，所以解碼時將接收到的二進制數(shù)據(jù)去掉尾部的r 位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。為了更清楚的了解 CRC 校驗碼的編碼過程，下面用一個簡單的例子來說明CRC 校驗碼的編碼過程。由于CRC-32、C

9、RC-16、CCITT 和CRC-4 的編碼過程基本一致，只有位數(shù)和生成多項式不一樣。為了敘述簡單，用一個CRC-4 編碼的例子來說明CRC 的編碼過程。設(shè)待發(fā)送的數(shù)據(jù) t（x）為12 位的二進制數(shù)據(jù)0；CRC-4 的生成多項式為g（x）= x4 + x +1，階數(shù)r為4，即10011。首先在t（x）的末尾添加4 個0 構(gòu)成x4t(x)，數(shù)據(jù)塊就成了00000。然后用g（x）去除x4t(x)，不用管商是多少，只需要求得余數(shù)y（x）。下表為給出了除法過程。從上面表中可以看出，CRC 編碼實際上是一個循環(huán)移位的模2 運算。對CRC-4，我們假設(shè)有除數(shù)次數(shù)被除數(shù)/ g（x）/結(jié)果余數(shù)1 00001

10、001100 000001 1 001110 1 1 001120 1100一個5 bits 的寄存器，通過反復(fù)的移位和進行CRC 的除法，那么最終該寄存器中的值去掉最高一位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述：/reg 是一個5 bits 的寄存器把 reg 中的值置0.把原始的數(shù)據(jù)后添加r 個0.While (數(shù)據(jù)未處理完)BeginIf (reg 首位是1)reg = reg XOR 0011.把reg 中的值左移一位，讀入一個新的數(shù)據(jù)并置于register 的0 bit 的位置。Endreg 的后四位就是我們所要求的余數(shù)。這種算法簡單，容易實現(xiàn)，對任意長度生成多項式

11、的G（x）都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長的話，這種方法就不太適合了。它一次只能處理一位數(shù)據(jù)，效率太低。為了提高處理效率，可以一次處理4 位、8 位、16 位、32 位。由于處理器的結(jié)構(gòu)基本上都支持8 位數(shù)據(jù)的處理，所以一次處理8 位比較合適。為了對優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個角度理解一下。在上面例子中，可以將編碼過程看作如下過程：由于最后只需要余數(shù)，所以我們只看后四位。構(gòu)造一個四位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg0（reg 的0 位），同時reg3 的數(shù)據(jù)移出reg。有上面的算法可以知道，只有當(dāng)移出的數(shù)據(jù)為1 時，reg 才和

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

13、te 為單位進行處理，即CRC-32。構(gòu)造一個四個Byte 的寄存器reg，初值為0x，數(shù)據(jù)依次移入reg0（reg 的0字節(jié)，以下類似），同時reg3 的數(shù)據(jù)移出reg。用上面的算法類推可知，移出的數(shù)據(jù)字節(jié)決定reg 和什么樣的數(shù)據(jù)進行XOR。由于有8 個bit，所以有28種選擇。上述算法可以描述如下：/reg 是一個4 Byte 的寄存器初始化 t/共有28256 項把 reg 中的值置0.把原始的數(shù)據(jù)后添加r/8 個0 字節(jié).While (數(shù)據(jù)未處理完)Begin把reg 中的值左移一個字節(jié)，讀入一個新的字節(jié)并置于reg 的第0 個byte 的位置。reg = reg XOR t移出的字

14、節(jié)End算法的依據(jù)和多項式除法性質(zhì)有關(guān)。如果一個m 位的多項式t（x）除以一個r 階的生成多項式g（x）， 01122221t(x) a 1x a x a x a x a mmmm = + + + + + ，將每一位kk a x （0=<k<m）提出來，在后面不足r個0 后，單獨去除g（x），得到的余式位y (x) k 。則將( ) ( ) ( ) 1 2 0 y x y x y x m m 后得到的就是t（x）由生成多項式g（x）得到的余式。對于CRC-32，可以將每個字節(jié)在后面補上32 個0 后與生成多項式進行運算，得到余式和此字節(jié)唯一對應(yīng)，這個余式就是上面算法種t中的值，由于

15、一個字節(jié)有8 位，所以t共有28256 項。多項式運算性質(zhì)可以參見參考文獻(xiàn)1。這種算法每次處理一個字節(jié)，通過查表法進行運算，大大提高了處理速度，故為大多數(shù)應(yīng)用所采用。三、CRC-32 的程序?qū)崿F(xiàn)。為了提高編碼效率，在實際運用中大多采用查表法來完成 CRC-32 校驗，下面是產(chǎn)生CRC-32校驗嗎的子程序。unsigned long crc_32_tab256=0x, 0x, 0xee0e612c, 0xba, 0x076dc419, 0x706af48f, 0xe963a535,0x9e6495a3,0x0edb8832, 0x5a05df1b, 0x2d02ef8d;/事先計算出的參數(shù)表，共

16、有256 項，未全部列出。unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len)unsigned long oldcrc32;unsigned long crc32;unsigned long oldcrc;unsigned int charcnt;char c,t;oldcrc32 = 0x; /初值為0charcnt=0;while (len-) t= (oldcrc32 >> 24) & 0xFF; /要移出的字節(jié)的值oldcrc=crc_32_tabt; /根據(jù)移出的字節(jié)的值查表c=Da

17、taBufcharcnt; /新移進來的字節(jié)值oldcrc32= (oldcrc32 << 8) | c; /將新移進來的字節(jié)值添在寄存器末字節(jié)中oldcrc32=oldcrc32oldcrc; /將寄存器與查出的值進行xor 運算charcnt+;crc32=oldcrc32;return crc32;參數(shù)表可以先在PC 機上算出來，也可在程序初始化時完成。下面是用于計算參數(shù)表的c 語言子程序，在Visual C+ 6.0 下編譯通過。#include <stdio.h>unsigned long int crc32_table256;unsigned long in

18、t ulPolynomial = 0x04c11db7;unsigned long int Reflect(unsigned long int ref, char ch) unsigned long int value(0);/ 交換bit0 和bit7，bit1 和bit6，類推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 個值for(int i = 0; i <= 0xFF; i+) temp=Reflect(i, 8);crc32_tablei= temp<< 24;for (int j = 0; j < 8; j+)uns