范 芳，馮雪林

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶400065；2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所 移動(dòng)計(jì)算與新型終端北京市重點(diǎn)實(shí)驗(yàn)室，北京100190)

0 引言

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

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

現(xiàn)有的簡(jiǎn)化算法，如最小和算法、歸一化最小和算法以及其他改進(jìn)的最小和算法都只是通過(guò)乘以補(bǔ)償系數(shù)來(lái)提高譯碼性能的目的，沒(méi)有考慮到可以通過(guò)與上一次變量節(jié)點(diǎn)信息結(jié)果的加權(quán)平均來(lái)提高譯碼可靠性，達(dá)到改善譯碼性能的目的。

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

1 已知的LDPC譯碼算法

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

此時(shí)，m=6，n=6，對(duì)應(yīng)的Tanner圖如圖1所示。

圖1 校驗(yàn)矩陣的Tanner圖

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

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

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

1.1 LLR-BP譯碼算法

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

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

① 初始化

當(dāng)信息序列經(jīng)過(guò)高斯信道后，輸出的先驗(yàn)似然比概率信息可表示為：

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

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

④ 譯碼判決：根據(jù)收集的所有變量節(jié)點(diǎn)的后驗(yàn)概率信息進(jìn)行譯碼判決，變量節(jié)點(diǎn)后驗(yàn)概率信息為

⑤ 停止譯碼

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

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

1.2 最小和算法

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

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

由簡(jiǎn)化公式可以看出，最小和算法沒(méi)有了雙曲正切函數(shù)的繁瑣計(jì)算，用簡(jiǎn)單的比較和加法運(yùn)算代替了原有復(fù)雜的指數(shù)和對(duì)數(shù)運(yùn)算，很大程度上降低了運(yùn)算量，在工程實(shí)現(xiàn)方面得到了大量應(yīng)用[15]。

1.3 歸一化最小和算法

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

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

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

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

改進(jìn)算法的具體譯碼步驟如下：

① 初始化

② 校驗(yàn)節(jié)點(diǎn)信息處理

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

④ 譯碼判決

⑤ 停止譯碼

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

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

3 復(fù)雜度與誤碼性能分析

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

3.1 復(fù)雜度分析

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

3.2 誤碼性能分析

不同β與最小和算法的誤碼性能對(duì)比如圖2所示，通過(guò)仿真對(duì)比得出，當(dāng)加權(quán)系數(shù)β為0.9時(shí)，改進(jìn)最小和算法能獲得較好的譯碼性能。

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

選取改進(jìn)最小和算法的加權(quán)系數(shù)β為0.9，將改進(jìn)最小和算法與LLR-BP算法、最小和算法、歸一化最小和算法的誤碼率性能進(jìn)行仿真對(duì)比，結(jié)果如圖3所示。

圖3 改進(jìn)算法與其他算法誤碼性能對(duì)比

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

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

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)比總結(jié)幾種經(jīng)典的LDPC譯碼算法，在最小和算法的基礎(chǔ)上，對(duì)變量節(jié)點(diǎn)更新進(jìn)行改進(jìn)，提出一種改進(jìn)的最小和算法。該算法的計(jì)算復(fù)雜度與最小和相比只增加了小部分，糾錯(cuò)性能得到了約0.5dB的提高，并且其復(fù)雜度低于傳統(tǒng)的LLR-BP譯碼算法，隨著信噪比的提高其性能接近LLR-BP算法，因此該算法在工程應(yīng)用上具有很大的發(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] 吳湛擊，王文博.現(xiàn)代糾錯(cuò)編碼與調(diào)制理論及應(yīng)用[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] 王新梅.糾錯(cuò)碼與差錯(cuò)控制[M].北京：人民郵電出版社，1989.

[10] 莊夢(mèng)溪.高速LDPC碼編譯碼器的研究與實(shí)現(xiàn)[D].西安電子科技大學(xué)，2012.

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

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

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

[14] 張福星，許生旺.一種改進(jìn)的多元LDPC碼譯碼算法[J].無(wú)線電通信技術(shù)，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] 孫斌，王鋼，楊文超，等.一種改進(jìn)型LLRBP算法的LDPC譯碼研究[J].無(wú)線電工程，2015，45(3)：4-6.

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