本科生在学习极化码时，并不是件简单的事情。网上极化码的资料很少，而且基本上都是较难的论文。这篇文章是用来帮你快速入门极化码。
Polar码背景2015 年，国际电信联盟无线通信部（International Telecommunication Union-Radio Communications Sector，ITU-R）明确了未来 5G三大典型应用场景，分别为：
增强型移动宽带（enhanced mobile broadband，eMBB）场景。要求支持更高的传输速率（峰值速率：上行链路达到 10 Gbit/s，下行链路达到 20 Gbit/s）、更高的频谱效率（峰值频谱效率：上行链路达到12 bit/(s·Hz)，下行链路达到 30 bit/(s·Hz)）等。
大规模机器类通信（massive machine type communication，mMTC）。要求支持更大连接数密度（(1×10^6)个连接(/km^2)）、更低能耗（终端电池使用寿命达到 15 年）；
场景和超高可靠性低时延通信（ultra-reliable and low latency communication，uRLLC）场景。要求支持更低的时延（上下行链路时延 0.5 ms，即端到端时延低于 1 ms）、更高的可靠度（达到 99.9999%，即 1 ms 内的误帧率低于(10^{-6})）、更低的错误平层等。
而4G 中采用的信道编码方案 Turbo 码因在可靠性（Turbo 码存在译码错误平层）、编译码复杂度、译码吞吐量和编码效率等方面难以有效满足 5G 场景下的各种性能要求。亟需为 5G 新空口（new radio，NR）设计更加先进高效的信道编码方案，以尽可能小的业务开销实现信息快速可靠传输。
目前，国内外研究机构已针对 5G 信道编码技术开展了大量研究，并已达成部分共识。Polar 码因其理论证明可达到香农极限，且具有可实用的线性复杂度编译码能力而受到业界重视，成为5G NR信道编码方案的强有力候选者。在 2016 年 11 月召开的 3GPP RAN1#87 次会议上确定eMBB场景的 5G 短码块信道编码方案采用 Polar 码作为控制信道编码方案。
Polar码概述2008 年，土耳其毕尔肯大学 Arikan 教授在国际信息论（International Symposium on Information Theory，ISIT）会议上首次提出信道极化（channel polarization）的概念。Polar码的核心思想是信道极化，不同的信道对于极化方法也有区别。
2009 年，Arikan教授在中对信道极化进行更为详细的阐述，并基于信道极化思想提出一种新型信道编码方法，即 Polar 码。 Arikan 分析了 Polar 码的极化现象，并给出 Polar 码在二元删除信道（binary erasure channel，BEC）中的具体构造方法以及编译码过程。
考虑到 Arikan E 给出的 Polar 码构造方法仅适用于 BEC 信道，具有较大的局限性，Mori 和 Tanaka 等人借鉴低密度奇偶校验（low-density parity-check，LDPC）码的构造方法，提出采用密度进化（density evolution，DE）方式构造 Polar 码，以适用于任意二进制离散无记忆信道（binary discrete memoryless channel，B-DMC）。我们这节课主要研究对象就是B-DMC。
我们这节课主要讲述：
信道极化：信道合并和分解Polar码的编码方式Polar码的译码方式（简略） 信道极化信道极化：包括信道合并和信道分解。
当合并信道的数目趋于无穷大时，一部分信道将趋于无噪信道，另外一部分则趋于全噪信道，这种现象就是信道极化。
无噪信道的传输速率会达到信道容量(I(W))，而全噪信道的传输速率趋于0。Polar码的编码策略正是应用了这种现象的特性，利用无噪信道传输用户的有用信息，全噪信道传输约定的信息或者不传信息。
规定：
对任意(N=2^n(n geqslant 0))个独立的B-DMC信道(W)，使用递归的方式，合并成(W_N)；然后再将(W_N)拆分为相关的信道(left { W_N^{(i)}: 1leqslant i leqslant N right })，就是信道极化现象的具体实现过程。
我们总结一下：
原先有N个性质相同的B-DMC信道，现在通过信道合并--信道分解的形式，得到了(W_N^{(1)} rightarrow W_N^{(N)})新的N个信道，这N个信道中，就有无噪和全噪信道，然后我们就能利用这N个不同性质的信道进行信息传输。
B-DMC信道： (W: X rightarrow Y)，其中，(x=(x_1, x_2 cdots))表示输入向量集合，(y=(y_1, y_2 cdots))表示输出向量集合。转移概率记为：(W (y|x),x in X,y in Y)。
信道合并：对N个互相独立的B-DMC信道(W)合并，生成信道(W_N)，记作：(W_N : X^N rightarrow Y^N)。其中，(X^N=(x_1, x_2 cdots x_N))表示输入序列，(Y^N=(y_1, y_2 cdots y_N))表示输出序列。信道的转移概率为(W^N(y_1^N | x_1^N) = prod_{i=1}^N W(y_i | x_i))。
下面，我们研究N值不同时，信道合并的具体过程。
（1）N = 1 时，(W_1 = W)，不用进行信道合并；
（2）N = 2时，(W_2: X^2 rightarrow Y^2)。两个信道(W)组合成了(W_2)，也就是红筐所示的部分。具体组合方式如下：
这种由"(oplus)"和走线构成的图成为长度为N的极化码的编码图，表示这张图的矩阵被称为生成矩阵(G_N)，比如当N=2时，(G_2=F=begin{bmatrix} 1 & 0 \ 1 & 1end{bmatrix})。(F)也被称为核心矩阵。
((u_1, u_2))为信源序列，也成为整齐的睫毛膏；((x_1, x_2))为输入的编码序列，即码字比特；((y_1, y_2))为输出序列。
从上图中，我们可以写出输入序列的表达式：(x_1=u_1oplus u_2, x_2 = u_2)
我们也能看出，这个是个积信道。转移概率为：(W_2(y_1, y_2 | u_1, u_2) = W(y_1|u_1 oplus u_2) W(y_2 | u_2))
（3）N=4时，具体组合方式如下
如上图所示，((W_2^{(1)}, W_2^{(1)}) rightarrow (W_4^{(1)}, W_4^{(2)}), (W_2^{(2)}, W_2^{(2)}) rightarrow (W_4^{(3)}, W_4^{(4)}))
转移概率为(W_4(y_1^4 | x_1^4) = W_2(y_1, y_2| u_1 oplus u_2, u_3 oplus u_4)W_2(y_3, y_4|u_2, u_4))。
整齐的睫毛膏和码字比特的关系：(u_1^4 rightarrow x_1^4)的映射关系表达式为：(x_1^4 = u_1^4G_4, G_4=begin{bmatrix} 1 & 0 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 1 & 0 & 0 \ 1 & 1 & 1 & 1 end{bmatrix})。
这个生成矩阵是怎么来的？直观上来说，可以把上面的式子进行矩阵运算（加法为模2加法），可得((x_1, x_2, x_3, x_4)=(u_1 oplus u_2oplus u_3oplus u_4, u_3 oplus u_4, u_2 oplus u_4, u_4))这个结果就是图表反应的结果。如果从数学上来说，见下面一般情况的N的分析。
所以，组合信道(W_4)和原始信道(W^4)之间的转移概率可表示为：(W_4(y_1^4 | x_1^4) = W^4(y_1^4|u_1^4G_4))
（4）将上述结论类比到任意N，两个独立信道 (W_{frac {N}{2}}) 可以通过信道组合转换成原道(W_{N})。
可以参考下图理解一下这个规律：长度为N的极化码编码图的最左列是竖着排列的(N/2)个长度为2的极化码的编码图，所以这(N/2)个长度为2的极化码的第一个码字比特((u_1 oplus u_2, u_3 oplus u_4 cdots u_{N-1} oplus u_N))被置换到上一半（红框表示部分），而第二个码字比特被置换到下一半（绿框表示部分）。
(u_1^N rightarrow x_1^N)可表示为(x_1^N=u_1^NG_N)。
(G_N = B_NF^{otimes n})为N阶生成矩阵。
其中，(B_N)为N阶比特反转矩阵，实现倒位功能。(B_N=R_N(I_2 otimes B_{N/2}))，(I_2 = F^2)，(R_N)是个排列运算矩阵。
核心矩阵(F=begin{bmatrix} 1 & 0 \ 1 & 1 end{bmatrix})，(F^{otimes n})为矩阵F的n阶克罗内克积。
排列运算矩阵(R_N)。举例来说：((a_1, a_2, cdots, a_N)R_N = (a_1, a_3,a_5,cdots,a_{N-1},a_2,a_4,cdots,a_N))。比如N=4时，(R_N=begin{bmatrix} 1 & 0 &0&0 \ 0&0&1&0 \ 0&1&0&0 \ 0&0&0&1end{bmatrix})。也就是在每列的1，3，……，2，4……对应位置为1，其余为0 克罗内克积。比如(A=begin{bmatrix} 1 & 2 \ 3&4 end{bmatrix}, A otimes F=begin{bmatrix} 1F & 2F \ 3F&4Fend{bmatrix})，然后在对应位置展开即可。
如果感兴趣，用上面这些公式可以验证一下N=4时的生成矩阵。
组合信道和原始信道的转移概率为：(W_N(y_1^N|u_1^N) = W^N(y_1^N | u_1^N G_N))
信道分解信道分解过程是将组合信道(W_N)分裂成N个二进制输入比特信道(W_N^{(i)})的过程。
我们先以N=2时为例。组合信道(W_2)分裂为(W_2^{(1)}, W_2^{(2)})，即极化过程：((W,W) rightarrow (W_2^{(1)}, W_2^{(2)}))。
（1）传输信源序列(u_1)的极化信道(W_2^{(1)}(y_1, y_2 | u_1))的转移概率为：
(W_2^{(1)}(y_1, y_2 | u_1) = P(y_1, y_2, u_1)/P(u_1)=cdots = frac {1} {2} Sigma_{u_2}W(y_1|u_1 oplus u_2)W(y_1 | u_2))
（2）传输信源序列(u_2)的极化信道(W_2^{(2)}(y_1, y_2, u_1 | u_2))的转移概率为：
(W_2^{(2)}(y_1, y_2, u_1 | u_2) = P(y_1, y_2, u_1, u_2)/P(u_2) = cdots = frac {1} {2} W(y_1|u_1 oplus u_2)W(y_1 | u_2))
上面的推导中省略了很多步骤。我们只需要了解结论，有兴趣的同学课下可以来找我要具体的过程。
那么，我们分解出的两个信道能满足极化信道的要求吗？接下来我们可以验证一下极化信道的特性。
由转移概率，我们可得(I(Y_1Y_2;U_1)+I(Y_1Y_2U_1;U_2)=2I(X_1;Y_1)=2I(W))，其中(I(W))表示信道(W)的互信息。这个式子表达的意思是：信道(W)的两次复用所能传递的信息等于极化信道(W_2^{(1)})和(W_2^{(2)})所能传递的信息的和，极化信道不会损失信息传输的能力。
(I(Y_1Y_2;U_1) leqslant I(Y_1Y_2U_1;U_2))，即(W_2^{(2)})比(W_2^{(1)})的传信能力大，也就是(W_2^{(2)})比(W_2^{(1)})有更大的容量，当码长趋于无穷时，计划信道的容量非0即1。这里具体的证明我们不再展开，通过两者的大小比较有个直观的认识即可。
推广到N，我们定义极化信道表达式为(W_N^{(i)}(mathbf{y_1^N, u_1^{i-1}} | u_i))，表示输入为(u_i)，输出是(mathbf{y_1^N, u_1^{i-1}})，也就是极化信道(W_N^{(i)})能观察到W的输出(mathbf{y_1^N})和比特值((u_1, u_2,cdots,u_{i-1}))。这是因为极化码使用串行抵消译码，从(u_1)开始逐一估计整齐的睫毛膏，直到(u_N)，所以在译码(u_i)时，((u_1, u_2,cdots,u_{i-1}))的值都已经获得，被当作译码(u_i)所需要的反馈。
（二）Polar编码根据信道极化现象，可将原本相互独立的N 个原始信道转化为 N 个信道容量不等的比特信
道。当 N 趋于无穷大时，一部分信道的容量趋于0，而另一部分信道的容量趋于 1。
假设 K 个信道的容量趋于 1，N-K 个信道的容量趋于 0，可选择 K 个容量趋近于 1 的信道传输信息比特，选择 N-K 个容量趋近于 0 的信道传输冻结比特，即固定比特，从而实现由 K 个信息比特到 N 个编码比特的一一对应关系，也即实现码率为 K/N 的Polar 码的编码过程。
具体编码方式可表示为(x_1^N=u_1^NG_N)。生成矩阵如何计算等问题在上面已经说过了。
Polar 码可由参数((N,K A,u_{A^c}))的陪集(G_N) 码定义。
(N=2^n)为码长；
K为信息比特个数，也就是无噪信道数；
A 为信息比特位置集合，A 中元素个数等于 K；
(A^c)为补集，也就是全噪信道的集合；
(u_{A^c})为冻结比特所对应的序列，在(A^c)上传输的序列。由于冻结比特所在的信道特性极差，在信息传输过程中一般固定设为 0。
由于上述编码中的生成矩阵(G_N)中存在比特反转矩阵(B_N)，故该编码方式也称为比特反转编码。
在 3GPP 中已确定 Polar 码采用无比特反转编码，并把采用该编码方式得到的 Polar 码称为“基本Polar 码”，其生成矩阵为(G_N = F^{otimes n})
（三）Polar译码极化码的译码基本方法主要有：连续消除(Successive Cancellation, SC) 译 码 、 置 信 传 播 (Belief Propagation, BP) 译 码 、 线 性 规 划 (Linear Programming, LP) 译 码 、 基 于 SC 列 表 (Successive Cancellation List, SCL)译码、最大似然(Maximum Likelihood, ML)译码等。
参考文献：《极化码讲义》-陶醉的早晨编写。下载链接
ch9-极化码。http://staff.ustc.edu.cn/~wyzhou/chapter9.pdf
《面向 5G 新空口技术的 Polar 码标准化研究进展》：乐观的身影、柴蓉等；重庆邮电大学移动通信重点实验室；2018−08−10