0 引言

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

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

1 N-PMS算法簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　步驟2：對特定的n和每一個m∈M(n)按照式(5)計算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，對譯碼軟信息進行硬判決,，若L(Qn)<0,，則n=1，反之n=0,，n=n+1轉到步驟(2),。否則執(zhí)行步驟(5)。

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

　　3 復雜度及存儲量分析

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

4 算法仿真與測試

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

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

　　圖3和圖4分別對比了PMS、N-PMS,、CMS和N-CMS系統(tǒng)的BER和FER性能,，按照是否引入歸一化權重因子分為兩組，即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在中低信噪比時譯碼復雜度較N-SMS有明顯的優(yōu)勢，但比N-PMS略高,；在高信噪比時N-CMS與N-PMS復雜度接近,，而且兩者都比N-SMS的復雜度低。

5 結論

　　本文提出了一種按照變量節(jié)點更新的歸一化串行最小和算法——N-CMS,。N-CMS算法采用競爭機制實時更新變量節(jié)點對校驗節(jié)點消息集合中最小的兩個值,，它在保持與N-SMS算法相同性能的前提下大幅降低了運算量。相對N-PMS算法而言,，N-CMS算法不論是在收斂速度,，還是在譯碼性能上都更有優(yōu)勢，其復雜度只有略微增加,。最為重要的是N-CMS算法具有極低的存儲需求,，尤其是在電力線載波通信所需的譯碼模塊的設計中，表現(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] 劉原華,，王新梅，胡樹楷,，等.一種改進的卷積LDPC碼置信傳播譯碼算法[J].西安電子科技大學學報,，2009， 36(3)：424-428.

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