一種改進的多元LDPC碼譯碼算法

張福星，許生旺

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

?

一種改進的多元LDPC碼譯碼算法

張福星，許生旺

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

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

多元LDPC碼；FFT-BP譯碼算法；算法改進

0 引言

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

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

1 混合譯碼

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

圖1 軟判決譯碼信息提取

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

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

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

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

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

2 改進思路及算法

2.1 改進思路

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

Qmn=Qmn*μ，

(4)

(5)

2.2 改進后的譯碼算法

改進后的FFT-BP譯碼算法過程為：

(1)初始化

(6)

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

(7)

(8)

(9)

(4)判決碼元符號

(10)

(5)更新可靠度信息

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

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

(7)更新消息向量

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

2.3 復雜度分析

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

乘法：2MN；

加法：2MN-M-N。

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

乘法：Ndvq；

加法：Ndv。

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

3 仿真分析

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

圖3 改進FFT-BP譯碼算法性能

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

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

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

4 結(jié)束語

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

[1] 劉 波,李旭東.LDPC碼在深空探測中的應用[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].無線通信技術,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)星導航中的應用[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]吳曉麗,孟 濤,李 云,等.一種改進的多進制LDPC碼的譯碼算法[J].空軍工程大學學報：自然科學版,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

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

2016-07-15

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

TN911.2

A

1003-3114(2016)06-56-3