削弱震蕩節(jié)點(diǎn)的LDPC碼譯碼算法研究

陳紫強(qiáng) 王廣耀

(1. 桂林電子科技大學(xué),廣西桂林 541004； 2. 桂林電子科技大學(xué)信息與通信學(xué)院,廣西桂林 541004)

1 引言

低密度奇偶校驗(yàn)(Low-Density Parity-Check)碼是誤碼性能最接近香農(nóng)極限的線性分組糾錯(cuò)碼[1]。近年來,低復(fù)雜度、高性能的LDPC碼譯碼算法成為國內(nèi)外研究的熱點(diǎn)[2- 6]。文獻(xiàn)[2]提出的置信傳播(belief propagation,BP)算法誤碼性能極好,但譯碼復(fù)雜度較高,不利于硬件實(shí)現(xiàn)。Elidan提出基于殘差值的置信傳播算法[3](Residual Belief-Propagation,RBP),根據(jù)節(jié)點(diǎn)更新前后消息的殘差值來進(jìn)行選擇更新,優(yōu)先更新殘差值最大的節(jié)點(diǎn),使其接收更多的外信息,從而加快收斂速度。然而,在每次迭代中都要對消息更新前后的殘差值進(jìn)行比較排序,確定消息的更新次序,因此在加快收斂速度的同時(shí)也會出現(xiàn)“貪婪性”問題,導(dǎo)致已經(jīng)正確譯碼的比特節(jié)點(diǎn)在譯碼更新處理中再次出錯(cuò)。文獻(xiàn)[4]對RBP算法作進(jìn)一步改進(jìn),提出了一種基于變量節(jié)點(diǎn)信息的譯碼算法(Variable-to-Check RBP,VC-RBP),仿真結(jié)果表明,該算法較RBP算法有著約0.3 dB的性能提升,且復(fù)雜度也有所降低。文獻(xiàn)[5]簡化了RBP算法剩余信息的計(jì)算公式,提出了一種復(fù)雜度更低,性能更好的校驗(yàn)節(jié)點(diǎn)信息動態(tài)策略分層BP算法。面向節(jié)點(diǎn)的殘差置信傳播算法(Node-Wise RBP,NW-RBP)[6]利用最大殘差值對節(jié)點(diǎn)進(jìn)行更新排序,首先更新完該節(jié)點(diǎn)的相鄰邊,然后再進(jìn)行判決,讓更多不可靠的變量節(jié)點(diǎn)接收外信息,從而改善貪婪性,但是該算法增加了譯碼復(fù)雜度,并且誤碼性能有待進(jìn)一步提高。

鑒于此,提出了基于變量節(jié)點(diǎn)消息震蕩現(xiàn)象的殘差置信傳播(VNO-RBP)算法。該算法采用先分組后選擇的動態(tài)調(diào)度思想,以相對殘差值為參考指標(biāo),優(yōu)先更新殘差值較大的節(jié)點(diǎn),加快譯碼收斂；同時(shí),對于譯碼過程中出現(xiàn)的震蕩節(jié)點(diǎn)前后兩次迭代中的LLR值作加權(quán)平均處理,提高該節(jié)點(diǎn)的可靠度；然后繼續(xù)進(jìn)行下一輪迭代。理論分析和實(shí)驗(yàn)仿真證明了本文提出的VNO-RBP算法的譯碼復(fù)雜度更低,并且誤碼性能優(yōu)于NW-RBP算法。

2 VNO-RBP譯碼算法

NW-RBP算法通過讓不可靠的變量節(jié)點(diǎn)獲得更多的外信息,降低了RBP算法的貪婪性。然而該算法選擇標(biāo)準(zhǔn)單一,使得優(yōu)先傳遞不可靠變量節(jié)點(diǎn)并不能降低該節(jié)點(diǎn)的不可靠度。在消息傳遞過程中,前后兩次迭代之間的變量節(jié)點(diǎn)LLR值可能會發(fā)生大幅震蕩,稱之為震蕩現(xiàn)象[7]。對于這類節(jié)點(diǎn)即使優(yōu)先更新,也不一定能夠消除震蕩現(xiàn)象。本文在動態(tài)調(diào)度算法的基礎(chǔ)上先引入停止準(zhǔn)則,然后設(shè)計(jì)一種震蕩節(jié)點(diǎn)消息處理方案,以降低震蕩節(jié)點(diǎn)對相鄰節(jié)點(diǎn)可靠度的影響。

2.1 停止準(zhǔn)則

停止準(zhǔn)則主要應(yīng)用于多步譯碼通信領(lǐng)域。在譯碼迭代消息達(dá)到特定條件時(shí)停止當(dāng)前譯碼,結(jié)束譯碼或者繼續(xù)進(jìn)行下一步譯碼[8]。VNO-RBP算法通過分析迭代次數(shù)與錯(cuò)誤節(jié)點(diǎn)個(gè)數(shù)的關(guān)系來確定基本的停止準(zhǔn)則。圖1為(864,432)QC-LDPC碼[9]在不同信噪比下進(jìn)行Log-BP譯碼時(shí)迭代次數(shù)與錯(cuò)誤節(jié)點(diǎn)個(gè)數(shù)的關(guān)系圖。仿真條件：AWGN信道下經(jīng)由BPSK調(diào)制,最大譯碼迭代次數(shù)為50次。從圖1中可以看出,在一定范圍內(nèi),隨著迭代次數(shù)的增長,錯(cuò)誤節(jié)點(diǎn)個(gè)數(shù)迅速減少。但當(dāng)?shù)螖?shù)增加到一定程度時(shí),錯(cuò)誤節(jié)點(diǎn)個(gè)數(shù)出現(xiàn)震蕩現(xiàn)象,導(dǎo)致譯碼消息難以收斂。我們根據(jù)這個(gè)特征來設(shè)置停止準(zhǔn)則,使用β作為Log-BP譯碼的第一步迭代次數(shù),若迭代β次仍無法全部譯碼成功,則進(jìn)行動態(tài)調(diào)度譯碼算法的第二步。根據(jù)圖1中譯碼迭代次數(shù)與錯(cuò)誤節(jié)點(diǎn)個(gè)數(shù)的關(guān)系,我們令β=3。譯碼的基本流程如下：

(1)使用Log-BP算法進(jìn)行迭代譯碼；

(2)迭代3次后,如果譯碼迭代消息滿足停止準(zhǔn)則,則跳至下一步；如果譯碼成功則結(jié)束譯碼；

(3)使用動態(tài)調(diào)度策略選擇優(yōu)先更新的節(jié)點(diǎn)；

(4)優(yōu)先更新相對殘差值較大的節(jié)點(diǎn)并對更新后的節(jié)點(diǎn)信息作震蕩處理,然后重新選取優(yōu)先更新的節(jié)點(diǎn)進(jìn)行下一次迭代；

(5)結(jié)合變量節(jié)點(diǎn)的后驗(yàn)LLR值對該節(jié)點(diǎn)進(jìn)行譯碼判決；

(6)計(jì)算伴隨式的值,若結(jié)果為0或達(dá)到最大迭代次數(shù),則結(jié)束譯碼,否則跳回第3步繼續(xù)迭代。

圖1 不同迭代次數(shù)下錯(cuò)誤節(jié)點(diǎn)個(gè)數(shù)的變化

2.2 動態(tài)調(diào)度策略

動態(tài)調(diào)度策略的主要思想就是根據(jù)一定的規(guī)則選擇優(yōu)先更新的節(jié)點(diǎn),然后采用Log-BP算法對選定的邊進(jìn)行更新。因此在動態(tài)調(diào)度算法中,邊的選擇策略直接影響著最終的誤碼性能[10]。由于本文的動態(tài)調(diào)度是基于Log-BP算法進(jìn)行改進(jìn)的,我們首先分析Log-BP算法的特點(diǎn)：

(1)在Log-BP譯碼過程中,部分變量節(jié)點(diǎn)只需要很少的迭代次數(shù)就擁有較高可靠度,不再產(chǎn)生震蕩。

(2)當(dāng)譯碼消息收斂時(shí),節(jié)點(diǎn)處更新前后的數(shù)值基本不變。

(3)節(jié)點(diǎn)處更新前后的數(shù)值相差很大時(shí),說明譯碼消息沒有收斂。

(4)譯碼過程中,即使進(jìn)行了多次迭代,依然存在震蕩現(xiàn)象。

動態(tài)調(diào)度策略就是利用上述特點(diǎn),根據(jù)一定的規(guī)則選擇優(yōu)先更新的節(jié)點(diǎn)。在現(xiàn)有的動態(tài)調(diào)度算法中,普遍以殘差值來決定變量節(jié)點(diǎn)的優(yōu)先更新順序,最大殘差值代表該節(jié)點(diǎn)最不可靠,在譯碼中擁有最大優(yōu)先權(quán)[11]。但是這種單一的判斷指標(biāo)并不具備完整性,事實(shí)上,最大殘差值并不意味著該處的變量節(jié)點(diǎn)絕對是最不穩(wěn)定的[12]。

本文提出的動態(tài)調(diào)度策略不再以最大殘差值作為決定節(jié)點(diǎn)是否優(yōu)先更新的指標(biāo),而是首先對變量節(jié)點(diǎn)進(jìn)行分組,然后使用相對殘差值rr(mc→ν)來進(jìn)行判定

(1)

其中,mc→ν為從校驗(yàn)節(jié)點(diǎn)c傳遞到變量節(jié)點(diǎn)ν的信息,f(mc→ν)表示mc→ν更新后的值。當(dāng)節(jié)點(diǎn)處的相對殘差值趨向于0時(shí),說明該節(jié)點(diǎn)的譯碼消息收斂；反之當(dāng)相對殘差值較大時(shí),說明該消息難以收斂。優(yōu)先更新最大相對殘差值對應(yīng)的節(jié)點(diǎn),會加快譯碼收斂速度。

對變量節(jié)點(diǎn)的分組采用如下策略：首先對于所有的變量節(jié)點(diǎn),將前后兩次迭代中消息符號發(fā)生改變的變量節(jié)點(diǎn)集合記為S,其余變量節(jié)點(diǎn)集合記為C。其次,定義S1為S中滿足|mi|>|f(mi)|的節(jié)點(diǎn)集合,S2為S中滿足|mi|<=|f(mi)|的所有節(jié)點(diǎn)集合,其中mi為變量節(jié)點(diǎn)νi的信息,f(mi)表示mi更新后的信息。最后將三組集合分別按照相對殘差值大小排序,具體優(yōu)先級如下：

(1)如果S1不為空集,選擇S1中對應(yīng)相對殘差值最大的節(jié)點(diǎn)優(yōu)先更新；

(2)如果S1為空集、S2不為空集,選擇S2中對應(yīng)相對殘差值最大的節(jié)點(diǎn)優(yōu)先更新；

(3)如果S為空集、C不為空集,選擇C中對應(yīng)相對殘差值最大的節(jié)點(diǎn)優(yōu)先更新。

2.3 震蕩節(jié)點(diǎn)的處理

變量節(jié)點(diǎn)消息更新：

L(l)(νij)=L(pi)+∑j′∈N(i)jL(l)(cj′i)

(2)

譯碼判決：

L(l)(νi)=L(pi)+∑j∈N(i)L(l)(cji)

(3)

假設(shè)某一變量節(jié)點(diǎn)的度數(shù)為dν,則由式(2)和式(3)可以得到：

(4)

其中,L(l)(νij)為該變量節(jié)點(diǎn)在第l次迭代中的LLR值,L(l)(νi)為該變量節(jié)點(diǎn)在第l次迭代中的譯碼判決消息值,L(pi)為該變量節(jié)點(diǎn)的先驗(yàn)消息。由式(4)可發(fā)現(xiàn),變量節(jié)點(diǎn)偽后驗(yàn)概率L(l)(νi)會隨著其LLR值的震蕩而出現(xiàn)無法收斂的情況,這勢必會導(dǎo)致譯碼的錯(cuò)誤判決。因此對震蕩節(jié)點(diǎn)的LLR值進(jìn)行修正,能夠及時(shí)糾正消息傳遞中的錯(cuò)誤消息的傳播,達(dá)到改善譯碼性能的目的。

一般錯(cuò)誤比特?cái)?shù)和震蕩節(jié)點(diǎn)個(gè)數(shù)同時(shí)變化,錯(cuò)誤節(jié)點(diǎn)的LLR值很小且符號頻繁變化[13]。當(dāng)某一變量節(jié)點(diǎn)的LLR值在相鄰兩次迭代過程中符號發(fā)生變化時(shí),前后兩個(gè)LLR值之間必有一個(gè)是趨于正確的[14-15]。用二者的均值來替代該節(jié)點(diǎn)第l次迭代之后的LLR值,可以降低前后兩次迭代變量節(jié)點(diǎn)LLR值的變化幅度,增加收斂到正確碼字的可能性。這種處理方案雖然不能完全消除變量節(jié)點(diǎn)LLR值的震蕩現(xiàn)象,但可以減少震蕩節(jié)點(diǎn)的數(shù)目,避免震蕩節(jié)點(diǎn)LLR值的傳播干擾其他節(jié)點(diǎn)的正確譯碼；從工程實(shí)現(xiàn)的角度分析,只需增加一個(gè)緩存器用于存儲上一次迭代中的變量節(jié)點(diǎn)外部LLR值,以及一個(gè)除法器用于將加權(quán)后的信息右移一位以得到變量節(jié)點(diǎn)的更新值,無需任何乘法器,付出的硬件資源代價(jià)很小。

在動態(tài)調(diào)度策略選中的節(jié)點(diǎn)中,將震蕩節(jié)點(diǎn)前后兩次迭代中的外部LLR值作均值處理。如果一個(gè)節(jié)點(diǎn)多次震蕩,那么它會被多次處理,直至節(jié)點(diǎn)的震蕩越來越小。如圖2所示,采用IEEE802.16e標(biāo)準(zhǔn)中的(864,432)QC-LDPC碼進(jìn)行傳統(tǒng)的Log-BP譯碼,假設(shè)采用全零碼字傳輸。對變量節(jié)點(diǎn)的外部LLR值作均值處理后,錯(cuò)誤節(jié)點(diǎn)數(shù)明顯有所減少,證明了均值處理方案的有效性。處理方式如下：

(5)

圖2 均值處理前后的錯(cuò)誤節(jié)點(diǎn)數(shù)目對比

2.4 VNO-RBP算法流程

在VNO-RBP譯碼算法中,首先進(jìn)行第一步譯碼并迭代3次。如果滿足停止準(zhǔn)則,則進(jìn)入下一步譯碼。第二部分的譯碼主要包括動態(tài)調(diào)度策略和震蕩節(jié)點(diǎn)外部消息的取均值處理,首先對所有變量節(jié)點(diǎn)按照既定的調(diào)度策略選擇最不可靠的變量節(jié)點(diǎn)νi。然后更新所有與該節(jié)點(diǎn)相連接的校驗(yàn)節(jié)點(diǎn)。判斷變量節(jié)點(diǎn)νi更新前后的取值是否需要進(jìn)行處理。更新相應(yīng)的變量節(jié)點(diǎn)消息,并計(jì)算后驗(yàn)消息。其中,mcν為信道初始消息,R(j)和C(i)分別表示校驗(yàn)節(jié)點(diǎn)cj及變量節(jié)點(diǎn)νi的相鄰節(jié)點(diǎn),用mcj→νi表示cj傳遞到νi的信息,用mνi→cj表示νi傳遞到cj的信息,其余符號參照Log-BP譯碼算法。具體的算法流程如下：

LDPC碼VNO-RBP譯碼算法流程1. 初始化mcν=0 2. 初始化mνi→cj=2yi/σ2 3. for 任意cj4. for 任意νi∈R(j)5. 計(jì)算mcj→νi6. end for7. end for8. for 任意νi9. 計(jì)算L(νi)與相對殘差值rr(mνi→cj) 10. end for11. 根據(jù)所提的節(jié)點(diǎn)分組策略選擇νi12. for 任意νi∈R(j)i13. 產(chǎn)生并傳遞mcj→νi14. end for15. 計(jì)算硬判決消息L(νi)

16. 判斷是否取均值處理17. 置rr(mνi→cj)=0 18. for 任意cj∈C(i)j19. 產(chǎn)生和傳遞mνi→cj20. end for21. if 不滿足停止準(zhǔn)則22. 返回到第3行23. end if

3 仿真結(jié)果與性能分析

為了驗(yàn)證本文所提算法性能的有效性,仿真分別采用IEEE802.16e標(biāo)準(zhǔn)碼中碼長為864,碼率為0.5的QC-LDPC碼,簡稱C1；以及碼長為1056,碼率為0.5的Mackay碼[16],簡稱C2。在AWGN信道下采用BPSK調(diào)制,設(shè)置最小誤幀數(shù)為10幀,最大譯碼迭代次數(shù)為50次,分別對Log-BP算法、NW-RBP算法以及VNO-RBP算法的誤碼性能進(jìn)行仿真比較。

從圖3、圖4中可以看出,本文提出的VNO-RBP算法的誤碼性能明顯優(yōu)于其他兩種算法。在碼C1條件下,當(dāng)信噪比為3.5 dB時(shí),VNO-RBP算法與Log-BP算法相比,誤碼率由10-4量級降到10-5量級,同時(shí)與NW-RBP算法相比,性能提升約0.31 dB。在碼C2條件下,當(dāng)信噪比為2.5 dB時(shí),VNO-RBP算法與Log-BP算法相比誤碼率由10-4量級降到10-5量級,與NW-RBP算法相比也有一定程度上的性能提升。主要是由于VNO-RBP算法優(yōu)先選擇相對殘差值較大的節(jié)點(diǎn)進(jìn)行更新以及對不可靠節(jié)點(diǎn)進(jìn)行震蕩處理,從而提高譯碼性能。

圖3 碼C1條件下的誤碼性能比較

圖4 碼C2條件下的誤碼性能比較

對于碼C1,當(dāng)誤碼率為10-5時(shí),分別對Log-BP,NW-RBP和VNO-RBP算法的平均迭代次數(shù)進(jìn)行比較分析,如表1所示。

表1 不同譯碼算法的平均迭代次數(shù)

由表1可得,與Log-BP,NW-RBP算法相比,VNO-RBP算法的平均譯碼迭代次數(shù)減少了55.2%和38.1%,明顯地加快了收斂速度。原因?yàn)閂NO-RBP算法在變量節(jié)點(diǎn)迭代更新過程中優(yōu)先更新相對殘差值較大的節(jié)點(diǎn),且對震蕩節(jié)點(diǎn)的LLR值進(jìn)行了加權(quán)處理,減少震蕩節(jié)點(diǎn)數(shù)目,從而促進(jìn)譯碼正確節(jié)點(diǎn)LLR值的傳遞,達(dá)到降低譯碼迭代次數(shù)的目的。

4 復(fù)雜性分析

對于規(guī)則LDPC碼,假設(shè)校驗(yàn)矩陣H為M行N列,dc與dν都是固定的,dc為校驗(yàn)節(jié)點(diǎn)的度數(shù),dν為變量節(jié)點(diǎn)的度數(shù)。令Log-BP算法中節(jié)點(diǎn)更新計(jì)算量E=dc*M=dν*N,表2以此為基準(zhǔn)表示出不同譯碼算法在一次迭代中的計(jì)算量。

表2 不同譯碼算法的運(yùn)算復(fù)雜度

從表1可以看出,Log-BP算法總體復(fù)雜度最低,NW-RBP的運(yùn)算量最大,VNO-RBP算法復(fù)雜度介于二者之間。其中VNU列代表變量節(jié)點(diǎn)更新的計(jì)算量,Residual列代表計(jì)算殘差值所需要的計(jì)算量,3種算法的校驗(yàn)節(jié)點(diǎn)更新計(jì)算量均為E。以(3,6)LDPC碼為例,VNO-RBP的計(jì)算量比NW-RBP減少約6E,因此本文所提的VNO-RBP算法在一定程度上降低了NW-RBP譯碼算法的復(fù)雜度。

5 結(jié)論

為了進(jìn)一步降低NW-RBP算法的誤比特率,提出一種基于變量節(jié)點(diǎn)消息震蕩的殘差置信傳播算法。采用新的動態(tài)調(diào)度策略,首先對變量節(jié)點(diǎn)進(jìn)行分組,然后優(yōu)先更新相對殘差值較大的變量節(jié)點(diǎn),加快譯碼收斂速度。同時(shí)對相鄰兩次迭代中發(fā)生震蕩變量節(jié)點(diǎn)的外部信息進(jìn)行加權(quán)平均處理,降低該變量節(jié)點(diǎn)的不可靠性。實(shí)驗(yàn)仿真和理論分析表明,本文所提的VNO-RBP算法的誤碼性能明顯優(yōu)于NW-RBP算法,同時(shí)復(fù)雜度也有所降低。

[1] Varnica N, Burd G, Gunnam K. Optimizing error floor performance of finite-precision layered decoders of low-density parity-check (LDPC) codes: US, US 8291292 B1[P]. 2012.

[2] Sibel J C, Crussiere M, Helard J F. Modeling BP decoding error events with the LDPC codes of the DVB-S2 standard[C]∥IEEE, International Symposium on Personal, Indoor, and Mobile Radio Communication. IEEE, 2014:902-907.

[3] Saha S, Hussain S R, Rahman A K M A. RBP: Reliable Broadcasting Protocol in Large Scale Mobile Ad Hoc Networks[C]∥IEEE International Conference on Advanced Information NETWORKING and Applications. IEEE Computer Society, 2010:526-532.

[4] Kim J H, Nam M Y, Song H Y, et al.Variable-to-Check Residual Belief Propagation for informed dynamic scheduling of LDPC codes[C]∥International Symposium on Information Theory and ITS Applications. IEEE Xplore, 2008:1- 4.

[5] Han G, Liu X. An efficient dynamic schedule for layered belief-propagation decoding of LDPC codes[J]. IEEE Communications Letters, 2009, 13(12):950-952.

[6] Zhou H, Li P, Feng J, et al. Floodingand node-wise RBP sequentially concatenated decoder for LDPC codes[C]∥Ieee/cic International Conference on Communications in China. IEEE, 2015:1- 4.

[7] Hera A, Boncalo O, Gavriliu C E, et al. Analysis and implementation of on-the-fly stopping criteria for layered QC LDPC decoders[C]∥2015 22nd International Conference Mixed Design of Integrated Circuits & Systems (MIXDES), Torun, 2015: 287-291.

[8] Bian Y, Wang Y, Wang J. Lowering the Error Floor of LDPC Codes by a Two-stage Hybrid Decoding Algorithm[C]∥International Conference on Communications and NETWORKING in China, 2007. Chinacom. IEEE, 2007:590-594.

[9] 安永寧.基于IEEE802.16e標(biāo)準(zhǔn)的碼率兼容QC-LDPC編譯碼器的FPGA實(shí)現(xiàn)[D].西安：西安電子科技大學(xué),2014.

An Y Q.FPGA implementation of rate-compatible QC-LDPC codec based on IEEE802.16e standard[D]. Xi’an: Xidian University,2014.(in Chinese)

[10]Qiu N, Chen W, Lu Y, et al. Informed dynamic scheduling for majority-logic decoding of non-binary LDPC codes[C]∥GLOBECOM 2013-2013 IEEE Global Communications Conference, 2013:1874-1878.

[11]Liu X, Jamalipour A. Informed dynamic scheduling strategies for novel majority-logic decoding of non-binary LDPC codes[C]∥2015 9th International Conference on Signal Processing and Communication Systems (ICSPCS), Cairns, QLD, 2015: 1- 6.

[12]Mhaske S, Uliana D, Kee H, et al. A2.48Gb/s FPGA-based QC-LDPC decoder: An algorithmic compiler implementation[C]∥Sarnoff Symposium. IEEE,2015:88-93.

[13]Shin B, Park H, No J S, et al. Multi-Stage Decoding Scheme with Post-Processing for LDPC Codes to Lower the Error Floors[J]. Ieice Transactions on Communications, 2011, 94-B(8):2375-2377.

[14]Gounai S. Decoding Algorithms Based on Oscillation for Low-Density Parity Check Codes[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2005, E88-A(8):2216-2226.

[15]Liu X, Zhang Y, Cui R. Variable-Node-Based Dynamic Scheduling Strategy for Belief-Propagation Decoding of LDPC Codes[J]. IEEE Communications Letters, 2015, 19(2):147-150.

[16]Mackay D J C. Good Error-Correcting Codes based on Very Sparse Matrices[J]. IEEE Transactions on Information Theory, 1999, 45(2):399- 431.