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

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