基于變量節(jié)點更新改進的最小和算法

范 芳，馮雪林

(1.重慶郵電大學 通信與信息工程學院，重慶400065；2.中國科學院計算技術研究所 移動計算與新型終端北京市重點實驗室，北京100190)

0 引言

LDPC碼是一種糾錯能力很強的線性分組碼，在20世紀60年代由Gallager[1]博士提出。 20世紀80年代 Tanner推廣了LDPC碼并給出LDPC碼的Tanner圖表示[2]，奠定了消息傳遞算法的基礎。20世紀90年代Mackay等人[3]在Gallager的消息傳遞算法基礎上提出了譯碼性能接近香農極限的BP算法，但其復雜度很大，不易于在硬件上實現。

為了滿足在工程方面的應用，研究者們提出了一些簡化的BP譯碼算法。其中，LLR-BP[4]譯碼算法是BP算法在對數域的簡化算法。該算法沒有損失BP算法的譯碼性能，但在迭代運算時仍需要大量的加法運算以及雙曲正切函數的查表計算，復雜度較高，不易于應用實現。最小和算法[5]是一種目前應用最多的簡化LLR-BP算法，用簡單的比較和加法運算代替了原有復雜的指數和對數運算，很大程度上降低了計算復雜度，在硬件實現方面易于應用，但譯碼性能損失較多。為了彌補最小和算法帶來的性能損失，在參考文獻[6]中提出了一種歸一化最小和算法，該算法是通過在最小和算法的校驗節(jié)點更新基礎上乘以一個補償系數，利用線性歸化的思想來修正幅度，提高譯碼性能。參考文獻[7]中提出一種將最小和算法的變量節(jié)點與校驗節(jié)點更新結果均乘以一個補償系數的算法。參考文獻[8]研究了一種自適應確定補償系數的算法。

現有的簡化算法，如最小和算法、歸一化最小和算法以及其他改進的最小和算法都只是通過乘以補償系數來提高譯碼性能的目的，沒有考慮到可以通過與上一次變量節(jié)點信息結果的加權平均來提高譯碼可靠性，達到改善譯碼性能的目的。

本文在研究最小和算法的基礎上，提出一種改進的最小和算法。該算法通過引入加權系數對前后2次變量節(jié)點外部信息值進行加權平均，修改了最小和算法的變量節(jié)點信息更新公式，保證了變量節(jié)點外部信息的可靠性，改善了譯碼性能。

1 已知的LDPC譯碼算法

LDPC碼是一種由其校驗矩陣H定義的具有特殊性的線性分組碼[9]。特殊性體現在校驗矩陣H中大部分都為0。在二元域上，LDPC碼的校驗矩陣H是由元素“0”和“1”構成的，假設有m行n列，則H中0的數量遠遠大于1的數量。LDPC碼可以由校驗節(jié)點和變量節(jié)點組成的Tanner圖表示[10]。校驗矩陣H的每一行為一個校驗節(jié)點c，每一列為一個變量節(jié)點v。為了更好地說明二者之間的關系，假設

此時，m=6，n=6，對應的Tanner圖如圖1所示。

圖1 校驗矩陣的Tanner圖

圖中,c1表示矩陣H的第一個校驗節(jié)點，也是矩陣H的第一行，與該校驗節(jié)點相連的v3和v4變量節(jié)點，表示矩陣H的第3列和第4列。從矩陣H中可以看出，第1行第3列和第1行第4列剛好是該行非零元素1的位置，也就是說，在Tanner圖中校驗節(jié)點和變量節(jié)點的連線對應矩陣H中非零元素1的位置。

為了方便敘述，本文將與校驗節(jié)點c相連的所有變量節(jié)點v的集合用M(v)表示，用N(c)表示與變量節(jié)點v相連的所有校驗節(jié)點c的集合[11]。

LDPC一般采用基于軟判決信息的迭代方法譯碼。在AWGN信道情況下，假設x=(x1，x2，…，xn-m)為隨機產生的信息序列，LDPC編碼后的信息序列為y=(y1，y2，…，yn)，用BPSK方式調制后，經過信道加擾后，在接收端接收到的軟判決序列為z=(z1，z2，…，zn)。由信道特性和接收到的軟判決序列可以得到各變量節(jié)點的先驗概率信息，通過變量節(jié)點和校驗節(jié)點之間信息的傳遞更新，最終可以得到各變量節(jié)點的后驗概率信息[12]。通過對變量節(jié)點的后驗概率信息判決進行譯碼。下面介紹的幾種常用譯碼算法都是基于對變量節(jié)點后驗概率信息判決的譯碼算法。

1.1 LLR-BP譯碼算法

LDPC碼經典的軟判決譯碼算法是LLR-BP譯碼算法，它的譯碼效果與接近香農極限的BP算法一樣，但有很高的復雜度，后面介紹的幾種譯碼算法都是在LLR-BP算法的基礎上進行簡化和改進得到的[13]。

對于一個二元加性高斯信道，其信道輸出服從高斯分布N(a，σ2)且輸入信息序列服從先驗等概，其中a是均值，σ2是方差。均值大小與調制方式有關，在二進制相移鍵控(BPSK)調制下，a為±1。對于一個接收隨機變量zi，其中i=1，2，…，n，譯碼過程如下：

① 初始化

當信息序列經過高斯信道后，輸出的先驗似然比概率信息可表示為：

② 校驗節(jié)點信息處理：校驗節(jié)點傳遞給與其相連的變量節(jié)點的信息為

③ 變量節(jié)點信息處理：變量節(jié)點傳遞給與其相連的校驗節(jié)點的信息為

④ 譯碼判決：根據收集的所有變量節(jié)點的后驗概率信息進行譯碼判決，變量節(jié)點后驗概率信息為

⑤ 停止譯碼

令k=k+1，重復以上步驟②～④，直到vHT=0或者達到規(guī)定的最大迭代次數時，譯碼停止，得到譯碼結果v。

從LLR-BP譯碼算法的校驗節(jié)點信息處理公式可知，需要用到函數tanh，這個函數存在復雜的指數和對數運算，不適用于硬件實現方面，因此在此基礎上進行了簡化改進，提出了幾種簡化算法，雖然譯碼性能有損失，但大大降低了復雜度，適用于硬件實現方面[14]。

1.2 最小和算法

最小和算法只是在LLR-BP算法的步驟②進行了近似簡化處理，得到如下改變后的校驗節(jié)點信息處理公式：

其他步驟都與LLR-BP算法相同。

由簡化公式可以看出，最小和算法沒有了雙曲正切函數的繁瑣計算，用簡單的比較和加法運算代替了原有復雜的指數和對數運算，很大程度上降低了運算量，在工程實現方面得到了大量應用[15]。

1.3 歸一化最小和算法

歸一化最小和算法是在最小和算法的校驗節(jié)點更新處乘以一個系數?，來彌補雙曲正切函數的近似帶來的譯碼性能損失[16]。歸一化最小和算法只在最小和算法校驗節(jié)點信息處理公式處做了變化，其余譯碼步驟均相同。歸一化最小和算法的校驗節(jié)點信息處理公式如下：

可知系數?的選取影響歸一化最小和算法的譯碼性能。系數?的取值，要通過仿真來確定，通常選取合適的值為0.8～0.9[17]。歸一化最小和算法彌補了最小和算法的一部分譯碼性能損失，但相比于LLR-BP算法，還存在性能損失。

2 基于變量節(jié)點更新改進的最小和算法

由現有的改進最小和算法可知，它們只是通過用補償系數來修正校驗節(jié)點外部信息的值，沒有考慮到變量節(jié)點前后2次信息更新時存在的誤差，這種誤差會造成譯碼判決錯誤，譯碼可靠性降低[18]。根據最小和算法的譯碼特性，提出一種基于變量節(jié)點更新的改進最小和算法。該算法在計算變量節(jié)點更新時，通過引入加權系數β對最小和算法的變量節(jié)點的前后2次外部信息值進行加權平均，修正變量節(jié)點外部信息，改善譯碼性能。

改進算法的具體譯碼步驟如下：

① 初始化

② 校驗節(jié)點信息處理

③ 變量節(jié)點信息處理

④ 譯碼判決

⑤ 停止譯碼

令k=k+1，重復以上步驟②～④，直到vHT=0或者達到規(guī)定的最大迭代次數時，譯碼停止，得到譯碼結果v。

由以上譯碼步驟可知，該算法保留了最小和算法在LLR-BP算法基礎上，用簡單的比較和加法運算代替原有雙曲正切函數的繁瑣計算，復雜度與最小和算法接近，并且通過對變量節(jié)點更新時進行前后兩次外部信息值加權平均，保證譯碼的可靠性，與最小和算法相比，明顯地提高了譯碼性能。

3 復雜度與誤碼性能分析

本文研究改進最小和算法時，采用加性高斯白噪聲傳輸信道，BPSK調制方式，選用相同碼型為QC-LDPC(1152，576)碼，編碼方法統(tǒng)一采用基于近似下三角校驗矩陣的線性編碼方法，設定最大譯碼迭代次數為30，對改進最小和算法的誤碼率性能進行仿真對比分析，驗證改進最小和算法的有效性。

3.1 復雜度分析

基于變量節(jié)點更新改進的最小和算法在譯碼迭代時需要增加一個緩存器用來寄存上一次變量節(jié)點的外部信息。假設LDPC碼的矩陣H為R行C列，對于行重和列重都固定的規(guī)則LDPC碼，設行重為dc[19]。對比最小和算法，改進最小和算法只增加了一次加權求和運算，因此只增加了R×dc的運算量。對比LLR-BP算法，改進最小和算法增加的這部分運算量還是很少的，但是卻可以很好修正變量節(jié)點外部信息，保證譯碼的可靠性，提高了糾錯性能。

3.2 誤碼性能分析

不同β與最小和算法的誤碼性能對比如圖2所示，通過仿真對比得出，當加權系數β為0.9時，改進最小和算法能獲得較好的譯碼性能。

圖2 不同β與最小和算法的誤碼性能對比

選取改進最小和算法的加權系數β為0.9，將改進最小和算法與LLR-BP算法、最小和算法、歸一化最小和算法的誤碼率性能進行仿真對比，結果如圖3所示。

圖3 改進算法與其他算法誤碼性能對比

由上面的仿真對比結果可知，在信噪比較低時，LLR-BP算法的性能最優(yōu)，其次分別是改進最小和算法、歸一化最小和算法、最小和算法。但隨著信噪比的提高，改進最小和算法的誤碼率逐漸接近LLR-BP算法，當誤碼率為10-4時，相比最小和算法與歸一化最小和算法性能提升分別約為0.5dB和0.2dB。

綜上所述，改進最小和算法糾錯性能優(yōu)于已有的最小和算法和歸一化最小和算法，并且隨著信噪比的提高，其糾錯性能接近LLR-BP算法，并且計算復雜度低于LLR-BP算法，是一種有效且具有發(fā)展前景的譯碼算法。

4 結束語

本文通過對比總結幾種經典的LDPC譯碼算法，在最小和算法的基礎上，對變量節(jié)點更新進行改進，提出一種改進的最小和算法。該算法的計算復雜度與最小和相比只增加了小部分，糾錯性能得到了約0.5dB的提高，并且其復雜度低于傳統(tǒng)的LLR-BP譯碼算法，隨著信噪比的提高其性能接近LLR-BP算法，因此該算法在工程應用上具有很大的發(fā)展前景。

[1]GALLAGERG.Low-Density-Parity-CheckCodes[J].IRETransactionsonInformationTheory(S0096-1000)，1962，8(1)：21-28.

[2]TANNERRM.ARecursiveApproachtoLowComplexityCodes.IEEETransactionsonInformationTheory[J].1981，27(5)：533-547.

[3]MACKAYDJC，NEALRM.NearShannonLimitPerformanceofLow-DensityParity-CheckCodes[J].ElectronicsLetters，1996，32(18)：1645-1646.

[4]FOSSORIERMPC，MIHALJEVICM，IMAIH.ReducedComplexityIterativeDecodingFollowDensityParityCheckCodesBasedOnBeliefPropagation[J].IEEETransactiononCommunication，1999，47(5)：673-680.

[5] 吳湛擊，王文博.現代糾錯編碼與調制理論及應用[M].北京：人民郵電出版社，2008.

[6]HOCEVARD.AReducedComplexityDecoderArchitectureviaLayeredDecodingofLDPCCodes[C]∥IEEEWorkshoponSignalProcessingSystems(SIPS),IEEE，2004：107-112.

[7]ZHANGXM，TAIY.High-speedMulti-block-rowLayeredDecodingforQuasi-cyclicLDPCCodes[C]∥SignalandInformationProcessing(GlobalSIP),IEEE，2014：11-14.

[8]ZHANGT，KESHABKP.Joint(3：κ)-regularLDPCCodeandDecoder/EncoderDesign[J].IEEETransactionsonSignalProcessing，2004，52(4)：1065-1079.

[9] 王新梅.糾錯碼與差錯控制[M].北京：人民郵電出版社，1989.

[10] 莊夢溪.高速LDPC碼編譯碼器的研究與實現[D].西安電子科技大學，2012.

[11]FANGYi，BIGuoan，GUANYongliang.DesignandAnalysisofRoot-protographLDPCCodesforNon-ergodicBlock-fadingChannels[J].IEEETransactionsonWirelessCommunications，2015，14(2)：738-749.

[12] 王飛，羅益，王振華，等.LDPC碼在BPSK通信系統(tǒng)中的性能分析[J].無線電通信技術，2015，41(1)：13-16.

[13]Al-FUQAHAA，GUIZANIM，MOHAMMADIM，elat.InternetofThings：aSurveyonEnablingTechnologies，Protocols，andApplications[J].IEEECommunicationsSurveys&Tutorials，2015，17(4)：2347-2376.

[14] 張福星，許生旺.一種改進的多元LDPC碼譯碼算法[J].無線電通信技術，2016，42(6)：56-58，69.

[15]ALBAYRAKC，TURKK.BP-basedApproximationMethodsforRatelessCodes[C]∥SignalProcessingandCommunication

ApplicationConference，Turkey，2016：1897-1900.

[16]KUMARAYVAC，WAVEGEDARACB.ImprovedLDPCDecodingAlgorithmsBasedonMin-SumAlgorithm[C]∥MoratuwaEngineeringResearchConference，2016：108-113.

[17]MOHSENINT，BAASBM.ASplit-DecodingMessagePassingAlgorithmforLowDensityParityCheckDecoders[J].JournalofSignalProcessingSystems，2010，61(3)：329-345.

[18] 孫斌，王鋼，楊文超，等.一種改進型LLRBP算法的LDPC譯碼研究[J].無線電工程，2015，45(3)：4-6.

[19]MAHDIA，PALIOURASV.OntheEncodingComplexityofQuasi-cyclicLDPCCodes[J].IEEETransactionsonSignalProcessing，2015，63(22)：6096-6108.