循環(huán)冗余校驗(yàn)CRC的算法分析
西南交通大學(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ò)誤地可能性增加，傳送信息地可靠性下降。若是要求可靠，則使得傳送消息地速率變慢。因此，如何合理地解決可靠性也速度這一對(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)等，這些方法都是增加數(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)式，由 。如一個(gè)8位二進(jìn)制數(shù)10110101可以表示為： 。多項(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ù)必須為1。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ù)越高，那么誤判的概率就越小。CCITT建議：2048 kbit/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗(yàn)碼生成多項(xiàng)式g（x）= 。采用16位CRC校驗(yàn)，可以保證在 bit碼元中只含有一位未被檢測(cè)出的錯(cuò)誤 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗(yàn)序列FCS中，使用CRC-16，其生成多項(xiàng)式g（x）= ；而在CCITT推薦的高級(jí)數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗(yàn)序列FCS中，使用CCITT-16，其生成多項(xiàng)式g（x）= 。CRC-32的生成多項(xiàng)式g（x）= 。CRC-32出錯(cuò)的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計(jì)算機(jī)等領(lǐng)域運(yùn)用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和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ù)據(jù)塊是m位的二進(jìn)制多項(xiàng)式t（x），生成多項(xiàng)式為r階的g（x）。在數(shù)據(jù)塊的末尾添加r個(gè)0，數(shù)據(jù)塊的長(zhǎng)度增加到m+r位，對(duì)應(yīng)的二進(jìn)制多項(xiàng)式為 。
（2） 用生成多項(xiàng)式g（x）去除 ，求得余數(shù)為階數(shù)為r-1的二進(jìn)制多項(xiàng)式y(tǒng)（x）。此二進(jìn)制多項(xiàng)式y(tǒng)（x）就是t（x）經(jīng)過(guò)生成多項(xiàng)式g（x）編碼的CRC校驗(yàn)碼。
（3） 用 以模2的方式減去y（x），得到二進(jìn)制多項(xiàng)式 。 就是包含了CRC校驗(yàn)碼的待發(fā)送字符串。
從CRC的編碼規(guī)則可以看出，CRC編碼實(shí)際上是將代發(fā)送的m位二進(jìn)制多項(xiàng)式t（x）轉(zhuǎn)換成了可以被g（x）除盡的m+r位二進(jìn)制多項(xiàng)式 ，所以解碼時(shí)可以用接受到的數(shù)據(jù)去除g（x），如果余數(shù)位零，則表示傳輸過(guò)程沒(méi)有錯(cuò)誤；如果余數(shù)不為零，則在傳輸過(guò)程中肯定存在錯(cuò)誤。許多CRC的硬件解碼電路就是按這種方式進(jìn)行檢錯(cuò)的。同時(shí) 可以看做是由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編碼的例子來(lái)說(shuō)明CRC的編碼過(guò)程。
設(shè)待發(fā)送的數(shù)據(jù)t（x）為12位的二進(jìn)制數(shù)據(jù)100100011100；CRC-4的生成多項(xiàng)式為g（x）= ，階數(shù)r為4，即10011。首先在t（x）的末尾添加4個(gè)0構(gòu)成 ，數(shù)據(jù)塊就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余數(shù)y（x）。下表為給出了除法過(guò)程。
除數(shù)次數(shù) 被除數(shù)/g（x）/結(jié)果 余數(shù)
0 1001000111000000 100111000000
10011
0000100111000000
1 100111000000 1000000
10011
000001000000
2 1000000 1100
10011
0001100
從上面表中可以看出，CRC編碼實(shí)際上是一個(gè)循環(huán)移位的模2運(yùn)算。對(duì)CRC-4，我們假設(shè)有一個(gè)5 bits的寄存器，通過(guò)反復(fù)的移位和進(jìn)行CRC的除法，那么最終該寄存器中的值去掉最高一位就是我們所要求的余數(shù)。
CRC校驗(yàn)由于實(shí)現(xiàn)簡(jiǎn)單，檢錯(cuò)能力強(qiáng)，被廣泛使用在各種數(shù)據(jù)校驗(yàn)應(yīng)用中。占用系統(tǒng)資源少，用軟硬件均能實(shí)現(xiàn)，是進(jìn)行數(shù)據(jù)傳輸差錯(cuò)檢測(cè)地一種很好的手段。
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
