极化码连续删除算法的改进*

李 纯，关成涛

(西昌卫星发射中心，海南 文昌 571300)

极化码连续删除算法的改进*

李 纯，关成涛

(西昌卫星发射中心，海南 文昌 571300)

提出一种改进的连续删除算法，通过添加监督节点来改善译码性能。具体的，根据发送序列里节点类型的不同，添加固定监督节点和信息监督节点来加强信息传输的可靠度，以提高译码的精度。仿真结果表明，与原始的连续删除算法相比，改进算法通过增加监督节点译码的计算量，从而提高了其译码的性能。

连续删除算法；可靠度；监督节点；极化码

0 引 言

通过信道极化的理论分析[1-2]，Arikan证明极化码可以获得Shannon理论极限性能，并且保持对数编译码复杂度。然而，研究表明，和传统的Turbo码、LDPC码相比，极化码在码长受限时，误码性能还不理想。为了推进极化码在工程上的应用，许多高性能译码算法被相继提出。

连续删除（Successive Cancellation，SC）算法由Arikan首次提出，利用比特信道似然概率的硬判决值输出译码序列，根据信道的拆分进行迭代计算。目前，所提出的译码算法主要分为两类：一类是基于SC的改进算法，如简化的SC（Simplified SC，SSC）、基于堆栈SC（SC Stack，SCS）、基于序列的SC（SC List,SCL）以及基于循环冗余校验（Cyclic Redundancy Check）辅助的SCL（CRC-SCL）串行译码算法；另一类是基于置信度传播（Belief Propagation，BP）的并行译码算法[3-7]。

传统的SC译码算法具有延迟大、精度不高等

缺陷，性能并不理想。改进的SC算法通过添加监督节点的方法来提高信息传输的可靠性，改善误码性能，并通过建立可靠条件，对码字进行信息纠错，一定程度上抑制了突发错误的出现。

1 极化码

极化码的待编码序列u1N由两部分构成：一部分为有效信息序列（uA）；一部分为对于编译码均已知的固定序列（）。固定序列的元素取值已知，根据信道极化理论，信道容量高的子信道发送信息位，信道容量低的子信道发送冻结比特。因为冻结比特的元素取值已知，所以Polar编码器某些中间节点也是已知的。图1为码长N=8的编码器结构，左边为编码输入端，右边为编码输出端，信息序列和固定比特序列分别为：uA={u4,u6,u7,u8}和={u1,u2,u3,u5}={0,0,0,0}；节点p(0,1)、p(0,2)、p(0,3)、p(0,5)、p(1,1)、p(1,5)取值已知。其中，p(1,1)、p(1,5)冻结比特产生中间节点。由于极化码生成矩阵GN逆矩阵等于本身[1]，所以极化码译码器具有与编码器相同的结构。受固定节点的影响，Polar译码器同样存在固定节点。

图1 N=8的Polar编码器

2 连续删除算法

SC算法是一种串行译码方法，其第i次译码依赖于前i-1次的译码结果。译码结束时，需要更新访问O(Nlog2N)个节点，算法的时间和空间复杂度均为O(Nlog2N)。整个译码过程可以分为三个阶段。

阶段1：初始化。经过噪声干扰后，接收端y=(y1,y2,…,yn)码字序列，每一个子信道都有一个似然比

阶段2：按照串行译码顺序，计算第i个比特信道的概率：

3 改进的连续删除算法

改进的SC译码算法基于固定序列，对于这个编译码序列是已知的，独立于整个译码过程。只要码率R＜1，Polar译码器就会存在已知的冻结比特，在SC译码无误的情况下，这些固定节点[8]需满足条件：

根据式（5）能够判断vi节点是否正确。为了便于表示，下文称式（5）为可靠度条件[9]。

在SC译码过程中，固定节点消息与信息节点消息同时进行迭代更新。迭代的同时，固定节点消息值同样会随着信道观测序列变化。由于高斯噪声的干扰，固定节点一定会出现不满足上述可靠度条件的情况，从而导致错误积累，影响后面译码的准确性。因此，本文提出给SC译码器中每个处理节点增加一个监督节点，用于修正每个节点的可靠性，提高译码的准确性，如图2所示。

图2 码长为8添加监督节点的Polar译码器

按照被发送序列中存在的不同类型节 点，监督节点分为两类：黑色节点为固定序列的监督节点，白色节点为信息序列的监督节点。监督节点自身消息固定且不能进行迭代更新。通过监督节点修正后，奇数时，迭代关系式如式（6）；偶数时，迭代关系式如式（7）。

添加的监督节点用以加强可靠度条件，因此固定序列的监督节点必须满足条件：

通过分析，存在关系式：

图3 SC译码算法路径搜索过程

信息监督节点不像固定监督节点，能够通过可靠度条件来检测消息节点消息是否存在错误，并通过加强固定序列的可靠性提升信息序列的译码能力。所以，在定义信息监督节点时应该满足：

通过式（10）可知，信息监督节点没有影响信息节点的似然比，不会影响信息节点消息的可靠度。

可见，在整个串行译码过程中，通过添加监督节点可加强固定序列的可靠度，从而保持信息序列的可靠度。一定程度上，监督节点的信息纠错能力提升了译码性能。

4 仿真结果

仿真中，物理信道假设为AWGN信道，采用BPSK调制方法，码长为N=32，码率R=0.5，设定一个信噪比为一次仿真实验，接收端按照数据帧来统计误比特率，每帧数据长度为码字的信息比特长度。每次实验的错误比特数不少于100，帧数少于100 000。为了评估所提算法的性能，对原始SC算法进行仿真，仿真结果如图4所示。

图4 不同译码算法对比

由图4可见，改进的SC算法的误比特率优于SC算法，表明增加监督节点能够有效提高SC消息传播的可靠度。通过提高冻结比特的可靠度，在迭代译码过程中保证了固定节点消息值不受信道观测序列的变化影响，始终满足从而提高译码性能。同时，监督节点通过式（9）修正，仅仅通过分子分母同时相乘校正因子来提高硬判结果，并没有改变迭代算法的复杂度，每次译码访问的节点数仍为O(Nlog2N)。该算法能够提升极化码SC的译码性能，但是依赖于监督节点的消息。

5 结 语

极化码是编码领域较新的一个课题，是目前唯一能够在BDMC上证明达到Shannon极限的码字，代表了未来通信发展的一个方向。增加监督节点连续删除算法在牺牲计算量的基础上，译码性能得到了一定提升，通过固定监督节点的可靠性消息的传播来保证译码的正确性。仿真结果表明，改进的SC算法的译码性能比原SC算法好。本文只是讨论了固定序列的可靠性条件，对消息序列的可靠性条件尚未开展讨论，下一步工作将在于如何确定所有的冻结比特始终能够满足可靠度条件。

[1] ArikanE. Channel Polarization: A Method for Constructing Capacity-achieving Codes for Symmetric Binary-input Memoryless Channels [J].IEEE Transactions onInformation Theory,2009,52(02):3051-3073.

[2] Arikan E.Channel Combining and Splitting for Cutoff Rate Improvement[C].In Proc. of IEEE Int. Symp. Inf. Theory2005,2005:671-675.

[3] 李斌,王学东,王继伟.极化码原理及应用[J].通信

技术,2012,45(10):21-23. LI Bin,WANG Xue-dong,WANG Ji-wei.Theory and Application of Polar Code[J].Communications Technology,2012,45(10):21-23.

[4] I Tal,A Vardy. List Decoding of Polar Codes[C]. IEEE International Symposium on Information Theory,2012,61(05):1-5.

[5] K Niu,K Chen. CRC-Aided Decoding of Polar Codes [J]. IEEE Communications Letters,2012,16(10):1668-1671.

[6] K Niu,K Chen.Stack Decoding of Polar Codes [J]. Electronics Letters,2012,48(12):695-697.

[7] Huang Z. L.,Diao C. J.,Chen M.Latency Reduced Method for Modified Successive Cancellation Decoding of Polar Codes[J].Electronics Letters,2012,48(23):1506-1506.

[8] Leroux C.,Raymond A.J.,Sarkis G.A.Vardy and Hardware Implementation of Successive-cancellation Decoders for Polar Codes [J].Journal of Signal Processing Systems,2012,69(03):305-315.

[9] Zhang Y.X.,Liu A.J. A Modified Belief Propagation Polar Decoder[J].IEEE. Communications Letters 2014,18(07):1091-1094.

李 纯（1989—），男，硕士，助理工程师，主要研究方向为卫星通信；

关成涛（1982—），男，学士，工程师，主要研究方向为现代通信技术。

A Modified Successive Cancellation Polar Decoder

LI Chun,GUAN Cheng-tao
(Xichang Satellite Launch Center,WenchangHainan571300,China)

In this paper, a modified successive cancellation (SC) polar decoder is proposed. Unlike the original SC polar decoders, a check node is added to each node of the proposed decoder. Both categories are augmented with a check node, referred to as a frozen check (FC) node or an information check node, depending on the type of the node to be checked. In the modified SC decoding, the messages passed from a node will be modified by multiplying the messages from the check node, so as to enhance the reliability of the propagated messages and to increase the decoding accuracy.The main consideration of our work is how to ensure that all the frozen nodes satisfy the reliability condition. Simulation results are given to show that the proposed decoder achieves better performance than of the original SC decoders, only at the expense of some additional multiplications, which reinforce its effectiveness.

Successive cancellation (SC) decoding;Reliability condition;Check node;Polar codes;

TN911.3

：A

：1002-0802(2016)-06-0683-04

10.3969/j.issn.1002-0802.2016.06.007

2016-02-03;

：2016-05-02 Received date:2016-02-02;Revised date:2016-05-02