0 引言

　　隨著信息化的發(fā)展,，人們對(duì)低密度奇偶校驗(yàn)(Low Density Parity Check,，LDPC)碼有了重新的認(rèn)識(shí)。LDPC碼作為高效的信道糾錯(cuò)編碼,，具有較低的譯碼復(fù)雜度,，系統(tǒng)吞吐量較大，已在電力線載波（Power Line Carrier,，PLC）通信,、第三代和第四代無線移動(dòng)通信等方面得到了廣泛應(yīng)用[1]。相對(duì)于turbo譯碼算法[2],，采用LDPC編碼和置信傳播(Belief Propagation,，BP)譯碼算法更受人們的青睞[3]。但是BP算法存在對(duì)硬件存儲(chǔ)量的需求較大以及對(duì)信道情況較為敏感等問題,。人們更趨向于魯棒性更好和復(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ā)模塊通常采用具有低存儲(chǔ)量和低復(fù)雜度的編,、譯碼算法。N-SMS算法雖然在存儲(chǔ)上較N-PMS算法有一定減少,，但N-SMS算法由于每次迭代都采用min操作來更新最小值,，復(fù)雜度相對(duì)較高,。

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

1 N-PMS算法簡(jiǎn)介

　　為了簡(jiǎn)化敘述，該文沿用文獻(xiàn)[7]中的部分符號(hào)定義,。設(shè)m和n分別表示校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn),，H為L(zhǎng)DPC碼對(duì)應(yīng)的校驗(yàn)矩陣，當(dāng)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)有邊相連接時(shí),，則hmn=1,，它是H中的第m行和n列的元素。N(m)={n|hmn=1}表示參與校驗(yàn)方程m的變量節(jié)點(diǎn)的集合,，N(m)\n為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個(gè)校驗(yàn)方程外,，其他與n相關(guān)的校驗(yàn)方程都滿足的條件下，xn=x的概率,；是由校驗(yàn)節(jié)點(diǎn)m傳遞給變量節(jié)點(diǎn)n的軟信息,，表示在xn=x，且參加第m個(gè)校驗(yàn)方程的除n外的其他變量節(jié)點(diǎn)的概率Qmn已知的條件下,，該校驗(yàn)方程成立的概率,，其中∈N(m)\n。

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

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

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

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

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

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

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

　　L(Qnm)=L(Qn)-L(Rmn)(7)

　　步驟4：對(duì)譯碼軟信息進(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)步驟

　　在N-PMS中，校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)是分別并行更新的,。文獻(xiàn)[4]指出,，對(duì)于H矩陣中的第m個(gè)校驗(yàn)式,，N-PMS在計(jì)算所有n∈N(m)集合中的最小值時(shí)，可以通過找出該集合中最小的兩個(gè)量1和2來簡(jiǎn)化運(yùn)算,。

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

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

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

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

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

　　步驟5：若HT=0，則譯碼成功,，程序結(jié)束,。否則轉(zhuǎn)到步驟(1)。

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

　　另一方面,，N-PMS需要較大的存儲(chǔ)，根據(jù)式(5),，對(duì)于每個(gè)校驗(yàn)式m,，需要2個(gè)單元來存儲(chǔ)2個(gè)最小值，所以對(duì)于N/2個(gè)校驗(yàn)式,，L(Rmn)總共需N個(gè)存儲(chǔ)單元,；根據(jù)式(6)、式(7),，L(Qn),、L(Qnm)分別需N和NJ個(gè)存儲(chǔ)單元。再來看N-SMS算法,，由于變量節(jié)點(diǎn)串行更新,，L(Rmn)只需2J個(gè)存儲(chǔ)，但N-SMS算法每次迭代都要進(jìn)行min操作,，對(duì)于每個(gè)校驗(yàn)式m,，L(Qnm)仍需2J個(gè)nm來計(jì)算，從而L(Qn),、L(Qnm)分別仍需N和NJ個(gè)存儲(chǔ)單元,。在N-CMS算法中，L(Rmn)也只需2J個(gè)存儲(chǔ),，由于N-CMS算法采用了競(jìng)爭(zhēng)機(jī)制,，每計(jì)算出一個(gè)，便用于1和2的更新,。所以對(duì)于每個(gè)校驗(yàn)式m,，只需分配1個(gè)臨時(shí)單元用于存儲(chǔ)，從而L(Qnm)共需N/2個(gè)單元,，L(Qn)需N個(gè)存儲(chǔ)單元,。綜上所述，N-PMS,、N-SMS和N-CMS所需存儲(chǔ)總量分別為2N+NJ,、N+(N+2)J和3N/2+2J,。顯而易見，相對(duì)于N-PMS算法和N-SMS算法,，N-CMS算法具有極低的存儲(chǔ)需求,，這對(duì)于設(shè)計(jì)成本低廉的譯碼模塊具有重要意義。

4 算法仿真與測(cè)試

　　仿真中選取碼率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ù)雜度幾個(gè)方面來進(jìn)行對(duì)比分析。

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

　　圖3和圖4分別對(duì)比了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的性能提升。

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

5 結(jié)論

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

　　參考文獻(xiàn)

　　[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 Shannonlimit 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 matrice[J].IEEETrans.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.