文檔RS糾錯編碼原理及其實現(xiàn)方法.doc

Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 1 RS糾錯編碼原理 及其實現(xiàn)方法 陳文禮 January 08 于鄭州 If you have any suggestion or criticism . please email to QQ83902112 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 2前言 隨著越來越多的系統(tǒng)采用數(shù)字技術(shù)來實現(xiàn)糾錯編碼技術(shù)也得到了越來越廣泛的應(yīng)用。RS碼既可以糾正隨機(jī)錯誤又可以糾正突發(fā)錯誤具有很強(qiáng)的糾錯能力在通信系統(tǒng)中應(yīng)用廣泛。近些年來隨著軟件無線電技術(shù)的發(fā)展RS編碼、譯碼一般都在通用的硬件平臺上實現(xiàn)。通常采用基于FPGA的VHDL編碼硬件實現(xiàn)或者在DSP、單片機(jī)上用C和匯編編程軟件實現(xiàn)。 RS糾錯編碼涉及的領(lǐng)域很廣特別是設(shè)計到很多數(shù)學(xué)知識。這對那些對數(shù)學(xué)不太感冒的工程技術(shù)人員來書是個不小的挑戰(zhàn)。盡管講RS編碼的書籍很多但是那些書都是采用循序漸進(jìn)逐步引入的方式從漢明碼到循環(huán)碼從循環(huán)碼到BCH碼BCH碼再引入RS碼。對于工程技術(shù)人員他們需要的是簡明扼要的講解和詳細(xì)的實現(xiàn)方法。 本人寫這篇文章的宗旨就是盡量最簡單的語言最簡短的篇幅來講RS糾錯編碼原理把重點來放在實現(xiàn)方法上。 為了便于讀者仿真本文采樣MATLAB程序?qū)崿F(xiàn)程序盡量符合硬件C語言寫法讀者經(jīng)過簡單修改即可應(yīng)用到工程中去。 本文讀者對象 本文是為那些初識RS編碼的學(xué)生、工程技術(shù)人員而寫并不適合做理論研究如果你是糾錯編碼方面的學(xué)者、專家那么本文并不適合你。 由于作者水平有限錯誤在所難免懇請讀者批評指正。 陳文禮 2008-01 于鄭州 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 3一、必備的一些代數(shù)知識 1、在糾錯編碼代數(shù)中把以二進(jìn)制數(shù)字表示的一個數(shù)據(jù)系列看成一個多項式。例如二進(jìn)制數(shù)字序列10101111可以表示成 式中的ix表示代碼的位置或某個二進(jìn)制數(shù)位的位置ix前面的系數(shù)ia表示碼的值。若ia是一位二進(jìn)制代碼則取值是0或1。Mx稱為信息代碼多項式。 多項式次數(shù) 稱系數(shù)不為0 的x的最高次數(shù)為多項式fx的次數(shù)記為fx。 2、域 域在RS編碼理論中起著至關(guān)重要的作用。 簡單點說域2mGF有2m 設(shè)2mq個符號 0120q 且具有以下性質(zhì) 域中的每個元素都可以用0121ma的和來表示。11q 為本原多項式px的根。 運算規(guī)則有 在糾錯編碼運算過程中加、減、乘和除的運算是在伽羅華域中進(jìn)行?，F(xiàn)以GF24域中運算為例 加法例108001001110101 模2加法相當(dāng)于0010與0111異或 減法運算與加法相同 乘法例810810mod153 除法例810221513/ 不理解沒關(guān)系下面的例子也許對你有幫助。 例 m4 41pxxx 求2mGF的所有元素 因為為px的根 得到410 或41 根據(jù)運算規(guī)則 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 4由此可以得到域的所有元素 元素 二進(jìn)制對應(yīng)碼 十進(jìn)制對應(yīng)值 0 0 0000 0 0 1 0001 1 1 1 0010 2 2 2 0100 4 3 3 1000 8 4 1 0011 3 5 21modp 0110 6 6 232modp 1100 12 7 3231modp 1011 11 8 3211modp 0101 5 9 231modp 1010 10 10 321modp 0111 7 11 2321modp 1110 14 12 32321modp1111 15 13 323211modp 1101 13 14 32311modp 1001 9 15 311modp 0001 1 由此可以看出本原多項式是求解域的全部元素的關(guān)鍵。讀者也許會有這樣的疑問我們?nèi)绾蔚玫絧x呢 本原多項式px的特性是211mxpx得到的余式等于0。 由于作者也是工程技術(shù)人員具體怎么得到px也沒有深究過。 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 5作者在設(shè)計RS編碼時候都是根據(jù)MATLAB指令rsgenpoly來得到px。 其格式為rsgenpolynk 參數(shù)n為碼長一般21mnk為信息碼元個數(shù)。 例如m4 碼長n15信息碼元長度為9 GF24的本原多項式可以根據(jù)指令 gtgtrsgenpoly159 得到 ans GF24 array. Primitive polynomial D4D1 19 decimal 二、線性分組碼的一些基本概念 1、線性分組碼一般用nk或nkd表示 n為碼長k為信息碼元的數(shù)目nk為監(jiān)督碼元的數(shù)目。d表示碼元距離。 定義兩個碼組上對應(yīng)位置上數(shù)字不同的個數(shù)稱為碼組的距離。 發(fā)送的碼字 123.nccccc 接收的矢量123.nrrrrr 信道錯誤圖樣ecr 例如c11000 r10001 e111000000101001 從而可以看出從左端起第2位和第5位是錯誤的。 2、校驗矩陣概念 碼長為n信息數(shù)為k監(jiān)督數(shù)為r。 這樣的一組碼形式為1212.krcmmmppp im表示第i個信息碼jp表示第j個校驗碼 各個校驗碼可從下列線性方程組求得。 111122112211222212112212.10.00.01.00.00.10kkrkkrrrrkkrhmhmhmppphmhmhmppphmhmhmppp 1-1 式中ijh是常數(shù) 校驗方程組可寫成校驗矩陣 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 611121212221210000100.0001kkrrrkhhhhhhHhhh 該矩陣具有r行和n列 故式1-1可以寫成 0THc或0TcH H矩陣稱為nkr碼的校驗矩陣。 發(fā)送矢量為c接收矢量為r 若0TrH 則說明接收到的碼有錯誤。 設(shè)錯誤圖樣為e 則可寫成以下關(guān)系式 rce 為了糾錯必須知道那些位上存在錯誤。這可由校正子又稱伴隨式s來確定 TTTTsrHcHeHeH 譯碼器的主要任務(wù)就是如何從s中得到最像e的錯誤圖樣e 從而譯出rce 設(shè)第i個是錯誤的 因此e0 0 0 1 0 0 第i個有錯誤 112111222212120 0 . 0 1 0 . 0100010001rrkkrkTiirihhhhhhhhhsrHhhh 計算出的矢量示出i是出錯誤的位置。 3、生成矩陣概念 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 7 生成矩陣G 它是一個k行n列的矩陣 若已知信息組m通過生存矩陣可求得相應(yīng)的碼字。 cmG m是k個信息元組成的信息組 這個應(yīng)該比較容易理解在此就不做過多解釋。 三、RS碼的一些重要性質(zhì) 1、RS 碼生成多項式 碼長21mn 監(jiān)督元數(shù)目2rnkt能糾正t個錯誤。 定義在nkd的RS碼中存在唯一的nk次多項式gx使得每一個碼多項式cx都是gx的倍式。gx稱為nkdRS碼的生成多項式。 一般情況下 22tgxxxx 2、定理 在2mGF中每個非0元素2221m均滿足211mx反之2110mx的根必在2mGF中。 所以 01211nnxxaxaxaxa 3、RS碼的校驗多項式 由于生成多項式gx是1nx的因式 1nxgxhx gx為nk次多項式則hx為k次多項式 1nxgxhx1010nkknkkgxgxghxhxh 由右式可以看出12nnxxx的系數(shù)均等于0 即 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 80001100110112110001iinkinknnnkknkkghghghghghghghghghgh 式中011iinkinkghghgh表示ix的系數(shù) 上式可簡寫為 0110iinkinkghghgh 121in 000nkkghgh 我們稱 1/nhxxgx為碼的校驗多項式。 4、RS碼的生成矩陣 kGIp 左邊是kk階單位方陣。這相當(dāng)于碼字多項式的第1n次至nk次的系數(shù)是信息位。而其余的位校驗位。 根據(jù)前面的定義 cx是gx的倍式 0modnkcxmxxrxgx nkmxx表示在信息組后面插nk個監(jiān)督碼元 modnkrxmxxgx 由kGIp可知生成矩陣?yán)锏男畔⒔M又叫基底矢量分別為 1000 01000001 所以很容易得到 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 9121000mod0100mod0001modnnknkxgxxgxGIpxgx 例 求735RS碼生成矩陣G 根據(jù)n7k3t2我們選取域32GF 32GF 本原多項式31pxxx 為px的根 310p 或 31 我們可以推算出32GF域的全部元素 元素 二進(jìn)制對應(yīng)碼 0 0 000 0 1 001 1 1 010 2 2 100 3 1 011 4 1a2 110 5 2a21modp 111 6 21a21modp 101 7 21a1modp 001 D5 其生成多項式為 23443323gxxxxxxxxx 143245modmodnxgxxxxgx Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 10223266modmodnxgxxxxgx 33323modmodnxgxxxxgx 由此可知其生成矩陣為 44526633100101010011G 5、RS碼的校驗矩陣 由于系統(tǒng)碼時生成多項式的倍式 Cxqxgx 22tgxxxx 所以cx必以22t為根。 即若碼字 121210nnnnCxcxcxcxc 則 121210iinininnCcccc 22it 由此可得出RS碼的校驗矩陣 121222212222111nnnnnntttH Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 11四、一些基本運算的軟件實現(xiàn) 由于編碼譯碼的運算都是在域中進(jìn)行的那么我們首先要計算出域中的元素對應(yīng)的二進(jìn)制或十進(jìn)制表示。 MATLAB程序如下 generate_gf生成域中的所有元素。 alpha_tozeros12m mask 1 alpha_tom1 0 for i1:m alpha_toi mask if Ppi0 alpha_tom1bitxoralpha_tom1mask end mask mask2 end maskalpha_tom for im2 : n if alpha_toi-1 gt mask alpha_toi bitxor alpha_tom1 bitxoralpha_toi-1mask2 else alpha_toi alpha_toi-12 end end alpha_to2m 0 把元素0放在最后一位。 例如可以根據(jù)計算出52GF的全部元素 alpha_to 1 2 4 8 16 5 10 20 13 26 17 7 14 28 29 31 27 19 3 6 12 24 21 15 30 25 23 11 22 9 18 0 在前面的例子中 108001001110101 42GF 810810mod153 這樣的計算看似簡單但是在實際的計算中i都是用對應(yīng)的二進(jìn)制表示例如在本例中8用0101表示我們并不能直觀看出0101對應(yīng)的的指數(shù)。為 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 12了便于運算我們計算出一個檢索數(shù)組:index_of如index_ofmm index_ofnn 。 mnalpha_toindex_ofmindex_of n 這樣以來運算就變得簡單多了。 index_of檢索數(shù)組可以由下面程序得出。 index_ofzeros12m for i1:2m-1 index_ofalpha_toii-1 end index_of 例m5 index_of 0 1 18 2 5 19 11 3 29 6 27 20 8 12 23 4 10 30 17 7 22 28 26 21 25 9 16 13 14 24 15 0 乘法運算就可以通過下面的程序很簡單的實現(xiàn)。 function yrs_mulab if ab0 y0 else a1 index_ofa b1 index_ofb cmoda1b1n n2m-1即碼長 y alpha_toc1 end 把x代入多項式fx即計算fx的值x為一常數(shù)。 程序中T為GF中元素對應(yīng)的二進(jìn)制表示值。 function yrs_polyfx xx index_of x-1 Llengthf-1 多項式的次數(shù) y1f1 常數(shù)項 for i1:L y1rs_addy1rs_mulfi1 alpha_to modixxn1 累加 end yy1 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 13 五、RS編碼 RS編碼軟件實現(xiàn) 其編碼電路基本上可分為兩類k級和nk級編碼器 1、nk級編碼器 其原理比較容易理解 由于系統(tǒng)碼時生成多項式的倍式 Cxqxgx 1212.nkkcrrrmmm nkCxqxgxmxxrx 信息碼乘以nkx然后再除gx就得到了余式rx也就得到了校驗位。 這里難點就是如何實現(xiàn)多項式乘法除法運算。 多項式乘法 設(shè)兩多項式 1110kkkkAxaxaxaxa 1110rrrrBxbxbxbxb 相乘過程可用下圖表示 00kaaarb1rb2rb2b1b0b 圖1 實現(xiàn)步驟如下 1 r個寄存器全部清0。 2 Ax最高次系數(shù)ka首先送入時乘法器輸出乘積的最高次項krx的系數(shù)krab同時ka 存入寄存器的第一級。 3 Ax的第二個系數(shù)1ka送入時ka由第一級進(jìn)入第二級寄存器同時與1rb相乘 11krkrabab就得到了乘積的1krx的系數(shù)。 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 144 這樣重復(fù)進(jìn)行直至1kr次移位后乘法器輸出乘積的常數(shù)項00ab。 乘法過程還有另外一種表示方法。 輸入輸出 00kaaarb1rb2rb2b1b0b 圖2 它的工作過程和圖1類似。 多項式除法 設(shè) 1110kkkkAxaxaxaxa 1110rrrrBxbxbxbxb 流程圖 0b1b2b1rb1rb01kaaa 圖3 1 開始運算時 r 個寄存器全部清0第一次移位時Ax最高次系數(shù)ka首先進(jìn)入最左一級寄存器r 次移位后寄存器1至寄存器2t的數(shù)值分別為 121krkrkkaaaa 2 第r1次移位時除法器輸出1krab這就是商的第一項krx的系數(shù)1krab同時反饋到后面的各級寄存器中即得到第一次除運算的余式。 3 以此類推經(jīng)k次移位后完成了整個除法運算過程移位寄存器中的值就是余式rx Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 15多項式相乘相除 分別設(shè) 1110kkkkAxaxaxaxa 1110rrrrHxhxhxhxh 1110rrrrGxgxgxgxg 計算/AxHxGx 該電路圖是圖2圖3兩種電路的結(jié)合。 輸入 00kaaa 0h1h2h1rh2rhrh0g1g2g1rg2rg1rg商輸出 圖4 如果HxGx次數(shù)不等只需按最高次數(shù)設(shè)計即可。 RS編碼電路 22122110ttttgxgxgxgxg 21tg 12111000nknnnknkkkmxxmxmxmxxx 那么/nkmxxgx的除法電路根據(jù)圖3可用下圖表示 0g1g2g21tg21/tg 輸入為nkmxx 因為21tg加法減法運算規(guī)則相同 所以又可以表示為 Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 16 21tg0g1g2g 寄存器1 . 寄存器2t 上述方法相當(dāng)于事先做好nkmxx再做除法這樣需要移位n次 而圖4的電路我們只需移位k次。 根據(jù) 221122110110ttnknkttnknkgxgxgxgxggxgxgxg 1nkg 1000nknknkxxxx 根據(jù)圖4/nkmxxgx的電路可表示為 輸入 商輸出12kmmm1nkg2nkg2g1g0g MATLAB程序?qū)崿F(xiàn) rrzeros1 n-k for ik:-1:1 feedback rs_adddatairrnn-kk if feedback 0 for jn-k-1:-1:1 if gj 0 rrj1 rs_add bbjrs_mulgjfeedback else rrj1 rrj end rr1 rs_mul gg1feedback end Zhengzhou Oriole Xinda Electronic Information Co.Ltd. 17 else for jn-k-1:-1:1 rrj1 rrj end rr1 0 end end 下面的程序是另一種比較簡潔的程序 rrzeros1n-k for i1:k feedback rs_addrrn-kdatak-i1 rrn-krs_addrrn-k-1rs_mulfeedbackgn-k rrn-k-1rs_addrrn-k-