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

張 哲，周 亮，周志恒

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

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

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

LDPC 碼是分組碼的一個(gè)重要子類[8-9]，其校驗(yàn)矩陣的構(gòu)造途徑多種多樣，提供了實(shí)現(xiàn)多子譯碼器系統(tǒng)的較大可能。文獻(xiàn)[10]在MBBP 的基礎(chǔ)上，針對(duì)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)群從一個(gè)具有良好環(huán)結(jié)構(gòu)的校驗(yàn)矩陣擴(kuò)展出具有相同環(huán)結(jié)構(gòu)的矩陣。但是對(duì)于一般的LDPC 碼而言卻很難找到其自同構(gòu)群[10,12]。

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

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

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

1 MBBP 算法以及mRRD 算法

1.1 MBBP 算法

MBBP 算法是一個(gè)多個(gè)子譯碼器構(gòu)建的并行譯碼系統(tǒng)[6]，它的子譯碼器是由使用不同校驗(yàn)矩陣的BP 譯碼模塊構(gòu)成。圖1 是MBBP 算法的結(jié)構(gòu)，其中子譯碼器 D0中的基礎(chǔ)譯碼模塊使用基礎(chǔ)校驗(yàn)矩陣H0對(duì)輸入進(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 算法的性能取決于子譯碼器輸出候選碼字的誤字率及其等價(jià)的誤碼率，進(jìn)一步地，依賴于各個(gè)子校驗(yàn)矩陣的環(huán)結(jié)構(gòu)。

1.2 mRRD 算法

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

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

1)初始化：令θ為單位置換；令t=0；記BP 譯碼輸入為L(zhǎng)(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)，因此可以保證每個(gè)子譯碼器的誤碼率沒有結(jié)構(gòu)性惡化。顯然，mRRD 算法構(gòu)建的關(guān)鍵是找到碼的自同構(gòu)群。

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

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

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

BP 算法是在校驗(yàn)矩陣的等效Tanner 圖上，計(jì)算變量節(jié)點(diǎn)的似然值并計(jì)算校驗(yàn)節(jié)點(diǎn)的信道外信息產(chǎn)出值，并在兩類節(jié)點(diǎn)之間交換信息后再進(jìn)行迭代計(jì)算的過程。若Tanner 圖中存在由某個(gè)變量節(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)的似然值估計(jì)存在較大誤差。因此，短環(huán)較多的校驗(yàn)矩陣通常無法獲得良好的譯碼性能。

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

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

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

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

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

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

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

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

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

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

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

以本原多項(xiàng)式作為連接多項(xiàng)式的產(chǎn)生的線性序列是m 序列，m 序列的截段可以等價(jià)為一個(gè)LDPC 碼的碼字。這種LDPC 碼可稱為m 序列碼[13]。由于m 序列產(chǎn)生器是一個(gè)線性移位反饋寄存器，因此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能代替 α重新表示整個(gè)有限域，即：

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

根據(jù)以上分析，本文設(shè)計(jì)了一種構(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)對(duì)應(yīng)向量做循環(huán)位移生成擴(kuò)展校驗(yàn)矩陣。

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

4 仿真驗(yàn)證

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

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

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

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

圖6 誤碼率曲線

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

5 結(jié) 束 語(yǔ)

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

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