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

王海泉 姚錢波 胡方寧 張 茴

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

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

王海泉 姚錢波 胡方寧 張 茴

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

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

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

引 言

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

考慮到各變量節點的可靠度，提出一種新的SBP譯碼（New Shuffled Belief Propagation，NSBP）.假設一個時變信道，每一個被傳輸的信號來自信道的噪聲是不同的，因此，所接收信號的可靠度是不同的.因為初始信息僅僅來自信道，所以它可以被用來預測變量節點的可靠度.根據信息的可靠度，將變量節點或校驗節點分成若干組，將可靠度高的節點分在第一組，可靠度低的節點分在第二組.

1 LDPC碼的SBP譯碼

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

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

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

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

SBP算法如下：

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

第一步：消息處理

對于1≤g≤G

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

第二步：對所有變量節點計算

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

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

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

如圖1所示，（a）、（b）分別表示分組數G＝1（標準BP譯碼）、2時的兩種情況.方框表示校驗節點，圓圈表示變量節點.

2 LDPC碼的NSBP譯碼

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

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

所以，它由lnP（yn｜xn＝1）和lnP（yn｜xn＝－1）決定.ln是一個連續遞增函數，若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中可以發現當yn從點B向點A變化時差值在增加，而差值是隨著噪聲的減小而增加的.因此，如果｜Ln1｜＞｜Ln2｜，則變量節點n1將比變量節點n2能提供更可靠的消息.

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

假設圖3中Ln＝［7.024 4 －0.664 8－9.063 7 7.478 1 －3.462 5 －7.896 7］為各變量節點收到的來自信道的初始概率似然比消息，則求出｜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）｝，當｜Lni｜≥7，i＝1，2，3，4，5，6時，可認為Lni的可靠度高；當｜Lni｜＜7時，可認為Lni的可靠度低.由圖可以看出，對于校驗節點c1，，它的度數dc1＝3，即有v1，v3，v4三個變量節點與它相連，對應于這三個變量節點的｜Lni｜都大于γ，即｜Ln1｜≥7，｜Ln3｜≥7，｜Ln4｜≥7，這三個變量節點都屬于vm，得d7＝3.因此，可以計算出ψ1＝3／dc1＝1.同理，可以計算出其他三個校驗節點對應比值為ψ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｜進行從大到小的排序，根據排序情況對變量節點進行均勻分組，｜Ln｜值大的變量節點被分在前面組.由上面的例子，得到排序9.063 7＞7.896 7＞7.478 1＞7.024 4＞3.462 5＞0.664 8.同樣，在考慮G＝2的情況下，根據排序情況將變量節點平均分成兩組，第1組由v3，v6，v4組成，第2組由v1，v5，v2組成.

3 仿真與分析

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

仿真1 Mackay構造的H（504，3，6），碼率為0.5的規則LDPC碼.標準BP譯碼，SBP譯碼（G＝2），NSBP譯碼（G＝2）三種譯碼策略.

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

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

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

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

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

按變量節點分組時：

仿真3 Mackay構造的H（504，3，6），碼率為0.5的規則LDPC碼.標準BP譯碼，SBP譯碼（G＝ 2），NSBP譯碼（G＝2）三種譯碼策略.

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

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

仿真4 H（405，15，9），碼率為0.5的非規則PEG碼.標準BP譯碼，SBP譯碼（G＝2），NSBP譯碼（G＝2）三種譯碼策略.

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

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

4 結 論

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

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

［2］ 王新梅，肖國鎮.糾錯碼原理與方法［M］.西安：西安電子科技大學出版社，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，FREY 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，FOSSORIER 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－），男，浙江人，博士，杭州電子科技大學教授，碩士研究生導師，主要研究方向為信號處理、空時碼、多天線系統.

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

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

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

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

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

一、征文范圍

本次年會誠征有關電波傳播及其應用相關領域最新研究進展的學術論文（中英文均可）。征文方向主要包括（但不限于）以下主題：

1.波理論與數值分析（包括計算電磁學、瞬態電磁場和非線性效應等）；

2.復雜環境與特殊媒質中電波傳播（包括叢林、地下、水下傳播及應用等）；

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

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

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

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

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

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

9.天線理論與測量技術；

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

11.電波環境及其傳播的測量新技術；

12.電波傳播在其它領域（如射電天文、地震預報、生物效應、核磁共振）中的應用；13.人工擾動電波環境的理論和監測技術；

14.電波傳播與大數據獲取、傳輸、處理有關的理論及技術。

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

二、征文要求

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

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

三、論文提交重要時間

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

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

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

四、會議論文評獎與發表

1、年會將對參會論文進行優秀論文評選，并頒發優秀論文證書。

2、優秀論文按專業內容分別推薦到《雷達學報》、《電子與信息學報》和《電波科學學報》正刊發表。

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

五、論文提交

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

1、發送郵件至：radars＠mail.ie.ac.cn，請注明郵件主題為“2015電波傳播學術年會”，投稿聯系人：賈守新，電話：010-58887062

2、采用網絡平臺投稿，請留意中科院電子所網站http：／／www.ie.cas.cn／的相關通知。

六、會議聯系人

1、會務聯系人

賈守新

電話：010-58887062

通信地址：北京海淀北四環西路19號

郵編：100190

電子郵件：sxjia＠mail.ie.ac.cn

2、中國電子學會電波傳播分會聯系人

馬鐵漢

電話：0373-3713101

通信地址：河南省新鄉市榮校路195號

郵編：453003

電子郵件：mtieh＠126.com

第十三屆全國電波傳播學術年會籌委會

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

王海泉，姚錢波，胡方寧，等.基于變量節點可靠度的洗牌置信傳播算法［J］.電波科學學報，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

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

聯系人：姚錢波E-mail：yqb0309＠163.com