基于BM算法的RS(18,10)譯碼的軟件實(shí)現(xiàn)和性能分析

王景煜， 景曉軍

（北京郵電大學(xué) 信息與通信工程學(xué)院，北京 100876）

0 引言

RS(Reed-Solomon)碼是一類具有優(yōu)良性能的極大距離糾錯(cuò)碼，RS碼廣泛地應(yīng)用在衛(wèi)星通信領(lǐng)域和地面無線移動(dòng)通信領(lǐng)域。本文設(shè)計(jì)了RS(18,10)，RS(18,10)是RS(255,247)的縮短碼，和RS(255,247)相比糾錯(cuò)能力更強(qiáng)。本文在對譯碼原理研究基礎(chǔ)上,提出了一種RS(18,10)譯碼器的matlab解決方案。RS譯碼仿真程序?yàn)橐院蟮乃惴?yàn)證和硬件設(shè)計(jì)調(diào)試中起著至關(guān)重要的作用。

1 譯碼原理

RS譯碼方法很多，根據(jù)關(guān)鍵方程的不同，可分為：BM迭代算法和Euclid迭代算法。還有人提出軟入軟出[1]的迭代譯碼算法。本文主要研究BM迭代算法硬判譯碼。

RS(18,10)是 RS(255,247)的縮短碼，所在的有限域是GF(2^8)。每個(gè)碼字有8個(gè)信息位，進(jìn)行一次編碼需要10個(gè)碼字，生成8個(gè)碼子的冗余信息。這18個(gè)碼字中任意四個(gè)碼字發(fā)生錯(cuò)誤均可以糾錯(cuò)[2]。該碼的本原多項(xiàng)式為：

該碼的生成多項(xiàng)式為：

1.1 伴隨式的計(jì)算

設(shè)R(x)是接收多項(xiàng)式，因?yàn)槭荝S(18,10)，所以一次編碼完成會(huì)產(chǎn)生18個(gè)碼字，可以表示為：

譯碼算法首先計(jì)算伴隨多項(xiàng)式iS，i=1,2,3…8，如果伴隨多項(xiàng)式的值為 0，則證明傳輸沒有發(fā)生錯(cuò)誤，如果有任何一位不為0，則在傳輸中發(fā)生錯(cuò)誤了。

伴隨多項(xiàng)式為：

式（2）可以寫為 ：

這樣根據(jù)式（3）就可以用硬件設(shè)計(jì)電路設(shè)計(jì) 8條同時(shí)處理的電路，這樣在18個(gè)處理時(shí)鐘就可以計(jì)算出8個(gè)伴隨值了。相應(yīng)的在進(jìn)行matlab設(shè)計(jì)rs_bansui.m模塊的時(shí)候，只要在m函數(shù)里做一個(gè)18次的循環(huán)就可以計(jì)算出伴隨式。

1.2 求解錯(cuò)位位置多項(xiàng)式

錯(cuò)誤位置多項(xiàng)式可以表示為：

求解關(guān)鍵方程是RS碼解碼器設(shè)計(jì)實(shí)現(xiàn)中最復(fù)雜的一個(gè)模塊（rs_bm.m）。在此用BM算法迭代求解。迭代算法就是首先選擇一組或者兩組合理的初始值0()xσ，然后進(jìn)行第一次迭代運(yùn)算求解出1()xσ，簡言之用0()xσ表示1()xσ。這樣一直迭代下去，最終迭代出的各個(gè)系數(shù)。

迭代過程步驟：

① 初始化合理值，令：② 計(jì)算jd，如果jd為0，則：

如果jd不為0，則找出j之前某一行i，i行在j行之前的i-D(i)最大，且，然后按照:計(jì)算出()x；

③ 計(jì)算1jd+，然后重復(fù)步驟②，迭代進(jìn)行8次，即可求解出錯(cuò)誤位置多項(xiàng)式的系數(shù)。

1.3 錢搜索法求解錯(cuò)誤位置

1.4 計(jì)算錯(cuò)誤值

譯碼算法的最后一個(gè)步驟就是計(jì)算錯(cuò)誤值，在1.3中我們已經(jīng)求出在 R(x)的那些位置發(fā)生了錯(cuò)誤，現(xiàn)在我們只需求出對應(yīng)位置上的錯(cuò)誤值就可以了。還是假設(shè)發(fā)生了v個(gè)錯(cuò)誤，根據(jù)式子：

可以求出第j個(gè)錯(cuò)誤值。其中的:

求出錯(cuò)誤值jw之后，然后根據(jù)1.3步驟中記錄的第j個(gè)錯(cuò)誤的位置和相應(yīng)位置的接收值進(jìn)行有限域的加法就可以恢復(fù)出正確值。

2 譯碼基本模塊的matlab實(shí)現(xiàn)和及其性能分析

RS碼的運(yùn)算全部都是在有限域內(nèi)進(jìn)行的，所以進(jìn)行有限域的基本運(yùn)算的設(shè)計(jì)是非常要的[3]。只要這些基本模塊編寫完成之后，按照上述的步驟即可進(jìn)行譯碼軟件代碼的編寫。

2.1 有限域加法器

rs_add.m模塊：y=rs_add(a,b)入口參數(shù)a,b均為模255的十進(jìn)制數(shù)，進(jìn)入函數(shù)后先進(jìn)行十進(jìn)制到二進(jìn)制的轉(zhuǎn)換，然后按比特異或，將結(jié)果進(jìn)行二進(jìn)制到十進(jìn)制的轉(zhuǎn)換并賦值給y。

2.2 有限域乘法器

rs_multi.m模塊：y=rs_multi(a,b) 口參數(shù)a,b均為模255的十進(jìn)制數(shù)，進(jìn)入函數(shù)后先進(jìn)行十進(jìn)制到二進(jìn)制的轉(zhuǎn)換，然后按比特進(jìn)行GF(2^8)域RS(18,10)的簡化的運(yùn)算。這樣硬件處理在一個(gè)運(yùn)算周期就可以完成乘法。

2.3 求逆器

rs_invers.m模塊：求逆運(yùn)算比較復(fù)雜，為了加速譯碼速度，考慮到該有限域的元素?cái)?shù)目總數(shù)不多，采用查找表法。在硬件實(shí)現(xiàn)時(shí)做一個(gè)rom的查找表即可。

2.4 性能仿真

圖1是對RS(18,10)碼在AWGN信道下的性能仿真，調(diào)制方式為bpsk，發(fā)送端和接收端對數(shù)據(jù)采用8倍過采樣根升余弦滾降濾波進(jìn)行成形濾波，假設(shè)接收端理想同步。‘*’為沒有加RS碼的性能曲線圖，‘o’為加了RS碼的性能曲線。橫軸為Eb/N0（單位為dB）,縱軸為誤比特率。

圖1 性能曲線

3 結(jié)語

本文對RS(18,10)的譯碼算法進(jìn)行了分析，并給出了進(jìn)行 matlab軟件實(shí)現(xiàn)的方法，其中算法考慮到硬件算法的設(shè)計(jì)，設(shè)計(jì)了很多基本運(yùn)算的m函數(shù)和算法各個(gè)模塊的m函數(shù)，這些都給算法驗(yàn)證和硬件設(shè)計(jì)提供了參考和指導(dǎo)。并且對該RS碼進(jìn)行了在AWGN信道下的性能仿真，可以看出，在Eb/N0比較小的時(shí)候RS碼的作用不是很顯著，但是隨著Eb/N0的提高，RS（18,10）可以顯著的提高誤比特率，在誤比特率為10-3的時(shí)候有3 dB的增益。

[1] 李國靜,鄒永忠,李道本.一種適用于RS的低復(fù)雜度軟入軟出譯碼方法[C]//第十二屆全國青年通信學(xué)術(shù)會(huì)議.北京:北方工業(yè)大學(xué),2007.

[2] [美] Schwarts M. Mobile Wireless Communications[M].許希斌,李云洲譯.北京:電子工業(yè)出版社,2006:120-130.

[3] [美] Proakis J P, Salehi M, Bauch G. Contemporary Communication Systems Using MATLAB and Simulink[M].劉樹棠譯.第2版.北京:電子工業(yè)出版社,2005:285-296.