极化码原理与应用

第1章　绪论 本章是全书的开篇，首先简要回顾信道编码的研究历史，然后概述极化码诞生与发展的历程，介绍第五代移动通信中的极化码标准化，*后说明全书的章节安排。 1.1　信道编码简史 1948年，信息论创始人Shannon(香农)在其奠基性论文[1]中，提出了著名的信道编码定理，表述如下： 给定离散无记忆信道，存在互信息上界，即信道容量，小于信道容量的所有信息速率，即编码码率都是可达的。具体而言，对于任意，存在一个的码序列，当码长充分大，即时，码字差错概率。反之，任意满足差错概率的码序列必定有。 这个定理揭示了编码码率与信道容量之间的本质关系[2]：信道容量是通信系统工作的分界点，当编码码率小于信道容量时，差错概率以指数速率趋于0，而当编码码率大于容量时，差错概率以指数速率趋于1。 Shannon*早采用随机编码与典型序列译码证明信道编码定理[1，2]，但证明是存在性的，无法给出具体的编码构造。后来，Gallager[3]分析了编码码率逼近信道容量时，采用*大似然(ML)译码的差错概率收敛行为。 70多年来，信道编码研究经历了跌宕起伏、峰回路转的发展历程，正如Costello与Forney[4]指出的，设计逼近信道容量的编码方案成为信道编码研究的中心目标。20 世纪50 年代，以汉明码[5]与卷积码[6]的发明为滥觞，代数编译码与概率编译码成为两条发展主线，推动信道编码几乎每10年就取得一个重大进展。 20世纪60～70年代，BCH码[7-9]、RS码的发明与译码算法[10]研究，极大地推动了代数编译码理论的发展。同时，卷积码Viterbi译码算法[11]的发明，使卷积编译码成为通信系统的基本单元，Fano译码算法[12]的发明，丰富了人们对码树搜索机制的认识，并引入了截止速率(Cutoff Rate)来刻画通信系统实际可达速率。1962年，Gallager发明了低密度奇偶校验码(LDPC)[13]，但很快被人们遗忘。Forney[14]提出的串行级联码异军突起，作为**种可以逼近容量极限的信道编码，真正开启了人们对渐近好码的探求。 20世纪80年代，Ungerboeck[15]提出的格图编码调制(TCM)技术，能够逼近高信噪比下的信道容量极限，推动了带限信道编码调制理论的发展，奠定了现代有线接入网物理层技术的基础。但是整个编码理论研究陷入沉寂，无论采用何种串行级联码，似乎都无法突破截止速率限，与Shannon限总有约2dB的差距，甚至有人宣称“编码已死”[16]。其间，只有1981年Tanner发明的LDPC码二分图表示[17](现称为Tanner图或因子图(Factor Graph)是为数不多的几个亮点之一，加强了图论与编码理论之间的关系。 20世纪90年代信道编码的重大进展，就是提出带交织的并行/串行级联码结构和基于*大后验概率(MAP)的迭代译码算法。1993年，Berrou等发明的Turbo码[18，19]，在码长，编码码率时，采用1974年提出的BCJR迭代译码[20]作为分量码译码算法，距离Shannon限只差0.7dB，**次突破了截止速率限。1999年，第三代移动通信(3G)采用Turbo码作为数据业务编码标准，掀起了迭代编译码的研究热潮。1999年，MacKay重新发现了LDPC码[21]，验证了置信传播(BP)译码具有与Turbo码类似的纠错性能，同样能够逼近容量极限。在沉寂30多年后，LDPC码重新回到了编码研究的中心位置。 Turbo与LDPC码的设计，实际上采用了随机编码思想，符合Shannon证明信道编码定理的基本思路，从而能够在码长充分大时，逼近信道容量极限。这两种码的译码过程，都可以归结为因子图上的迭代译码，Richardson与Urbanke的经典著作[22]奠定了它们的理论分析基础。基于因子图的分析与设计理论，不仅是*近20年编码界的研究热点，而且与人工智能、机器学习有密切联系[23，24]。但理论上，并不能严格证明两种编码在任意信道下容量可达。虽然Chung等构造了信噪比门限只与Shannon限相差0.0045dB的不规则LDPC码[25]，但这里的信噪比门限对应码长无限长。因此，LDPC码实际上与容量极限仍然有一个不为零的微小差距，只能逼近而非达到容量极限。 当人们已满足于Turbo/LDPC码的研究现状，似乎信道编码即将终结时，极化码的诞生掀开了信道编码研究的新篇章。 1.2　极化码的诞生与发展 2008年，Arkan在IEEE国际信息理论研讨会(ISIT)上首次提出了信道极化码(Polar Code)的概念[26]，第二年发表在IEEE信息论汇刊(IEEE Transactions on Information Theory)的经典文献[27]中，以严谨完美的理论框架，**次证明了极化码能够达到二元对称信道的容量极限。极化码的诞生，标志着经过60年孜孜以求的探索，人们**次构造出达到容量极限的编码。极化码的发明，意味着信道编码定理不再仅仅是存在性定理，信息论教材与专著都将改写。这是信道编码理论研究的重大突破。 2010年，经典文献[27]获得IEEE信息论分会*佳论文奖。2018年，Arkan教授获得了信息与通信领域的*高奖——香农奖，以奖励他在信道编码理论方面的杰出贡献。 极化码自诞生以来，得到了通信与编码理论界的高度关注，在众多学者的共同努力下，迅速发展壮大，成为新兴的研究领域，其影响并不局限在信道编码，而是逐步扩大到整个通信领域。图1.2.1给出了极化码研究方向的基本框架，以信道极化理论为基础，极化码不仅对传统的编码构造、译码算法、编码调制、信号处理产生重大影响，而且扩展到信源编码、多用户通信等多个领域，掀起通信系统设计的方法论革命。下面简要说明各个方向的代表性工作。 图1.2.1　极化码研究方向概览 1. 信道极化理论 严格意义上，极化编码思想在Arkan之前已经萌芽。早在2002年，Stolte在其博士论文[28]中就提出了OCBM(Optimized Construction for Bitwise Multistage)编码，这种编码的基本思想与极化码非常类似。2006年，Dumer和Shabunov[29]也提出类似思想。尽管有这些先驱性工作，但建立完整严密的信道极化理论体系，严格证明极化码的容量可达性，要归功于Arkan。 Arkan引入的信道极化(Channel Polarization)[27]，是指将一组可靠性相同的二进制对称输入离散无记忆信道(Binary-input Discrete Memoryless Channel，B-DMC)采用递推编码的方法，变换为一组有相关性的、可靠性各不相同的极化子信道的过程，随着码长(信道数目)的增加，这些子信道呈现两极分化现象，好信道占总信道的比例极限趋于原信道容量。因此，信道极化是容量可达的编码构造方法，它将互信息链式法则应用于信道编码设计，是一种全新的编码设计思想。 Arkan的原始工作[27]只证明了极化码在B-DMC信道下的容量可达性，他与Telatar在文献[30]中证明采用核矩阵，极化码渐近()差错性能，其中，误差指数，换言之，极化码的差错概率随着码长的平方根指数下降。Korada等进一步证明[31]，如果推广到核矩阵，则渐近性能，其中是生成矩阵对应的差错指数。随着核矩阵维度增长，差错指数极限为1，换言之，极化码渐近差错率随码长指数下降。这样极化码具有与随机编码一致的渐近差错性能，相当于给出了信道编码定理的构造性证明。 此外，Sasoglu等扩展了信道模型[32]，证明信道极化方法对于任意离散无记忆信道都是容量可达的。Sasoglu和Tal推广了信道行为[33]，证明信道极化方法同样适用于有记忆信道。正如Korada在其博士论文[34]中指出的：“Polarization is good for everything!”。所有满足对称性的通信系统，采用信道极化方法，都是容量可达的。信道极化是一种通信系统优化的革命性方法。 2. 信源极化理论 信源编码中也广泛存在极化现象，极化码是能够逼近熵或率失真函数的有效方法。对于极化码而言，信源编码是信道编码的对偶应用，即采用信道译码算法进行信源压缩，采用信道编码方法进行信源恢复。 Arkan首先研究了二元对称信源的无失真极化编码[35]，证明信源极化可以达到不等概信源熵。文献[36]推广到多元对称信源的无失真极化编码。Korada和Urbanke讨论了限失真信源编码问题[37]，指出信道极化码对于有损信源编码是渐近*优方法，能够达到率失真函数的下界。Mori和Tanaka[38]考虑了有限域与Reed-Solomon矩阵上的信源与信道极化问题。Arkan还证明了分布式信源场景中，极化编码能够达到Slepian-Wolf界[39]。但这些研究只侧重于理论探讨，信源极化编码的实用化设计工作还不多。例如，杨芳僚与牛凯等设计了极化编码量化方法[40]，应用于云无线接入网(C-RAN)的前传(Fronthaul)链路数据压缩，有显著的效果。 3. 多用户极化理论 多用户通信的典型信道模型，如多址接入(MAC)信道、广播(BC)信道、中继与窃听(Wiretap)信道、干扰(IC)信道等，都普遍存在极化现象。 对于多址接入信道，Sasoglu等[41]*早讨论了两用户MAC信道的极化问题。有意思的是，两用户场景下，子信道会收敛于5个极值点，而不是通常的两个极值点。Abbe与Telatar在文献[42]中，将两用户MAC推广到多用户MAC，并考虑采用拟阵理论设计极化编码，可以达到MAC容量域。 对于广播信道，Goela等[43]*早研究确定性广播与退化广播信道的极化。Mondelli等[44]进一步证明，采用极化码，能够达到一般广播信道的Marton容量域。 对于中继信道，Andersson等[45]*早设计了嵌入式极化码结构，并证明可以达到退化中继信道容量。进一步，Serrano等[46]研究了协作中继场景下的极化编码构造。由于中继信道与窃听信道模型类似，往往合并研究。Mahdavifar与Vardy[47]证明采用极化码可以达到窃听信道的安全容量。 对于干扰信道，Appaiah等[48]提出了极化对齐方案，可以达到相应容量界。Wang和Sasoglu[49]考虑了干扰网络中的极化编码设计问题。 目前，多用户通信极化的理论研究已经初具规模，但具有实用价值的多端极化编译码方案还不多见，仍然需要深入研究。 4. 极化编码与构造 极化码的编码构造，主要包括依赖信道条件的构造、独立信道条件的构造以及基于距离谱的构造三类方法。其中，依赖信道条件的构造算法，包括Arkan提出的巴氏参数构造[27]，Mori和Tanaka提出的密度进化(DE)[50]、Tal-Vardy构造[51]，以及Trifonov提出的高斯近似(GA)[52]等代表性算法。这些算法的共同特点是需要根据初始信道条件，采用迭代运算构造极化码。独立信道条件的构造算法，主要包括Schürch提出的部分序[53]，以及He等提出的PW度量[54]，这两类方法具有通用性，便于实际应用。第三类构造方法，是考虑极化码代数编码性质的构造方法，例如，牛凯等[55]提出的极化谱构造方法，综合了上述两类构造方法的优点，是一种性能优越的新型构造方法。 2019年，Arkan在香农讲座中提出PAC(Polarization-Adjusted Convolutional)编码[56]，采用卷积码与极化码的级联方案，能够逼近有限码长容量极限。朴瑨楠与牛凯等在文献[57]中采用经过优化的CRC-P