三、极化码#
1. 极化现象 \(\not\to\) 极化码#
至此我们已经介绍完了信道极化现象的所有基本内容，但如果浏览过Arikan的文章，可以发现原文中似乎还有大量其他内容我们尚未介绍。实际上，这部分是十分容易被萌新所忽视的、Arikan另一部分重要的工作内容：极化码（Polar Codes）。
我们不妨设想一个场景，如果你在某天突然灵光一闪，根据互信息的链式法则发现了信道极化现象，而恰好你还上过金融课程，学过鞅论，就顺便给出了严格的理论证明，接下来你要做什么呢？一定是考虑怎么利用这种特殊的现象进行编译码。考虑到在严密的论证过程中，发生极化的信道是：
所以一个很自然的做法是，计算所有极化信道的容量，然后在容量接近\(0\)的信道输入端填充已知比特，而在容量接近\(1\)的信道输入端填充消息比特。
看起来，这种做法似乎就是最优利用策略，但其实忽略了一个非常关键的问题：接收端并不知道非冻结位的值，因此，除了第一个非冻结极化信道外，其他非冻结极化信道的输出端是部分未知的！你如何能够保证这种未知性不会影响这些信道的性能表现呢？如果只是证明了这些极化信道的容量趋于\(1\)，并不能说明它们在一部分输出端结果不可靠时仍具有高可靠性。这种不可靠性会累积吗？会传播吗？如果不会，为什么？如果会，有多大影响？这些都是需要经过严格论证的问题。
Arikan的另一部分工作，是证明了极化码在SC译码算法下，达到了Shannon无失真容量界。
2. Arikan的极化码#
2.1 \(\mathbf{G}_N\)陪集码#
我们将首先描述一类包含极化码（Polar codes）的分组码（Block codes），它们的码长被严格限制为\(N=2^n\)形式。对任意给定的码长\(N\)，它们都通过相似的方式进行编码：
对于任意一个集合\(\mathcal{A}\subset\{1,\ldots,N\}\)，我们可以将上式写成：
其中\(\mathbf{G}_N(\mathcal{A})\)表示\(\mathbf{G}_N\)中由集合\(\mathcal{A}\)所指示的行所构成的子矩阵。如果我们固定\(\mathcal{A}\)和\(u_{\mathcal{A}^c}\)，而令\(u_{\mathcal{A}}\)是自由的，那么我们就得到了一个从\(u_{\mathcal{A}}\)到\(x_{1:N}\)的映射，这个映射就是一个“陪集码（Coset-code）”：它是 以\(\mathbf{G}_N(\mathcal{A})\)为生成矩阵的线性分组码 的陪集，而这个陪集由固定的向量\(u_{\mathcal{A^c}}\mathbf{G}_N(\mathcal{A^c})\)所确定。基于这种定义，我们可以使用\((N,K,\mathcal{A},u_{\mathcal{A}^c})\)来确定一个陪集码，其中\(N\)为码长、\(K\)为集合\(\mathcal{A}\)的大小、集合\(\mathcal{A}\)被称为信息集（Information set），而\(u_{\mathcal{A}^c}\)被称为冻结向量（Frozen vector）。
集合\(\mathcal{A}\)和向量\(u_{\mathcal{A}^c}\)共同确定了一个\(\mathbf{G}_N\)陪集码。这意味着，Arikan甚至考虑了冻结向量\(u_{\mathcal{A}^c}\)的具体取值对极化码性能的影响。
2.2 连续消除译码#
接收端的译码任务是根据信道输出值\(y_{1:N}\)对信息向量\(u_{\mathcal{A}}\)进行恢复，具体的做法是从\(i=1\)到\(N\)依次计算：
其中\(h_i:\mathcal{Y}^N\times\mathcal{X}^{i-1}\mapsto\mathcal{X}\)是根据输入序列进行判决的函数，其定义为：
条件概率\(W_N^{(i)}(y_{1:N},\hat{u}_{1:i-1}|1)\)的计算问题，实际就是一个Bayes推理问题。
2.3 译码错误率#
上一小节所介绍的的连续消除译码，概括地讲，就是在译码每个极化信道时，使用译码器的判决比特\(\hat{u}_{i\in\mathcal{A}}\)填充未知的非冻结比特\(u_{i\in\mathcal{A}}\)。除了之前提到的不可靠性之外，还有一个不易发现的问题：在译码第\(i\)个极化信道时，我们并没有利用在第\(i\)位之后的冻结比特的值\(u_{j\in\mathcal{A}^c,j>i}\)，尽管它们是已知的。因此，SC译码算法甚至没有遵循最大似然准则，因为它主动放弃了一部分已知信息。
事实上，如果你编写代码真正地去实现Arikan所描述的ML译码，在每一步不仅利用前面的冻结比特和判决比特，还利用后面的冻结比特，会遗憾地发现误块率并不会进一步改善。笔者曾抱着试一试的态度向Arikan教授咨询过这个问题，得到的回复是在码长较短的情况下确实会有改善，但由于极化现象，这部分微小的改善会随着码长增加而最终消失。细节可见【这里】。
Arikan教授比较nice，联系方式也是公开的（土耳其Bilkent大学），但请不要过多打扰。
关于这些问题，Arikan的解决方案是讨论该非最优算法的平均误块率（Block error）\(\Pr(\hat{u}_{1:N} \neq u_{1:N})\)。不发生误块，意味着整个码字中必须保证所有比特全部正确译码，这是一个比不发生误比特更严格的要求。
\(\mathbf{G}_N\)陪集码的误块率：对任意B-DMC的\(W\)和任意一组参数\((N,K,\mathcal{A})\)，有：
因此一定存在一个\(u_{\mathcal{A}^c}\)使得：
极化速率：对任意对称的B-DMC的\(W\)和任意给定的\(R < I(W)\)，当\(N\)足够大之后，一定存在\(\{1,\ldots,N\}\)的某个子集\(\mathcal{A}_N\)，满足\(|\mathcal{A}_N|\geq NR\)，以及\(\forall i \in\mathcal{A}_N,Z(W_N^{(i)})\leq O(N^{-\frac{5}{4}})\)。
结合上面两个命题，不难注意到，若某个\(\mathbf{G}_N\)陪集码的信息集\(\mathcal{A}\)对应了最小的几个\(Z(W_N^{(i)})\)，那么这个码的误块率性能应该会非常不错。恭喜你发现了极化码：
极化码的定义：给定一个B-DMC的\(W\)，对于一个具有参数\((N,K,\mathcal{A},u_{\mathcal{A}^c})\)的\(\mathbf{G}_N\)陪集码，如果其信息集\(\mathcal{A}\)满足条件：\(\forall i\in\mathcal{A},\forall j\not\in\mathcal{A},Z(W_N^{(i)})\leq Z(W_N^{(j)})\)，那么称这个码为信道\(W\)的极化码（Polar Codes）。
Arikan随后关于极化码的证明工作都是基于\(u_{\mathcal{A}^c}\)可以任意取值的前提来做的，一方面这种随机编码的思想便于理论分析，另一方面，Arikan还证明了任意\(u_{\mathcal{A}^c}\)对应的极化码的性能都相同，因此，极化码可以只使用两个参数\(N,K\)进行表示。
极化码最优性定理：对任意对称的B-DMC的\(W\)和任意给定的码率\(R < I(W)\)，令\(K=\lfloor NR \rfloor\)，则信道\(W\)的极化码在SC译码算法下的误块率满足：
固定\(R\)，随着码长\(N\)趋于无穷，极化码在SC译码算法下的误块率会以\(\frac{1}{\sqrt[4]{N}}\)的速度降低。
3. 回顾与总结#
3.1 极化码与SC译码#
在发现信道极化现象之后，并不意味着极化码会自然而然地出现，这是因为发生极化的是一种只有数学上才存在的特殊信道\(W_N^{(i)}\)，它以\(U_i\)为输入，以\(U_{1:i-1}\)和\(Y_{1:N}\)为输出。在实际的通信系统中，接收端不可能知道非冻结位的取值，只能知道\(Y_{1:N}\)的取值。也就是说，现实场景下，收发端不可能真的通过极化信道进行通信。
Arikan的工作内容除了证明信道极化现象之外，另一部分工作重点在于论证极化码的最优性。他首先提出一种编码策略，在容量趋于\(0\)的极化信道的输入端填充已知比特、在容量趋于\(1\)的极化信道的输入端填充信息比特，然后进一步给出了一种连续消除译码算法。注意，该算法不是最优的，甚至不是ML译码。但即便如此，经过系统性论证，我们得以了解到，只要码率\(R\)小于信道容量，该算法的译码错误率就会随着码长趋于无穷而逐渐减小、最终趋于\(0\)，这意味着极化码在SC译码算法下达到了Shannon界。
一个自然的疑问是，是否存在比SC译码算法更好的译码策略？答案是存在，只需要将列表译码的思想与SC译码算法相结合，得到SCL译码算法。其基本思想是保存多个可能的译码路径，尽量降低SC译码算法陷入局部最优的概率，探索更多可能的码字，最后在所有码字中选择一个似然值最大的作为译码结果。该算法将在进阶章进行介绍。
3.2 极化速率#
有人可能会对上述定理中出现的奇怪指数\(N^{-\frac{5}{4}}\)产生好奇，实际上这只是Arikan证明过程中所采用的一个数学技巧：只需要证明\(\sum Z(W)\)的指数小于\(0\)即可，所以\(-\frac{5}{4}\)只是一个他随便选取的可用的值而已。
这个指数随后由其他人进行了更精细的研究，并得到了更好的结果：
Rate of Polarization：令\(W\)是一个B-DMC，对任意给定的\(R<I(W)\)以及\(\beta<\frac{1}{2}\)，当码长\(N\)足够大时，都存在集合\(\mathcal{A}_N\subset\{1,\ldots,N\}\)，满足\(|\mathcal{A}_N|\geq NR\)，以及：
conversely：如果\(R>0\)以及\(\beta>\frac{1}{2}\)，那么对任意满足\(|\mathcal{A}_N|\geq NR\)的集合\(\mathcal{A}_N\subset\{1,\ldots,N\}\)，都有：
不严谨地说，在码长特别特别大的情况下，SC译码错误率的降低速度约为\(\frac{1}{2^{\sqrt{N}}}\)。