趙 旸， 耿相銘

（上海交通大學 電子信息與電氣工程學院，上海 200240）

0 引言

里德-所羅門碼（RS碼）是性能優(yōu)良的多進制BCH碼，相比于其他線性分組碼，在同樣的編碼效率下，RS碼具有較強的糾錯能力，特別是在短的中等碼長下，其性能很接近于理論值，不但可以糾正隨機錯誤、突發(fā)錯誤及兩者的結(jié)合，而且可以用來構(gòu)造其他碼類，如RS碼和卷積碼構(gòu)成的級聯(lián)碼已經(jīng)被用在深空通信的下行鏈路中，因此RS碼在數(shù)字存儲和通信系統(tǒng)中獲得了廣泛應用，例如用于CD-ROM、DVD和陸地數(shù)字傳輸中定義在GF(28)上的縮短RS碼。

一般來說，對于定義在有限域GF(2m)符號位寬度為m的RS碼，其碼字長度n等于2m-1，這類RS碼稱為系統(tǒng)碼或全碼。在工程應用中，要使RS碼具有較高的實時性，一般選用碼字長度較短的碼型；另外還需要靈活配置碼率。對于系統(tǒng)碼，可選的短碼類型較少，因此常常通過截短系統(tǒng)碼信息位碼元符號個數(shù)的方法來得到合適的碼字長度，即構(gòu)造縮短碼，這樣不僅可以滿足系統(tǒng)實時性的要求，還可以根據(jù)需要獲得不同的碼率。

1 RS編譯碼原理

1.1 編碼原理

RS碼是線性分組碼，編碼的過程即是根據(jù)k個信息碼元及(n, k, t)RS碼的特性獲得n-k個校驗碼元的過程。

GF(2m)上的本原元為α，則生成多項式為[1]：

假設(shè)m=(m0, m1,…,mk-1)表示GF(2m)上的k個信息符號序列，可寫成信息多項式為：

則可以按如下方法構(gòu)造碼字多項式C( x)：首先將信息多項式左移r=n-k位，得到m( x)·xn-k，然后用m( x)·xn-k除以生成多項式g( x)得到商式h( x)和余式r( x)：

所得到的余式r( x)就是校驗多項式，其次數(shù)為r=n-k次；然后令C( x)=xn-km( x)+r( x)，即將信息位放置于碼字前半部分，監(jiān)督位放置于碼字的后半部分，就得到編碼后的碼字多項式C( x)。RS碼的編碼電路如圖1所示。

圖1 RS碼編碼電路

1.2 譯碼原理

RS碼譯碼的一般流程為[2]：

1) 由接收碼字R( x)計算伴隨式。

2) 根據(jù)伴隨式及Berlekamp_Messey算法求出錯誤位置多項式σ(x)。

3) 用錢搜索法解出錯誤位置多項式σ(x) 的根，從而得到錯誤數(shù)及確定錯誤位置。

4) 利用 Forney算法求得錯誤位置上的錯誤值，從而得到錯誤圖樣E( x)。

5) 在RS碼的糾錯范圍內(nèi)，即錯誤數(shù)l不大于t時，R( x)+E( x)=C( x)，完成糾錯。

譯碼流程如圖2所示。

1.2.1 計算伴隨式

根據(jù)接收信息多項式R( x)，可以得到最多糾正t個差錯的RS碼的伴隨式：

式中,α是有限域GF(2m)的本原元。

假設(shè)發(fā)端發(fā)送的碼字多項式為：

收端收到的碼字多項式為：

由信道產(chǎn)生的錯誤圖樣多項式為：

而R( x)=C( x)+E( x)，則有：

容易證明α1, α2,…,α2t均為發(fā)送碼字多項C( x)的根，即C(αi)=0(1≤i≤2t )，因此：

圖2 RS碼編碼電路

可知伴隨式Si只與誤差多項式E( x)有關(guān)，如果所有的2t個伴隨式都為0，說明(e0, e1,…,en)=0，即錯誤個數(shù)為 0；否則說明編碼信號在信道傳輸過程中產(chǎn)生了誤碼。

根據(jù)伴隨式的計算公式：

可以采用高效的迭代算法——Horner準則來計算伴隨式的值[3]：

伴隨式計算示意如圖3所示。

圖3 伴隨式計算示意

1.2.2 譯碼核心模塊

定義錯誤位置多項式為：

式中，l表示錯誤符號數(shù)，l≤t時可以正確糾正這l個誤碼，顯然是式(12)的根，定義錯誤值多項式為：

另外，定義伴隨式多項式S( x)為：

則這三者滿足方程:

式(15)稱為關(guān)鍵方程，關(guān)鍵方程的求解是RS譯碼算法的核心部分。工程應用中往往利用BM迭代算法結(jié)合錢搜索法求解錯誤位置，F(xiàn)orney算法求解錯誤值。

BM算法就是利用一個迭代過程求解關(guān)鍵方程，即以σ(0)(x)=1,ω(0)(x )=1為初始條件，然后通過迭代計算得到σ(k)(x)和ω(k)(x)以滿足：

當k=2t時得到滿足關(guān)鍵方程的錯誤位置多項式σ(2t)(x)和錯誤值多項式ω(2t)(x)。具體迭代過程如下[4]：

初始條件：

多項式σ(2t)(x)就是錯誤位置多項式σ(x)。

在求得錯誤位置多項式后，下一步是如何求出錯誤位置多項式的根以確定錯誤位置，錢聞天教授提出了著名的Chien搜索算法，該方法為一種窮舉搜索法，即對碼的每個位置逐位予以檢索來確定錯誤位置。

由式(12)可知錯誤位置多項式：

那么Chien搜索算法即是要驗證：

對于接收序列，依據(jù)上式對每一個α-j(j=0,1,…,n -1)檢驗，即可檢出第j個接收符號是否出錯，該過程就是Chien搜索。

在得到錯誤位置后，由于RS碼是非二進制碼，所以還要求第j個錯誤位置上對應的錯誤值，這一步利用Forney公式計算：

求得錯誤位置和錯誤值后，將錯誤值與錯誤位置上的接收符號模2相加，即可糾正誤碼。

1.3 RS(16,12)縮短碼的編譯碼

每個縮短碼RS( n, k)，都有一個系統(tǒng)碼RS( n1, k1)作為其母碼，這里 n1=2m-1，m表示構(gòu)成每個RS符號所需的比特數(shù)，而且 k1-k=n1-n 。對于RS(16,12)縮短碼，m可以選擇 5，6，7，8…，只需要滿足2m＞16。為了計算方便，選擇m=8，即一個RS符號占1 byte（8 bit）。那么RS(16,12)縮短碼的母碼為系統(tǒng)碼RS(255,251)。

由于縮短碼和其母碼校驗位數(shù)相等，即2t=n1-k1=n-k ，因此它們具有相同的糾錯能力?？s短碼的常用構(gòu)造方法是將一幀系統(tǒng)碼信息位的前k1-k個符號置零，即符號 c250=c249=…=c12=0。但是在縮短碼的編譯碼過程中，并不需要對前k1-k個符號為0的系統(tǒng)碼進行編譯碼，然后去除冗余的長0串，這是因為刪去長零碼元并不會對Horner編碼、伴隨式計算、BM迭代過程等運算模塊產(chǎn)生影響。利用系統(tǒng)碼的編譯碼電路，可以實現(xiàn)縮短碼的編譯碼。

根據(jù)式(18),在RS碼譯碼中的Chien搜索模塊中，需要驗證[5]：

對于接收序列，依據(jù)該式對每一個α-j(j=0,1,…,n -1)檢驗，即可檢出第 j個接收符號是否出錯。RS系統(tǒng)碼要從第n1-1個接收符號處開始搜索，即從α-(n1-1)開始代入式(18)檢驗。而縮短RS碼的高n1-n個信息位符號數(shù)據(jù)被截去了，沒有經(jīng)過信道傳輸也就不可能發(fā)生錯誤，所以α-(n1-1)，α-(n1-2)，…,α-n不可能是的根，在Chien搜索中不需要對它們進行計算，只需要對指數(shù)表中的后n個值，即α-(n-1)，α-(n-2)，…，α-0進行搜索。利用該方法可以省去n1-n步 Chien搜索，當n1-n值較大時，可以大大降低譯碼延時。對于RS(16,12)縮短碼，每一幀可以省去239步Chien搜索，性能大幅優(yōu)化。

2 性能仿真

按照圖4的步驟對RS(16,12)縮短碼糾錯性能進行仿真分析。

RS(16,12)縮短碼采用QPSK調(diào)制，使用高斯白噪聲信道和瑞利衰落信道兩種信道模型分別MATALAB仿真，計算采用RS編碼和不采用RS編碼的信號經(jīng)過信道傳輸后的誤符號率（SER）。之所以計算 SER而非誤比特率（BER），是為了突出體現(xiàn)RS編碼在糾正突發(fā)性錯誤方面的優(yōu)勢：對于一個GF(28)上的RS碼符號由 8比特構(gòu)成，因此在一個RS符號內(nèi)糾正1比特隨機錯誤和糾正8比特突發(fā)連續(xù)錯誤沒有區(qū)別。RS碼符號在傳輸中產(chǎn)生錯誤的過程如圖5所示。

1 024 幀數(shù)據(jù)mi=(mi0,mi1,…,mi11)經(jīng)過RS編碼、調(diào)制后送入信道，i=0,1,…,1023，在收端解調(diào)、RS譯碼后計算出SER_RS；與原始1 024幀數(shù)據(jù)不經(jīng)過RS編碼直接調(diào)制后在信道中傳輸，收端計算出的SER_NORS進行比較。信道模型分別為高斯白噪聲信道和瑞利衰落信道（多普勒頻移10 Hz），如圖6和圖7所示。

通過軟件仿真可以看出，RSN=9.5 dB時，對于高斯白噪聲信道和瑞利衰落信道（多普勒頻移10 Hz），通過RS(16,12)編碼可以將誤符號率分別提高2個和1個數(shù)量級。說明RS編碼具有優(yōu)良的糾錯性能，尤其適合于糾正信道傳輸過程中產(chǎn)生的突發(fā)連續(xù)錯誤。

圖6 高斯白噪聲信道下SER

圖7 瑞利衰落信道下SER

表1 9.5 dB下信道傳輸SER比較

3 結(jié)語

文中在分析RS系統(tǒng)碼編譯碼原理的基礎(chǔ)上給出了RS(16,12)縮短碼的切實可行的編譯碼方案，由此可以看出RS碼低復雜度的優(yōu)點。并對RS(16,12)碼在高斯白噪聲信道和瑞利衰落信道下的糾錯性能進行軟件仿真和分析，可以看出RS碼在低信噪比條件下、誤碼數(shù)超過其糾錯能力時糾錯性能并不明顯，但隨著信噪比的提高，可以大幅提高誤符號率和誤比特率，而RS碼本身的特性使其具有很強的突發(fā)連續(xù)錯誤檢錯能力。這些優(yōu)點使得RS碼在工程中得到了廣泛應用。

[1] 宋洋軍，權(quán)進國，林孝廉.DMR標準RS碼編譯碼器的FPGA實現(xiàn)[J].通信技術(shù)，2010，43(06):13-15.

[2] 王海東.Reed-Solomon碼在 MPEG-4視頻流傳輸中的應用[J].通信技術(shù)，2007，40(05):56-64.

[3] SWEENEY P. 差錯控制編碼[M].俞越，張丹譯.北京：清華大學出版社，2004：122-138.

[4] MORELOS-ZARAGOZA R. 糾錯編碼的藝術(shù)[M].張力軍譯.北京：北京交通大學出版社，2007:79-91.

[5] 王景煜，景曉軍.基于BM算法的RS(18,10)的譯碼的軟件實現(xiàn)和性能分析[J].通信技術(shù)，2010，43(04):70-71.