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經(jīng)過BPSK調制后的信號，g是均值為0、方差為的高斯噪聲。設s經(jīng)過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.