基于變量節(jié)點可靠度的洗牌置信傳播算法

王海泉 姚錢波 胡方寧 張 茴

（杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州310018）

基于變量節(jié)點可靠度的洗牌置信傳播算法

王海泉 姚錢波 胡方寧 張 茴

（杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州310018）

提出了一種新的低密度奇偶校驗（Low-Density Parity-Check，LDPC）碼串行譯碼策略.該方法基于原有的LDPC碼串行譯碼策略，根據(jù)來自信道的初始消息的可靠度對變量節(jié)點或校驗節(jié)點進行均勻分組.對所提方法的誤碼率與平均迭代次數(shù)進行了分析.仿真結(jié)果表明：該策略的性能比原來的LDPC碼串行譯碼策略有很大提高.

LDPC碼；BP譯碼；SBP譯碼；BER性能

引 言

低密度奇偶校驗（Low-Density Parity-Check，LDPC）碼是Gallager［1］在1962年提出來的一種基于稀疏校驗矩陣的線性分組碼［2］.近年來，LDPC碼受到廣泛關(guān)注，是因為它可以采用和積算法［3－4］進行譯碼，從而可以達到非常接近香農(nóng)限的性能，且譯碼復(fù)雜度僅隨碼長線性增加.最常見的是標(biāo)準(zhǔn)置信傳播（Belief Propagation，BP）譯碼［5］，它是一種全并行策略，每輪迭代中需要同時更新所有的校驗節(jié)點（或變量節(jié)點）消息.另一種是洗牌BP譯碼（Shuffled Belief Propagation，SBP［6］），它是一種串行策略，將校驗節(jié)點（或變量節(jié)點）分成若干組，每輪迭代中依次更新各個組的校驗節(jié)點（或變量節(jié)點）消息，組內(nèi)并行，組間串行.與標(biāo)準(zhǔn)BP相比，SBP已有很好的性能提高［7］.

考慮到各變量節(jié)點的可靠度，提出一種新的SBP譯碼（New Shuffled Belief Propagation，NSBP）.假設(shè)一個時變信道，每一個被傳輸?shù)男盘杹碜孕诺赖脑肼暿遣煌?，因此，所接收信號的可靠度是不同?因為初始信息僅僅來自信道，所以它可以被用來預(yù)測變量節(jié)點的可靠度.根據(jù)信息的可靠度，將變量節(jié)點或校驗節(jié)點分成若干組，將可靠度高的節(jié)點分在第一組，可靠度低的節(jié)點分在第二組.

1 LDPC碼的SBP譯碼

在標(biāo)準(zhǔn)BP算法中，置信消息是迭代地被更新的.每一次迭代由兩步組成：第一步，利用上一次迭代中獲得的變量節(jié)點傳遞到校驗節(jié)點（V→C）的消息來更新所有校驗節(jié)點傳遞到變量節(jié)點（C→V）的消息；第二步，利用第一步中新獲得的C→V的消息來更新所有的V→C的消息.

假設(shè)有一個M×N的奇偶校驗矩陣.在SBP中，校驗節(jié)點或變量節(jié)點將被平均分成G組，每組含有MG＝M／G個校驗節(jié)點或MG＝N／G個變量節(jié)點.先對第1組校驗節(jié)點和其相鄰的變量節(jié)點進行消息的更新，接著依次進行第2組，第3組，…直到第G組.前面己經(jīng)更新的消息將在后面分組中用到.不失一般性，在下面僅僅描述基于校驗節(jié)點的SBP，變量節(jié)點的分組算法可以用相同的方式推出.

假設(shè)碼字c＝（c1，c2，…，cN）經(jīng)過雙相移相鍵控（Binary Phase-Shift Keying，BPSK）調(diào)制，然后經(jīng)過一個均值為0、方差為σ2的加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道，相應(yīng)的接收到的碼字為y＝（y1，y2，…，yN）.

Gg表示第g組校驗節(jié)點集，1≤g≤G；l表示迭代計數(shù)；Imax表示最大迭代次數(shù)；N（m）表示與校驗節(jié)點m相連的變量節(jié)點的集合；M（n）表示與變量節(jié)點n相連的校驗節(jié)點的集合；N（m）＼n表示除n外與校驗節(jié)點m相連的變量節(jié)點的集合；M（n）＼m表示除m外與變量節(jié)點n相連的校驗節(jié)點的集合；Lnm表示變量節(jié)點n傳給校驗節(jié)點m的消息；Lmn表示校驗節(jié)點m傳給變量節(jié)點n的消息.

SBP算法如下：

初始化：變量節(jié)點n到校驗節(jié)點m的消息初始化為從信道傳來的消息，即

第一步：消息處理

對于1≤g≤G

a）校驗節(jié)點處理：?m∈Gg，n∈N（m），

第二步：對所有變量節(jié)點計算

第三步：硬件判決和迭代停止條件判定

b）如果D（l）HT＝0或者到達最大迭代次數(shù)Imax，迭代停止，否則l＝l＋1，返回第一步.

現(xiàn)舉例一個（6，2）線性分組碼在一次迭代中SBP譯碼的譯碼過程.

如圖1所示，（a）、（b）分別表示分組數(shù)G＝1（標(biāo)準(zhǔn)BP譯碼）、2時的兩種情況.方框表示校驗節(jié)點，圓圈表示變量節(jié)點.

2 LDPC碼的NSBP譯碼

譯碼初始時，各變量節(jié)點都會收到來自信道的初始概率似然比為消息Ln.

假設(shè)信息用二進制表示為un＝｛0，1｝，用BPSK（0→1，1→－1）調(diào)制為xn＝｛1，－1｝，所收到的信號為yn＝xn＋wn，wn是高斯白噪聲.在譯碼開始前，所有變量節(jié)點都會收到來自信道的對數(shù)似然比為

所以，它由lnP（yn｜xn＝1）和lnP（yn｜xn＝－1）決定.ln是一個連續(xù)遞增函數(shù)，若P（yn｜xn＝1）和P（yn｜xn＝－1）相差越大，則｜Ln｜越大.從圖2可以看到，在yn＝－1（P（yn｜xn＝－1）＝a，P（yn｜xn＝1）＝b）和yn＝1處可以獲得最大差值，表明信道沒有噪聲.在圖2中可以發(fā)現(xiàn)當(dāng)yn從點B向點A變化時差值在增加，而差值是隨著噪聲的減小而增加的.因此，如果｜Ln1｜＞｜Ln2｜，則變量節(jié)點n1將比變量節(jié)點n2能提供更可靠的消息.

設(shè)Vm＝｛vn‖Ln｜≥γ，vn∈N（m）｝，γ為預(yù)先確定的常數(shù).dγ為校驗節(jié)點m的度，dr為變量節(jié)點屬于Vm的個數(shù)，ψm＝dγ／dm表示在連接校驗節(jié)點m的變量節(jié)點中它的｜Ln｜超過γ的比例.因此，ψm可以表示校驗節(jié)點m收到信息的可靠性比例.對ψm進行從大到小排序，根據(jù)可靠性比例將校驗節(jié)點分成G組.在考慮G＝2的情況下，校驗節(jié)點被分為G1＝｛m｜ψm≥δ｝和G2＝｛m｜ψm＜δ｝兩組，δ為預(yù)先設(shè)定的門值.對于變量節(jié)點，將其分成G1＝｛n‖Ln｜≥γ｝和G2＝｛n‖Ln｜＜γ｝兩組.

假設(shè)圖3中Ln＝［7.024 4 －0.664 8－9.063 7 7.478 1 －3.462 5 －7.896 7］為各變量節(jié)點收到的來自信道的初始概率似然比消息，則求出｜Ln｜＝［7.024 4 0.664 8 9.063 7 7.478 1 3.462 5 7.896 7］.取γ＝7，Vm＝｛vn‖Ln｜≥7，vn∈N（m）｝，當(dāng)｜Lni｜≥7，i＝1，2，3，4，5，6時，可認為Lni的可靠度高；當(dāng)｜Lni｜＜7時，可認為Lni的可靠度低.由圖可以看出，對于校驗節(jié)點c1，，它的度數(shù)dc1＝3，即有v1，v3，v4三個變量節(jié)點與它相連，對應(yīng)于這三個變量節(jié)點的｜Lni｜都大于γ，即｜Ln1｜≥7，｜Ln3｜≥7，｜Ln4｜≥7，這三個變量節(jié)點都屬于vm，得d7＝3.因此，可以計算出ψ1＝3／dc1＝1.同理，可以計算出其他三個校驗節(jié)點對應(yīng)比值為ψ2＝2／dc2＝2／3，ψ3＝1／dc3＝1／3，ψ4＝1／dc4＝1／2，對所求得的四個比值進行排序，得ψ1＞ψ2＞ψ3＞ψ4.在考慮平均分成G＝2組的情況下，用C1和C2組成第1組G1，G3和G4組成第2組G2.

因為｜Ln｜的大小可以反映它的可靠度，所以對｜Ln｜進行從大到小的排序，根據(jù)排序情況對變量節(jié)點進行均勻分組，｜Ln｜值大的變量節(jié)點被分在前面組.由上面的例子，得到排序9.063 7＞7.896 7＞7.478 1＞7.024 4＞3.462 5＞0.664 8.同樣，在考慮G＝2的情況下，根據(jù)排序情況將變量節(jié)點平均分成兩組，第1組由v3，v6，v4組成，第2組由v1，v5，v2組成.

3 仿真與分析

仿真是通過Matlab實現(xiàn)的，基于BPSK調(diào)制方式，信道為二元輸入的，均值為0、方差1的高斯白噪聲信道按校驗節(jié)點分組時：

仿真1 Mackay構(gòu)造的H（504，3，6），碼率為0.5的規(guī)則LDPC碼.標(biāo)準(zhǔn)BP譯碼，SBP譯碼（G＝2），NSBP譯碼（G＝2）三種譯碼策略.

在有限迭代次數(shù)的情況下，三者的誤碼率（Bit Error Rate，BER）性能比較如圖4所示；在最大迭代次數(shù)為100的情況下，三者的平均迭代次數(shù)比較如圖5所示.

由圖4可以看出，NSBP譯碼的性能高于SBP譯碼.由圖5可以看出，當(dāng)信噪比（Singal-to-Noise Ratio，SNR）在0～2.5dB范圍內(nèi)，NSBP譯碼的迭代次數(shù)比SBP譯碼的少，尤其在1dB處減少了13.4%.

仿真2 H（405，15，9），碼率為0.5的非規(guī)則PEG（Progressive-Edge-Growth）碼［8－9］.標(biāo)準(zhǔn)BP譯碼，SBP譯碼（G＝2），NSBP譯碼（G＝2）三種譯碼策略.γ＝4，δ＝83.33%.

在有限迭代次數(shù)的情況下，三者的BER性能比較如圖6所示；在最大迭代次數(shù)為100的情況下，三者的平均迭代次數(shù)比較如圖7所示.

由圖6可知，當(dāng)SNR大于1dB時，NSBP譯碼的誤碼性能略高于SBP譯碼.由圖7可知：當(dāng)SNR在0.5～2.5dB范圍內(nèi)，NSBP譯碼的迭代次數(shù)與SBP譯碼相比減少了23%；當(dāng)SNR大于2.5dB時，NSBP譯碼的迭代次數(shù)與SBP譯碼相近.因此，算法的復(fù)雜度降低了.

按變量節(jié)點分組時：

仿真3 Mackay構(gòu)造的H（504，3，6），碼率為0.5的規(guī)則LDPC碼.標(biāo)準(zhǔn)BP譯碼，SBP譯碼（G＝ 2），NSBP譯碼（G＝2）三種譯碼策略.

在有限迭代次數(shù)的情況下，三者的BER性能比較如圖8所示；在最大迭代次數(shù)為50的情況下，三者的平均迭代次數(shù)比較如圖9所示.

由圖8可以看出，NSBP譯碼的性能好于SBP譯碼.由圖9可知，當(dāng)SNR在0.5～2.5dB范圍內(nèi)，NSBP譯碼的迭代次數(shù)比SBP譯碼的少，尤其在2dB處減少了21%.

仿真4 H（405，15，9），碼率為0.5的非規(guī)則PEG碼.標(biāo)準(zhǔn)BP譯碼，SBP譯碼（G＝2），NSBP譯碼（G＝2）三種譯碼策略.

在有限迭代次數(shù)的情況下，三者的BER性能比較如圖10所示；在最大迭代次數(shù)為50的情況下，三者的平均迭代次數(shù)比較如圖11所示.

由圖10可知：當(dāng)SNR大于0.5dB時，NSBP譯碼的性能略高于SBP譯碼；尤其，在1～2dB范圍內(nèi)，NSBP明顯好于SBP.由圖11可知：當(dāng)SNR在0.5～2.5dB范圍內(nèi)，NSBP譯碼的迭代次數(shù)與SBP譯碼相比減少了25.7%；當(dāng)SNR大于2.5dB時，NSBP譯碼的迭代次數(shù)與SBP譯碼相近.因此，算法的復(fù)雜度降低了.

4 結(jié) 論

本文提出了一種基于SBP的新串行譯碼方法，在AWGN信道仿真結(jié)果表明，這種新的譯碼策略有效地降低了迭代次數(shù)，提高了譯碼速度，譯碼性能明顯提高.

［1］ GALLAGER R G.Low-density parity-check codes［J］.IRE TransInformTheory，1962，8（1）：21-28.

［2］ 王新梅，肖國鎮(zhèn).糾錯碼原理與方法［M］.西安：西安電子科技大學(xué)出版社，1991.

［3］ MCELIECE ROBERT J，MACKAY D J C，CHENG Jungfu.Turbo decoding as an instance of Pearl’s“belief propagation”algorithm［J］.IEEE Journal on Selected Areas in Communications，1998，16（2）：140-152.

［4］ KSCHISCHANG F R，F(xiàn)REY B J，LOELIGER H.Factor graphs and the sum-product algorithm［J］.IEEE Trans Info Theory，2001，47（2）：498-519.

［5］ MACKAY D J C.Good error-correcting codes based on very sparse matrices［J］.IEEE Trans Inf Theory，1999，45（2）：399-431.

［6］ ZHANG Juntan，F(xiàn)OSSORIER M.Shuffled iterative decoding［J］.IEEE TransCommun，2005，53（2）：209-213.

［7］ MANSOUR M M，SHANBHAG N R.Highthroughput LDPC decoders［J］.IEEE Trans on VLSI Systems，2003，11（6）：976-996.

［8］ RICHARDSON T J，SHOKROLLAHI M A，URBANKE R L.Design of capacity-approaching irregular low-density parity-check codes［J］.IEEE Transactions on Information Theory，2001，47（2）：619-637.

［9］ HUA Xiao，BANIHASHEMI A H.Improved progressive-edge-growth construction of irregular LDPC codes［J］.IEEE Communications Letters，2004，8（12）：715-717.

作者簡介

王海泉 （1964－），男，浙江人，博士，杭州電子科技大學(xué)教授，碩士研究生導(dǎo)師，主要研究方向為信號處理、空時碼、多天線系統(tǒng).

胡方寧 （1976－），女，浙江人，博士，School of Engineering and Science Jacobs University Bremen（JUB）講師，主要研究方向為信道編碼.

張 茴 （1989－），女，浙江人，杭州電子科技大學(xué)碩士研究生，主要研究方向為通信抗干擾.

姚錢波 （1989－），男，浙江人，杭州電子科技大學(xué)碩士研究生，主要研究方向為信道編碼.

第十三屆全國電波傳播學(xué)術(shù)年會暨呂保維院士百年華誕紀(jì)念會征文通知（第一輪）

經(jīng)中國電子學(xué)會電波傳播分會研究決定，將于2015年9月16日（周三）至19日（周六）在北京懷柔雁棲湖畔召開“第十三屆全國電波傳播學(xué)術(shù)年會暨呂保維院士百年華誕紀(jì)念會”（13th Chinese National Symposium on Radio Propagation（CNSRP’2015）＆Centennial Commemoration of Academician B.W.Lü）。此次會議由中國電子學(xué)會電波傳播分會主辦，中國科學(xué)院電子學(xué)研究所和中國電子科技集團第二十二研究所承辦?，F(xiàn)將有關(guān)事宜通知如下：

一、征文范圍

本次年會誠征有關(guān)電波傳播及其應(yīng)用相關(guān)領(lǐng)域最新研究進展的學(xué)術(shù)論文（中英文均可）。征文方向主要包括（但不限于）以下主題：

1.波理論與數(shù)值分析（包括計算電磁學(xué)、瞬態(tài)電磁場和非線性效應(yīng)等）；

2.復(fù)雜環(huán)境與特殊媒質(zhì)中電波傳播（包括叢林、地下、水下傳播及應(yīng)用等）；

3.對流層電波（含光波）傳播與無線電氣象；

4.電離層電波傳播與空間等離子體物理；

5.無線電波（含光）遙感理論和新技術(shù)；

6.無線通信（含移動通信、室內(nèi)通信、MIMO）中的電波傳播；

7.SAR、雷達、遙感、電磁探測中的電波傳播問題；

8.無線電偵測與定位的電波理論及新技術(shù)；

9.天線理論與測量技術(shù)；

10.電磁兼容、噪聲干擾、無線電頻譜管理（含認知頻譜共享）與檢測；

11.電波環(huán)境及其傳播的測量新技術(shù)；

12.電波傳播在其它領(lǐng)域（如射電天文、地震預(yù)報、生物效應(yīng)、核磁共振）中的應(yīng)用；13.人工擾動電波環(huán)境的理論和監(jiān)測技術(shù)；

14.電波傳播與大數(shù)據(jù)獲取、傳輸、處理有關(guān)的理論及技術(shù)。

今年恰逢我國電波傳播研究的開拓者、奠基人呂保維院士百年誕辰，為紀(jì)念呂保維院士為我國電波事業(yè)孜孜奮斗一生及作出的卓越貢獻，為秉承呂保維院士治學(xué)、深究、育人的高尚情操，會議安排紀(jì)念呂保維院士的特別議程，并歡迎各種形式的紀(jì)念文稿。

二、征文要求

1.來稿必須是未曾在國內(nèi)外公開發(fā)表過的文章，無弄虛作假，無一稿多投，不得涉及國家秘密。

2.論文一般4－6頁，以正式論文的形式（包括題目、作者姓名、作者單位、摘要、關(guān)鍵詞、正文、參考文獻）書寫應(yīng)征論文。中文論文請包括英文題目、作者、作者單位、摘要和關(guān)鍵詞；英文論文請附上中文題目、作者、作者單位、摘要和關(guān)鍵詞。論文摘要應(yīng)包括目的、方法、結(jié)果、結(jié)論四部分。

三、論文提交重要時間

●提交論文截止日期：2015年7月10日

●通知論文接收日期：2015年8月8日

●提交論文修改稿日期：2015年8月20日

四、會議論文評獎與發(fā)表

1、年會將對參會論文進行優(yōu)秀論文評選，并頒發(fā)優(yōu)秀論文證書。

2、優(yōu)秀論文按專業(yè)內(nèi)容分別推薦到《雷達學(xué)報》、《電子與信息學(xué)報》和《電波科學(xué)學(xué)報》正刊發(fā)表。

3、其它會議論文以《電波科學(xué)學(xué)報》增刊形式出版發(fā)表。

五、論文提交

會議論文可用兩種方式提交：

1、發(fā)送郵件至：radars＠m(xù)ail.ie.ac.cn，請注明郵件主題為“2015電波傳播學(xué)術(shù)年會”，投稿聯(lián)系人：賈守新，電話：010-58887062

2、采用網(wǎng)絡(luò)平臺投稿，請留意中科院電子所網(wǎng)站http：／／www.ie.cas.cn／的相關(guān)通知。

六、會議聯(lián)系人

1、會務(wù)聯(lián)系人

賈守新

電話：010-58887062

通信地址：北京海淀北四環(huán)西路19號

郵編：100190

電子郵件：sxjia＠m(xù)ail.ie.ac.cn

2、中國電子學(xué)會電波傳播分會聯(lián)系人

馬鐵漢

電話：0373-3713101

通信地址：河南省新鄉(xiāng)市榮校路195號

郵編：453003

電子郵件：mtieh＠126.com

第十三屆全國電波傳播學(xué)術(shù)年會籌委會

2015年1月10日

Shuffled belief propagation decoding based on variable nodes reliability

WANG Haiquan YAO Qianbo HU Fangning ZHANG Hui
（School of Communications Engineering，Hangzhou Dianzi University，Hangzhou Zhejiang310018，China）

This paper proposes a new group shuffled belief propagation（BP）decoding of low-density parity-check（LDPC）codes，which divides check nodes or variable nodes into groups based on the reliability of the initial channel message.The bit error rate and the average number of iterations are analyzed with additive white Gaussian noise（AWGN）channel.Simulations verify that the proposed decoding strategy greatly improves the decoding performance.

low-density parity-check（LDPC）codes；belief propagation（BP）；shuffled belief propagation（SBP）；bit error rate（BER）performance

TN911.22

A

1005-0388（2015）01-0078-06

王海泉，姚錢波，胡方寧，等.基于變量節(jié)點可靠度的洗牌置信傳播算法［J］.電波科學(xué)學(xué)報，2015，30（1）：78-83.

10.13443／j.cjors.2014040802

WANG Haiquan，YAO Qianbo，HU Fangning，et al.Shuffled belief propagation decoding based on variable nodes reliability［J］.Chinese Journal of Radio Science，2015，30（1）：78-83.（in Chinese）.doi：10.13443／j.cjors.2014040802

2014-04-08

國家自然科學(xué)基金面上項目（No.61372093）；浙江省數(shù)據(jù)存儲傳輸及其應(yīng)用技術(shù)研究重點實驗室建議基金；國家自然科學(xué)基金項目（No.61201142）

聯(lián)系人：姚錢波E-mail：yqb0309＠163.com