李萬臣, 王茂朝

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001

一種新的WIMAX標(biāo)準(zhǔn)LDPC碼的軟判決譯碼算法

李萬臣, 王茂朝

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001

WIMAX標(biāo)準(zhǔn)下的LDPC碼采用準(zhǔn)循環(huán)編碼方式，其譯碼多為和積（SP）譯碼算法。為了進(jìn)一步降低譯碼復(fù)雜度，通過大量仿真分析獲得最優(yōu)乘性因子的值，并推導(dǎo)出近似線性公式，提出了一種改進(jìn)型的歸一化最小和(MNMS)算法。在此基礎(chǔ)上，與校驗(yàn)節(jié)點(diǎn)匹配(CNM)算法相結(jié)合，進(jìn)一步提高譯碼性能。仿真結(jié)果表明，這種新算法相比歸一化最小和(NMS)算法、抵消最小和(OMS)算法、校驗(yàn)節(jié)點(diǎn)匹配(CNM)算法，其譯碼性能有明顯改善，性能幾乎接近和積（SP）譯碼算法。

WIMAX標(biāo)準(zhǔn)LDPC碼；改進(jìn)型歸一化最小和算法；和積算法；校驗(yàn)節(jié)點(diǎn)匹配算法

低密度奇偶校驗(yàn)碼（low density parity check codes, LDPC）[1]是由Gallager博士在1962年首次提出。隨著近代硬件水平的飛速發(fā)展，Mackay[2],Spielman[3]等人對(duì)LDPC碼進(jìn)行了深入研究。LDPC碼相比Turbo碼，具有抗突發(fā)差錯(cuò)特性，避免可能帶來的時(shí)延，性能更接近香農(nóng)限，已成為當(dāng)前研究的熱點(diǎn)[4]。全球微波互聯(lián)接入WIMAX[5](Worldwide Interoperability for Microwave Access)也將LDPC編碼用做其信道編碼的方案之一。

LDPC譯碼中的和積譯碼算法是一種軟判決譯碼算法，能獲得很好的性能，但是其譯碼復(fù)雜度高，不便于硬件實(shí)現(xiàn)。文獻(xiàn)[6]中提出了2種改進(jìn)型最小和算法，在校驗(yàn)節(jié)點(diǎn)更新時(shí)引入乘性因子α，提出歸一化最小和算法；引入加性因子β，提出抵消最小和算法。為了簡(jiǎn)化，校驗(yàn)因子取常數(shù)。但實(shí)際上校驗(yàn)因子的值隨著信噪比的不同應(yīng)該有所改變。文中通過大量仿真，分析推導(dǎo)出WIMAX標(biāo)準(zhǔn)LDPC碼隨信噪比變化乘性因子的計(jì)算公式，提出一種新的改進(jìn)型歸一化最小和算法，同時(shí)結(jié)合文獻(xiàn)[7]中提出的校驗(yàn)節(jié)點(diǎn)匹配算法提出一種新的軟判決譯碼算法。仿真結(jié)果表明，這種新算法的譯碼性能更加接近和積譯碼算法。

1 和積譯碼算法

和積譯碼算法是一種基于置信傳播的迭代軟判決譯碼算法，其步驟如下。

1）初始化。

假設(shè)信道傳遞給信息節(jié)點(diǎn)的初始概率消息為L(zhǎng)( pi)，(i=1,2,…,N)。計(jì)算L( pi)的值，對(duì)于每一個(gè)信息節(jié)點(diǎn)為i和與其相連的在集合C( i)中的校驗(yàn)節(jié)點(diǎn)j，設(shè)定變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的初始消息為L(zhǎng)(0)(q)=L( P)=2y/σ2

ijii

2）迭代處理。

a）校驗(yàn)節(jié)點(diǎn)的消息處理。

對(duì)所有校驗(yàn)節(jié)點(diǎn)j和與其相鄰的在集合R( j)中的信息節(jié)點(diǎn)i，第l次迭代時(shí)，通過信息節(jié)點(diǎn)判斷校驗(yàn)節(jié)點(diǎn)的消息

b）信息節(jié)點(diǎn)的消息處理。

對(duì)所有信息節(jié)點(diǎn)i和與其相鄰的在集合C( i)中的校驗(yàn)節(jié)點(diǎn)j，第l次迭代時(shí)，通過校驗(yàn)節(jié)點(diǎn)判斷信息節(jié)點(diǎn)的消息

c）譯碼判決。

對(duì)所有信息節(jié)點(diǎn)計(jì)算硬判決消息

若L(l)(q)＞0，則c?=0；否則c?=1。

i i i

3）停止。

如果達(dá)到最大迭代次數(shù)，或者對(duì)于矩陣H滿足Hc?T=0，運(yùn)算停止，否則繼續(xù)進(jìn)行迭代處理。

2 幾種降低復(fù)雜度的譯碼算法

2.1 最小和譯碼算法

由式（1）用近似最小值代替得出判決公式：

最小和譯碼算法[8]可以大大減少和積算法的復(fù)雜度和存儲(chǔ)容量，同時(shí)不需要對(duì)信道進(jìn)行估計(jì)，可以省略σ2的計(jì)算，進(jìn)一步降低運(yùn)算量。

2.2 歸一化最小和譯碼算法和抵消最小和算法

在最小和算法中計(jì)算校驗(yàn)信息L( rji)時(shí)，為表述方便，設(shè)式（1）和（2）中的L( rji)分別表示為L(zhǎng)1、L2,L2相比和積算法中的L1過高估計(jì)了其幅值。特別是當(dāng)βij之間相差很小時(shí)，這種誤差會(huì)更大。

基于以上考慮引入乘性因子α得到歸一化最小和譯碼算法

引入加性因子β得到抵消最小和算法

上述兩種算法對(duì)信息節(jié)點(diǎn)處理時(shí)，引入了乘性因子和加性因子，在稍增加復(fù)雜度的情況下，最小和算法獲得了更好的譯碼性能。

2.3 校驗(yàn)節(jié)點(diǎn)匹配譯碼算法

這種算法其復(fù)雜度在最小和算法的基礎(chǔ)上僅略微增加，就能獲得逼近和積譯碼算法的譯碼性能。

3 新的軟判決譯碼算法

3.1 改進(jìn)型歸一化最小和譯碼算法

在最小和算法中，乘性因子α取小于1的數(shù)來校正校驗(yàn)節(jié)點(diǎn)的信息。通常來講，乘性因子α一般取常數(shù)，所以歸一化處理的性能由乘性因子α的取值來決定。但是實(shí)際上為了獲得最優(yōu)的性能，乘性因子α的取值應(yīng)隨著迭代次數(shù)和信噪比的變化而改變，可以考慮在稍微增加復(fù)雜度的情況下分析不同信噪比下乘性因子α的取值。

在AWGN信道下，采用BPSK調(diào)制，根據(jù)WIMAX標(biāo)準(zhǔn)給出的基校驗(yàn)矩陣，構(gòu)造出碼率為1/2、碼長(zhǎng)為2 304的QC-LDPC碼。考慮誤碼率從10?1到10?6時(shí)，信噪比在0～4 dB，每隔0.5 dB取一個(gè)仿真節(jié)點(diǎn)，對(duì)應(yīng)的乘性因子α在0.5～0.95，每隔0.5個(gè)單位取值仿真。在不同的信噪比情況下，誤碼率隨α變化曲線如圖1、2所示。

圖1 0～2.0 dB誤碼率隨乘性因子α變化曲線

圖2 2.5～4.0 dB誤碼率隨乘性因子α變化曲線

通過觀察得到在不同信噪比下最優(yōu)的乘性因子α如表1所示。

表1 不同信噪比下最優(yōu)乘性因子α取值

可以看出最優(yōu)乘性因子α的值隨著信噪比的增加而相應(yīng)的增加，并且可近似看成每當(dāng)信噪比增加0.5 dB，乘性因子α也相應(yīng)增加0.05。當(dāng)信噪比小于0.0 dB，譯碼誤碼率在10?1數(shù)量級(jí)以下，不具備實(shí)際應(yīng)用價(jià)值。所以從信噪比為0.0 dB考慮，此時(shí)的最優(yōu)乘性因子α為0.55，具體算法實(shí)現(xiàn)如下。

定義ω=0.55，信噪比取樣點(diǎn)數(shù)為S，則每個(gè)取樣點(diǎn)中的增量:

當(dāng)i=1:S時(shí)，設(shè)改進(jìn)型歸一化最小和算法的乘性因子為η，則η近似線性計(jì)算公式為

信噪比取樣點(diǎn)數(shù)S的取值可在硬件實(shí)現(xiàn)復(fù)雜度和譯碼性能兩者之間權(quán)衡，得到相對(duì)理想的取值。

3.2 改進(jìn)型歸一化最小和算法與校驗(yàn)節(jié)點(diǎn)匹配結(jié)合的新算法

校驗(yàn)節(jié)點(diǎn)匹配算法是根據(jù)每個(gè)校驗(yàn)節(jié)點(diǎn)相連的信息節(jié)點(diǎn)的數(shù)目來更新校驗(yàn)節(jié)點(diǎn)信息。而WIMAX標(biāo)準(zhǔn)中的LDPC是一種非規(guī)則的LDPC，即行重不同；因此考慮在改進(jìn)型歸一化最小和算法的基礎(chǔ)上，在判決校驗(yàn)信息時(shí)，應(yīng)用校驗(yàn)節(jié)點(diǎn)匹配算法來進(jìn)一步優(yōu)化譯碼判決。其算法相比和積算法有如下不同：

在校驗(yàn)節(jié)點(diǎn)的消息處理中，對(duì)所有校驗(yàn)節(jié)點(diǎn)j和與其相鄰的在集合R( j)中的信息節(jié)點(diǎn)i，第l次迭代時(shí)，通過引入改進(jìn)型歸一化乘性因子η，當(dāng)i=1:S時(shí)，同時(shí)結(jié)合校驗(yàn)節(jié)點(diǎn)匹配算法，得到通過信息節(jié)點(diǎn)判斷校驗(yàn)節(jié)點(diǎn)的消息。

4 性能仿真與結(jié)果分析

圖3 新算法與檢驗(yàn)節(jié)點(diǎn)匹配算法性能比較

采用MATLAB與C語言相結(jié)合的仿真環(huán)境，在AWGN信道下，采用BPSK調(diào)制，根據(jù)WIMAX標(biāo)準(zhǔn)給出的基校驗(yàn)矩陣，構(gòu)造出碼率為1/2、碼長(zhǎng)為2 304的QC-LDPC碼。對(duì)本文提出的新算法與校驗(yàn)節(jié)點(diǎn)匹配算法在上述相同條件下進(jìn)行仿真，誤碼率性能曲線如圖3所示。

通過圖3可以看出，本文提出的新算法相比性能較好接近和積譯碼算法的校驗(yàn)節(jié)點(diǎn)匹配算法，在BER=10?5時(shí)，大約有0.08 dB的提高。

繼續(xù)分析，歸一化最小和譯碼算法和抵消最小和譯碼算法采用文獻(xiàn)[10]給出的性能最優(yōu)取值α=0.95和β=0.10。在上述相同條件下進(jìn)行仿真，誤碼率性能曲線如圖4所示。

圖4 5種譯碼算法性能比較

可以看出和積算法與最小和算法之間相差約有0.3 dB，在BER=10?5時(shí)，本文提出的新算法相比最小和算法有大約0.25 dB的提高，而與歸一化最小和算法和抵消最小和算法相比也有0.15～0.2 dB的提高，與性能優(yōu)異但復(fù)雜度高的和積算法相差僅有0.05 dB。當(dāng)信噪比高于3 dB時(shí)，本文提出的新算法與和積算法的誤碼率均為0。

5 結(jié)束語

通過對(duì)常用的LDPC軟判決譯碼研究，在提出改進(jìn)型歸一化最小和譯碼算法的基礎(chǔ)上，與校驗(yàn)節(jié)點(diǎn)匹配算法結(jié)合，得到了一種性能優(yōu)異并且復(fù)雜度相對(duì)和積算法很低的新算法。仿真結(jié)果表明，這種新算法的譯碼性能相比歸一化最小和算法、抵消最小和算法、校驗(yàn)節(jié)點(diǎn)匹配算法更加逼近和積譯碼的性能。

[1] GALLGER R G．Low-density parity-check codes[J]．IRE Trans on Imformation Theory，1962, 8(1): 21-26．

[2] MACKAY D J C, NEAL R M. Near Shannon limit performance of low density parity check codes[J]. Electronics Letters, 1996, 32(18): 1645-1646．

[3] LUBY M G, MITZENMACHER M, SHOKROLLAH M A M，et al．Expander codes[J]．IEEE Trans on Imformation Theory, 1996, 42: 1710-1722.

[4] 袁東風(fēng), 張海剛．LDPC碼理論與應(yīng)用[M]．北京: 人民郵電出版社, 2008: 64-66.

[5] 謝剛, 趙哲峰, 雷少帥, 等. WIMAX技術(shù)原理及應(yīng)用[M]. 北京: 北京郵電大學(xué)出版社, 2010: 12-13.

[6] CHEN J，F(xiàn)OSSORIER M P C．Near-optimum universal belief propagation based decoding of low-density parity check codes[J]. IEEE Transactions on Communications, 2002, 50(3): 06-414．

[7] HOWARD S，SCHLEGEL C，GAUDET V．Degree-matched check node decoding for regular and irregular LDPCs[J]．IEEE Trans on Circuits and Systems, 2006, 53(10): 1054-1058．

[8] FOSSORIER MPC, MIHALJEVIC M, IMAI H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE Transactions on Communications, 1999, 47(5): 673-680.

[9] HOWARD S L, SCHLEGEL C, GAUDET V C. Degree-matched check node decoding for regular and irregular LDPCs[J]. IEEE Trans on Circuits and Systems II: Express Briefs, 2006, 53(10): 1054-1058.

[10] 于學(xué)明. LDPC碼的研究及其在OFDM系統(tǒng)中的應(yīng)用[D]. 哈爾濱: 哈爾濱工程大學(xué), 2011: 32-36.

A novel soft decision decoding algorithm for WIMAX standard LDPC codes

LI Wanchen，WANG Maozhao

College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001,China

WIMAX standard LDPC is based on quasi-cyclic encoding, and the decoding usually uses the sum-product decoding algorithm. In order to further reduce decoding complexity, a novel modified normalized min-sum (NMS) algorithm is proposed in this paper. The optimal multiplicative factor is obtained by a lot of simulation samples and analyses, and the approximate linear formula is deduced as well. On the basis of it, combining with the check node degree-matched algorithm, the decoding performance is improved further. Simulation results indicate that the proposed novel algorithm improves the decoding performance greatly compared with the NMS algorithm, the offset min-sum (OMS) algorithm and check node degree-matched (CNM) algorithm, and the BER is very close to the sum-product algorithm.

WIMAX standard LDPC codes; modified normalized min-sum algorithm; sum-product algorithm; check node degree-matched algorithm

TN911.22

A

1009-671X（2014）01-0039-04

10.3969/j.issn.1009-671X.201211017

2012-11-19.

李萬臣（1963-）, 男, 教授；王茂朝（1984-）, 男, 碩士研究生.

李萬臣, E-mail: lwchen@hrbeu.edu.cn.