張 哲，周 亮，周志恒

(電子科技大學(xué)通信抗干擾國家級重點(diǎn)實(shí)驗(yàn)室 成都 610054)

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

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

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

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

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

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

1 MBBP 算法以及mRRD 算法

1.1 MBBP 算法

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

圖1 MBBP 算法結(jié)構(gòu)

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

MBBP 算法的性能取決于子譯碼器輸出候選碼字的誤字率及其等價的誤碼率，進(jìn)一步地，依賴于各個子校驗(yàn)矩陣的環(huán)結(jié)構(gòu)。

1.2 mRRD 算法

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

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

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

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

由于自同構(gòu)群中的置換作用于基礎(chǔ)矩陣后得到的擴(kuò)展矩陣具有和基礎(chǔ)矩陣一樣的環(huán)結(jié)構(gòu)，因此可以保證每個子譯碼器的誤碼率沒有結(jié)構(gòu)性惡化。顯然，mRRD 算法構(gòu)建的關(guān)鍵是找到碼的自同構(gòu)群。

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

對于構(gòu)造LDPC 碼的擴(kuò)展校驗(yàn)矩陣的許多方法而言，不經(jīng)意的方法會導(dǎo)致矩陣中的短環(huán)更短也更多，將其用于子譯碼器中的BP 處理時，難以有效改善譯碼性能。為獲得適于多子譯碼器的擴(kuò)展矩陣序列，本節(jié)首先分析短環(huán)導(dǎo)致譯碼性能惡化的機(jī)理和消除短環(huán)影響的途徑，然后再給出一種可改善譯碼性能的擴(kuò)展譯碼模塊級聯(lián)基礎(chǔ)譯碼模塊的子譯碼器結(jié)構(gòu)。

2.1 BP 算法中短環(huán)的影響分析

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

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

圖3 Tanner 圖中短環(huán)的信息流動

以圖3a 為例，第一次迭代的信息通過校驗(yàn)節(jié)點(diǎn) c1傳給了 v2。第二次迭代的時候， v2把信息經(jīng) c2傳回給了 v1，完成了一次循環(huán)。圖3b 通過3 次迭代完成了一次循環(huán)。

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

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

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

圖4 并行組合譯碼結(jié)構(gòu)

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

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

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

3 本原式構(gòu)造的LDPC 碼及其擴(kuò)展校驗(yàn)矩陣的構(gòu)造方法

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

3.1 編碼方式

3.2 擴(kuò)展校驗(yàn)矩陣的構(gòu)造方法

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

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

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

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

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

5)依照式(10)，將fq(x)對應(yīng)向量做循環(huán)位移生成擴(kuò)展校驗(yàn)矩陣。

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

4 仿真驗(yàn)證

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

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

不同信噪比下誤碼率仿真結(jié)果如圖5 所示?？梢?，譯碼性能隨著子譯碼器個數(shù)增加而改善，但是子譯碼器個數(shù)大于5 后，譯碼性能趨于穩(wěn)定。

圖5 子譯碼器個數(shù)的誤碼率曲線

圖6 誤碼率曲線

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

5 結(jié) 束 語

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

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