系统极化码的置信传播译码性能分析*

陈国泰，张朝阳，张 亮，陈平平

系统极化码的置信传播译码性能分析*

陈国泰1，2，张朝阳**2，张 亮2，陈平平3

（1.福建师范大学福清分校电信学院，福州 350300；2.浙江大学信息与通信工程研究所，杭州 310027；3.福州大学物理与信息工程学院，福州 350116）

置信传播（BP）算法可以为系统极化码提供软信息作为判决依据，也可以为系统极化码在级联迭代译码中提供交换软信息。在详细描述基于信道极化结构的置信传播算法基础上，比较了系统极化码在软信息判决方法和极化编码判决方法下错误率性能的差异。仿真结果表明，软信息判决方法可以提高系统极化码的误比特率，在高信噪比下误帧率方面也略有提高。

系统极化码；级联码；置信传播算法；软信息判决；译码性能

1　引 言

由于Arikan最初提出的极化码是非系统极化码（Nonsystematic Polar Codes，NSPC），为了便于实现类似Turbo码的并行级联码，2011年Arikan在非系统极化码的信道极化结构上构造出系统极化码（Systematic Polar Codes，SPC）［6］，并仿真得到比非系统极化码更好的误比特率性能。这些作者在分析系统极化码的错误率时，先将信道接收的信息按非系统极化码进行译码并判决，再将判决的非系统极化码字经极化编码获得系统极化码的译码判决（本文称之为极化编码判决方法）。

置信传播（Belief Propagation，BP）算法在极化码译码时可以得到软信息并可用作级联码中迭代译码时的交换信息［7-8］，因此BP算法在极化码中也是备受关注的译码算法。文献［9］最先利用BP算法分析极化码的性能，文献［10-11］分别分析了基于信道极化结构上的BP算法，这些研究工作是针对非系统极化码的。本文在［10-11］的基础上给出了详细的BP算法步骤，并用该算法对系统极化码的译码性能进行分析，比较了在软信息判决方法和极化编码判决方法下的错误率性能差异。

2　极化码

N（=2n）个相互独立且具有信道容量I（W）的信道W，经过信道合并和信道分离，可以使这N个独立的信道形成新的N个信道，而这新的N个信道前后存在依赖关系，当N→∞时，占总数比例为I（W）的信道趋于无噪信道（“好”信道），比例为1-I（W）的信道趋于全噪信道（“坏”信道）。

图1是信道极化的过程。首先右端N个信道进行合并：

式中：G=F⊗n是F的n次Kronecker幂；u=（u0，u1，…，uN-1）为输入比特信息；x=（x0，x1，…，xN-1）为极化码码字；y=（y0，y1，…，yN-1）为信道接收的信息。信道分离是根据式（1）所示的信道转移概率实现：

根据转移概率可以计算出Bhattacharyya参数来评价分离后的比特信道的“好坏”程度（或其他方法来评价比特信道的“好坏”程度，可参见文献［12］及其所列文献）。

为了构造系统极化码，使用户传输的比特信息作为码字中的一部分，Arikan在靠近信道这一端（如图1中的右端）选择与左端非冻结比特信道具有相同索引值的比特位用于配置用户比特信息，并基于图1的结构推算出右端其他未知的比特（如图1中带“？”的比特），这些未知比特与用户比特信息形成一个极化码码字。关于系统极化码的编码方案，可参见文献［13］及其文献列表。

图1　N=8的信道极化过程Fig.1　Channel polarization and polar encoder with N=8

3　极化码的置信传播（BP）算法

Arikan在提出极化码时采用一种SC算法作为极化码的译码算法，但是由于SC算法在有限码长下不能得到理想的极化码译码性能，在文献［9］中，Arikan采用经典BP算法（即基于校验矩阵实现置信传播译码）对RM码和非系统极化码的性能进行比较分析。在文献［10-11］中，研究工作者研究了基于信道极化结构（如图2）的BP算法（本文称为极化码BP算法）。其中，Zhang等人［10］的研究结果表明了极化码BP算法在译码性能上可优于经典BP算法。由于系统极化码和非系统极化码具有相同的信道极化结构，极化码BP算法同样适用于系统极化码，而且BP算法可以为系统极化码产生软信息作为迭代译码中的交换信息。本节在现有研究成果的基础上，阐述了极化码BP算法的详细步骤，特别是对初值设置、信息输出（译码判决以及用于信息交换的软信息）加以说明。

对于长度为N（=2n）的极化码，根据信道极化层次从左到右分为层次0至层次n-1（如图2），极化码BP算法从信道接收到的信息开始从右向左进行置信传播（如图2上方所示），再从左向右进行置信传播（如图2下方所示）形成一次迭代。注意，图2是在图1的信道极化结构做了位置置换。为了节省译码的计算量，在BP算法译码之前将冻结位从左向右推算，将确定性的节点也作为冻结位处理（如图2斜线圆点所示）。

图2　极化码的BP算法译码流程图（N=8）Fig.2　Decoding process of BP algorithm for polar codes（N=8）

（3）从左端向右端开始 由R（k）和L（k+1）推算出R（k+1）（k=0，1，…，n-2），对于系统极化码，根据硬判决或者软信息交换的需要决定是否进一步推算出R（n），否则可以不需要计算以节省运算量；系统极化码的软信息输出为R（n）+L（n）；步骤2和3形成一次迭代；

（4）重复步骤2～3直至满足迭代停止条件为止，比如达到最大迭代次数。

在极化码BP算法中，置信传播分为处理单元（Processing Element，PE）内部置信传播和处理单元间置信传递。处理单元间置信传递实际上是一个位置置换的过程，可以参照快速傅里叶变换的蝶形结构中的位置置换（如图2所示），这里不展开说明。对于处理单元来说，根据处理单元左端的冻结情况，可以分为4种情况来处理，如图3所示。在图3（c）情况下，由于信息已知而无需进行置信传播，图3（d）情况是不可能发生的情况，因为经过信道极化后，下方的信道必被提升而“好”于上方的信道。

图3　极化码BP算法中的4种不同处理单元Fig.3　Four types of processing element in BP algorithm for polar codes

图3（a）情况的置信传播分向左传播和向右传播。向左置信传播按式（3）进行：

而向右置信传播的计算式子如下：

图3（b）情况由于2j位被冻结（假定被设置为0），则向左置信传播的式子为

而向右传播的表达式为

以上式子中，⊗的具体运算如下：

对于图3（b）情况，由于2j位被冻结而不需要置信传播，因此式（5）也可以不进行计算。可以看到，在图3（b）情况下置信更新的计算量很小。

通常，系统极化码的判决方式为：以非系统极化码方式进行译码，得到，通过式（1）得到系统极化码码字，从中提取信息位（如N=8时x3、x5、x6、x7的信息值）作为系统极化码的判决。在前面所描述的BP算法中，步骤3所得到的软信息R（n）+ L（n）也可以依据进行硬判决作为系统极化码的判决结果。遗憾的是，这种方法得到的判决不一定是极化码码字。

当系统极化码作为级联子码［7-8］时，R（n）将作为外部信息传递给其他译码模块。

4　性能仿真与分析

为了比较在BP算法下不同判决方法在错误率上的性能差异，本节给出了码率为1/2、长度为1 024（210）系统极化码在加性高斯白噪声（Additive White Gaussian Noisy，AWGN）信道下的仿真结果。其中，采用二进制移相键控（BPSK）进行调制｛0→+1，1→-1｝，每个信噪比点的仿真帧数为200 000。本节还提供了非系统极化码的仿真结果，考虑了在串行抵消（SC）算法以及串行抵消列表（SC List Decoding，SCL）译码算法下的仿真性能。其中在BP算法中最大迭代次数设定为60次，在SCL算法中路径保留条数L设定为32。

图4是在上述仿真参数下的误比特率和误帧率性能。其中，“using NSPC”表示系统极化码采用极化编码判决方法，而“using Soft-decision”表示系统极化码采用软信息判决方法。另外，在SC算法和SCL算法中，系统极化码是采用极化编码判决方法。

图4显示，系统极化码的误比特率总优于非系统极化码的误比特率。在BP算法中，利用软信息判决的系统极化码的误比特率略优于通过非系统极化码所得的性能。由于软信息做出的判决有时不是一个极化码码字，因此在误帧率方面会略差；但在高信噪比时，软信息判决的误帧率略优于非系统极化码做出的判决。

图4　N=1 024系统极化码的译码性能Fig.4　Performance of systematic polar codes with N=1 024

由图4中可以看到，BP算法的性能优于SC算法，但SCL算法可以获得比BP算法更好的性能，其原因之一是SCL算法能较好地利用信道极化的特点进行译码。

5　结束语

系统码是构造并行级联码的子码，BP算法可以为系统极化码提供软信息以实现级联码中迭代译码的信息交换。本文详细描述了基于信道极化结构上的BP算法，并在该算法下比较了在软信息判决方法和极化编码判决方法下的系统极化码译码性能。

仿真结果表明在软信息判决方法下，系统极化码可以获得更好的误比特率性能。由于BP算法未能较好地利用极化码的极化特性，在译码性能上劣于串行抵消列表译码法。如何将极化码的极化特性融合到BP算法中以提高BP算法在系统极化码的译码性能是值得研究的一个问题，本文提供的算法步骤可以为深入探讨该问题提供有益的参考。

［1］ ARIKAN E.Channel polarization：a method for construc-ting capacity-achieving codes for symmetric binary-input memoryless channels［J］.IEEE Transactions on Information Theory，2009，55（7）：3051-3073.

［2］ TAL I，VARDY A.List decoding of polar codes［J］.IEEE Transactions on Information Theory，2015，61（5）：2213-2226.

［3］ NIU K，CHEN K.CRC-aided decoding of polar codes［J］. IEEE Communications Letters，2012，16（10）：1668-1671.

［4］ 包昕，王达，刘婉月.利用软解调序列的LDPC码闭集识别方法［J］.电讯技术，2015，55（1）：55-60.

BAO Xin，WANG Da，LIU Wanyue.A finite set recognition algorithm of LDPC coding by using soft-demodulation sequence［J］.Telecommunication Engineering，2015，55（1）：55-60.（in Chinese）

［5］ 肖创创，郭荣海，李际平，等.直升机卫星通信系统Turbo码外交织器设计与仿真［J］.电讯技术，2014，54（4）：486-490.

XIAO Chuangchuang，GUO Ronghai，LI Jiping，et al.Design and simulation of Turbo codes'interleaver in helicopter satellite communication system［J］.Telecommunication Engineering，2014，54（4）：486-490.（in Chinese）

［6］ ARIKAN E.Systematic polar coding［J］.IEEE Communications Letters，2011，15（8）：860-862.

［7］ ZHANG Q，LIU A，ZHANG Y，et al.Practical design and decoding of parallel concatenated structure for systematic polar codes［J］.IEEE Transactions on Communications，2016，64（2）：456-466.

［8］ LIU A，WU D，ZHANG Q，et al.Parallel concatenated systematic polar codes［J］.Electronics Letters，2016，52（1）：43-45.

［9］ ARIKAN E.A performance comparison of polar codes and Reed-Muller codes［J］.IEEE Communications Letters，2008，12（6）：447-449.

［10］ ZHANG Y，LIU A，PAN X，et al.A modified belief propagation polar decoder［J］.IEEE Communications Letters，2014，18（7）：1091-1094.

［11］ YUAN B，PARHI K.Architectures for polar BP decoders using folding［C］//Proceedings of 2014 IEEE International Symposium on Circuits and Systems（ISCAS）. Melbourne，Australia：IEEE，2014：205-208.

［12］ VANGALA H，VITERBO E，HONG Y.A comparative study of polar code constructions for the AWGN channel［J］.Mathematics，2015（1）：1-7.

［13］ CHEN G T，ZHANG Z，ZHONG C，et al.A low complexity encoding algorithm for systematic polar codes［J］.IEEE Communications Letters，2016，20（7）：1277-1280.

陈国泰（1975—），男，福建莆田人，2009年于福州大学获博士学位，现为福建师范大学福清分校电子与信息工程学院副教授，主要研究方向为信源信道编码、无线通信技术；

CHEN Guotai was born in Putian，Fujian Province，in 1975.He received the Ph.D.degreed from Fuzhou University in 2009.He is now an associate professor.His research concerns source coding，channel coding and wireless communications.

Email：chenguot@163.com

张朝阳（1973—），男，湖北蕲春人，1998年于浙江大学获博士学位，现为浙江大学教授、信息与通信工程系主任、浙江省信息处理与通信网络重点实验室主任、中国电子学会信息论分会副主任委员，主要研究方向为信息论与编码理论、信号处理技术及无线通信与网络；

ZHANG Zhaoyang was born in Qichun，Hubei Province，in 1973.He received the Ph.D.degree from Zhejiang University in 1998.He is now a professor，the Chair of the Department of Information and Communication Engineering，and the Director of Zhejiang Provincial Key Laboratory of Information Processing，Communication and Networking.He also serves as the Deputy Director of the Information Theory Society of the Chinese Institute of Electronics（CIE）.His research concerns information theory and coding theory，signal processing techniques，and wireless communications and networking.

Email：ning_ming@zju.edu.cn

张 亮（1988—），男，河南郑州人，2011年于浙江大学获学士学位，现为浙江大学博士研究生，主要研究方向为无线通信与信道编码；

ZHANG Liang was born in Zhengzhou，Henan Province，in 1988.He received the B.S.degree from Zhejiang University in 2011.He is currently working toward the Ph.D.degree.His research concerns wireless communications and channel coding.

陈平平（1986—），男，福建泉州人，2012年于厦门大学获博士学位，现为福州大学讲师，主要研究方向为信道编码理论、网络编码与无线通信。

CHEN Pingping was born in Quanzhou，Fujian Province，in 1986.He received the Ph.D.degree from Xiamen University in 2012.He is now a lecturer.His research concerns channel coding theory，network coding and wireless communications.

Performance Analysis of Systematic Polar Codes with Belief Propagation Algorithm

CHEN Guotai1，2，ZHANG Zhaoyang2，ZHANG Liang2，CHEN Pingping3
（1.School of Electronics and Information，Fuqing Branch of Fujian Normal University，Fuzhou 350300，China；
2.Institute of Information and Communication Engineering，Zhejiang University，Hangzhou 310027，China；
3.College of Physics and Information Engineering，Fuzhou University，Fuzhou 350116，China）

Belief propagation（BP）algorithm can generate soft information for systematic polar codes（SPC）to make decoding decisions and the soft information also can be used as extrinsic information in turbo decoding.This paper first provides a detailed description of BP algorithm based on the structure of channel polarization.Then，it introduces two decision methods，one of which is by exploiting the soft information while the other one is by using polar encoding.The decoding performance under these two methods are compared by simulation，and the simulation results demonstrate that a better bit error rate（BER）performance can be obtained if the soft information is used，while the frame error rate（FER）performance is slightly improved as well in high signal-to-noise ratio（SNR）regime.

systematic polar codes；concatenated codes；belief propagation algorithm；soft decision；decoding performance

The National Basic Research Program of China（973 Program）（2012CB316104）；The National High-tech R&D Program of China（863 Program）（2014AA01A702）；The National Natural Science Foundation of China（No.61371094，61401391，61401099）；The Research Fund of Education Department of Fujian Province（JA12350，JA14339）

**通信作者:ning_ming@zju.edu.cn ning_ming@zju.edu.cn

TN911.22

A

1001-893X（2016）08-0839-05

10.3969/j.issn.1001-893x.2016.08.002

2016-01-08；

2016-05-05

date:2016-01-08；Revised date:2016-05-05

国家重点基础研究发展计划（973计划）项目（2012CB316104）；国家高技术研究发展计划（863计划）项目（2014AA01A702）；国家自然科学基金资助项目（61371094，61401391，61401099）；福建省教育厅中青年教育科研项目（JA12350，JA14339）

引用格式:陈国泰，张朝阳，张亮，等.系统极化码的置信传播译码性能分析［J］.电讯技术，2016，56（8）：839-843.［CHEN Guotai，ZHANG Zhaoyang，ZHANG Liang，et al.Performance analysis of systematic polar codes with belief propagation algorithm［J］.Telecommunication Engineering，2016，56（8）：839-843.］