基于競爭機(jī)制的LDPC碼串行最小和算法*

梁 溪，龍翔林，章恩友，楊 帆

（1.電子科技大學(xué) 通信與信息工程學(xué)院，四川 成都 611731；2.寧波迦南電子有限公司，浙江 寧波 315000）

基于競爭機(jī)制的LDPC碼串行最小和算法*

梁 溪1，龍翔林2，章恩友2，楊 帆1

（1.電子科技大學(xué) 通信與信息工程學(xué)院，四川 成都 611731；2.寧波迦南電子有限公司，浙江 寧波 315000）

針對譯碼模塊設(shè)計(jì)成本和功耗的問題，提出了一種LDPC碼串行最小和算法。該算法是一種采用權(quán)重因子的基于變量節(jié)點(diǎn)更新的串行算法，它基于競爭機(jī)制來更新變量節(jié)點(diǎn)對校驗(yàn)節(jié)點(diǎn)消息集合中的最小值。與傳統(tǒng)串行算法相比，在不損失性能的前提下，它大幅降低了譯碼所需的復(fù)雜度。另一方面，與并行最小和算法相比，新算法不僅大幅降低了所需存儲量，而且性能也有一定的提升，復(fù)雜度只有略微增加。

電力線載波通信；串行最小和算法；低密度奇偶校驗(yàn)碼；迭代譯碼；歸一化權(quán)重因子

0 引言

隨著信息化的發(fā)展，人們對低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼有了重新的認(rèn)識。LDPC碼作為高效的信道糾錯編碼，具有較低的譯碼復(fù)雜度，系統(tǒng)吞吐量較大，已在電力線載波（Power Line Carrier，PLC）通信、第三代和第四代無線移動通信等方面得到了廣泛應(yīng)用[1]。相對于 turbo譯碼算法[2]，采用 LDPC編碼和置信傳播(Belief Propagation，BP)譯碼算法更受人們的青睞[3]。但是BP算法存在對硬件存儲量的需求較大以及對信道情況較為敏感等問題。人們更趨向于魯棒性更好和復(fù)雜度更低的譯碼算法，最典型的就是并行最小和(Parallel Min-Sum，PMS)算法[4]。這類算法在實(shí)現(xiàn)中只需要加法和比較運(yùn)算，且不需要知道信道情況，可以獲得性能和復(fù)雜度的良好折衷?？紤]到PMS算法前后兩次迭代譯碼過程中，參與信息交換的置信度被過高估計(jì)，文獻(xiàn)[5]通過引入歸一化權(quán)重因子來減少這種負(fù)面影響，使其性能逼近最優(yōu)BP算法的性能，可稱之為歸一化并行最小和(Normalized Parallel Min-Sum，N-PMS)算法。隨著研究的深入，人們提出了不同的譯碼機(jī)制來提高置信傳播的效率，其中較為重要的一類是采用權(quán)重因子的串行最小和(Normalized Serial Min-Sum，N-SMS)算法[6]。在電力線載波通信中，收發(fā)模塊通常采用具有低存儲量和低復(fù)雜度的編、譯碼算法。N-SMS算法雖然在存儲上較N-PMS算法有一定減少，但N-SMS算法由于每次迭代都采用min操作來更新最小值，復(fù)雜度相對較高。

為實(shí)現(xiàn)可靠通信，并綜合考慮實(shí)現(xiàn)成本、器件功耗以及處理復(fù)雜度的問題，針對N-SMS算法提出了一種基于競爭機(jī)制的歸一化的串行最小和(Normalized Competitive Min-Sum，N-CMS)算法。該算法在按照自然順序更新變量節(jié)點(diǎn)對校驗(yàn)節(jié)點(diǎn)消息的同時，還利用競爭關(guān)系更新變量節(jié)點(diǎn)對校驗(yàn)節(jié)點(diǎn)消息集合中的最小值。與文獻(xiàn)[6]類似的是，N-CMS在更新某一變量節(jié)點(diǎn)時，同時利用了與該節(jié)點(diǎn)之前已更新的軟信息和該節(jié)點(diǎn)之后還未更新的軟信息，所以N-SMS算法與N-CMS算法的性能相同。不同的是，N-CMS通過采用競爭機(jī)制來更新屬于同一校驗(yàn)式的變量節(jié)點(diǎn)集合中的最小值，避免了文獻(xiàn)[6]中采用min操作的復(fù)雜運(yùn)算，并進(jìn)一步減少了存儲量。

1 N-PMS算法簡介

為了簡化敘述，該文沿用文獻(xiàn)[7]中的部分符號定義。設(shè)m和n分別表示校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)，H為LDPC碼對應(yīng)的校驗(yàn)矩陣，當(dāng)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)有邊相連接時，則hmn=1，它是H中的第m行和n列的元素。N(m)={n|hmn=1}表示參與校驗(yàn)方程m的變量節(jié)點(diǎn)的集合，N(m) 為 N(m)中除去元素 n后構(gòu)成的集合；相應(yīng)地，M(n)={m|hmn=1}表示與變量節(jié)點(diǎn) n相連的校驗(yàn)節(jié)點(diǎn)的集合，M(n)m為集合M(n)中除去元素 m后構(gòu)成的集合。設(shè)是從變量節(jié)點(diǎn)n傳遞給校驗(yàn)節(jié)點(diǎn)m的軟信息，表示在給定接收序列y，并且除了第m個校驗(yàn)方程外，其他與 n相關(guān)的校驗(yàn)方程都滿足的條件下，xn=x的概率；是由校驗(yàn)節(jié)點(diǎn)m傳遞給變量節(jié)點(diǎn)n的軟信息，表示在xn=x，且參加第m個校驗(yàn)方程的除n外的其他變量節(jié)點(diǎn)的概率 Qn~m已知的條件下，該校驗(yàn)方程成立的概率，其中∈N(m) 。

設(shè) s為長為 N的編碼序列 x=[x1，x2，…，xN]T經(jīng)過BPSK調(diào)制后的信號，g是均值為 0、方差為 σ2的高斯噪聲。設(shè)s經(jīng)過AWGN信道后的接收序列為y=[y1，y2，…，yN]T，BP譯碼后的序列為。其中：

定義變量信息、校驗(yàn)信息和后驗(yàn)信息分別為：

傳統(tǒng)的N-PMS算法可歸納如下：

初始化：令先驗(yàn)信息L(Pn)=yn，L(Qnm)=L(Pn)

步驟1：判斷是否達(dá)到設(shè)定的最大迭代次數(shù) MT，若是則程序結(jié)束；否則執(zhí)行步驟(2)。

步驟2：對m=1，2，…，M和所有的n∈N(m)計(jì)算：

在上式中，αnm=sign(L(Qnm))和 βnm=abs(L(Qnm))，分別表示 L(Qnm)的符號和絕對值，λ為歸一化權(quán)重因子，滿足0≤λ≤1。

步驟3：對n=1，2，…，N和所有的m∈M(n)計(jì)算：

步驟 4：對譯碼軟信息進(jìn)行硬判決，若 L(Qn)＜0，則n=1，否則n=0，n=1，2，…，N。若 HT=0，則譯碼成功，程序結(jié)束，否則轉(zhuǎn)到步驟(1)。

2 N-CMS算法的原理與實(shí)現(xiàn)步驟

基于文獻(xiàn)[4]的思想，設(shè)變量節(jié)點(diǎn)n更新前與更新后L(Qnm)的絕對值分別為 βnm和，γ1和 γ2是集合 n∈N(m)所有βnm中最小的兩個值，不失一般性令 γ1≤γ2。當(dāng) βnm完成到的更新后，使得 n∈N(m)集合在 βnm更新前求得的γ1和γ2可能并不是當(dāng)前最小的兩個值，例如存在的情況，此時的兩個最小值應(yīng)為和 γ1。倘若不對γ1和γ2進(jìn)行更新，則會導(dǎo)致的值不準(zhǔn)確，使得性能和收斂速率都會受到影響。但若要采用min操作來更新γ1和γ2，則計(jì)算復(fù)雜度會較高。如在文獻(xiàn)[6]中，對于碼率1/2的規(guī)則 (N，J，2J)LDPC碼，N-SMS在每次迭代中操作需要次加法運(yùn)算，當(dāng)J較大時，簡化N-SMS算法的復(fù)雜度是很有必要的。

本文在更新 βnm的過程中，同時利用和 γ2三者間的關(guān)系來更新屬于校驗(yàn)式m的兩個最小值γ1和 γ2。若小于 γ1，則在集合 n∈N(m)中最小值為，次最小值才為 γ1；若大于 γ1但小于 γ2，則在集合 n∈ N(m)中最小值仍為γ1，次小值 γ2需更新為；若大于γ2，則集合中最小的兩個值仍為γ1和γ2，不發(fā)生變化。以上的競爭機(jī)制可簡單概括為：若 β′nm＜γ1，則令 γ1=，γ2=γ1；若，則 γ1不變，；若γ2，則γ1和γ2都保持不變。N-CMS算法可描述為：

步驟1：判斷是否達(dá)到設(shè)定的最大迭代次數(shù)MT，若是則程序結(jié)束；否則按照 n=1，2，…，N的順序更新變量節(jié)點(diǎn)對校驗(yàn)節(jié)點(diǎn)的消息，執(zhí)行步驟(2)。

步驟2：對特定的n和每一個m∈M(n)按照式(5)計(jì)算L(Rmn)，此處的 min操作由γ1和 γ2取代。

步驟 3：對特定的 n和每一個 m∈M(n)依據(jù)式(6)、式(7)算出 L(Qn)和 L(Qnm)，由更新后的 L(Qnm)得出后，再根據(jù)競爭模式更新γ1和γ2。

步驟4：若n≤N，對譯碼軟信息進(jìn)行硬判決，若L(Qn)＜0，則n=1，反之n=0，n=n+1轉(zhuǎn)到步驟(2)。否則執(zhí)行步驟(5)。

3 復(fù)雜度及存儲量分析

表1 三種算法

4 算法仿真與測試

仿真中選取碼率1/2的(512，3，6)規(guī)則LDPC碼通過AWGN信道，譯碼分別采用N-PMS算法和N-CMS算法。為了使得信息得到充分的傳播，在仿真中令最大迭代譯碼次數(shù)MT=30。下面從歸一化權(quán)重因子的選取、誤比特率(Bit Error Rate，BER)、誤幀率(Frame Error Rate，F(xiàn)ER)、收斂速率和譯碼平均譯碼復(fù)雜度幾個方面來進(jìn)行對比分析。

為簡化討論，此處利用蒙特卡羅方法來獲得N-PMS和N-CMS的歸一化權(quán)重因子。如圖1和圖2所示，兩者都在λ=0.8時表現(xiàn)出最佳的性能，因此將λ=0.8作為最佳歸一化權(quán)重因子用于之后的仿真。

圖1 采用N-PMS算法在1 dB、2 dB和3 dB時，誤比特率與歸一化權(quán)重因子的關(guān)系

圖2 采用N-CMS算法在1 dB、2 dB和3 dB時，誤比特率與歸一化權(quán)重因子的關(guān)系

圖3 和圖4分別對比了PMS、N-PMS、CMS和N-CMS系統(tǒng)的BER和FER性能，按照是否引入歸一化權(quán)重因子分為兩組，即PMS和N-PMS，CMS和N-CMS。可以看出，不論哪一組歸一化算法均比非歸一化的算法性能要好得多，約有0.5～0.7 dB的性能差距。此外，即使都是歸一化算法，N-CMS較N-PMS也有0.1～0.2 dB的性能提升。

圖3 誤比特率比較

圖4 誤幀率比較

由圖5可知，CMS所需的平均迭代譯碼次數(shù)要少于PMS，類似的，N-CMS所需的平均迭代譯碼次數(shù)也少于N-PMS。從圖6可以得出，N-CMS在中低信噪比時譯碼復(fù)雜度較N-SMS有明顯的優(yōu)勢，但比N-PMS略高；在高信噪比時N-CMS與N-PMS復(fù)雜度接近，而且兩者都比N-SMS的復(fù)雜度低。

圖5 所需平均迭代譯碼次數(shù)

5 結(jié)論

本文提出了一種按照變量節(jié)點(diǎn)更新的歸一化串行最小和算法——N-CMS。N-CMS算法采用競爭機(jī)制實(shí)時更新變量節(jié)點(diǎn)對校驗(yàn)節(jié)點(diǎn)消息集合中最小的兩個值，它在保持與N-SMS算法相同性能的前提下大幅降低了運(yùn)算量。相對N-PMS算法而言，N-CMS算法不論是在收斂速度，還是在譯碼性能上都更有優(yōu)勢，其復(fù)雜度只有略微增加。最為重要的是N-CMS算法具有極低的存儲需求，尤其是在電力線載波通信所需的譯碼模塊的設(shè)計(jì)中，表現(xiàn)出巨大的實(shí)用價(jià)值。

圖6 N-PMS、N-SMS和N-CMS所需平均復(fù)雜度比較

[1]DEVELI I，KABALCI Y.Analysis of the use of different decoding schemes in LDPC coded OFDM systems over indoor PLC channel[J].Electronics&Electrical Engineering，2014，20(1)：76-80.

[2]BERROU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon limit error-correcting coding：turbo codes[C].In ICC93，1993(5)：1064-1070.

[3]MACKAY D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Trans.Inform.Theory，1999 (45)：399-431.

[4]FOSSORIER M P C，MIHALJEVIC M，IMAI H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation[J].IEEE Trans.Commun，1999(47)：673-680.

[5]CHEN J，F(xiàn)OSSORIER M P C.Decoding low-density parity check codes with normalized APP-based algorithm[C].Proc. IEEE Global Communications Conference，2001，9(1)：1026-1030.

[6]劉原華，王新梅，胡樹楷，等.一種改進(jìn)的卷積LDPC碼置信傳播譯碼算法[J].西安電子科技大學(xué)學(xué)報(bào)，2009，36 (3)：424-428.

[7]楊帆，羅振東，田寶玉.改進(jìn)的LDPC串行譯碼[J].北京郵電大學(xué)學(xué)報(bào)，2008，31(4)：130-134.

A serial min-sum algorithm for LDPC codes based on competitive scheme

Liang Xi1，Long Xianglin2，Zhang Enyou2，Yang Fan1
（1.University of Electronic Science and Technology of China,Chengdu 611731，China；2.Ningbo Jianan Electronics Co.，Ltd，Ningbo 315000，China）

Considering the designing costs and the power consumption issues in the decoding module,a serial min-sum algorithm for LDPC codes is proposed.The new algorithm is a type of variable-to-check message updating algorithm using normalized factor, it updates the minimum value among the variable-to-check messages based on a competitive scheme.Compared to the conventional normalized serial min-sum algorithm,it reduces the decoding complexity significantly without any performance loss.On the other hand,compared with the normalized parallel min-sum algorithm,the new approach not only reduces amount of memory,but also has some performance improvement with a little complexity increased.

power line carrier communication；serial min-sum algorithm；low density parity check codes；iterative decoding；normalized factor

TN911.22

A

10.16157/j.issn.0258-7998.2015.11.025

梁溪，龍翔林，章恩友，等.基于競爭機(jī)制的LDPC碼串行最小和算法[J].電子技術(shù)應(yīng)用，2015，41(11)：89-92，100.

英文引用格式：Liang Xi，Long Xianglin，Zhang Enyou，et al.A serial min-sum algorithm for LDPC codes based on competitive scheme[J].Application of Electronic Technique，2015，41(11)：89-92，100.

2015-07-10)

梁溪（1992-），男，碩士研究生，主要研究方向：通信與信息系統(tǒng)。

國家自然科學(xué)基金（61301272）；四川省應(yīng)用基礎(chǔ)研究計(jì)劃（2014JY0037）；中央高校基金（ZYGX2013J008）

龍翔林（1971-），男，碩士，總工程師，主要研究方向：用電信息采集系統(tǒng)及電力線載波通信。