Reed-Solomon碼性能增強譯碼算法

鄭相全，段 文

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

0 引言

自1960年Reed-Solomon(RS)碼[1]被構造后，由于其突出的抗突發性能，已被廣泛應用于通信系統中，包括數字存儲、衛星和深空空間通信，移動數據通信和擴頻系統。1961年Gorenstein和Zierler證明了RS碼是非二進制BCH碼的子類[2]。因此，RS碼編碼有按BCH碼編碼方式和RS碼定義方式2種編碼結構[3]，其中BCH碼編碼方式可以構造RS系統碼格式[4]。

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

1 RS碼編碼格式分類

1.1 計算映射RS碼定義格式

RS碼是采用編碼方式為計算映射編碼[1]，這種編碼方式是后續GSA[6]和KVA[7]算法的基礎。

設信息多項式為：

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

(1)

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

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

(2)

因此，

m·G，

(3)

式中，

(4)

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

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

(5)

假設接收的硬判決碼字序列為：

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

在接收端，可構造n個方程組。若信道無差錯時，該方程組為：

假設取上述方程組的前k個方程，對應的系數行列式為：

即上述方程組的任意k個方程是相互獨立的，即假設信道無差錯傳輸時，上述的任意k個方程組即可求解出發送的碼元信息序列。

1.2 RS碼的系統碼編碼格式

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

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

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

(6)

式中，α為RS編/譯碼符號域GF(q)內的本原元。由生成多項式可得k個相互獨立的碼字多項式：

因此，RS碼的一個生成矩陣為：

(7)

設信息符號序列m=(mk-1，mk-2，…，m1，m0)，為一行向量，其作為系數對應的信息多項式為m(x)=mk-1xk-1+mk-2xk-2+…+m1x1+m0。

設碼字符號序列c=(cn-1，cn-2，…，c1，c0)，其作為系數對應的碼字多項式為C(x)=cn-1xn-1+cn-2xn-2+…+c1x1+c0。因此碼字序列可生成

c=m·G。

(8)

對生成矩陣進行行列式變換，可得下列標準矩陣形式：

G=[IkP]，

(9)

式中，Ik為k×k單位矩陣；基于標準生成矩陣，可得系統RS碼的碼字多項式為：

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

(10)

p(x)為系數取自校驗序列的校驗多項式。

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

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

(11)

因此，RS碼字多項式可表示為：

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

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

m(x)xn-kmodg(x)。

(12)

2 基于多項式插值的列表譯碼算法

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

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

(13)

GS算法的主要思路是利用多項式插值方法，將接收到的序列通過多項式插值的方法重構生成多項式。

Koetter-Vardy(KV)算法在GS算法的基礎上，依據信道輸出的每個軟信息，給出了每個差值點不同的重數分配方法。總體上，KA算法主要分為5步：計算可靠性矩陣/Reliability Matrix；求重數矩陣/Multiplicity Matrix；Koetter-Vardy插值(軟插值)；Roth-Ruckenstein多項式分解(求根)候選碼字的選擇輸出。Koetter-Vardy Algorithm (KVA)流程如圖1所示。

圖1 Koetter-Vardy Algorithm (KVA)流程

3 基于信道軟輸出可信度的性能增強算法

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

3.1 廣義最小距離譯碼

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

根據接收序列r得到硬判決接收序列RHD，并對RHD中的每一個符號分配一個可靠值；修正硬判決接收序列RHD，產生?(dmin+1)/2」個序列的列表。

若dmin為偶數，修正RHD的方法為：刪除最不可靠的符號、刪除最不可靠的3個符號、……、刪除最不可靠的dmin-1個符號；若dmin為奇數，修正RHD的方法為：不刪除任何符號、刪除最不可靠的2個符號、……、刪除最不可靠的dmin-1個符號。

使用糾錯糾刪代數譯碼算法對每一個修正后的候選碼字進行譯碼。計算每一個候選譯碼碼字的軟判決譯碼度量，選擇最可能的候選碼字為譯碼結果。

3.2 Chase系列算法

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

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

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

在3種Chase算法中，Chase-II在差錯性能和譯碼復雜度上具有最優的平衡。RS碼的Chase譯碼均指Chase-II譯碼結構。

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

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

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

表1 RS碼硬判決譯碼算法糾錯能力對比及示例

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

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

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

4 結束語

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