基于变量节点可靠度的洗牌置信传播算法

王海泉 姚钱波 胡方宁 张 茴

（杭州电子科技大学通信工程学院，浙江杭州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