針對特定LDPC 碼的多子譯碼器并行組合譯碼方法

張 哲，周 亮，周志恒

(電子科技大學通信抗干擾國家級重點實驗室 成都 610054)

對于分組糾錯碼的譯碼，通過多個子譯碼器構建的并行譯碼系統比單譯碼器系統有明顯的性能提升[1]。因此，較早即有多子譯碼器結構概念的Chase算法[2]和其變型的混合譯碼系統[3-4]。Chase 算法作為廣義最小距離譯碼算法[5]的推廣，它通過對軟判決接收序列的不同似然門限選取和處理而獲得多個待譯碼的“硬判決接收”序列，因此多個可并行實現的子譯碼器輸出的候選碼字為最后的最大后驗概率原則提供了最佳碼字的輸出可能。在并行譯碼系統中，針對具體分組碼的代數結構特性，設計和構造多個具有對同一信息數據進行不完全相同的校驗譯碼的獨立子譯碼器是一個挑戰性難題。

文獻[6]提出了一類稱為MBBP (multiple-based belief propagation) 的方法，可以選取一個校驗矩陣(即基礎矩陣)擴展出多個不同的其他校驗矩陣(即擴展校驗矩陣)，再由這些擴展矩陣各自獨立構成了一個子譯碼器。文獻[7]提出的mRRD(modified random redundant decoding)算法結合了MBBP 思想和RRD(random redundant decoding)算法[3]來設計子譯碼器。其中，RRD 算法隨機選取碼的自同構群中的置換元素作用于基礎矩陣來構造擴展校驗矩陣用以譯碼，直到譯碼成功或達到次數上限時輸出一個特定碼字。

LDPC 碼是分組碼的一個重要子類[8-9]，其校驗矩陣的構造途徑多種多樣，提供了實現多子譯碼器系統的較大可能。文獻[10]在MBBP 的基礎上，針對PEG(progressive edge-growth)算法[11]構造的LDPC 碼提出了一種合并短環來獲取擴展校驗矩陣的方法。文獻[12]提出一種由循環碼構造的LDPC 碼，利用mRRD 算法取得了并行譯碼的較大性能提升。這些MBBP 算法運用中的BP 譯碼模塊所使用的擴展校驗矩陣均需要具有良好的環結構，但是文獻[6, 10]并沒有給出相應的矩陣擴展方法。雖然mRRD 算法使用自同構群從一個具有良好環結構的校驗矩陣擴展出具有相同環結構的矩陣。但是對于一般的LDPC 碼而言卻很難找到其自同構群[10,12]。

本文提出的多子譯碼器并行組合譯碼方法，與MBBP 算法不同之處在于新設計了包含兩種子譯碼器的組合結構。第一種子譯碼器是擴展譯碼模塊與基礎譯碼模塊級聯，前者通過BP 算法輸出輔助譯碼的外信息，后者確定候選碼字。其中擴展譯碼模塊的BP 算法迭代次數設置為其對應擴展校驗矩陣中最短環長的一半，以此避免BP 算法受短環的影響。第二種子譯碼器則僅包含基礎譯碼模塊。這兩類子譯碼器的輸出的候選碼字通過同一個LMS(east metric selector)依據最大后驗概率原則篩選出最終譯碼碼字。

本文提出的并行組合譯碼方法對由本原多項式生成的LDPC 碼[13]尤為有效。這類LDPC 碼編碼開銷極低，其碼字是連接多項式是本原式的線性移位寄存器生成的序列片段。由此，本原式作為序列的零化約束關系可以轉換為序列(即碼字)奇偶校驗關系。本原式對應特征向量的循環位移即為生成該碼的基礎校驗矩陣。具體地，為了構建用于并行組合譯碼的子譯碼器的擴展譯碼矩陣，首先找出約束此LDPC 碼的m 序列，再使用多個特定采樣間隔進行采樣獲得采樣序列；然后由采樣序列獲得約束它們的新本原多項式，并把這些新本原式對采樣序列的約束轉化為對碼字序列的約束；最后，將這些新本原式的對應向量循環位移生成擴展校驗矩陣。

本文使用本原式f(x)=x89+x38+1構造了碼長3 000 的m 序列編碼，并進行了誤碼率仿真實驗。實驗中構造了6 個由約束采樣序列的本原式生成的擴展校驗矩陣。此外，通過實驗觀察發現當子譯碼器個數為5 時，誤碼率曲線即有良好的收斂特性。誤碼率仿真結果顯示，本文提出的并行組合譯碼方法比文獻[13]中的單譯碼器譯碼算法有約0.4 dB的提升。

1 MBBP 算法以及mRRD 算法

1.1 MBBP 算法

MBBP 算法是一個多個子譯碼器構建的并行譯碼系統[6]，它的子譯碼器是由使用不同校驗矩陣的BP 譯碼模塊構成。圖1 是MBBP 算法的結構，其中子譯碼器 D0中的基礎譯碼模塊使用基礎校驗矩陣H0對輸入進行BP 譯碼，子譯碼器Di(i=1,2,···,N)中擴展譯碼模塊則使用了擴展校驗矩陣 Hi進行BP 譯碼。

圖1 MBBP 算法結構

式中，d(a,b)是向量a 和b的歐幾里得距離。

MBBP 算法的性能取決于子譯碼器輸出候選碼字的誤字率及其等價的誤碼率，進一步地，依賴于各個子校驗矩陣的環結構。

1.2 mRRD 算法

mRRD 算法與MBBP 類似，由N+1個完全相同的子譯碼器D0,D1,···,DN并行構成，但每個子譯碼器的內部構造與MBBP 算法不同。mRRD 算法的子譯碼器結構如圖2 所示。

mRRD 算法第i 個子譯碼器 Di的譯碼流程是：

1)初始化：令θ為單位置換；令t=0；記BP 譯碼輸入為L(0)=Lch；最大迭代次數為t0。

4)隨機選取置換γ ∈Per(C)，令θ=θγ；將θ作用于基礎矩陣 H0得到校驗矩陣并記為Ht+1=g(θ,H0)；令t=t+1，回到步驟2)。

由于自同構群中的置換作用于基礎矩陣后得到的擴展矩陣具有和基礎矩陣一樣的環結構，因此可以保證每個子譯碼器的誤碼率沒有結構性惡化。顯然，mRRD 算法構建的關鍵是找到碼的自同構群。

2 多子譯碼器并行組合譯碼方法

對于構造LDPC 碼的擴展校驗矩陣的許多方法而言，不經意的方法會導致矩陣中的短環更短也更多，將其用于子譯碼器中的BP 處理時，難以有效改善譯碼性能。為獲得適于多子譯碼器的擴展矩陣序列，本節首先分析短環導致譯碼性能惡化的機理和消除短環影響的途徑，然后再給出一種可改善譯碼性能的擴展譯碼模塊級聯基礎譯碼模塊的子譯碼器結構。

2.1 BP 算法中短環的影響分析

BP 算法是在校驗矩陣的等效Tanner 圖上，計算變量節點的似然值并計算校驗節點的信道外信息產出值，并在兩類節點之間交換信息后再進行迭代計算的過程。若Tanner 圖中存在由某個變量節點至校驗節點再至其他變量節點并最終回返至原變量節點自身的較短連接回路(即短環)，則環中各節點的信息難以在足夠多的節點中遍歷足夠的交互與平滑處理，從而導致變量節點的似然值估計存在較大誤差。因此，短環較多的校驗矩陣通常無法獲得良好的譯碼性能。

圖3 展示了Tanner 圖中短環的信息流動情況，其中圖3a 與3b 分別是4 環和6 環的情況。實線代表第一次迭代時候的信息傳遞，段狀虛線和點狀虛線分別代表第2 次和第3 次迭代時候的信息流。

圖3 Tanner 圖中短環的信息流動

以圖3a 為例，第一次迭代的信息通過校驗節點 c1傳給了 v2。第二次迭代的時候， v2把信息經 c2傳回給了 v1，完成了一次循環。圖3b 通過3 次迭代完成了一次循環。

從圖3 可以看出，若迭代次數是短環環長的一半，則短環中流動的信息將不會再次流入原始起點，從而消除了由短環引起的節點信息估計存在誤差的問題。

2.2 多子譯碼器并行組合譯碼方法

雖然，將BP 算法的迭代次數設置為校驗矩陣的最短環長的一半，可有效消除短環在譯碼中的影響。但是，此時BP 算法無法輸出有效碼字。為了解決這個問題，本文提出一種在擴展BP 之后級聯基礎譯碼模塊的組合并行譯碼方法，其譯碼結構如圖4 所示。

圖4 并行組合譯碼結構

本文提出的并行組合譯碼方法的步驟如下：

1)初始化：設候選碼字集合S =?；將信道接收值序列y的向量LLR 值 Lch分別輸入到N+1個子譯碼器。

3)當N+1個子譯碼器譯碼結束后，若S =?，則譯碼結束并宣稱譯碼失敗。

3 本原式構造的LDPC 碼及其擴展校驗矩陣的構造方法

以本原多項式作為連接多項式的產生的線性序列是m 序列，m 序列的截段可以等價為一個LDPC 碼的碼字。這種LDPC 碼可稱為m 序列碼[13]。由于m 序列產生器是一個線性移位反饋寄存器，因此m 序列碼的編碼開銷極低。為了將并行組合譯碼方法應用于m 序列編碼上，本節先介紹該碼的編碼方法，然后分析其采樣序列的約束關系，最后給出用這種約束關系構造擴展校驗矩陣的方法。

3.1 編碼方式

3.2 擴展校驗矩陣的構造方法

由于GF(2k)可表示為本原元α的冪指數形式：

因此，αq∈GF(2k)是該有限域的本原元的充分必要條件為gcd(q,2k-1)=1，其中gcd(a,b)是a和b的最大公約數[14]。而且新找出的本原元 αq能代替 α重新表示整個有限域，即：

記本原元 αq是k階本原式fq(x)的根，那么本原式fq(x)的形式為：

根據以上分析，本文設計了一種構造擴展校驗矩陣的方法。為滿足gcd(q,2k-1)=1的采樣間隔q，構造擴展校驗矩陣的步驟為：

1)生成f(x)約束下的m 序列 (ai)。

5)依照式(10)，將fq(x)對應向量做循環位移生成擴展校驗矩陣。

由向量做循環位移生成的矩陣一定存在許多短環。因此，盡管該擴展校驗矩陣不適合MBBP 算法中的子譯碼器，但是能用于本文提出的并行組合譯碼方法中的子譯碼器。

4 仿真驗證

在深空通信和極低信噪比等場合，必須利用極低碼率糾錯碼的極限糾錯能力。為示范這類應用，本節構造一個極低碼率m 序列LDPC 碼，選擇本原多項式為f(x)=x89+x38+1，設計碼長為3 000，碼率約0.03。仿真性能指標為誤碼率，對比對象為該碼的單譯碼器譯碼算法[13]。

為驗證子譯碼器個數對于誤碼率的影響，本文通過第3 節提出的方法，以采樣間隔q=3,5,7,9,11,13構造出6 個擴展校驗矩陣，對應的本原式fq(x)分別如下：

不同信噪比下誤碼率仿真結果如圖5 所示。可見，譯碼性能隨著子譯碼器個數增加而改善，但是子譯碼器個數大于5 后，譯碼性能趨于穩定。

圖5 子譯碼器個數的誤碼率曲線

圖6 誤碼率曲線

圖6 展示了不同譯碼方法下m 序列碼的誤碼率曲線，從圖中可以看出，本文提出的并行組合譯碼方法比原單譯碼器譯碼算法有更好的性能，當誤碼率為10-5時，本文的方法比原單譯碼器譯碼算法提升約0.4 dB。

5 結 束 語

研究和設計適用于分組碼譯碼的并行譯碼系統是提高分組碼糾錯性能的又一條有效途徑，適用于編碼復雜度低但譯碼復雜度可寬容的，例如深空探測信息回傳地球等通信場合。

本文提出了一種新的多子譯碼器并行組合譯碼系統，消除了子譯碼器中BP 譯碼模塊里校驗矩陣的短環對譯碼的影響，降低了構造適合的擴展校驗矩陣的難度。針對m 序列編碼，本文提出了一種構造擴展譯碼矩陣的方法，以適用于本文提出的并行組合譯碼方法。仿真實驗顯示，在誤碼率為10-5時，本文提出的并行組合譯碼方法比原單譯碼器譯碼方法提升約0.4 dB。