一種改進(jìn)的多元LDPC碼譯碼算法

張福星，許生旺

(北京跟蹤與通信技術(shù)研究所，北京 100094)

?

一種改進(jìn)的多元LDPC碼譯碼算法

張福星，許生旺

(北京跟蹤與通信技術(shù)研究所，北京 100094)

在多元LDPC碼的軟判決譯碼算法中，迭代過程中沒有使用判決結(jié)果和校驗(yàn)和中隱藏的一些信息，在判決結(jié)果中隱藏著穩(wěn)定性信息，校驗(yàn)和中隱藏著變量節(jié)點(diǎn)的可靠度信息。從混合譯碼算法思路出發(fā)，借鑒硬判決譯碼算法中統(tǒng)計(jì)校驗(yàn)和的做法和聯(lián)合迭代檢測譯碼算法中的反饋調(diào)整思想，對FFT-BP譯碼算法進(jìn)行了改進(jìn)。改進(jìn)算法利用迭代過程中的可靠性和穩(wěn)定度信息，對由變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的消息向量進(jìn)行調(diào)整以使其提供更多正確信息。仿真結(jié)果表明，改進(jìn)的譯碼算法在沒有增加復(fù)雜度的前提下，提升了FFT-BP譯碼算法的性能，在不同參數(shù)設(shè)置下，性能改進(jìn)在0.2 dB左右。

多元LDPC碼；FFT-BP譯碼算法；算法改進(jìn)

0 引言

Gallager在1963年提出了二元LDPC碼概念[1]，Davey和MacKay于1998年引出了多元域上的LDPC碼[2]。研究結(jié)果表明[3]，在突發(fā)噪聲信道中，多元LDPC碼可以獲得更好的性能，當(dāng)采用中短碼長時，多元LDPC碼的性能，特別是抗突發(fā)誤碼能力要明顯優(yōu)于二元LDPC碼[4]。但是，多元LDPC碼的譯碼復(fù)雜度隨著多元域階數(shù)的增大而急劇增長[5]，限制了其實(shí)際應(yīng)用。多元LDPC碼的推廣應(yīng)用需要尋求復(fù)雜度低的譯碼算法。

多元LDPC碼譯碼算法主要可分為軟判決譯碼算法和硬判決譯碼算法。軟判決譯碼算法主要有BP、FFT-BP[6-7]和EMS[8]算法等，這些算法均是通過消息向量的迭代進(jìn)行譯碼的，其普遍特點(diǎn)是復(fù)雜度高，但性能良好。硬判決譯碼算法由二元LDPC碼的大數(shù)邏輯譯碼[9]和比特翻轉(zhuǎn)譯碼[10]推廣而來，這些算法譯碼復(fù)雜度低，但性能有損失。

1 混合譯碼

在軟判決譯碼算法中，信道接收序列只被檢測器用于一次性地提取軟譯碼信息，如圖1所示，其中X為發(fā)送序列，Y為接收序列，SISO為軟輸入軟輸出檢測器，U為譯碼輸出的結(jié)果。因?yàn)镾ISO檢測器生成的概率或者似然比度量，能夠包含接收序列中的絕大部分信息。在軟譯碼判決算法中，只利用SISO檢測器提取出的信息進(jìn)行迭代譯碼。

圖1 軟判決譯碼信息提取

軟判決譯碼算法忽略了兩部分可利用的信息。一是信號的接收序列本身包含的信息，在檢測器中并不能一次提取完畢；二是迭代過程中判決結(jié)果也包含著變量節(jié)點(diǎn)可靠性和穩(wěn)定性信息，這一部分信息在迭代中并沒有得到利用。

對接收序列只利用一次的問題，在文獻(xiàn)[11]中，提出了一種新的對接收序列的處理模式，如圖2所示。該處理模式源于硬判決算法，檢測器基于最大似然準(zhǔn)則對接收序列進(jìn)行硬判決得到估計(jì)序列，不產(chǎn)生任何軟信息。估計(jì)序列在多元LDPC碼的硬譯碼器中經(jīng)由碼約束關(guān)系和消息傳遞原理得到糾錯，同時根據(jù)大數(shù)邏輯規(guī)則產(chǎn)生可靠度向量。譯碼器將糾錯完的序列和可靠度向量反饋給檢測器，檢測器利用獲得的反饋信息對軟接收序列進(jìn)行修正。修正將受到噪聲污染而偏離原始發(fā)送信號的接收信號逐漸移動到正確的發(fā)送星座點(diǎn)上。這種處理模式對接收序列的利用并不僅僅是單次的信息提取，而且是基于判決結(jié)果的反饋式的多次修正和信息提取。

圖2 一種新的接收序列處理模式

這種新的處理模式將軟判決譯碼算法中的迭代過程引入到硬判決譯碼算法中，并利用譯碼獲得的信息對譯碼初始狀態(tài)進(jìn)行調(diào)整，是一種混合式的譯碼算法。

對于軟判決譯碼過程中迭代出的結(jié)果包含信息未充分利用問題，也可以從混合譯碼的角度來進(jìn)行思考。在硬判決譯碼算法中，如大數(shù)邏輯譯碼算法中，常常通過對判決結(jié)果的統(tǒng)計(jì)分析，來對碼字的可能值進(jìn)行判斷和調(diào)整。可以將這種做法遷移到軟判決譯碼算法中，將迭代后的判決結(jié)果用于微調(diào)譯碼向量，使迭代結(jié)果朝更有利的方向發(fā)展。

2 改進(jìn)思路及算法

2.1 改進(jìn)思路

將硬判決譯碼算法中的統(tǒng)計(jì)反饋調(diào)整思想應(yīng)用到FFT-BP譯碼算法中，可以實(shí)現(xiàn)碼算法性能上的提升。在聯(lián)合迭代檢測譯碼算法中[12]，2個最重要的譯碼策略是：

① 利用校驗(yàn)和信息，采用大數(shù)邏輯進(jìn)行統(tǒng)計(jì)。大數(shù)邏輯是指在校驗(yàn)和提供的變量節(jié)點(diǎn)的外部信息中，對應(yīng)符號出現(xiàn)的次數(shù)越多，該變量節(jié)點(diǎn)實(shí)際為該符號的可能性就越大；

② 利用變量節(jié)點(diǎn)的統(tǒng)計(jì)信息，對檢測器接收端的信息序列進(jìn)行調(diào)整。具體為使用統(tǒng)計(jì)獲得的軟信息，采用反饋的方式，對接收序列進(jìn)行“去噪化”，使其慢慢移動到實(shí)際發(fā)送的星座點(diǎn)位置附近。

將這2個策略推廣到FFT-BP譯碼算法中：

① 統(tǒng)計(jì)迭代譯碼的判決結(jié)果和其校驗(yàn)和，獲得變量節(jié)點(diǎn)對應(yīng)的穩(wěn)定度信息和可靠度信息。在判決結(jié)果穩(wěn)定的節(jié)點(diǎn)中既有保持正確的，也有保持錯誤的，此時需要利用可靠度信息來加以區(qū)分；

② 用獲得的譯碼信息對迭代過程進(jìn)行反饋調(diào)整。可以在保證穩(wěn)定度和可靠度的前提下，對消息向量進(jìn)行微調(diào)。調(diào)整可靠度高的變量節(jié)點(diǎn)的概率值，使其在下一次譯碼迭代時提供更多的正確信息。

在具體實(shí)現(xiàn)中，消息向量的調(diào)整幅度應(yīng)與變量節(jié)點(diǎn)可靠度和穩(wěn)定度有關(guān)。隨著穩(wěn)定度的逐漸增加，消息向量更確定的保持在正確或錯誤的狀態(tài)。此時，引入可靠度對其正確性進(jìn)行判斷，可靠度高的節(jié)點(diǎn)，認(rèn)為其已經(jīng)穩(wěn)定在正確的判決值下。

可靠度可采用非法校驗(yàn)值進(jìn)行衡量[13]。若信道為加性高斯白噪聲信道，編碼碼字為c=[c1c2…cN]，接收端接收信息y=c+n，n為加性噪聲，則對y作如式(1)運(yùn)算。

(1)

I=[(H·y)T(modq)·H](modq)= (φT·H)(modq)。

(2)

非法校驗(yàn)值為零的變量節(jié)點(diǎn)可靠程度較高，非法校驗(yàn)值不為零的變量節(jié)點(diǎn)可靠程度低。

(3)

在得到變量節(jié)點(diǎn)的穩(wěn)定度和可靠度信息后，對可靠程度高和已穩(wěn)定的變量節(jié)點(diǎn)，可將其視作為已成功譯碼的變量節(jié)點(diǎn)，并進(jìn)行傾向性的調(diào)整。思路是將此變量節(jié)點(diǎn)譯碼結(jié)果對應(yīng)位置的概率值調(diào)整為最大值。在改進(jìn)的譯碼算法中，調(diào)整消息向量Qmn的方式如式(4)和式(5)進(jìn)行調(diào)整的公式為：

Qmn=Qmn*μ，

(4)

(5)

2.2 改進(jìn)后的譯碼算法

改進(jìn)后的FFT-BP譯碼算法過程為：

(1)初始化

(6)

同時用式(1)計(jì)算發(fā)送序列每個位置的非法校驗(yàn)，用式(2)初始化非法校驗(yàn)值I。對H(m,n)≠0的位置，譯碼消息向量初始化為：

(7)

(8)

(9)

(4)判決碼元符號

(10)

(5)更新可靠度信息

對當(dāng)前迭代判決出的結(jié)果，用式(2)重新計(jì)算此時的非法校驗(yàn)值信息。

(6)更新穩(wěn)定度信息

(7)更新消息向量

根據(jù)計(jì)算的非法校驗(yàn)值和統(tǒng)計(jì)的變量節(jié)點(diǎn)穩(wěn)定度信息，對相應(yīng)的消息向量進(jìn)行調(diào)整。如果k(n)>c，且此位置的非法校驗(yàn)值為0，即I=0，則依式(4)和式(5)更新消息向量。μ可根據(jù)實(shí)際情況進(jìn)行大小的調(diào)整。μ可取為較接近1的值以確保在迭代初期，譯碼正確與否并不明朗時，對消息向量的調(diào)整并不會引入額外的錯誤。

2.3 復(fù)雜度分析

若為q進(jìn)制的多元LDPC碼，校驗(yàn)矩陣大小為M×N，行重為dc，列重為dv，則單次迭代增加的計(jì)算量為：

乘法：2MN；

加法：2MN-M-N。

對消息向量進(jìn)行更新的步驟的計(jì)算量與當(dāng)前迭代中統(tǒng)計(jì)出的需要改進(jìn)的節(jié)點(diǎn)數(shù)有關(guān)，其可能的最大計(jì)算量為：

乘法：Ndvq；

加法：Ndv。

改進(jìn)后的譯碼算法在單次迭代中增加了計(jì)算可靠度和統(tǒng)計(jì)穩(wěn)定度的計(jì)算量，可能增加的最大乘法計(jì)算量為2MN+Ndvq，最大加法計(jì)算量為2MN-N-M+Ndv。雖然單次迭代的計(jì)算量有些許線性增加，但隨著對消息向量傳遞的調(diào)整改進(jìn)，譯碼所需的迭代次數(shù)會下降。

3 仿真分析

對提出的改進(jìn)算法進(jìn)行仿真驗(yàn)證，所用的仿真碼型為Mackay隨機(jī)構(gòu)造法構(gòu)造的碼長700的16元規(guī)則LDPC碼，其行重為6，列重為3，碼率為3/7。仿真使用的調(diào)制方式為16QAM，信道為AWGN信道，譯碼的最大迭代次數(shù)為20，仿真停止條件為錯誤100 bit，μ值為調(diào)整步長，c為穩(wěn)定度參數(shù)。本文仿真了多種μ值和c值下的性能情況，并進(jìn)行了綜合的比較，仿真結(jié)果如圖3所示。

圖3 改進(jìn)FFT-BP譯碼算法性能

從圖中可以看出，不同參數(shù)下的改進(jìn)譯碼算法與原始譯碼算法相比均有一定的性能提升，性能提升的幅度在0.1～0.2dB左右。

此外，仿真還統(tǒng)計(jì)了不同參數(shù)下譯碼算法的平均迭代次數(shù)，如表1所示。可以看出，不同參數(shù)下改進(jìn)算法的平均迭代次數(shù)與原始譯碼算法相比，并沒有顯著變化，即在只增加了計(jì)算可靠度和統(tǒng)計(jì)穩(wěn)定度的計(jì)算量的條件下，實(shí)現(xiàn)了性能的改進(jìn)。

表1 不同參數(shù)下的譯碼平均迭代次數(shù)

4 結(jié)束語

從混合譯碼思路出發(fā)，討論了將硬判決譯碼思想應(yīng)用到FFT-BP譯碼算法中的問題。從大數(shù)邏輯譯碼算法中的統(tǒng)計(jì)調(diào)整思想出發(fā)，將其應(yīng)用到FFT-BP譯碼算法中，對FFT-BP譯碼算法進(jìn)行了改進(jìn)。在統(tǒng)計(jì)的穩(wěn)定度信息和計(jì)算的可靠度信息的基礎(chǔ)上，迭代中改進(jìn)的譯碼算法對變量節(jié)點(diǎn)的消息向量進(jìn)行傾向性的調(diào)整，使消息向量能夠提供更多的正確信息。仿真結(jié)果表明，改進(jìn)的FFT-BP譯碼算法可以獲得更好的性能。

[1] 劉 波,李旭東.LDPC碼在深空探測中的應(yīng)用[J].無線電工程,2009，39(10):13-15.

[2]DaveyD,MacKayD.Low-densityParityCheckCodesoverGF(q)[J].IEEECommunicationsLetters,1998,2(6):165-167.

[3]ChenJ,WangL,LiY.PerformanceComparisonbetweenNon-binaryLDPCCodesandReed-SolomonCodesoverNoiseBurstsChannels[C] ∥ProcICCCAS2005.HongKongIEEEPress，2005:1-4.

[4] 李 丹,白寶明,孫 蓉.多元LDPC碼與二元LDPC碼的性能比較[J].無線通信技術(shù),2007,16(3)：1-6.

[5]WymeerschH,SteendamH,MoeneclaeyMA.ComputationalComplexityandQuantizationEffectsofDecodingAlgorithmsforNon-binaryLDPCCodes[C]∥IEEE.InternationalConferenceonSpeechandSignalProcessing.Montreal:IEEE,2004:669-672.

[6]SongH，CruzJR.Reduced-complexityDecodingofQ-aryLDPCCodesforMagneticRecording[J].IEEETransMagn,2003,39(3):1081-1087.

[7]BarnaultL,DeclercqD.FastDecodingAlgorithmforLDPCCodesOverGF(2q)[C]∥IEEE.ProceedingofIEEEITW2003.Paris:IEEE，2003:70-73.

[8]DeclercqD,FossorierM.DecodingAlgorithmsforNonBinaryLDPCCodesOverGF(q)[J].IEEETransactiononCommunication，2007,55(4):633-643.

[9]ZhaoD，MaX，ChenC,etal.AlowComplexityDecodingAlgorithmforMajority-logicDecodableNonbinaryLDPCCodes[J].IEEECommun.Lett,2010,14(11):1062-1064.

[10]盧建波.硬判決LDPC譯碼算法在衛(wèi)星導(dǎo)航中的應(yīng)用[J].無線電工程,2012,42(9):38-40.

[11]WangXP,BaiBM,MaX.ALow-complexityJointDetection-decodingAlgorithmforNonbinaryLDPC-codedModulationSystems[C]∥inProc.IEEEIntSympInformTheory,Jun,2010:794-798.

[12]ChenC,HuangQ,ChaoC,etal.TwoLow-complexityReliability-basedMessage-passingAlgorithmsforDecodingNon-binaryLDPCCodes[J].IEEETransactionsonCommunication,2009,57(12):3597-3606.

[13]吳曉麗,孟 濤,李 云,等.一種改進(jìn)的多進(jìn)制LDPC碼的譯碼算法[J].空軍工程大學(xué)學(xué)報：自然科學(xué)版,2010,11(4):73-77.

Modified FFT-BP Decoding Algorithm of Non-binary LDPC Codes

ZHANG Fu-xing,XU Sheng-wang

(Beijing Institute of Tracking and Telecommunications Technology,Beijing 100094,China)

Some information hidden in the decision results and sum of check equations is not used in soft-decision decoder for non-binary LDPC codes.However,stability and reliability information lies in the iteration results.In this paper,following the clue of hybrid decoding,the ideas in hard-decision decoding algorithm are used to modify the FFT-BP algorithm.In the new decoding algorithm,the stability and reliability information is used,and small adjustments are applied to the iteration results.Simulation results show that the modified FFT-BP algorithm can realize a performance improvement of about 0.2 dB.

non-binary LDPC code;FFT-BP decoding algorithm;modified algorithm

10.3969/j.issn.1003-3114.2016.06.14

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

2016-07-15

張福星(1992—)，男，碩士研究生，主要研究方向：信息與通信系統(tǒng)。許生旺(1963—)，男，研究員，主要研究方向：圖像通信。

TN911.2

A

1003-3114(2016)06-56-3