Reed-Solomon碼性能增強(qiáng)譯碼算法

鄭相全，段 文

(1.軍事科學(xué)院 系統(tǒng)工程研究院，北京 100141；2.北京直屬保障大隊(duì)，北京 100071)

0 引言

自1960年Reed-Solomon(RS)碼[1]被構(gòu)造后，由于其突出的抗突發(fā)性能，已被廣泛應(yīng)用于通信系統(tǒng)中，包括數(shù)字存儲(chǔ)、衛(wèi)星和深空空間通信，移動(dòng)數(shù)據(jù)通信和擴(kuò)頻系統(tǒng)。1961年Gorenstein和Zierler證明了RS碼是非二進(jìn)制BCH碼的子類[2]。因此，RS碼編碼有按BCH碼編碼方式和RS碼定義方式2種編碼結(jié)構(gòu)[3]，其中BCH碼編碼方式可以構(gòu)造RS系統(tǒng)碼格式[4]。

已經(jīng)提出的RS譯碼算法主要是基于信道輸出硬判決信息的BM算法和歐幾里德算法[5]。這些傳統(tǒng)的RS碼譯碼算法利用了編碼時(shí)所依附有限域的代數(shù)結(jié)構(gòu)來進(jìn)行譯碼，所以又稱為代數(shù)譯碼。(n，k)RS碼采用代數(shù)譯碼方法進(jìn)行譯碼時(shí)，會(huì)有糾錯(cuò)能力的限制。本文首先從RS碼的2種編碼格式出發(fā)，介紹了突破RS碼設(shè)計(jì)糾錯(cuò)能力的2類譯碼增強(qiáng)算法，最后總結(jié)了這2類算法存在的問題并指出了其后續(xù)的研究方向。

1 RS碼編碼格式分類

1.1 計(jì)算映射RS碼定義格式

RS碼是采用編碼方式為計(jì)算映射編碼[1]，這種編碼方式是后續(xù)GSA[6]和KVA[7]算法的基礎(chǔ)。

設(shè)信息多項(xiàng)式為：

m(x)=mk-1xk-1+mk-2xk-2+…+m1x1+m0。

(1)

設(shè)支撐集D={x1，x2，…，xn}∈GF(2m)，為兩兩互異的一個(gè)點(diǎn)集；則RS碼的碼字可由變量x遍歷支撐集內(nèi)的值，依次代入消息符號(hào)多項(xiàng)式進(jìn)行計(jì)算得到[8]，

c=(m(x1)，m(x2)，…，m(xn))，

(2)

因此，

m·G，

(3)

式中，

(4)

為k列n行的范德蒙矩陣[9]。顯然，RS碼的碼長由支撐集的階數(shù)決定。

設(shè)α為RS碼符號(hào)域GF(2m)的一個(gè)本原元，則符號(hào)域GF(2m)中的一種排序?yàn)椋?0，1，α，α2，…，αn-2)，其中n=2m為符號(hào)域的階數(shù)。若按順序依次取符號(hào)域內(nèi)所有非零元素構(gòu)成的集合D={1，α，α2，…，αn-2}時(shí)，生成矩陣為：

(5)

假設(shè)接收的硬判決碼字序列為：

r=(rn-1，rn-2，…，r0)。

在接收端，可構(gòu)造n個(gè)方程組。若信道無差錯(cuò)時(shí)，該方程組為：

假設(shè)取上述方程組的前k個(gè)方程，對(duì)應(yīng)的系數(shù)行列式為：

即上述方程組的任意k個(gè)方程是相互獨(dú)立的，即假設(shè)信道無差錯(cuò)傳輸時(shí)，上述的任意k個(gè)方程組即可求解出發(fā)送的碼元信息序列。

1.2 RS碼的系統(tǒng)碼編碼格式

由于RS碼為最小距離可分的[10]，因此參數(shù)為(n，k)的RS碼的最小漢明距離dmin=n-k+1。作為BCH碼的子類，可得RS碼的生成多項(xiàng)式為：

g(x)= (x-α)(x-α2)…(x-αdmin-1)=

gn-kxn-k+gn-k-1xn-k-1+…+g1x+g0，

(6)

式中，α為RS編/譯碼符號(hào)域GF(q)內(nèi)的本原元。由生成多項(xiàng)式可得k個(gè)相互獨(dú)立的碼字多項(xiàng)式：

因此，RS碼的一個(gè)生成矩陣為：

(7)

設(shè)信息符號(hào)序列m=(mk-1，mk-2，…，m1，m0)，為一行向量，其作為系數(shù)對(duì)應(yīng)的信息多項(xiàng)式為m(x)=mk-1xk-1+mk-2xk-2+…+m1x1+m0。

設(shè)碼字符號(hào)序列c=(cn-1，cn-2，…，c1，c0)，其作為系數(shù)對(duì)應(yīng)的碼字多項(xiàng)式為C(x)=cn-1xn-1+cn-2xn-2+…+c1x1+c0。因此碼字序列可生成

c=m·G。

(8)

對(duì)生成矩陣進(jìn)行行列式變換，可得下列標(biāo)準(zhǔn)矩陣形式：

G=[IkP]，

(9)

式中，Ik為k×k單位矩陣；基于標(biāo)準(zhǔn)生成矩陣，可得系統(tǒng)RS碼的碼字多項(xiàng)式為：

C(x)=m(x)xn-k+p(x)，

(10)

p(x)為系數(shù)取自校驗(yàn)序列的校驗(yàn)多項(xiàng)式。

由定義可知，每個(gè)BCH碼類的碼字都可被其生成多項(xiàng)式g(x)整除，由式(10)可得：

p(x)=C(x)+m(x)xn-k≡m(x)xn-kmodg(x)，

(11)

因此，RS碼字多項(xiàng)式可表示為：

C(x)=m(x)xn-k+p(x)≡m(x)xn-k+

在對(duì)斷路器的處理中，在一些特殊的情況下會(huì)采取就地操作的形式完成相應(yīng)的動(dòng)作。但在實(shí)際應(yīng)用中，我們會(huì)經(jīng)常發(fā)現(xiàn)在進(jìn)行就地電動(dòng)操作時(shí)，機(jī)構(gòu)的動(dòng)作經(jīng)常會(huì)出現(xiàn)錯(cuò)誤，或機(jī)構(gòu)不動(dòng)作[5]。在發(fā)生這種情況時(shí)，首先要對(duì)電源的操作情況進(jìn)行檢查，確保其處于正常狀態(tài)。其次對(duì)機(jī)構(gòu)分、合閘線圈進(jìn)行減壓，如果是因線圈燒毀引起的機(jī)構(gòu)錯(cuò)誤動(dòng)作或不動(dòng)作，則應(yīng)當(dāng)對(duì)線圈進(jìn)行更換，在對(duì)線圈的阻止大小進(jìn)行對(duì)比時(shí)，要對(duì)操作電流的是交流電還是直流電進(jìn)行區(qū)分。

m(x)xn-kmodg(x)。

(12)

2 基于多項(xiàng)式插值的列表譯碼算法

傳統(tǒng)的RS碼譯碼算法利用編碼時(shí)所依附有限域的代數(shù)結(jié)構(gòu)來進(jìn)行譯碼，所以又稱為代數(shù)譯碼。(n，k)RS碼采用傳統(tǒng)代數(shù)譯碼方法進(jìn)行譯碼時(shí)，其糾錯(cuò)能力為t=(dmin-1)/2，其中dmin=n-k+1為碼字的最小距離。

1997年Guruswami和Sudan[11]指出突破RS碼的糾錯(cuò)能力限是可能的。Guruswami-Sudan(GS)算法的糾錯(cuò)能力已突破傳統(tǒng)代數(shù)的糾錯(cuò)能力t，其糾錯(cuò)能力可達(dá)：

(13)

GS算法的主要思路是利用多項(xiàng)式插值方法，將接收到的序列通過多項(xiàng)式插值的方法重構(gòu)生成多項(xiàng)式。

Koetter-Vardy(KV)算法在GS算法的基礎(chǔ)上，依據(jù)信道輸出的每個(gè)軟信息，給出了每個(gè)差值點(diǎn)不同的重?cái)?shù)分配方法?？傮w上，KA算法主要分為5步：計(jì)算可靠性矩陣/Reliability Matrix；求重?cái)?shù)矩陣/Multiplicity Matrix；Koetter-Vardy插值(軟插值)；Roth-Ruckenstein多項(xiàng)式分解(求根)候選碼字的選擇輸出。Koetter-Vardy Algorithm (KVA)流程如圖1所示。

圖1 Koetter-Vardy Algorithm (KVA)流程

3 基于信道軟輸出可信度的性能增強(qiáng)算法

雖然GS算法被廣泛認(rèn)為是能夠突破RS碼糾錯(cuò)能力的第一種譯碼算法，但是Forney在1966年提出的譯碼結(jié)構(gòu)(不指定編碼類型)以及Chase在1972年利用信道軟輸出提供的可靠性信息來產(chǎn)生比HDD譯碼算法更好的性能增強(qiáng)算法，該過程的糾錯(cuò)能力可以擴(kuò)展到HDD譯碼算法的2倍[12-13]。

3.1 廣義最小距離譯碼

廣義最小距離(Generalized Minimum Distance，GMD)譯碼：對(duì)于最小漢明距離為dmin的(n，k)線性分組碼，GMD譯碼算法基于糾錯(cuò)糾刪代數(shù)譯碼算法，產(chǎn)生最多?(dmin+1)/2」個(gè)候選碼字，最后從候選碼字譯碼結(jié)果中選擇最可能的一個(gè)作為譯碼輸出[14]。若2v+e≤dmin-1，則糾錯(cuò)糾刪譯碼算法可以糾正v個(gè)錯(cuò)誤和e個(gè)刪除的所有組合。GMD算法考慮e≤dmin-1個(gè)刪除出現(xiàn)在dmin-1個(gè)最不可靠位置的所有情況，這些最不可靠位置為最可能出錯(cuò)的位置。

根據(jù)接收序列r得到硬判決接收序列RHD，并對(duì)RHD中的每一個(gè)符號(hào)分配一個(gè)可靠值；修正硬判決接收序列RHD，產(chǎn)生?(dmin+1)/2」個(gè)序列的列表。

若dmin為偶數(shù)，修正RHD的方法為：刪除最不可靠的符號(hào)、刪除最不可靠的3個(gè)符號(hào)、……、刪除最不可靠的dmin-1個(gè)符號(hào)；若dmin為奇數(shù)，修正RHD的方法為：不刪除任何符號(hào)、刪除最不可靠的2個(gè)符號(hào)、……、刪除最不可靠的dmin-1個(gè)符號(hào)。

使用糾錯(cuò)糾刪代數(shù)譯碼算法對(duì)每一個(gè)修正后的候選碼字進(jìn)行譯碼。計(jì)算每一個(gè)候選譯碼碼字的軟判決譯碼度量，選擇最可能的候選碼字為譯碼結(jié)果。

3.2 Chase系列算法

作為GMD譯碼方法的推廣，Chase發(fā)明了3種算法：Chase-III、Chase-II和Chase-I。

Chase-III：非常類似GMD算法，區(qū)別就在于修正硬判決信息時(shí)用取反操作代替了刪除操作(即將1變?yōu)?，0變?yōu)?)，在譯碼時(shí)僅使用糾錯(cuò)的譯碼算法即可；具體方法不再贅述。對(duì)于二進(jìn)制碼，Chase-III算法和GMD譯碼算法的差錯(cuò)性能大致相同，所需的算法復(fù)雜度也大致相等。

Chase-II：是對(duì)Chase-III的一個(gè)改進(jìn)，它產(chǎn)生一個(gè)用于譯碼的更大的候選碼字列表。Chase-II算法中，局限在硬判決接收序列z的?dmin/2」個(gè)最不可靠位置上的所有可能錯(cuò)誤組合組成的錯(cuò)誤模式的集合E個(gè)被用來修正z。集合E稱為測(cè)試錯(cuò)誤模式集合(Test Error Pattern Set)，它由2?dmin/2」個(gè)測(cè)試錯(cuò)誤模式組成，這些錯(cuò)誤模式是考慮到z的?dmin/2」個(gè)最不可靠位置上0和1的所有組合而得到的。因此，Chase-II算法的候選碼字的列表隨最小距離dmin指數(shù)增長，這將有可能導(dǎo)致過多的計(jì)算空間和計(jì)算復(fù)雜度，不過Chase-II的差錯(cuò)性能要遠(yuǎn)勝Chase-III。

在3種Chase算法中，Chase-II在差錯(cuò)性能和譯碼復(fù)雜度上具有最優(yōu)的平衡。RS碼的Chase譯碼均指Chase-II譯碼結(jié)構(gòu)。

列表輔助譯碼和有界距離譯碼之間關(guān)系的示意圖如圖2所示。假設(shè)應(yīng)判決的接收向量為r，在有界譯碼算法中，當(dāng)硬判決的接收向量r落入某碼字c0的漢明球內(nèi)，有界距離譯碼算法譯接收向量r為碼字c0，此時(shí)distance(c0，r)≤dmin/2；當(dāng)接收向量r沒有落入任一個(gè)碼字所在的漢明球內(nèi)，如圖2(b)所示，此時(shí)有界距離算法譯碼失敗；在Chase輔助譯碼中，對(duì)于圖2 (b)情形，通過對(duì)接收向量r的若干個(gè)最不可靠比特位進(jìn)行翻轉(zhuǎn)，“輔助”修正后的接收向量r′進(jìn)入到某個(gè)碼字的漢明球內(nèi)，如圖2(c)所示。顯然對(duì)于有限距離無法譯碼的碼字，可以通過不可靠位的輔助修正，可能會(huì)被糾正過來，從而突破有限距離譯碼的糾錯(cuò)能力。

圖2 RS碼有界距離譯碼算法

以(255，239)RS 碼為例，對(duì)上面算法的誤幀率性能進(jìn)行了比較，具體的仿真參數(shù)如表1所示。(255，239)RS碼的不同譯碼算法誤幀率性能對(duì)比如圖3所示。

表1 RS碼硬判決譯碼算法糾錯(cuò)能力對(duì)比及示例

參量參量值(255,239)RS碼碼符號(hào)長度n=2m-1255信息符號(hào)個(gè)數(shù)k239校驗(yàn)符號(hào)個(gè)數(shù)r=n-k=2t16最小碼距(符號(hào))dmin=2t+117符號(hào)域GF(2m)GF(256)BMA糾錯(cuò)能力dmin-1 /28GS糾錯(cuò)能力n-n-dmin n8.647RS碼Chase譯碼糾錯(cuò)能力(最大)2t16

圖3 (255，239)RS碼的不同譯碼算法誤幀率性能對(duì)比

從圖3的(255，239)RS碼誤幀率性能可以看出，相對(duì)于傳統(tǒng)的BMA譯碼算法，KV算法可以提升RS碼的性能，在誤幀率為10-3時(shí)，大約有0.35 dB的性能增益；但此時(shí)RS碼的Chase譯碼算法有大約0.65 dB的增益，接近漢明距離大1倍的 (255，223)RS碼的BMA算法的性能，這和前面的分析是一致的。

4 結(jié)束語

Chase列表譯碼算法的性能隨著不可靠位的增大而增強(qiáng)，最大可擴(kuò)展到其設(shè)計(jì)糾錯(cuò)能力的2倍；然而Chase譯碼算法的復(fù)雜度隨著最可靠位的位數(shù)呈指數(shù)級(jí)的增加。針對(duì)Chase譯碼復(fù)雜度高的問題，文獻(xiàn)[15-16]分別利用多項(xiàng)式插值和Belief Propagation迭代算法的低復(fù)雜度的譯碼算法；文獻(xiàn)[17]提出的概率生成候選測(cè)試向量的Chase譯碼算法，但是這些算法對(duì)dmin來講，復(fù)雜度的改善還是非常有限的。尋找更低的低復(fù)雜度的Chase列表譯碼算法結(jié)構(gòu)是后續(xù)研究的方向。