循環(huán)冗余校驗的原理及軟件實現(xiàn)

1、天津輕工業(yè)學(xué)院學(xué)報JOURNAL OF TIANJ IN INSTITUTE OF LIGHT INDUSTRY1999年第4期N o 41999循環(huán)冗余校驗的原理及軟件實現(xiàn)葛方暉(天津職業(yè)技術(shù)師范學(xué)院自動化系，天津300222)摘要：論述了循環(huán)冗余校驗的數(shù)學(xué)模型以及編碼原理，并給岀了軟件的實現(xiàn)方法。關(guān)鍵詞：數(shù)據(jù)通信；信道;循環(huán)冗余校驗；生成多項式1中圖法分類號：TN 911172文獻標識碼:A文章編號:1001 2456X (1999 ) 0420046 203石左?"弩E $ %陜也r> 自 F*""-t"站 吃由n Vi 4 i> U如

2、_其!_田r 工沖 PII i m',1 訂' Vill1月fl v .丄£甘左諄PR INCIPL EOF CYCL IC RED UNDANCY CHECK廣于啦苫胡VX利:iii AV*AND SOFTWARE REAL IZAT IONGE Fang-hu i(T ianjin V ocati onal and T echnical T eachers' Co liege, T ianjin 300222Ch ina)Abstract : T h is paper p resents the m athem aticalmodeland coding

3、p rinci p le ofcyclicredundancycheck , and show the softw are m plem entati on.Key words : D ata Comm unicati on ; Channel ; CyclicRedundancy Check ; Generato rPo lynomial在數(shù)據(jù)通信的過程中，由于信道傳輸特性不理想和加性噪聲的影響，所收到的數(shù)字信號不可避免地會受到干擾，嚴重時發(fā)生誤碼，影響系統(tǒng)的工作。在接收端為了檢查所收到的數(shù) 據(jù)是否正確，可采用多種檢錯方法。比如奇偶校驗法，校驗和法以及行列冗余碼校驗等，但都有一定缺乏。本文介

4、紹一種強有力的檢錯方法，即循環(huán)冗余校驗，并將其成功地應(yīng)用于無線 測控系統(tǒng)中，收到了令人滿意的效果。1循環(huán)冗余校驗的數(shù)學(xué)模型循環(huán)冗余校驗簡稱循環(huán)碼或CRC碼(Cyclic Redundancy Check)，是一種高效能的檢錯和糾錯碼，在數(shù)據(jù)通信中應(yīng)用甚廣。循環(huán)碼編碼通過模 2運算來建立信息位和校驗位之間的 約束關(guān)系。首先將所傳數(shù)據(jù)看成高次多項式，把此多項式除以預(yù)先給定的生成多項式，其余 數(shù)作為校驗位附加在所傳數(shù)據(jù)的尾部一并傳送，即在一個長度為n的碼組中有k個信息和r個校驗位。譯碼時用同樣的生成多項式去除，若余數(shù)為零，則可判斷收到的數(shù)據(jù)是正確的。S收稿日期：19992082103 作者簡介：葛方

5、暉（19702，男（漢族），江蘇人，講師，碩士. 1994-2蝕9 ChiiKi Acadwnic Joumal blectrcuiit Publishing Hcu池，All right s rcscFvcd,cnk第4期葛方暉：循環(huán)冗余校驗的原理及軟件實現(xiàn)47假設(shè)待編碼的k位信息是：M =(m k- i, m k- 2,m 2, m i, m o)它所對應(yīng)的信息多項式是k- 1k- 2M (x) = m k- 1x + m k- 2x+2+ m 2x + m1x+ m0用xn- k乘M(x)得：n- kn- 1n- 2x M(x ) = m k- ix + m k- 2x+n- k+ 2+

6、 m 2x+n- k+ in- km ix + m ox用給定的(n, k)循環(huán)碼生成多項式g (x)除xn k? M (x)得：x" k? M (x) = q(x)? g (x) + R (x)(1)式中q(x)和R(x)分別是除法的商式和余式。因為生成多項式g(x)是(n- k)次，所以R (x ) 一定是等于或小于(n- k- 1)次,即：R (x) =rn-k-ix"-" 1 +rn-k- 2- k- 2+ +r2x2+rix+ro由 式得 xn- k?M (x)+ R(x)= q(x)? g (x),上式表明 xn- k? M (x)+ R (x)是 g

7、(x) 的倍式，其次數(shù)等于或小于(n- 1)。所以xn- k? M (x)+ R (x)是g (x )生成的循環(huán)碼的一個 碼多項式,把xn- k? M (x) + R (x)展開得：xn-k?M (x) +n- 1n- 2R (x) = m k- 1 ? x + m k- 2 ? x +n- k+ 2n - k+ 1+ m 2x+ m 1 x此碼多項式對應(yīng)的碼字是 所以碼字是由不加改變的n- kn - k- 1n - k- 22+ m °x + n- k- 1x + n- k- 2x + +r?x+ 2x+ r°:(mk- 1, mk- 2,m 2, m 1 ,m o, r

8、n- k- 1, rn- k- 2r2, r 1, ro)k位信息碼元，其后再附加(n- k)位校驗碼元組成的。在接收端，對收到的碼字進行譯碼,即除以g (x)xn-k?M (x) + R (x) g (x)= q(x)? g (x) + R (x)+ R (x) g (x)=q (x) ? g (x ) g (x ) = q (x )若傳輸正確，則余數(shù)為零，當余數(shù)為非零時，判斷數(shù)據(jù)傳送有誤，以達到數(shù)據(jù)通信的檢錯目的。例如：對于(7,3)循環(huán)碼，待編碼的信息為M = 101,生成多項式g (x)= x4+ x'+ x2+ 1, 則 M (x)= x2+ 1x7- 3? M (x)= x

9、4(x2+ 1)= x6+ x4,其碼字為1010000,運用長除法，所以碼字為 1010011,傳送時將信息位與校驗位一同發(fā)出，在接收方譯碼時，也采用相同的長除法。若余數(shù)為零，則接收正確。2生成多項式g(x)的種類用于進行CRC除法的生成多項式有多種，推薦使用的有3種：(1)CRC212：用于6位字符的同步系統(tǒng)中，校驗碼組長12位,生成多項式是g(x)= x12+ x11+ x3+ x2+ x+ 1它能檢測出長度在12位以內(nèi)的突發(fā)差錯。(2)CRC216：用于8位字符的同步系統(tǒng)，校驗碼組長16位,生成多項式是g (x) = x16+ x15+ x 2+ 1它能檢測出全部16位以下和16位長的

10、突發(fā)差錯，以及99%的長度大于16位的突發(fā)差錯。(3) CRC2DCITT：也是對8位字符進行計算，產(chǎn)生的校驗碼組長16位,生成多項式是16g (x)= x +12其檢錯能力同CRC216。© 994-20ChinaJoumal Electronic PublishiiigAH rights reserved,48?天津輕工業(yè)學(xué)院學(xué)報1999年10月3 CRC校驗的軟件實現(xiàn)在實現(xiàn)循環(huán)碼的編碼時，大體有兩種方法，即硬件法 和軟件法。硬件法采用除法電路來完成，該除法電路是一 個根據(jù)生成多項式而形成的帶反饋連接的移位寄存器，在很多通信設(shè)備中已廣泛采用。但在有些系統(tǒng)中，為了簡化硬件設(shè)備，往往

11、采用軟件的方法來實現(xiàn)。循環(huán)碼編碼在軟件實現(xiàn)過程中，多項式的除法運算是通過右移移位和異或運算來完成的。在本系統(tǒng)中采用 的生成多項式是CRC216,即g(x)= x16+ x15+ x?+ 1。由 于在進行異或運算的過程中，其最高位的運算結(jié)果是已 知的，即當信息位多項式右移，移出位為“1”時與生成多 項式進行異或運算，其運算結(jié)果必定為 0,因此當信息多 項式移出位為“1 ”時，移出位可不參加運算，生成多項式 的最高位也不參加運算，也不需存儲，于是兩個字節(jié)就可 以表達一個17比特的生成多項式，所以參與異或運算的 生成多項式只用兩個字節(jié)表示 。對一幀數(shù)據(jù)進行 CRC編碼的軟件流程見圖1。流程圖中，3字

12、節(jié)右移一位操作，是將Ro的最低位 移出，R1的最低位移入 Ro的最高位，R2的最低位移入 R1的最高位，R2的最高位補0,之所以這樣做，是為了保 證R1R0與# A 001H異或時，R1的最高位總是信息位 ， 當右移8次后，R2中的數(shù)值為0,而R1R0中為余數(shù)，完成 一個字節(jié)的運算。此時再取數(shù)據(jù)區(qū)中的下一個數(shù)據(jù)，送入R 2中,繼續(xù)上述操作，直到數(shù)據(jù)長度減為 0時為止，R 1R 0 中即為CRC校驗位，也就是這一幀數(shù)據(jù)的余數(shù)位。解碼過程與編碼過程相似，操作時兩個字節(jié)的 CRC 位不清0,直接參與運算，當信息字節(jié)長度減為 0時, R1R0的值為0,則表示接收正確，否則有誤。需要說明的是，由于右移操作是把信息字節(jié)中的最 低位當作最高位進行運算，則生成多項式也需按逆序運將一林據(jù)未尾 境加兩牛字節(jié)務(wù)這圖牛字節(jié)淸0 做為將素的CRC指針常向數(shù)據(jù)區(qū)首址 井將所揩數(shù)據(jù)"陽數(shù)據(jù)指卡1 .將所三字節(jié)右移一悅 蔣出悅為用的晟低位將生馬與# A001H異或移位次數(shù)喊1檢度宇節(jié)誡1加曲中的數(shù)值即対 CRC校驗位圖1 CRC編碼流程圖算,即 x15+ x2+ 1 的 16進制形式為(1000 0000 0000 0101)B= 8005 H,其逆序為(1010 00000000 0001)b= A 001 H。正序和逆序的性質(zhì)是一樣的，使用哪種方式由與之通信的上位機