Polar码的编码原理

1、Polar码的编码原理,王俊南 107551500910,所讲内容：,1.Polar码简介 2.信道极化 2.1信道组合 2.2信道分解 2.3信道极化定理 2.4极化速率 3.Polar码编码,1.Polar码简介 1948 年，Shannon 在他的开创性论文“通信的数学理论”中第一次提出了在有噪信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错编码的基础。20 世纪 50 年代初，汉明（Hamming）、斯列宾（Slepian）、普兰奇（Prange）等人在香农的基础上，设计出了一系列的性能优异的编译码方案，并以此为基础得出了编码信道下各种信道情况的香农限。香农限作为通信

2、系统中的性能极限，具有非常重要的意义。纠错码的快速发展，促使了编码下的香农限的提出，也带动了通信领域中设计和构造逼近香农限的纠错码的研究。目前研究成果最多、比较成熟的逼近香农限的纠错码是 LDPC 码和 Turbo 码；虽然两种码字的性能已十分优异，但人们一直坚持寻找性能更加好，可以达到香农限并且编译码简单的编码方法。 Polar码是由E. Arikan于2007年基于信道极化理论提出的一种线性信道编码方法，该码字是迄今发现的唯一一类能够达到香农限的编码方法，并且具有较低的编译码复杂度，当编码长度为N时，复杂度大小为 O ( NlogN)。Polar码的核心思想就是信道极化理论，不同的信道对应

3、的极化方法也有区别。Polar码自从提出以来，就一直吸引了众多学者的兴趣，是这几年信息领域研究的热点。,2.1 信道极化 Polar 码的理论基础就是信道极化。信道极化包括信道组合和信道分解部分。当组合信道的数目趋于无穷大时，则会出现极化现象：一部分信道将趋于无噪信道，另外一部分则趋于全噪信道，这种现象就是信道极化现象。无噪信道的传输速率将会达到信道容量 I (W )，而全噪信道的传输速率趋于零。Polar 码的编码策略正是应用了这种现象的特性，利用无噪信道传输用户有用的信息，全噪信道传输约定的信息或者不传信息。 1、信道组合 信道组合就是对给定的B-DMC（Binary-input Disc

4、rete Memotyless Channel）信道W利用递归的方法，来构造一个组合信道 。当n=0，W 1= W；当n=1，就是利用两个相互独立的信道W 1递归组合成信道 ，如图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 的映射关系u x 可以表示为：,并且， 。所以，可以得出W4的转移概率表达式为 （1.4） 依此类推，可以

5、得出信道组合的一般递推关系，如图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、信道分解 在完成组合信道 之后，信道极化

6、的下一个步骤是信道分解，把信道 分解成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信道的特殊情况下，在满足一些定理前提下, 可通过如下递

7、推公式计算， （1.15） （1.16） 2.2 Polar 码编码 为了利用信道极化的效果，构造了一种能够达到对称信道容量 I (W )的编码方法，称为 Polar 码。Polar 码的基本思想就是：能够单独处理每一个信道 并且使用 趋于零的信道来传输信息。那么如何选择好的信道来传输信息就是 Polar 码编码的关键。,Polar 码是一种线性分组码，有效信道的选择也就对应着生成矩阵的行的选择。下面首先详细介绍 Polar 码的编码过程。 Polar 码是一种线性分组码，编码公式与别的线性分组码类似，由信息序列乘以生成矩阵，具体公式如下， （1.17） 其中， 是将要传输的信息序列， 就是生

8、成矩阵， 。 假设 A 是集合 的任意子集，公式（1.17）可以写成如下形式， （1.18） 其中，矩阵 是由 A 决定的矩阵 的子矩阵， 是 去掉 的矩阵，也是 的矩阵。 如果固定 A 和 ，但 是任意变量，那么就可以把源序列 映射到码字序列 ，这种映射关系称为陪集编码（Coset Code）。Polar 码就是陪集码的例子，由四个参数 共同决定的陪集码，N 表示码字的码长，K 表示信息位的长度；,A 对应着生成矩阵 中用来传输有用信息的行，即 中的行，并且 A 中元素个数等于 K； 称为冻结位，用来传输固定的信息，即对应着性能较差的比特信道；码率 R=K/N。 例，Polar 码的编码参数为 ，则具体的编码映射关系为 （1.19） 给定源信息序列 ，则对应的码字为 。 由以上 Polar 码的编码理论可知，最重要的就是寻找性能好的信道，即对应 值较小的信道，也是序列 A 中元素的值。下面以 N=16 为例来说明如何来选择信道的。,（1.20）,取初值 ，由公式（2.15）和（2.16）可计算出 ，具体各项值是： 。对 序列进