“太极混一”——极化码原理及5G应用

牛凯

摘要：极化码是第一种达到信道容量的构造性编码，已列入5G移动通信的控制信道编码标准，这是信道编码领域近年来的重大突破。旨在阐述极化码的基本原理与5G中的应用。基于信道极化观点，分析了极化码蝶形编码结构与基本的串行抵消译码算法，提出了级联极化编码结构，并归纳了高性能译码算法的特点。另外，还深入分析了5G移动通信中极化码设计的基本思想，概括了极化码实用编码的3种方式：凿孔、缩短与重复。最后，指出极化信息处理是未来通信系统优化的新型方法。

关键词：极化码;信道极化;串行抵消译码;串行抵消列表译码;串行抵消堆栈译码;极化信息处理

Abstract： Polar code is the first error control code achieving the channel capacity and has been accepted as the coding scheme of the control channels of the 5G wireless communication systems， which is the great breakthrough of the channel coding field in recent years. In this paper， the primary principle of the polar code and the application in 5G systems are surveyed. First， based on the viewpoint of channel polarization， the butter-fly structure of polar coding and successive cancellation decoding are analyzed. Then， the concatenated polar code is proposed and the characteristics of high-performance decoding algorithms are summarized. Furthermore， the design of polar codes in 5G systems is addressed and three practical coding schemes of polar codes are overviewed， which is puncturing， shortening and repetition. In the end， it is pointed out that polar coded information processing will become the new diagram of the communication system optimization in the future.

Key words： polar code; channel polarization; successive cancellation decoding; successive cancellation list decoding; successive cancellation stack decoding; polar coded information processing

1948年，信息論创始人C. E. Shannon在经典文献[1]中，提出了著名的信道编码定理。70年来，构造逼近信道容量的编码是信道编码理论的中心目标。近20年来，虽然以Turbo与低密度校验码（LDPC）为代表的信道编码具有优越的纠错性能，但难以从理论上证明这些码渐近可达信道容量。2009年，土耳其学者E. Ar?kan在文献[2]中提出了极化码的设计思想，首次以构造性方法证明信道容量渐近可达。由于在编码理论方面的杰出贡献，该论文获得了2010年电子和电气工程师协会（IEEE）信息论分会的最佳论文奖，引起了信息论与编码学术界的极大关注。

极化码发明近10年来，成为信道编码领域的热门研究方向，其理论基础已经初步建立，人们对极化码的渐近性能有了深入理解。特别是2016年底，极化码入选5G移动通信的控制信道编码候选方案，并最终写入5G标准[3]，极大推动了极化码的应用研究。

1 极化码原理

本节我们将详细介绍极化码的基本原理，包括信道极化原理、极化码构造算法以及极化码的基本译码算法与增强型译码算法。

1.1 信道极化与编码

极化码的构造依赖于信道极化现象，我们首先介绍信道极化的基本原理，然后概述极化码的编码过程。

（1）信道极化。

所谓信道极化，最早由E.Ar?kan引入[2]，是指将1组可靠性相同的二进制对称输入离散无记忆信道（B-DMC）采用递推编码的方法，变换为1组有相关性的、可靠性各不相同的极化子信道的过程，随着码长（即信道数目）的增加，这些子信道呈现两极分化现象。图1给出了二元删余信道（BEC）的信道极化演进示例。

令B-DMC信道转移概率为[Wyx]，则信道互信息与可靠性度量（Bhattacharyya参数，简称巴氏参数）定义如公式（1）：

[ZW=y∈YWy0Wy1]。  （2）

图1 a）给出了删余率为0.5的BEC信道的映射关系[W：X∈0，1→Y]，其信道互信息为[IW=0.5]，巴氏参数[ZW=0.5]。

图1 b）是2信道极化过程，[u1，u2∈0，1]是输入信道的两比特，[x1，x2∈0，1]是经过模2加编码后的两比特，分别送入信道后得到[y1，y2∈Y]2个输出信号。对应的编码过程可以表示为：

[x1，x2=u1，u21011=u1，u2F]。  （3）

通过矩阵[F]的极化操作，将一对独立信道[W，W]变换为2个相关子信道[W-，W+]。其中，[W-：X→Y2]，[W+：X→Y2×X]，其信道输入输出关系分别如图1 b）中绿线和粉线所示。这2个子信道的信道互信息与可靠度量满足公式（4）的关系：

[IW-≤IW≤IW+ZW-≥ZW≥ZW+]。  （4）

由于[IW-=0.25

上述编码过程可以推广到4信道极化，如图1 c）所示。此时，每2个[W-]信道极化为[W--]与[W-+]2个信道，每2个[W+]信道极化为[W+-]与[W++]2个信道。这样原来可靠性相同的4个独立信道变换为可靠性差异更大的4个极化信道。

信道极化变换可以递推应用到[N=2n]个信道，给定信源序列[UN1]与接收序列[YN1]，序列互信息可以分解为多个子信道互信息之和，即满足公式（5）中的关系：

其中，[IUi;YN1Ui-11]是第[i]个极化子信道的互信息，相应的信道转移概率为[WiNYN1Ui-11Ui]。这就是信道极化分解原理，其本质是通过编码约束关系，引入信道相关性，从而导致各个子信道的可靠性或容量差异。图1 d）给出了码长[N=20～28]时，极化子信道互信息的演进趋势。其中，每个节点的上分支表示极化变换后相对好的信道（红线标注），下分支表示相对差的信道（蓝线标注）。显然，随着码长增长，好信道集聚到右上角（互信息趋于1），差信道集聚到右下角（互信息趋于0）。

E. Ar?kan证明了当信道数目充分大时，极化信道的互信息完全两极分化为无噪的好信道（互信息趋于1）与完全噪声的差信道（互信息趋于0），并且好信道占总信道的比例趋于原始B-DMC信道[W]的容量[IW]，而差信道比例趋于[1-IW][2]。

（2）极化编码。

极化码有2种基本编码结构，即非系统码与系统码。下面我们简述各自的结构特点。

首先，根据信道极化的递推过程，可以得到非系统极化码的编码结构。令[uN1=u1，u2，...，uN]表示信息比特序列，[xN1=x1，x2，...，xN]表示编码比特序列，E. Ar?kan证明[2]编码满足公式（6）：

[xN1=uN1GN]， （6）

其中，编码生成矩阵[GN=BNF?n]，[BN]是排序矩阵，完成比特反序操作，[F?n]表示矩阵[F]进行[n]次Kronecker积操作。

图2给出了码长[N=8]，码率[R=0.5]的极化码编码器的示例。由图2可知，对于非系统极化码，根据巴氏参数选择可靠性高的[u4，u6，u7，u8]作为信息比特，信息位长度为4，而可靠性较差的[u1，u2，u3，u5]作为固定比特，取值为0。经过3级蝶形运算，可以得到编码比特序列[x81]。对于系统极化码，则需要将信息位承载在[x4，x6，x7，x8]，对应的编码器左侧输入（信源侧）比特则通过代数运算[4]确定取值。由于采用蝶形结构编码，极化码的编码复杂度则可表示为[ONlogN][2]。

（3）实用化极化编码。

笔者在文献[5]中提出了循环冗余校驗（CRC）-Polar级联方案，如图3所示。由[k]个信息比特组成的序列首先送入CRC编码器，级联[m]个CRC校验比特后送入极化码编码器，产生[N]比特码字。这种级联编码方案，以CRC编码作为外码，极化码作为内码，具有显著的性能增益，目前已经成为极化码的主流编码方案。

由于极化码原始码长限定为2的幂次，即[N=2n]，而实际通信系统往往要求任意码长编码。为了满足这一要求，需要设计极化码的速率适配方案，主要包括凿孔、缩短、重复3种操作。假定速率适配后的码长为[M

笔者在文献[6]中提出了准均匀凿孔（QUP）适配方案，并进一步在文献[7]中提出了反向准均匀缩短（RQUS）适配方案。其中，QUP是凿孔方案，适用于低码率的情况;RQUS是缩短方案，适用于高码率的情况。可以证明，QUP与RQUS方案是理论最优的速率适配方案[7]，并且RQUS与文献[8]中提到的缩短方案等价。

1.2 极化码构造

极化码构造算法的目的是精确计算各个子信道的互信息或可靠性，然后从大到小排序，选择其中好的子信道集合承载信息比特;因此，构造算法是极化码编码的关键。

E. Ar?kan最早提出基于巴氏参数的构造算法[2]。假定初始信道的巴氏参数为[ZW]，则从[N]扩展到[2N]个极化信道的迭代计算过程如公式（7）：

[ZW2i-12N=2ZWiN-ZWiN2ZW2i2N=ZWiN2]。（7）

这种构造算法复杂度较低，但只适用于BEC信道，对于其他信道，例如二元对称信道（BSC）、加性白噪声信道（AWGN）等，该方法并非最优。

Mori基于密度进化（DE）方法，得到了BSC、AWGN信道下最优的子信道选择准则[9]，但由于涉及到变量与校验节点比特LLR概率分布计算，计算复杂度很高，限制了其应用。更好的方法是I. Tal与A. Vardy提出的迭代算法[10]，通过引入极化子信道的上下界近似，该方法能以中等复杂度保证较高的计算精度，但码长很长时，其计算复杂度也会变大。

P. Trifonov所提出的高斯近似（GA）算法[11]是目前较流行的构造方法。给定AWGN信道的接收信号模型为[yi=si+ni，i=1，2，…，N]，噪声功率为[σ2]，则接收比特的LLR[Lyi?N2σ2，4σ2]服从高斯分布。信道极化的LLR均值迭代公式为：