1、天津輕工業學院學報JOURNAL OF TIANJ IN INSTITUTE OF LIGHT INDUSTRY1999年第4期N o 41999循環冗余校驗的原理及軟件實現葛方暉(天津職業技術師范學院自動化系，天津300222)摘要：論述了循環冗余校驗的數學模型以及編碼原理，并給岀了軟件的實現方法。關鍵詞：數據通信；信道;循環冗余校驗；生成多項式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在數據通信的過程中，由于信道傳輸特性不理想和加性噪聲的影響，所收到的數字信號不可避免地會受到干擾，嚴重時發生誤碼，影響系統的工作。在接收端為了檢查所收到的數 據是否正確，可采用多種檢錯方法。比如奇偶校驗法，校驗和法以及行列冗余碼校驗等，但都有一定缺乏。本文介

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

5、暉（19702，男（漢族），江蘇人，講師，碩士. 1994-2蝕9 ChiiKi Acadwnic Joumal blectrcuiit Publishing Hcu池，All right s rcscFvcd,cnk第4期葛方暉：循環冗余校驗的原理及軟件實現47假設待編碼的k位信息是：M =(m k- i, m k- 2,m 2, m i, m o)它所對應的信息多項式是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)循環碼生成多項式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) 的倍式，其次數等于或小于(n- 1)。所以xn- k? M (x)+ R (x)是g (x )生成的循環碼的一個 碼多項式,把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此碼多項式對應的碼字是 所以碼字是由不加改變的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 )若傳輸正確，則余數為零，當余數為非零時，判斷數據傳送有誤，以達到數據通信的檢錯目的。例如：對于(7,3)循環碼，待編碼的信息為M = 101,生成多項式g (x)= x4+ x'+ x2+ 1, 則 M (x)= x2+ 1x7- 3? M (x)= x

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

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

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

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