王海泉 姚錢波 胡方寧 張 茴

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

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

王海泉 姚錢波 胡方寧 張 茴

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

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

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

引 言

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

考慮到各變量節(jié)點(diǎn)的可靠度，提出一種新的SBP譯碼（New Shuffled Belief Propagation，NSBP）.假設(shè)一個(gè)時(shí)變信道，每一個(gè)被傳輸?shù)男盘?hào)來自信道的噪聲是不同的，因此，所接收信號(hào)的可靠度是不同的.因?yàn)槌跏夹畔H僅來自信道，所以它可以被用來預(yù)測變量節(jié)點(diǎn)的可靠度.根據(jù)信息的可靠度，將變量節(jié)點(diǎn)或校驗(yàn)節(jié)點(diǎn)分成若干組，將可靠度高的節(jié)點(diǎn)分在第一組，可靠度低的節(jié)點(diǎn)分在第二組.

1 LDPC碼的SBP譯碼

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

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

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

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

SBP算法如下：

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

第一步：消息處理

對(duì)于1≤g≤G

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

第二步：對(duì)所有變量節(jié)點(diǎn)計(jì)算

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

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

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

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

2 LDPC碼的NSBP譯碼

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

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

所以，它由lnP（yn｜xn＝1）和lnP（yn｜xn＝－1）決定.ln是一個(gè)連續(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從點(diǎn)B向點(diǎn)A變化時(shí)差值在增加，而差值是隨著噪聲的減小而增加的.因此，如果｜Ln1｜＞｜Ln2｜，則變量節(jié)點(diǎn)n1將比變量節(jié)點(diǎn)n2能提供更可靠的消息.

設(shè)Vm＝｛vn‖Ln｜≥γ，vn∈N（m）｝，γ為預(yù)先確定的常數(shù).dγ為校驗(yàn)節(jié)點(diǎn)m的度，dr為變量節(jié)點(diǎn)屬于Vm的個(gè)數(shù)，ψm＝dγ／dm表示在連接校驗(yàn)節(jié)點(diǎn)m的變量節(jié)點(diǎn)中它的｜Ln｜超過γ的比例.因此，ψm可以表示校驗(yàn)節(jié)點(diǎn)m收到信息的可靠性比例.對(duì)ψm進(jìn)行從大到小排序，根據(jù)可靠性比例將校驗(yàn)節(jié)點(diǎn)分成G組.在考慮G＝2的情況下，校驗(yàn)節(jié)點(diǎn)被分為G1＝｛m｜ψm≥δ｝和G2＝｛m｜ψm＜δ｝兩組，δ為預(yù)先設(shè)定的門值.對(duì)于變量節(jié)點(diǎn)，將其分成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é)點(diǎn)收到的來自信道的初始概率似然比消息，則求出｜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時(shí)，可認(rèn)為Lni的可靠度高；當(dāng)｜Lni｜＜7時(shí)，可認(rèn)為Lni的可靠度低.由圖可以看出，對(duì)于校驗(yàn)節(jié)點(diǎn)c1，，它的度數(shù)dc1＝3，即有v1，v3，v4三個(gè)變量節(jié)點(diǎn)與它相連，對(duì)應(yīng)于這三個(gè)變量節(jié)點(diǎn)的｜Lni｜都大于γ，即｜Ln1｜≥7，｜Ln3｜≥7，｜Ln4｜≥7，這三個(gè)變量節(jié)點(diǎn)都屬于vm，得d7＝3.因此，可以計(jì)算出ψ1＝3／dc1＝1.同理，可以計(jì)算出其他三個(gè)校驗(yàn)節(jié)點(diǎn)對(duì)應(yīng)比值為ψ2＝2／dc2＝2／3，ψ3＝1／dc3＝1／3，ψ4＝1／dc4＝1／2，對(duì)所求得的四個(gè)比值進(jìn)行排序，得ψ1＞ψ2＞ψ3＞ψ4.在考慮平均分成G＝2組的情況下，用C1和C2組成第1組G1，G3和G4組成第2組G2.

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

3 仿真與分析

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

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

按變量節(jié)點(diǎn)分組時(shí)：

仿真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時(shí)，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時(shí)，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).糾錯(cuò)碼原理與方法［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)師，主要研究方向?yàn)樾盘?hào)處理、空時(shí)碼、多天線系統(tǒng).

胡方寧 （1976－），女，浙江人，博士，School of Engineering and Science Jacobs University Bremen（JUB）講師，主要研究方向?yàn)樾诺谰幋a.

張 茴 （1989－），女，浙江人，杭州電子科技大學(xué)碩士研究生，主要研究方向?yàn)橥ㄐ趴垢蓴_.

姚錢波 （1989－），男，浙江人，杭州電子科技大學(xué)碩士研究生，主要研究方向?yàn)樾诺谰幋a.

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

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

一、征文范圍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二、征文要求

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

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

三、論文提交重要時(shí)間

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

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

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

四、會(huì)議論文評(píng)獎(jiǎng)與發(fā)表

1、年會(huì)將對(duì)參會(huì)論文進(jìn)行優(yōu)秀論文評(píng)選，并頒發(fā)優(yōu)秀論文證書。

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

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

五、論文提交

會(huì)議論文可用兩種方式提交：

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

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

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

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

賈守新

電話：010-58887062

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

郵編：100190

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

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

馬鐵漢

電話：0373-3713101

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

郵編：453003

電子郵件：mtieh＠126.com

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

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é)點(diǎn)可靠度的洗牌置信傳播算法［J］.電波科學(xué)學(xué)報(bào)，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é)基金面上項(xiàng)目（No.61372093）；浙江省數(shù)據(jù)存儲(chǔ)傳輸及其應(yīng)用技術(shù)研究重點(diǎn)實(shí)驗(yàn)室建議基金；國家自然科學(xué)基金項(xiàng)目（No.61201142）

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