Polar码的编码原理

Polar码的编码原理王俊南107551500910所讲内容：1.Polar码简介2.信道极化2.1信道组合2.2信道分解2.3信道极化定理2.4极化速率3.Polar码编码1.Polar码简介1948年，Shannon在他的开创性论文“通信的数学理论”中第一次提出了在有噪信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错编码的基础。20世纪50年代初，汉明（Hamming）、斯列宾（Slepian）、普兰奇（Prange）等人在香农的基础上，设计出了一系列的性能优异的编译码方案，并以此为基础得出了编码信道下各种信道情况的香农限。香农限作为通信系统中的性能极限，具有非常重要的意义。纠错码的快速发展，促使了编码下的香农限的提出，也带动了通信领域中设计和构造逼近香农限的纠错码的研究。目前研究成果最多、比较成熟的逼近香农限的纠错码是LDPC码和Turbo码；虽然两种码字的性能已十分优异，但人们一直坚持寻找性能更加好，可以达到香农限并且编译码简单的编码方法。Polar码是由E.Arikan于2007年基于信道极化理论提出的一种线性信道编码方法，该码字是迄今发现的唯一一类能够达到香农限的编码方法，并且具有较低的编译码复杂度，当编码长度为N时，复杂度大小为O(NlogN)。Polar码的核心思想就是信道极化理论，不同的信道对应的极化方法也有区别。Polar码自从提出以来，就一直吸引了众多学者的兴趣，是这几年信息领域研究的热点。2.1信道极化Polar码的理论基础就是信道极化。信道极化包括信道组合和信道分解部分。当组合信道的数目趋于无穷大时，则会出现极化现象：一部分信道将趋于无噪信道，另外一部分则趋于全噪信道，这种现象就是信道极化现象。无噪信道的传输速率将会达到信道容量I(W)，而全噪信道的传输速率趋于零。Polar码的编码策略正是应用了这种现象的特性，利用无噪信道传输用户有用的信息，全噪信道传输约定的信息或者不传信息。1、信道组合信道组合就是对给定的B-DMC（Binary-inputDiscreteMemotylessChannel）信道W利用递归的方法，来构造一个组合信道。当n=0，W1=W；当n=1，就是利用两个相互独立的信道W1递归组合成信道，如图2.1所示。信道W2对应的传输概率为：（1.1）当n=2时，利用两个独立的W2信道来组合成W4信道：，组合步骤如图2.2，对应的传输概率公式为：（1.2）在图2.2中，R4是把序列(s1,s2,s3,s4)映射成v=(s1,s2,s3,s4)的排列操作。信道W4的输入序列u到信道W的输入序列X的映射关系ux可以表示为：414144141→41并且，。所以，可以得出W4的转移概率表达式为（1.4）依此类推，可以得出信道组合的一般递推关系，如图2.3，由两个独立的信道组成信道。的输入序列首先会被转化成序列，对应的关系为，（1.5）其中，1≤i≤N/2。代表一种翻转操作，作用于序列作为信道的输入序列。（1.4）图2.3中从信道到信道的映射是线性的，定义矩阵表示这种映射关系，矩阵称为生成矩阵。则可以推到出之间的转移概率关系为：（1.6）其中，是比特翻转操作，核心矩阵，符号⊗代表Kronecker积（张量积）。对于矩阵A与B的张量积定义为。假设A，B分别是m×n，r×s的矩阵，，则（1.7）则，（1.8）2、信道分解在完成组合信道之后，信道极化的下一个步骤是信道分解，把信道分解成N个二进制输入信道，对应的转移概率定义为（1.9）其中，。由公式（2.9）可知，当N=2时，信道分解的情况为对应的转移概率公式为（1.10）（1.11）当N=2时的信道分解图如图2.4所示。图2.5、2.6分别对应N=4，N=8时的信道分解方式。从这三幅图中可以看出，分解过程也是一个递归的过程。当N=4时首先被分解成两个相互独立的信道,然后再将W2分解成两个相互独立的W。当N=8时，也可依此类推。（1.12）（1.13）（1.14）当基本信道W是BEC信道的特殊情况下，在满足一些定理前提下,可通过如下递推公式计算，（1.15）（1.16）2.2Polar码编码为了利用信道极化的效果，构造了一种能够达到对称信道容量I(W)的编码方法，称为Polar码。Polar码的基本思想就是：能够单独处理每一个信道并且使用趋于零的信道来传输信息。那么如何选择好的信道来传输信息就是Polar码编码的关键。Polar码是一种线性分组码，有效信道的选择也就对应着生成矩阵的行的选择。下面首先详细介绍Polar码的编码过程。Polar码是一种线性分组码，编码公式与别的线性分组码类似，由信息序列乘以生成矩阵，具体公式如下，（1.17）其中，是将要传输的信息序列，就是生成矩阵，。假设A是集合的任意子集，公式（1.17）可以写成如下形式，（1.18）其中，矩阵是由A决定的矩阵的子矩阵，是去掉的矩阵，也是的矩阵。如果固定A和，但是任意变量，那么就可以把源序列映射到码字序列，这种映射关系称为陪集编码（CosetCode）。Polar码就是陪集码的例子，由四个参数共同决定的陪集码，N表示码字的码长，K表示信息位的长度；A对应着生成矩阵中用来传输有用信息的行，即中的行，并且A中元素个数等于K；称为冻结位，用来传输固定的信息，即对应着性能较差的比特信道；码率R=K/N。例，Polar码的编码参数为，则具体的编码映射关系为（1.19）给定源信息序列，则对应的码字为。由以上Polar码的编码理论可知，最重要的就是寻找性能好的信道，即对应值较小的信道，也是序列A中元素的值。下面以N=16为例来说明如何来选择信道的。（1.20）取初值，由公式（2.15）和（2.16）可计算出，具体各项值是：。对序列进行降序排列，选取值最小的4个比特信道，这四个信道对应的行号的组成集合A，。则在矩阵中集合A对应的行构成。（1.21）同理，通过矩阵和可得出。在给定输入信息序列后就可编出16位的Polar码码字。谢谢大家！不足之处，还望见谅！