RS(16,12)縮短碼編譯碼原理及性能

2024年2月15日發(作者：安全行車)

2012年第02期，第45卷 通 信 技 術 Vol.45，No.02,2012

總第242期 Communications Technology No.242,Totally

RS(16,12)縮短碼編譯碼原理及性能分析

趙 旸， 耿相銘

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

【摘 要】在各類數字通信系統以及計算機存儲和運算系統經常利用差錯控制編碼降低誤碼率，提高通信質量，滿足對數據傳輸通道可靠性的要求。RS碼是一種性能優良的前向糾錯碼，具有同時糾正隨機錯誤和突發錯誤的能力，它的構造特點決定了其非常適合于糾正突發性錯誤。文中在闡述RS系統碼編譯碼原理的基礎上，提出了RS(16,12)縮短碼的編譯碼方法，利用MATLAB對RS(16,12)縮短碼在高斯信道和瑞利信道條件下的糾錯能力進行仿真，并分析其糾錯性能。

【關鍵詞】里德-所羅門碼(RS碼)；縮短碼；編譯碼；瑞利信道；MATLAB仿真

【中圖分類號】TN918 【文獻標識碼】A 【文章編號】1002-0802(2012)02-0049-04

Encoding and Decoding Algorithm forRS(16,12)Shortened Codes

and Its Performance Analysis

ZHAO Yang， GENG Xiang-ming

(SEIEE, Shanghai Jiaotong University, Shanghai 200240)

【Abstract】In various digital communication systems and computer storage and computing

systems, the error control coding is often ud to reduce bit or symbol error rate, and thus to

improve communication quality and meet the reliability requirements of data transmission. RS code,

as an excellent forward error correction code, has the capability to correct both random error

and burst error, and its structured characteristics feature its suitability for correcting burst

errors. Bad on description of theRSsystem code’s encoding and decoding principles, this paper

proposRS(16,12)shortened code’s encoding and decoding method. And with MATLAB

theRS(16,12)shortened code’s error correction capability in the AWGN and Rayleigh fading channel

conditions is simulated.

【Key words】Reed-Solomon code; shortened code; encoding & decoding algorithm; Reyleigh fading

channel; MATLAB simulation

儲和通信系統中獲得了廣泛應用，例如用于0 引言

CD?ROM、DVD和陸地數字傳輸中定義在GF(28)里德-所羅門碼（RS碼）是性能優良的多進制BCH碼，相比于其他線性分組碼，在同樣的編碼效特別是在短的中率下，RS碼具有較強的糾錯能力，等碼長下，其性能很接近于理論值，不但可以糾正隨機錯誤、突發錯誤及兩者的結合，而且可以用來構造其他碼類，如RS碼和卷積碼構成的級聯碼已經被用在深空通信的下行鏈路中，因此RS碼在數字存收稿日期：2011-11-11。

作者簡介：趙 旸（1987- ），男，碩士研究生，主要研究方向為信號處理與無線通信技術；耿相銘（1965- ），男，高級工程師，碩士，碩士生導師，主要研究方向為數字信號處理及硬件設計。

上的縮短RS碼。

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

49

1

RS編譯碼原理

1.1 編碼原理

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

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

g(x)?(x??)(x??2)?(x??2t2t)??(x??i)，

i?1(1)

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

m(x)?m0?m1x???m?2k?2xk?mk?1xk?1， (2)

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

xn?km(x)/g(x)?h(x)g(x)?r(x)， (3)

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

g0g1g2t?2g2t?12t2t?1212m0,m1,?,mk?11

圖1

RS碼編碼電路

1.2 譯碼原理

RS碼譯碼的一般流程為[2]： 1) 由接收碼字R(x)計算伴隨式。

2) 根據伴隨式及Berlekamp_Mesy算法求出錯誤位置多項式?(x)。

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

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

5) 在RS碼的糾錯范圍內，即錯誤數l不大于t時，R(x)?E(x)?C(x)，完成糾錯。

譯碼流程如圖2所示。

1.2.1計算伴隨式

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

Si?R(?i),1≤i≤2t， (4)

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

假設發端發送的碼字多項式為：

50

C(x)?c0?c1x???cn?1xn?1， (5)

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

R(x)?r10?r1x???rn?n?1x， (6)

由信道產生的錯誤圖樣多項式為：

E(x)?e0?e1x???en?1n?1x， (7)

而R(x)?C(x)?E(x)，則有：

Si?R(?i)?C(?i)?E(?i),1≤i≤2t。 (8)

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

Si?R(?i)?C(?i)?E(?i)?E(?i),1≤i≤2t。(9)

R(x)C(x)E(x)R(x)?0求解求得錯誤圖樣?1計算伴隨式錯誤用ChienS位置搜索法i,i?1,2,?,2t多項?求?(x)式?(x)的根?t?1計算錯誤位置上的錯誤值Yi

圖2

RS碼編碼電路

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

根據伴隨式的計算公式：

n

?1Si?R(?i)??rj(?i)j， (10)

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

Sii?(((rn?1??i?rn?2)???rn?3)??i??r1)??i?r0。 (11)

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

?0?1?2t?1DS1DS2DS2tr0,r1,?,rn?1 圖3 伴隨式計算示意

1.2.2譯碼核心模塊

定義錯誤位置多項式為：

?l(x)??(1??jx)?(1??1x)(1??2x)?(1??lx)?

j?11??1x??2x2????llx,l≤t， (12)

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

?ll(x)??e1j?(1??jx)??0??1x??2x2????l?1xl?。

i?1ijj??1i(13)

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

S(x)?s1?s2x???s2tx2t?1， (14)

則這三者滿足方程:

?(x)?S(x)??(x)modx2t。 (15)

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

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

?(k)(x)?S(x)??(k)(x)modxk,k?1,2,?,2t， (16)

當k?2t時得到滿足關鍵方程的錯誤位置多項式?(2t)(x)和錯誤值多項式?(2t)(x)。具體迭代過程如

下[4]：

初始條件：

?(0)(x)?1,B(0)(x)?1,L(0)?0,?(k)?0,k≤0，其中：t?(k?1)???(k)jSk?1?j，

j?01)L(k?1)???(k)?L,?(k??0or2L(k)≤k,??k?1?L(k),?(k?1)?0and2L(k)≤k,

B(k?1)(x)????xB(k)(x),?(k?1)?0or2L(k)?k,

???(k)(x)?(k?1),?(k?1)?0and2L(k)≤k,?(k?1)(x)??(k)(x)??(k?1)B(k)(x)?x。 (17)

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

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

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

?l(x)??(1??ix)?(1??1x)(1??2x)?(1??lx)?

i?11??2lli1x??2x????lx?1???ix,l≤t，

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

?l??1????(??j)ii?0,rj有錯,j?0,1,?,n?1,?i?1 (18)

?l1???(??j???i)i?0,rj正確。i?1 對于接收序列，依據上式對每一個??j(j?0,1,?,n?1)檢驗，即可檢出第j個接收符號是否出錯，該過程就是Chien搜索。

在得到錯誤位置后，由于RS碼是非二進制碼，

所以還要求第j個錯誤位置上對應的錯誤值，這一步利用Forney公式計算：

Y?(x)?(x)j?x?'(x)?。 (19)

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

1.3

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

每個縮短碼RS(n,k)，都有一個系統碼RS(n1,k1)作為其母碼，這里n1?2m?1，m表示構成每個RS符號所需的比特數，而且k1?k?n1?n。對于RS(16,12)縮短碼，m可以選擇5，6，7，8?，只需要滿足2m?16。為了計算方便，選擇m?8，即一個RS符號占1 byte（8 bit）。那么RS(16,12)縮短碼的母碼為系統碼RS(255,251)。 由于縮短碼和其母碼校驗位數相等，即2t?n1?k1?n?k，因此它們具有相同的糾錯能力。縮短碼的常用構造方法是將一幀系統碼信息位的前k1?k個符號置零，即符號c250?c249???c12?0。但是在縮短碼的編譯碼過程中，并不需要對前k1?k個符號為0的系統碼進行編譯碼，然后去除冗余的長0串，這是因為刪去長零碼元并不會對Horner編碼、伴隨式計算、BM迭代過程等運算模塊產生影響。利用系統碼的編譯碼電路，可以實現縮短碼的編譯碼。

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

?l??ji?1???i?(?)?0,rj有錯,j?0,1,?,n?1,?i?1

?l1???(??j)i???i?0,rj正確。i?1 對于接收序列，依據該式對每一個??j(j?0,1,?,n?1)檢驗，即可檢出第j個接收符號是否出錯。RS系統碼要從第n1?1個接收符號處開始搜索，即從??(n1?1)開始代入式(18)檢驗。而縮短RS碼的高n1?n個信息位符號數據被截去了，沒有經過信道傳輸也就不可能發生錯誤，所以??(n1?1)，??(n1?2)，?,??n不可能是

l

1???i?(??j)i?0， (20)

i?1的根，在Chien搜索中不需要對它們進行計算，只需要對指數表中的后n個值，即??(n?1)，??(n?2)，?，??0進行搜索。利用該方法可以省去n1?n步Chien搜索，當n1?n值較大時，可以大大降低譯碼延時。對于RS(16,12)縮短碼，每一幀可以省去239步Chien搜索，性能大幅優化。

2 性能仿真

按照圖4的步驟對RS(16,12)縮短碼糾錯性能進51

行仿真分析。 圖4RS(16,12)性能測試框

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

QPSK調制（無線信道）高斯白噪聲QPSK解調 圖5

RS符號傳輸中誤碼示意

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

通過軟件仿真可以看出，RSN=9.5 dB時，對于高斯白噪聲信道和瑞利衰落信道（多普勒頻移

10 Hz），通過RS(16,12)編碼可以將誤符號率分別提高2個和1個數量級。說明RS編碼具有優良的糾錯性能，尤其適合于糾正信道傳輸過程中產生的突發連續錯誤。

52

RESR SN/dB

圖6 高斯白噪聲信道下SER RESR SN/dB

圖7 瑞利衰落信道下SER

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

誤符號率 高斯百噪聲信道 瑞利衰落信道SER_RS 2.44?10?4 3.50?10?3 SER_NORS1.00?10?2 1.52?10?2

3 結語

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

參考文獻

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

[2] 王海東.Reed-Solomon碼在MPEG-4視頻流傳輸中的應

用[J].通信技術，2007，40(05):56-64.

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

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

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