信道极化与Polar码构造

唐嘉麒

(广东省电信规划设计院有限公司 移动咨询设计院云南项目部，云南 昆明 630299)



信道极化与Polar码构造

唐嘉麒

(广东省电信规划设计院有限公司 移动咨询设计院云南项目部，云南 昆明 630299)

摘要：极化码是一种基于信道极化现象的容量可达的新型编码技术。该文从信道极化原理入手，介绍信道极化现象及极化信道模型，详细阐述了线性陪集的极化码构造方法，给出了串行抵消译码算法的具体实现流程和仿真结果。

关键词：信道极化；极化码；串行抵消译码算法

香农第二定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有可能实现任意可靠的信息传输。这个存在性定理揭示出，我们可以用接近信道容量的传输速率进行通信。香农在证明该定理时，为了保证码字本身具有很好的纠错能力，采用了无穷码长的随机编码的思想，同时采用最大似然译码算法充分发挥码的纠错性能。然而，这在实际中是无法实现的，因为采用随机编码会使码长度趋于无穷大，而且采用最大似然译码算法进行译码会使系统的复杂度变高，在程序上难以实现[1]。

在随后的研究中发现，最终能够逼近香农容量限的Turbo码和LDPC码，都部分使用了随机编码的思想[2]。LDPC码以其瀑布区域良好的性能，已经成为了新一代卫星通信中的信道编码方案。尽管这些信道编码技术被统一纳入因式图的理论框架，采用迭代译码技术，能够逼近香农极限，具有优越的纠错性能。但其编译码的理论基础尚不完备，如何证明这些码具有渐进最优性能非常困难[3]。2009年，Arikan提出信道极化码(polar codes)的设计思想[4]，基于信道极化(channel polarization)现象，首次以构造性的方法分析了编码的渐进性能，引起了信息论与编码学术界的极大关注。

Polar 码是一种新的信道编码方案，它是基于信道极化理论提出的一种线性分组码。理论上，它在低译码复杂度下能够达到信道容量且无错误平层[5]，而且当码长N增大时，其优势会更加明显。

1信道极化原理

Arikan针对一组独立的二进制对称输入离散无记忆信道(B-DMC)，提出了采用编码的方法，使各个子信道呈现出不同的可靠性，随着码长(即信道数目)的增加，这些子信道呈现两极分化现象，称为信道极化。研究发现，信道的极化现象是普遍存在的。

1.1信道参数

在信道极化的描述中，存在两个极为重要的参数——对称容量(Symmetriccapacity)和巴塔恰利亚系数(Bhattacharyyaparameter)，分别描述如下：

(1)

(2)

对称容量表达的是信道的速率，而巴氏系数则反映了信道的可靠性。

1.2信道极化模型

假设B-DMC信道W：对于两个信道极化，是信道的输入比特，是信道的输出比特，如图1所示。

由图1可以看出，数据在极化信道的传输分为编码、传输两个步骤。显然，编码部分存在如下关系：

(3)

四个信道的极化模型如图2所示，其编码关系由式(4)给出，G4是生成矩阵。

图1　两信道的极化模型

图2　四信道的极化模型

(4)

值得注意的是，在图2中显然存在一个位置交换的结构，称为比特翻转。因此，G4与F之间存在如下关系，其中BN是比特翻转矩阵，运算F⊗F是克罗内克积。

G4=B4F⊗2

(5)

推而广之，当信道数目增加到N(=2n)时，生成矩阵可表达为

GN=BNF⊗n

(6)

1.3信道极化现象

(7)

(8)

2Polar码构造方法

Arikan提出了一种线性陪集的Polar码构造方法——从N个信道中选择信道质量较好的一部分作为信息传输信道，剩余部分作为冻结比特传输信道，并用式(9)完成编码。

(9)

信道质量可以采用1.1节中提出的对称容量或者巴氏系数来衡量，Arikan采用的是后者。本文采用前者(BEC方法)来作为衡量指标，构造任意码率R的Polar编码算法如下：

图3　N=1 024时的信道极化现象

1)用式(7)及式(8)计算信道容量值I(W)；

2)将I(W)按值从大到小排序，排序过程中用标记数组flag记录原信道的索引值，保持两个数组同一下标记录的值对应同一个子信道；

3)flag中的前N×R个记录就是该信道下需要找出的信息位下标，存入A中，剩余部分存入Ac中；

4)构造生成矩阵GN，从中选取A所对应的行构造G(A)，其余部分构造G(Ac)；

5)冻结比特序列uA，全部置0，用式(9)完成编码。

值得注意的是，在构造生成矩阵GN时，如果采用了比特翻转，译码结果即为信息序列，否则在译码时则需比特翻转。下面以ε=0.5，uA=(1，1，0，1)的Polar编码为例，给出(8,4,A,(0,0,0,0))编码的结果，其中A={4，6，7，8}。

(10)

3基于串行抵消(SC)的Polar译码算法的实现

(11)

(12)

(13)

图4　SC译码算法流程

值得一提的是，图4所示的算法中设计了一个位置标志序列z。该标记序列是一个二进制向量，明确指示了码字中的信息位(“1”表示)和冻结位(“0”表示)。译码时当识别到某一位符号zi=0时，即认定为冻结位，对应的比特直接译码为ui=0。由于在编码过程中，采用了比特翻转，其译码结果即为最终结果。

4Polar码的可靠性评价

Polar码是一种“容量可达”而非“逼近”的结构化编码方式，并且译码性能不存在错误平层。本节利用误块率(BlockErrorRatio,BLER)和巴氏系数来衡量Polar码的SC译码可靠性。

(14)

(15)

假设码率为R，码长为N，信息信道的个数|A|=K=N×R，误块率的上下界可以分别由式(16)和(17)表示。

(16)

(17)

图5给出了码长分别为210、215、220时，删除概率ε=1/2的BEC信道误块率上下界。显然，当码长增大时Polar码是容量可达的。另外，如果码率足够小，采用SC译码实现容量可达的Polar码是完全可行的。图6给出了码长为N=256时的误块率仿真曲线。

图5　码长分别为210、215、220时，删除概率ε=1/2的BEC信道误块率

5结束语

Polar码是一种依赖于信道极化现象的全新编码方式，具有编译码简单、可靠性高等特点，然而译码算法局限于串行译码的瓶颈。另外，Polar码与LDPC码和Turbo码一样，是基于有限域的编码方法，其码长也受到2n的限制。译码算法的并行化，码长的自由化以及欧式域的编码拓展已成为目前研究的重点。

图6　码长N=27时，删除概率ε=1/2的BEC信道误块率

参考文献：

[1]孙叶.基于SC算法的Polar码译码性能研究[D].西安：西安电子科技大学，2013.

[2]李斌，王学东，王继伟.极化码原理及应用[J].通信技术，2012，45(10)：21-23.

[3]李桂萍，任华，刘小航.信道极化与极化码的研究进展与展望[J].科学技术与工程，2014，14(1)：132-138.

[4]ERDAL Arikan. Channel polarization：a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J].IEEE Transactions on Information Theory，2009，55(7)：3 051-3 073.

[5]SARKIS Gabi，GIARD Pasca，VARDY Alexander，et al.Fastpolar decoders：algorithm and implementation[J].IEEE Journal on Selected Areas in Communications，2014，32(5)：946-957.

A Study on the Channel Polarization and Construction of the Polar Code

TANG Jiaqi

(Yunnan Mobile Support Center of Mobile Communications Consulting and Design Institute of Guangdong Planning and Designing Institute of Telecommunications Co., Ltd.，Kunming Yunnan650299，P.R.China)

Abstract：The polar code is a new capacity-achieving coding technology based on the channel polarization．Based on its principle，this article introduces the channel polarization and the polarized channel model，expounds the construction method of the polar code based on the linear coset，and gives the implementation process and simulation result of the successive cancellation decoding algorithm．

Key words：channel polarization；polar code；SC decoding algorithm

收稿日期：2015-10-30

作者简介：唐嘉麒(1986-)，工程师，研究方向为无线通信技术。

中图分类号：TN911.22

文献标识码：A

文章编号：1008-8032(2016)02-0049-04