文檔RS糾錯編碼原理及其實現方法.doc

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