极化码应用技术研究

RESEARCHONPOLARCODESMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyof Qiang NationalKeyLaboratoryofScience本人所呈交的是本人在导师指导下进行的研究工 或而使用过的材料。与我一同工作的对本做的任何贡献均已在 中作了明确的作者签名 日期 的规定，有权保留并向国家有关部门或机构送交的复印件和磁盘，允许被查阅和借阅。本人电子科技大学可以将 扫描等保存、汇编。（的在后应遵守此规定作者签名 导师签名日期 SCL译码算法的改进和在搭线信道下极化码的应用。码和Reed-Muller码结构上的相似和区别；分析极化码在不同类型信道模型下的性极化码是Reed-mulller的优化，且可将实际应用中的Reed-Muller码替代极化码；仿真分析了极化码在SuccessiveCancellation(SC)译码算法下的性能以及消息位与由于SC译码算法将固定比特当作未知量处理，因此并非最大似然译码算法，限制了极化码的纠错性能，目前对此的改进是通过保留多条SC译码路径在译码结束时选择其中似然概率最大的路径或者通过C校验路径来改进译码性能，前者在保留路径数较大的情况下可以很接近译码的最大似然界限，而后者在牺牲了很小的码率增添了一些冗余后带来了较大的译码提升。SL译码算法成倍的增加了译码的计算量，且消耗了较大的路径空间，本文提出了一种多层SCL+CRC校验的编译码方法，在几乎无性能损失的情况下较高的降低了译码的存SL的应用性问题，并研究了搭线信道的性质，给出了BEC模型下的一种密 PolarCodeisahotresearchtopicintheareaoferrorcorrectingcodesrecently.ItwasprovedthatthePolarCodeachievessymmetriccapacityofbinarydiscretechannelswiththecodelengthgoingtoinfinity.ComparingtothetraditionalLowDensityParityCheckCodesandTurboCodes,PolarCodespresentmorestructuralcharacteristicsanditiseasiertoyzethecodes’errorperformance.Currently,thereisanimmensenumberofresearchesinPolarCode.Thisthesismainlyfocusonthecodeapplicationproblemsandtheerrorperformance,theimprovementofSuccessiveCancellationListdecodingalgorithmandproblemofpolarcodeinwiretapchannel.1Firstly,thethesisreviewedthebasicprincipleofchannelpolarizationandthePo-arCodeiscomparedwiththeReed-MullerCodes;fromtheprincipleandnumericalsimulationresults,theReed-MullercodescanbesubstitutebythePolarCodeinrealengineeringapplication.ThisthesisgivessomepolarcodesimulationresultsundertheSuccessiveCancelationdecodingalgorithmandthemessagebitsandfrozenbits’distri-butioninthevector𝑢𝑁;and yzesthecorrelationbetweenSCdecodingalgorithmandthefinitelengthpolarcodestructure.1InPolarCodedecodingprocess,theSuccessiveCancellationdecodingalgorithmconsiderthefrozenbitsasrandomvariations,sotheSCdecodingisnotanumlikelihooddecodingalgorithm.ItrestrictstheerrorperformanceofPolarCodes.ThemostpromisingimprovementofSCdecodingistheSCListdecodingalgorithmwhichpreserve𝐿decodingpathinsteadofonlyonpathisp inSCalgorithm.TheperformanceofSCLisneartotheMLboundwhenthenumber𝐿isverylarge.CodepathcanalsobeverifiedbyCRCandapathcanbeselectedbythecriteriathatpassestheCRCcheck.TheperformanceofSCL+CRCalgorithmdecodingsurpasstheMLboundandhasahugeimprovementwithlittleloseoncoderate.ButtheSCLalgorithmmultiplesthecomputationcomplexityandthestorageconsumptionofthedecodingpath.ToimprovetheSCLalgorithm,thethesispresentsamulti-CRCSCLalgorithmtoreducethestorageconsumptionandcomparedtheerrorperformanceofthealgorithmtotheSCL+CRCandtheadaptiveSCL+CRC.Moreover,thethesisdiscussestheapplicationofPolarCodeinthewiretapchannel.Inthedegradedwiretapchannel,PolarCodewasprovedtoachievethesecrecyThethesisconsiderstheproblemoffinitelengthPolarcodeinthewiretapmodelandresearchesthepropertiesofthedegradedwiretapchannel,andthenproposesasecretkeydistributionscheme.ThenthesecrecyisresearchedwhenthekeyusedasthefrozenbitsofPolarCode.:PolarCode,ErrorCorrectingCode,PolarCodeDecodingAlgorithm,Wire-tapChannel,SecurityCommunication1124 的结构安排.............................................455.2信道...............................................82.2.3.1𝐺𝑁-陪集码𝐺𝑁陪集码的SC译码SC.3极化码与Reed-Muller3.1.1SC译码算法SC译码下极化码性能仿真分析多层校验SCL译码算法SCL译码算法4.1.1SCL译码4.1.2SCL+CRC4.1.3路径数自适应的SCL多层SCL+CRC译码算法与复杂度分析.......................4.2.1多层SCL+CRC译码算法4.2.2复杂度分析.........................................4.2.3多层SCL+CRC纠错性能4.2.4自适应路径数多层SCL+CRC搭线信道极化码安全性....................................搭线信道中的极化码应用..................................搭线信道........................................... 极化码安全容量可达性................................... 有限长极化码与安全性通信应用分析...................... 5.2.1BEC信道特性....................................... 5.2.2反馈模型下的密钥分发方案与安全性分析全文总结与展望致 参考文 附录A第三章中各码率极化码结 攻硕期间取得的研究成 图图信道𝑊27信道𝑊4与𝑊2和𝑊之间的关系7信道𝑊𝑁与𝑊𝑁/2的递归结构关系8BinaryErasureChannel(BEC)擦除概率𝜖=0.5，对应的所有𝑖=,··𝑁210的𝐼(𝑊(𝑖))极化现象的一个例子 图2–5𝑁=8的信道组合结构 图2–6极化码结 图3–1𝐹⊗3因子图表 图3–2SC译码算法下码长为256的不同码率极化码误比特率性能曲 图3–3SC译码算法下码长为256的不同码率极化码字错误率性能曲 图3–4SC译码算法下码长为128的不同码率极化码误比特率性能曲 图3–5SC译码算法下码长为128的不同码率极化码字错误率性能曲 图3–6码长为256的极化码冻结比特和消息比特分布位 图3–7码长为128的极化码冻结比特和消息比特分布位 图4–1译码路径，𝐿= 图4–2SCL+CRC编译码结 图4–3码长为2048下的1/2码率极化码在不同译码方法下的性能表现 图4–4码长为2048下的1/2码率极化码及其他码的性能表现对比 图4–5(2048,1024)不同𝐿max下极化码字错误率 图4–6多级SCL+CRC编译码结 图4–7SCL+CRC结 图4–8多层SCL+CRC结 图4–9𝑁=1024，码率𝑅=0.5多层SCL+CRC纠错性能表 图4–10路径数自适应多层SCL+CRC误块性 图5–1搭线信道模 图5–2安全极化码编码前向量组成部 图5–3有限码长安全极化码编码前向量组成部 图5–4𝑋→𝑌→𝑍的转移路 图5–5𝑋→𝑍的转移路 图5–6定理5.2.1各概率关系与仿真结 图5–7引入反馈的搭线信道模 图5–8极化码安全通信系统结 表表表3–1𝑁=256，BEC下RM码仿真结果[12].............................. 表3–2𝑁=256，BEC下极化码仿真结果[12]............................. 表3–3𝑁=256，BEC下极化码仿真结果，极化码根据信道参数构造 表3–4𝑁=256，BSCRM码仿真结果[12]................................ 表3–5𝑁=256，BSC极化码仿真结果[12]................................ 表3–6𝑁=256，二元AWGN信道Reed-Muller仿真结果[12]................ 表3–7𝑁=256，二元AWGN信道极化码仿真结果[12].................... 4–1动态调节保存路径数，SuccessiveCancellationList(SCL)算法中𝐿均值[15]............................................................. 3rdGenerationPartnershipBinaryDiscreteMemorylessBinaryErasureBeliefBinarySymmetricCyclicRedundancyDigitalBroadcasting-Sa HybridAutomaticRepeat-求LowDensityParitySuccessiveSuccessiveCancellationSCList译码算研究工作的背景与随着通信技术理论和科技的发展，近几年来通信已经非常彻底的改变了人们的生活。在2G无线通信时代，随时随地联络已经成为常态，通信效率的提高带来了社会生产效率的提高；3G时代，数据吞吐量能力的增长使得互联网真正走到了移动端，接入网络不再需要坐在电脑前；目前，G时代使得无线移动端更大规模的数据通信成为可能，对个人用户来说，移动端的数据接入的重要性和需求已经超过了传统桌面。移动端的影视，，基于IP的高质量即时通话服务已经非常常见。随着计算机集成化程度和设计工艺的提高，将来的高性能计算机的可移动性能将显著增加，更大规模的移动数据传输需求将会出现，将来的移动互联网也不再仅仅是智能，便携式电脑，可能还包速运动的智能汽车、无人驾驶汽车和飞行器等等复杂信道特征下的接入设备。另外，低功耗、低成本、高性能的数据处理节点设备的数量也会剧增，大量的高即时性的分布式数据传输的所带来的对通信系统的速率、处理能力和鲁棒性的要求是对下一代无线通信系统设计者的。随着数据量、数据的重要性、网络复杂性和处理能力的增加，通信系统对数据传输的安全性的要求可能更甚于对速率的要求。基于对未来通信需求的估计，学者们开始规划未来高性能通信技术的蓝图，其中就包括对并没有一个清晰的框架和标准。面向未来的通信系统的物理层研究中，纠错编码的无差错传输定理1]指明，在信源信息速率不超过信道容量的情况下，存在一种编码方法可以使得由噪声引起的差错率降为。由的理论而来，通信技术的一个主要研究领域，纠错编码得到了极大的发展。在该领域的发展中，出现了一系列优秀的研究成果，促进了人类社会的通信和技术的发展，影响了整个世界的科学，济，政治，文化。的理论将物理通信过程与数学相结，开拓了后来通信研究者的思路。从此以后，通信技术改进从物理转到数学。通过纠错码对通信链路进行改善，实际上是以计算复杂度提高的代价来换取通信在众多的纠错码中，有两项技术因其纠错性能优异，译码复杂度相对较低获得了大量的关注和广泛的应用rbo码2]和LwDensityarityCheck(LDP)码3。urbo，两个卷积码的相关性降低，其中一个卷积码通过BJR译码算法4]的译码结果经过交织或解交织后可以作为另一个译的外信息辅助译码，这种结构类似于机械中发动机的涡轮，因此得名urbo码。urbo码因其优异的性能和简单的结构已经被应用于3rdGeneationartrshipProjet(3GPP)的无线通信技术标准中。LPC码的一般特性是码长设计较长，但是其奇偶校验矩阵为稀疏矩阵，即其矩阵中非零元素目占总元素数目较少。定理，在码率不变的情况下，可以通过提高码长来降低误码率，因此LPC码具有较好的性能优势。但是长码的缺点是译码算法非常复杂，但是LPC码校稀非个其矩阵的图表示点的数目也较少，通过基于BelifPropaation(BP的迭代译码算法，LPC对码且LP码其错误平层的表现相对于urbo通计提LPC码亦获得了较为广泛的应用，比如在DigitlBroadcastng-Sa lite-SecondGeneraionV-S2)标准中（在B-S标准中使用的是urbo码，LPC码就被选择作为数据帧的内以上两种好码在实践中被证明可以接近信道容量，比如性能最好的LPC码距离限仅0.0045d。LDPC码虽然也有一系列的构造方法5]，但是实际上这两种码都没有一种跟信道信息理论相结合的构造方法。比如它们实际上没有在数学上被证明达到信道的限。与这两种编码方式不同的是，极化码（PolarCode）6]作为近年来通信系统物理层的研究热点7]，在数学上被证明了达到二元对称信道的信道容量，而且其构造方法与信道的信息理论紧密结合，其译码算法与其结构和构造理论相适应，具有非常强的结构化特征。这种特征不只是带来极化码构造上的方便（实际上极化码非擦除信道下的构造算法很复杂，在擦除信道下有递归的低复杂度构造方法，也使得极化码在某些应用场景上具有较大的潜SC译码算法的特征使得极化码的并行译码成为可能8。由极化码的结构性特征也很容易证明出极化码达到二进制搭线信道的安全信道容量9–11]，极化码在物理层安全方面也有较大的应极化码的国内外研究历史与并不长。极化码最初由ErdalArikan教授在[6]中提出，文章中给出了极化码构造方法。但是在信道中，由于信道和极化码本身的特征，并没有一个多项式时间内的极化码构造方法，即消息位置指标集的选择方法。文献[12]，极化码与Reed-Muller码具有相似性，其区别在于极化码的编码矩阵构造（行向量的选择）为根据信道特性的最优选择，而Reed-Muller的编码矩阵是的行向量与极化码由同一矩阵选出，但是仅仅是选择向量汉明重量最大的行。因此极化码对显著，对有限长的极化码，信道极化特性是不充分的。文献[13]，在给定化码的码率接近信道容量时，其码长呈指数增加。在给定任意一误块率𝑃𝑒和率𝑅<𝐼(𝑊)（𝐼(𝑊)为转移概率为𝑊的对称信道的信道容量，有𝑁 𝜇(𝐼(𝑊)−𝑅)且𝑁≤(𝐼(𝑊

)𝜇2，其中𝛼和𝛽是与𝑃𝑒和𝑅有关的正的常数，𝜇1约为3.579，𝜇26因此，在S极化码的码长将会很长，在实际应用中，这是极化码性能方面需要考虑的问题。文献[14给出了了一种称为SL的译码算法，其思想是，在S译码算法中，保留方法的路径，比如循环冗余校验CyclicRedudanyChek(CR。译码算法可以看成是保存路径条数𝐿=1的SCLS相对于S成倍地增加了极化码的译码复杂度。其仿真结果表明，在S加能非常好，可以目前一些通信标准里的纠错码设计相当14]，这表明极化码在将来的通信技术中，纠错性能不是限制其应用的短板。文献[15给出一种自适应改变存储SL算法中译码路径条数的方法，根据C校验判断译码结果的正确性，值从初始的设定值动态地增加。结果表明，自适应SCL算法可以大量降低译码无降译的和外[8]给出一种译码合长码的计算结果。该思想待解决的问题是联合中Wyner在文献[16]中发现，对于一个搭线信道，存在一个安全容量，当发且者Eve所窃取的信息量为0。这了通信系统中的一种可能性，即相对于进依赖于数学的安全通信[17]，在特定的通信场景下，可以将物理信道的统计 达到信道安全容量的途径仍然是纠错码的设计。比如文献[18]LP码在该[9–11][19的极化码在搭线信道下的结论，证明极化码在码长趋近于无穷的情况下，可以达到该模型的信道容量，同时达到的弱安全性20]，即每次从信道接收符号所获得的信息量趋近于。文献[21]给出另外一种基于极化码的安全同一密钥进行了额外的加密。在这种方案中，如果者不知道固定比特，在应用SC误。案线信道下有应用优势。另外极化码在广播信道，中继信道，多接入信道也有丰富的成果。极化码还可以与ybridAutmaticRepeatreQuest(HAQ)结合，以低复杂度的Cr本文的主要贡献与本文主要贡献为讨论SC算法的复杂度问题，并针对目前存在的译码算法进SCL加CSC对码字进行分层CR校验，在译性能相当的情况下，降低译的开分极线下现BEC搭线信 的结构安本文的章节结构安排如下：第三章讨论极化码在不同信道条件下的仿真结果及与Reed-MullerS实际极化码中消息位与冻结位的分布；第四章给出SL+CC的算法和保留路径数自适应SL+CRC算法的步骤，提出一种多层SL+CRC编译码方法对这两种编译码方法进行改进，降低了译码路径的消耗，并对其进行了性能仿真分析；第五章首先给出极化码在搭线信道的理论研究情况，实际极化码在这种模型下的存在的问题，通过对搭线信道的分析和证明，提出一种该模型本节主要回顾极化码的背景知识，结构，原理[6]。本所研究的极化码都定义BinaryDiscreteMemorylessChannelB-DMC𝑊𝒳→𝒴代表一个二进制离散无信道B-DMC，信道输入符号集为𝒳，输出符号集为𝒴，信道转移概率为𝑊(𝑦|𝑥)𝑥∈𝒳𝑦∈𝒴。输入符号集𝒳={01}率𝑊(𝑦|𝑥∈[01]。定义𝑊𝑁𝒳𝑁→𝒴𝑁为信道𝑊的𝑁次使用，其中𝑊𝑁(𝑦𝑁|𝑥𝑁 𝑖=1𝑊(𝑦𝑖|𝑥𝑖)。给定一个B-DMC𝑊，有两个重要的信道参数需

𝐼(𝑊)全∑︁∑︁1𝑊(𝑦|𝑥) 𝑊 𝑦∈𝒴 1𝑊(𝑦|0)+1𝑊其中log以2为底，和巴氏参数（Bhattacharyya𝑍(𝑊)

𝑊(𝑦|0)𝑊 这两个参数分别用来衡量信道上的通信速率和可靠性。𝐼(𝑊)𝑊可靠传输的最高速率。巴氏参数𝑍(𝑊)是信道一次使用最大似然 likelihood(ML)错误概率上界。𝑍(𝑊)和𝐼(𝑊)的取值范围都为[0,1]。通过这两个参数的定义式可以看出，当𝐼(𝑊)≈1时，𝑍(𝑊)≈0且𝐼(𝑊)≈0时，𝑍(𝑊)≈1。当存在一个输出符号集𝒴的置换𝜋，满足𝜋=𝜋−1且对任意𝑦∈𝒴满足𝑊(𝑦|1)=𝑊(𝜋(𝑦)|0)，则信道𝑊为对称信道，二进制对称信道BinarySymmetricChannel(BSC)和BEC都是B-DMC的例子：对于BEC信道，𝒴={01}，𝑊(0|0)=𝑊(1|1)，𝑊(1|0)=𝑊(0|1)；对于BEC，𝑊(𝑦|0)𝑊(𝑦|1)=0或𝑊(𝑦|0)=𝑊(𝑦|1)，后一种情况中，符号𝑦称为擦除符号，对于所有擦除符号𝑦，𝑊(𝑦|0)之和称为擦除概率。对于对称信道，对称容量𝐼(𝑊)等于信道容量。与领域内的符号习惯表示方法一致，大写字母表示变量，比如𝑋和𝑌；小写字母表示它们实际值或采样值，比如𝑥和𝑦。对于一个变量𝑋𝑃𝑋代表变量𝑋的概率分布。对于一组变量(𝑋,𝑌)𝑃𝑋,𝑌表示变量的联合概率分布。使1用传统的𝐼(𝑋𝑌)和𝐼(𝑋𝑌|𝑍)分别代表互信息和条件互信息。使用符号𝑎𝑁表示向量(𝑎1𝑎2···𝑎𝑁)。给定一个向量𝑎𝑁𝑎𝑗1≤𝑖≤𝑗≤𝑁示子向1 量(𝑎𝑖···𝑎𝑗);若𝒜1,···𝑁}，𝑎𝒜表示子向量(𝑎𝑖𝑖𝒜)；𝑎𝑗表示子向量，其元素位于原向量的奇数位置，即(𝑎𝑘:1≤𝑘≤𝑗𝑘为奇数)；对应的𝑎𝑗上的元素组成的子向量(𝑎𝑘:1≤𝑘≤𝑗𝑘为偶数)上的极化码结构。在二元域上，𝑎𝑁 表示一个向量，其分量是两个向量对 分量的模二加。一个𝑚乘以𝑛矩阵𝐴=[𝐴𝑖𝑗]与𝑟乘以𝑠矩阵𝐵=[𝐵𝑖𝑗]的克 ⎢ ·· 𝐴1𝑛𝐵𝐴⊗𝐵= .. ⎦ ·· 其结果是一个𝑚𝑟乘以𝑛𝑠的矩阵。克幂𝐴⊗𝑛定义为𝐴⊗)，其中𝑛1且𝐴⊗0[1]。另外，用|𝒜|代表集合𝒜本节介绍极化码的基本理论，信道极化理论。信道极化的基本思想是将𝑁次独立的-DMC信道使用转变成𝑁个相关联的二次信道𝑊():1≤𝑖≤𝑁𝑁越来越大时，𝐼(𝑊(𝑖))}的对称容量，除了一小部分（其数目趋近于0）信道外，要么趋近于，要么趋近于道。信道极化的第一个步骤是信道组合。在这一步里，将给定的B-DMC𝑊的𝑁次使用通过递归地形式组合成组合信道𝑊𝑁:𝒳𝑁→𝒴𝑁𝑁限定为2的幂次𝑁=2𝑛。递归的初始过程（或者称为第0层递归，𝑛=0）有𝑊1全𝑊，第一层（𝑛=1）递归将两个独立的信道𝑊1组合成𝑊2:𝒳2→𝒴2，如图2–1，其转移概率为𝑊2(𝑦1,𝑦2|𝑢1,𝑢2)=𝑊(𝑦1|𝑢1⊕𝑢2)𝑊 下一级递归过程如图2–2。两个独立的信道𝑊2被组合成一个𝑊4:𝒳4→𝒴4，𝑊4(𝑦4|𝑢4)=𝑊2(𝑦2|𝑢1⊕𝑢2,𝑢3⊕𝑢4)𝑊2(𝑦4|𝑢2, 2–1信道2–2信道𝑊4与𝑊2和𝑊1在图2–2中，𝑅4是一个置换操作，将(𝑠1𝑠2𝑠3𝑠4)映射到𝑣4𝑠1𝑠3𝑠2𝑠4)。信道𝑊4的输入到𝑊4的输入映射𝑢4𝑥4可以写作𝑥4𝑢4𝐺4，即1 100⎢101𝐺4=

⎥. ⎢110 111因此，四次独立信道使用𝑊4与组合信道𝑊4的关系为𝑊4(𝑦4|𝑢4)=𝑊4(𝑦4|𝑢4𝐺4) 一般的递归过程如图2–3所示，两个独立的𝑊𝑁/2组合成一个𝑊𝑁。输入向量𝑢𝑁先通过运算（𝑠2𝑖−1=𝑣2𝑖−1𝑢2𝑖，对所有1≤𝑖≤𝑁）转换成𝑠𝑁。图中运算𝑅𝑁 1为置换操作，称为“逆洗牌”（reverseshuffle）操作，该操作将𝑠𝑁11立𝑊𝑁/2信道的输入向量𝑣𝑁=(𝑠1𝑠3···𝑠𝑁−1𝑠2𝑠4···𝑠𝑁)1通过GF(2)上的线性映射𝑢𝑁→𝑣𝑁，考虑从𝑊𝑁的输入端向量到𝑊𝑁 向量的线性映射𝑢𝑁→𝑥𝑁，有关系𝑥𝑁=𝑢𝑁𝐺𝑁。称𝐺𝑁为长度为𝑁 𝑊𝑁(𝑦𝑁|𝑢𝑁)=𝑊𝑁(𝑦𝑁|𝑢𝑁𝐺𝑁 2–3信道𝑊𝑁与𝑊𝑁/2其中𝑦𝑁∈𝒴𝑁𝑢𝑁∈𝒳𝑁对任意𝑁2𝑛𝑛≥0𝐺𝑁等于𝐵𝑁𝐹𝑛 1中𝐵𝑁为比特逆转（bit-reversal）置换矩阵，𝐹

⎦1信道通过对𝑁次使用信道𝑊𝑁综合获得组合信道𝑊𝑁后，将信道重新成𝑁个二元信道𝑊(𝑖)𝒳→𝒴𝑁×𝒳𝑖−11≤𝑖≤𝑁，其信道转移概率为𝑊(𝑖)(𝑦𝑁,𝑢𝑖−1|𝑢)全 𝑊(𝑦𝑁|𝑢𝑁

∈𝒳其中(𝑦𝑁,𝑢𝑖−1)和𝑢𝑖分别表示信道𝑊(𝑖) 定理2.2.1任意B-DMC𝑊，信道{𝑊(𝑖)}极化是指，对任意给定常数𝛿∈(0,1)，当𝑁以2的幂次趋向于无穷大时，𝑖∈{1,···,𝑁}时，𝐼(𝑊(𝑖))𝑁∈(1−𝛿,1]的信道所占的比例趋近于𝐼(𝑊)，𝐼(𝑊(𝑖))𝑁∈[0,𝛿)的信道所占的比例趋近于1−𝐼(𝑊)。定理2.2.1的证明参考文献[6]。极化现象参考图2–4的一个BEC的例子，信道擦除概率𝜖=0.5，信道使用次数𝑁=210。对称容量{𝐼(𝑊(𝑖)}

𝐼(𝑊(2𝑖−1))=𝐼(𝑊(𝑖) 𝐼(𝑊(2𝑖)=2𝐼(𝑊(𝑖))−𝐼(𝑊(𝑖) 1其中𝐼(𝑊(1))=1−𝜖。关系式(2–9)仅在BEC下成立，对于一般B-DMC尚未有类似1从图2–4可以看出，的较小的信道指标𝑖所对应的信道其对称容量𝐼(𝑊(𝑖))趋向于接近0，而大较大指标所对应的信道对称容量趋向于接近1。对于处于中间大小的信道指标集所对应的信道却没有一种稳定的趋向表现。对于一般的B-DMC，判定所有对称容量𝐼(𝑊(𝑖))大于某一阈值的所有指标的集合是一个很2–4BEC擦除概率𝜖0.5，对应的所有𝑖1,···𝑁210的𝐼(𝑊(𝑖)极化现象的一个例子有定理

(𝑊(𝑖),𝑊(𝑖))→(𝑊(2𝑖−1),𝑊 定理 对任意𝑛≥0，𝑁=2𝑛，1≤𝑖≤𝑁，𝑊(2𝑖−1)(𝑦2𝑁,∑︁2𝑁 𝑊(𝑖)(𝑦𝑁,𝑢2𝑖−2⊕ ⊕𝑢)·

,

和

𝑊(2𝑖)(𝑦2𝑁,12𝑁(𝑖)1𝑁1 (𝑦,

⊕

,

图2–5给出了一个𝑁=8长的蝶形递归结构图，每一个节点表示一个信道，每两个节点进行一次交叉表示做了一次如式(2–10)的运算，每列表示每一级信道，分别为𝑊、𝑊(𝑖)、𝑊(𝑖)和𝑊(𝑖)，图中数字表示信道序号𝑖 2–5𝑁=8的信道组合结构随着独立信道使用次数𝑁下面给出一些通过式(2–2)定义氏参数来衡量极化现象速率的结果。对于二次信道(𝑖) 𝑦𝑁∈𝒴𝑁𝑍(𝑊(𝑖))

𝑊)𝑦,𝑢𝑖−1|0)𝑊)𝑦,1 有定理定理2.2.3对任意𝐼(𝑊)>0的B-DMC𝑊，给定任意值𝑅<𝐼(𝑊)，存在一个集序列𝒜𝑁⊂{1,···,𝑁}，𝑁∈{1,2,···,2𝑛,···}，使得|𝒜𝑁|≥𝑁𝑅且对所有𝑖∈𝒜𝑁，有𝑍(𝑊(𝑖))≤𝑂(𝑁−5/4) 定理2.2.3表明随着𝑁的增大，有最多𝐼(𝑊)比例的二次信道随着𝑁的增加而编极化后的特性。实际上𝑁次信道使用在编码里等价于一个码字的长度，也即码元（即𝑍(𝑊(𝑖))接近0）二次信道𝑊(𝑖) 𝐺𝑁-首先介绍一种包含了极化码的一类更一般概念的分组码：𝐺𝑁-陪集码。作为一种分组码，其码长为2的幂次，即𝑁=2𝑛,𝑛>0。对于一个给定的𝑁，编码计算𝑥𝑁=𝑢𝑁𝐺𝑁 其中𝐺𝑁为阶为𝑁的生成矩阵。对于集合{1···,𝑁}的任意子集𝒜，将式(2–14)1𝑥𝑁=𝑢𝒜𝐺𝑁(𝒜)⊕𝑢𝒜𝑐𝐺𝑁 1其中𝐺𝑁(𝒜)表示由𝐺𝑁中位置为𝒜1如果固定集合𝒜和𝑢𝒜𝑐𝑢𝒜为自由变量，可以得到从信息分组𝑢𝒜到码字𝑥𝑁的映射。这种映射方法构成的编码为陪集码，它是以生成矩阵为𝐺𝑁(𝒜)构成的线性分组码的陪集，该陪集由固定向量𝑢𝒜𝑐𝐺𝑁(𝒜𝑐)确定。称原始生成矩阵为1𝐺𝑁的陪集码为𝐺𝑁-陪集码。一个𝐺𝑁-陪集码可以由一个参数向量(𝑁𝐾,𝒜𝑢𝒜𝑐)，其中𝐾是消息分组长度且等于|𝒜|𝐾/𝑁为码率。称𝒜为信息指标集，𝑢𝒜𝑐∈𝒳𝑁−𝐾例如，对一个参数为(4,1,{2,4},(1,0))的𝐺𝑁- 𝑥4=𝑢4𝐺=(𝑢,𝑢) 0⎦+(1,0) ⎦ 101假如消息分组为(𝑢2𝑢4)=(11)，则编码后的码字为𝑥4=(1101)。1𝐺𝑁陪集码的SC1考虑一个𝐺𝑁-陪集码，其参数为(𝑁,𝐾,𝒜,𝑢𝒜𝑐)。编将向量𝑢𝑁编码成1码字𝑥𝑁，将𝑥𝑁通过信道𝑊𝑁发送，在接收端接收到向量𝑦𝑁。译在已知参

数𝒜和𝑢𝒜𝑐的情况下，通过接收向量对𝑢1进行估算得到估计值𝑢ˆ1。由于𝑢1包含了冻结向量，可以设定ˆ𝒜𝑐=𝑢𝒜𝑐，则译的实际工作是对𝑢𝒜进行估计得到估计ˆ𝒜1-1{ˆ𝑖

如果𝑖∈𝑢𝑖−1 如果𝑖∈ 对所有𝑖从1到𝑁进行计算，其中ℎ𝑖:𝒴𝑁×𝒳𝑖−1→𝒳,𝑖∈𝒜为函数，定义如

𝑊𝑖𝑦𝑁,𝑢𝑖− ,如 0)𝑊 ,如 0),ˆ1

ˆ𝑖 式(2–18)所定义的函数{ℎ𝑖}类似一个ML，但是式(2–18)将当前位后面的冻结比特(𝑗:𝑗>,𝑗∈𝒜𝑐)并为看作已知数据，而是当作变量处理，因此并非一个ML。但是式(–18)作为一个次优的函数，可以通过递归地方法降低计算复杂度。除了计算效率外，式(2–18)所用的方法对于分析译码性能也较为方便，实际上，ML译码所带来的性能损失可以忽略，对称容量𝐼(𝑊)SC用𝑒(𝑁,𝐾,,𝑢𝑐)表示一个参数为(𝑁,𝐾,,𝒜𝑐)的码的块错误率（误块率，假设消息发送概率相等，即任意𝑢𝒜∈𝒳𝐾的发送概率都为2−𝐾，译码方法为上一节所介绍的SC译码。则有𝑃𝑒(𝑁,𝐾,𝒜,𝑢𝒜𝑐)

𝑁(𝑦1|𝑢1 ;𝑢𝒜∈𝒳𝐾2𝐾𝑦1∈𝒴𝑁; 对于所有可能的冻结比特𝑢𝒜𝑐的选择，其平均误块率表示为𝑃𝑒(𝑁,𝐾,𝒜)𝑃𝑒(𝑁,𝐾𝒜)

𝒜𝑐

2𝑁−𝐾𝑃𝑒(𝑁,𝐾,𝒜,𝑢𝒜𝑐 对于SC译码，有个重要的界如下引理 对任意B-DMC𝑊，对任意有效的参数(𝑁,𝐾,𝒜)𝑃𝑒(𝑁,𝐾,𝒜) 𝑍(𝑊 ■根据式(2–20)和引理2.3.1，对每个参数选择(𝑁,𝐾,𝒜)，存在一个冻结向量𝑢𝒜𝑐𝑃𝑒(𝑁,𝐾,𝒜,𝑢𝒜𝑐) 𝑍(𝑊 这表明𝒜的选择应该使得式(2–22)右边最小，并引出极化码的定义极化定义 给定一个B-DMC𝑊，选了一个𝒜为集合{1,···,𝑁}的𝐾元子集 并对所有𝑖𝒜和𝑗𝒜，使得𝑍(𝑊𝑁𝑍(𝑊𝑁)，则称参数为(𝑁,𝐾𝒜𝑢𝒜𝑐)的𝐺𝑁由定义2.3.1[6]看出，极化码与信道参数是有关的，对于某一个信道构造的有𝑖∈𝒜和𝑗∈𝒜𝑐，𝐼(𝑊(𝑖)≥𝐼(𝑊(𝑗))成立的𝐾元指标子集𝒜 码氏参数与消息块错误概率界有关。向量与冻结比同构成编码前向量，经过编编码产生极化码。本节给出极化码版本的信道编码定理。编码定理作为通信领域的发现，给定一个B-DMC𝑊和𝑅>0，定义𝑃𝑒(𝑁𝑅)�𝑃𝑒(𝑁𝑁𝑅𝒜)，𝒜的选择与信道𝑊下的极化码相对应。因此，𝑃𝑒(𝑁,𝑅)表示信道𝑊下码长为𝑁，码率为𝑅的极化码在SC译码算法下，针对所有可能的冻结向量𝑢𝒜𝑐的平均消息块错误概率。极2.3.1对任意给定B-DMC𝑊和𝑅<𝐼(𝑊)，极化码在SC译码算法下的块𝑃(𝑁,𝑅)=𝑂(𝑁−1 ■定理 对任意B-DMC𝑊和任意给定𝑅<𝐼(𝑊)，考虑一系列参数为(𝑁,𝐾,𝒜,𝑢𝒜𝑐)的𝐺𝑁陪集码，𝑁增大趋近于无穷，𝐾=⌊𝑁𝑅⌋，𝒜按照信道𝑊的极化码的定义选择， 固定为任意一个值，则在SC译码算法下的误块率符合𝑃𝑒(𝑁,𝐾,𝒜,𝑢𝒜𝑐)= ■另外使用标度律分析的SC下的极化码性能结果参考文献[23]定理2.3.3 对于𝐺𝑁-陪集码，其编码复杂度和SC译码算法复杂度都是𝑂(𝑁log𝑁)，其中𝑁是码长。 从定理2.3.[6]可以看出，编译码复杂度与码率和冻结比特的选择无关。在极化码的构造方面，除了BEC以外，尚未发现低复杂度的构造方法。在BEC构造复杂度为(𝑁)。极化码根据其原理可以进行递归构造，但是仅限于BEC，在其他信道上大多采用近似构造的方法。本节介绍目前极化码下复杂性最低的构造方法，即在BEC对任意𝑁2𝑛其中𝑛1和1𝐾𝑁设参数为(𝑁,𝐾的极化码生成矩阵为𝐺𝑃(𝑁,𝐾)是个𝐹⊗𝑛的𝐾×𝑁子矩阵。首先，通过如下递归计算向量𝑧𝑁𝑍𝑁,1···𝑧𝑁,𝑁)，2{ 2

对1𝑗𝑧2𝑘,𝑗

2

对𝑘1≤𝑗≤

对所有𝑘1222···2𝑛−1，并使得𝑧1,1𝜖，𝜖为擦除概率。接下来计算(1···𝑁)的置换𝜋𝑁𝑖1···𝑖𝑁)，使得对任意1𝑗𝑘𝑁，不等式𝑧𝑁,𝑗𝑧𝑁,𝑖𝑘成立。生成矩阵𝐺𝑝(𝑁𝐾)为矩阵𝐹𝑛的𝑖1···𝑖𝐾行的行向量组成的矩阵。该算法的计算复杂度为𝑂(𝑁log𝑁)。本章首先从信道极化的原理介绍，然后讨论信道通过组合，得到的新的二次信道的极化现象，进而引入𝐺𝑁-陪集码。通过与极化现象相适应的𝐺𝑁-陪集码相似的Reed-Muller码相对比。另外对极化码在SC译码算法下的性能进行了仿真分析，通过随机构造的方法，分析极化码的冻结位分布，对SC译码算法下的极化极化码与Reed-Muller极化码在结构上与Ree-Muller码比较相似。Reed-Mull码可以看成是冻结向量为0的一种𝐺𝑁-陪集码。在构造上，极化码根据二次信道𝑊(𝑖)氏参数来选择较好的二次信道对应的行向量组组成生成矩阵。而Reed-Mullr码是在同一𝐺𝑁矩𝑅𝑀(,𝑛)的Reed-Mullr码选择𝐺𝑁=𝐹⊗中汉明重量大于等于2𝑛−𝑟的行组成生成矩阵。因此两种码Reed-Muller码的一种优化构造。本节给出对极化码和Reed-MullerP结果来自文献[12。BP译码不是本文主要考虑的译码问题，但是由于Reed-Muller码可以通过BP进行译码，对两种编码使用同样的译码算法可以进行公平的对比。BP译码算法[3]应用于极化码的原因在于𝐺𝑁-陪集码生成矩阵𝐹⊗𝑛的稀疏性和与Reed-Muller码的相似性。Reed-Muller码通过𝐹⊗𝑛的因子图（如图3–1为一个⊗3因子图表示）利用BP译码算法进行译码[24],因此可以将同样的译码算法应用的极化码上。Muller码性能要好，针对各信道擦除概率构造的极化码比单个极化码结构使用在不同信道条件下的表现要好。表3–4和表3–5给出在BSC下的极化码和Reed-Muller码仿真结果，极化码在BSC下的构造按照BSC方法构造，其初始构造参数为𝜖=1𝐶，其中𝐶为BSC信道容量。可以看出，在BSC下，极化码优于Reed-Muller码。表3–6和表3–7给出Reed-Muller码和极化码在不同信噪比下加性信道表现。以上仿真中，通用极化码（未根据信道参数构造的极化码初始条件𝑧1,1=1/2。从仿真结果可以看出，极化码可以在所有Reed-Muller码的应用场景中代替Reed-Muller码，降低编码的译码门限，提高编码的纠错性能。另外文3–1𝐹⊗3 给出了极化码在BSC信道、瑞利信道、二元AWGN信道下的BP译码性能仿真结果，结果表明，极化码性能优于Reed-Muller码。SC译码顾具体的译码算法，即式(2–18)中条件的递归计算方法。𝐿(𝑖)(𝑦𝑁,ˆ𝑖−1

ˆ𝑖−1)卢 ˆ𝑖−1

𝑖−ˆ𝑖

0,如果𝐿 其

1)≥

𝐿(𝐿(𝑖)ˆ2ˆ2𝑖−2 ˆ2𝑖−2𝐿(2𝑖−1)(𝑦𝑁,ˆ2𝑖−2)1 𝐿(𝑖) ˆ2ˆ2𝑖−2 ,ˆ2𝑖−2 ,和ˆ2𝑖−1ˆ2𝑖−2𝑢2𝑖−2)]1−2

𝐿(𝑖) ˆ2𝑖−2 1因此，计算一个𝑁长极化码的似然比问题可以转化为两个计算𝑁/2长极化码的似然比问题，最终递归成计算1长极化码似然比问题，且𝐿(𝑖=𝑊(𝑦𝑖|0)/𝑊(𝑦𝑖|1)1SC译码下极化码性能仿根据节3.1的分析，极化码作为Reed-Mull码的优化，是基于SC译码的极化结构下的结论，对于在P译码和近似构造信道下（无最优简化构造算法的信道，比如二元WG，S，极化码的P译码仿真结果12,25]表明其纠错性能强于Reed-Muller码，但是，P迭代译码复杂度较高，虽然极化码可以在理论上被证明为好码（即当码长趋近于无穷时，在S译码下极化码达到对称信道容量，P译码下的极化码与LP码和BJ算法下的urb码相比较在复杂度上有劣势。与极化码结构最有一致性的S到对称信道容量，但是其译码算法本身却为非ML译码，限制了极化码性能的进一步提升，本节给出一些极化码在S译码下不同码长的一些仿真，并对其进行对比。针对仿真中极化码的构造问题，由于非BEC下极化码无低复杂度的构造方–2（码长𝑁=256WG信道下的性能仿真曲线，极化码采用随机构造，选取性能最好的极化码进行对比，图中横坐标为𝑠𝑁0，与表3–7中的数据进行对比，可见复杂度更高的BP迭代算法下的极化码性能表现更好，由于图中信噪比参数为𝐸𝑠𝑁0，在低码率下，纠错性能差距已经不大，代表了该码长下的S图3–3给出上述三种码率的极化码字错误率仿真数据，可见在低码率的情况下，其不同码率的码字的字纠错能力类似，而低码率下的信息比特纠错能力略好为256极化码消息位和冻结位的分极化码的构造问题就是选取极化码冻结比特位置和消息比特位置的问题，图3–7和图3–6给出通过仿真选出的随机构造性能较好的极化码的冻结位和消息位与图2–4不同，图2–4其信道极化后的互信息较大的二次信道（信息位的位置）处于编码向量𝑢𝑁11信息位大部分位于编码向量𝑢𝑁中靠后的位置。这实际上与SC译码为非ML准则的1量𝑢𝑗（包括已知的冻结比特和已经通过估计出的比特）看作已知，而对𝑢𝑁中 任一信息位𝑢𝑗

本章根据极化码的的误码率性能仿真结果，和补充的SC译码算法的仿真，考虑PolarCodes与Reed-Mullr比较和分析，并分析极化码和Reed-Muller码在生成矩阵构造上的区别。从本章引Reed-Muller码具有一定的性能提升，因此，不管从理论上还是仿真结果来看，极化码都是对Reed-Muller码的优化，在实际Reed-Muller码应用的地方可以使用极化码进行替换。但是与信道极化理论最一致的SC译码，虽然其计算复杂度比使用迭代方式译码的P性规划译码26–28]复杂度要低（𝑂(𝑁𝑙𝑜𝑔𝑁)）6]，但是其性能差距也较大，其原因主要有两点：一，SC2𝑛特定码率和性能需要的码长以指数增长29]，因此短码纠错性能有瓶颈；另外极化码的SC译码算法为非ML译码，虽然在码长趋近于无穷时，在理论上不影响极化码达到对称信道容量的结论，但是对有限长极化码，这是SC译码限制极化码性能的重要原因。在本节的讨论的内容基础上，我们在后面将介绍目前学术界对极化码的S3–1𝑁=256，BEC下RM码仿真结果--------------------3–2𝑁=256，BEC下极化码仿真结果------------------3–3𝑁=256，BEC下极化码仿真结果，极化码根据信道参数构造------------------3–4𝑁=256，BSCRM码仿真结果--------------3–5𝑁=256，BSC极化码仿真结果--------------3–6𝑁256，二元AWGN信道Reed-Muller仿真结果信噪比-----------------------------------3–7𝑁256，二元AWGN信道极化码仿真结果信噪比-----------------------------------本章讨论极化码的S译码算法，作为S译码算法的改进，其纠错性能有了较大的提高。在节已经介绍了极化码的SS算法由于将比特以后的冻结向量作为未知信息，因此S并非M译码，目前对于短的极化码，已有M译码算法的研究30。但是在长码长的情况下，C译码由于其递归地运算过程和与极化码结构的适应性，针对极化码仍然是最有应用前景的译码算法。SC算法是针对SC算法针对误码性能上的改进方法，在𝑁=2048的码长下，SC相对于ML界相差03B左右14]，而SL算法与ML界基本重合，如果牺牲较小的编码速率，通过对编码信息进行冗余校验，则可以在使用S译码算法的接收端使用R辅助译码路径选择，这实际上是一种级联码，目前极化码也有一些与Reed-olomen码和LP码等的级联研究31–33。SCL译码的缺点是译和，极，SL译。SCL译码算SCL译S译码算法的基本思想是在SC过因(2–18)每一个比特位被确定为0或者，而是保存多条可能的译码路径。如图4–1表示了一个S的译码过程，其中保存的最大路径数𝐿=，虚线表示被舍弃的路径，而实线表示被保留的路径。二叉树的每一层表示对应的编码前的向量的比特位。当SCL译码结束后，从4条路径中选择似然概率最大的一条或者通过其他方法(比如)4–1译码路径，𝐿用𝑆(𝑖)表示第𝑖步中保存的所有路径。𝐿表示最大路径数，SCL译码步骤如下[14,34]，初始化，使𝑆(0)={Φ，𝑃(Φ)=1，其中Φ2.比特估计，对位于𝑖=1,··𝑁扩展，对于每一个在保存路径集𝑆(𝑖−1)中的路径，在估计𝑢𝑖使得𝑢ˆ𝑖={ˆ𝑖|ˆ𝑖−1ˆ𝑖 11(ˆ𝑖(ˆ𝑖−1)𝑝(ˆ𝑖ˆ𝑖−1 其中𝑏01} 𝑦,^𝑖−|^𝑖(ˆ𝑖

=

) 𝑏 𝑊𝑦) 𝑏

ˆ𝑖 ˆ𝑖其中1c表示示性函数，即如果条件𝑐满足，则1c1。可以看出，每经过一步扩展运算过程，保留路径数翻一番，|𝑆(𝑖)|=2|𝑆(𝑖−1)|。筛选一，如果经过步骤2a后，|𝑆(𝑖)|≤𝐿，则略过此步骤，否则保留𝐿ˆ𝑖(ˆ𝑖 11路径，当所有比特被估计完成后，对保留路径集合𝑆(𝑁)中所有比特序列重新编码并计算似然概率，选择其中最大者所对应的序列作为输 𝑊(𝑦𝑖|𝑥𝑖=(ˆ𝑁·𝐺𝑁 从以上译码过程看出，最大保留路径数𝐿=1的SCL算法等同于SCSCL+CRC译现方法。SCL算法作为一种改进SC算法的扩展，并未改变SC译码算法本身的过程，即仍然把当前比特后面的冻结比特认为是未知信息，非ML译码。这说 仅有唯一通过CRC的一条路径时，输出该路径没有路径通过CRC校验时，输出似然概率最大的一条路径在SCL添加CRC校验后，极化码的纠错性能大幅度提高，优于对应码长的ML界。如图4–3给出了码长为2048下的1/2码率极化码在不同译码方法下的性能表现，当保留路径条数𝐿增大时，译码纠错能力提高，最终与ML界重合。添加CRC进行辅助校验选择路径时，纠错能力仍有0.7dB左右的提升，超过了ML译码性能界，但是由于添加冗余校验比特，因此有非常小的码率损失。图4–4给出极化码及目前应用在WiMax中的LDPC码性能对比，SCL+CRC比相近码长的LDPC码纠错能路径数自适应的SCL译在S译码算法中，最大保留路径数一般被事先设定好，当译码运算中被保留的路径数|𝑆()|>𝐿，多余的路径将被舍弃。在译码过，由于纠错码本身的纠错能力较强，传输中多数码字实际需要保存的路径数并不需要那么多，仅可能有少量码字因偶然原因使得出错概率增加，需要保存较多译码路径，所以动态调节𝐿的大小是一种有效节省译空间的方法。动态改变值的算法过程如下1.初始化使得最大保存路径数为𝐿=1，设定一个最大值4–3码长为2048下的1/2码率极化码在不同译码方法下的性能表现4–4码长为2048下的1/2码率极化码及其他码的性能表现对比对接收向量进行极化码的SCL译码，并对所有最终保留的译码路径进行CRC校验；如果有一条或者多条保留路径序列通过了CRC校验，则输出通过CRC校验重新设置𝐿变为原来的两倍，如果𝐿≤𝐿𝑚𝑎𝑥表4–1给出在动态设定保存路径数目时，实际译码过保存的译码路径条数的平均值，当信噪比𝐸𝑏/𝑁0增大时，𝐿的均值随之减小，且实际保存的路径数目远远小于设定的最大值；图4–5给出不同最大保存路径数𝐿𝑚𝑎𝑥设置下的极化码SCL译码性能表现。有趣的现象是，在𝐸𝑏/𝑁0较大，信道条件较好时，平均保存路径数都在2附近，但是较大的𝐿𝑚𝑎𝑥的𝐿均值也较大，且纠错表现更好，这说明在较好信道条件下，极少的码字在传输过，接收向量出现了较大的偏差很高的保存译码路径条数，而对大多数码字的译码来说，从表4–1看出，保存过多的译码路径条数造成的运算和浪费极大，因此动态调节𝐿的大小是非常有4–1动态调节保存路径数，SCL算法中𝐿的均值𝐿𝑚𝑎𝑥=𝐿𝑚𝑎𝑥=-𝐿𝑚𝑎𝑥=--𝐿𝑚𝑎𝑥=--𝐿𝑚𝑎𝑥=--多层SCL+CRC译码算法与复杂度分为了减少极化码的SCL译码路径所占用的器空间，改进SCL译码自适应路径数算法下的计算复杂度和降低SC译码过前期已估计比特错误造成的错误，我们引入多层SCL算法。多层SCL+CRC1SCL+CRC编译码算法如图4–2，包含消息比特和冻结比特的编码向量𝑢𝑁通过CRC校验并被添加了冗余比特，在SCL译码结束之后，𝐿14–5(2048,1024)不同𝐿max下极化码字错误率出结果。多层SCL与其区别是对编码序列进行分段CRC校验，由于SC译的特性，译码结果是从𝑢1到𝑢𝑁顺序输出，因此，在SCL译码每进行一段时，对已输出的序列进行CRC校验，如图4–6所示。在每一段校验结束后，仅保留该段的一条通过CRC校验的或似然概率最大的一条路径，在后面的SC译码过仅适用该条类似节4.1.1，我们给出多层SCL+CRC译码步骤初始化，使𝑆(0){Φ}，𝑃(Φ)1，其中Φ2.比特估计，对位于𝑖=12,···,𝑁的比特进行估计，其过程如节4.1.1，当译码过程进行到每段的段尾（设此时完第𝑖个比特）时，进入下一步；3.路径，对保留路径集合𝑆)中所有比特序列重新编码并计算似然概率，进行CRC校验，按照与单层SCL+CRC相同的规则选择该段的路径并作为该段的估计结果。如果𝑖=𝑁本节分析多层SCL的复杂度问题如图4–7给出SCL+CRC编译码算法中对译码路径的空间占用。在译码过𝐿，忽略在路径数未达到𝐿时的比特的误差，认为在每一个比特（每一级）译码时都了𝐿个路径，而每个路径在第𝑖步了𝑖𝐿个比特，SCL译码结束时，总共占用了𝑁𝐿bits的空间，如图4–7阴影部分所示。在多级SCL+CRC译码算法中，如图4–8所示，译码路径被分成了𝑀层 个比特，每译完一层，便通过CRC校验，选出一条最优路径并舍弃其在该阶段所保存的路径，因此在译码的任何一级𝑖（由于𝑁>>𝑀，同样设在每一级译码过保存了𝐿条路径，总共保存的路径数为𝐿(𝑖mod𝑁)+𝑖∖𝑁≤𝐿𝑁+ 𝑖∖𝑁，所以在译码进行到第𝑁级的时候总的占用空间为𝐿𝑁+(1−1𝑁)

𝜂=𝑀+𝐿− 当我们去掉CRC校验运算，并将整个码字分为𝑀=𝑁层，此时多级SCL译码等价 𝑁−10SC译码，也等价于𝐿=1的SCL译码（因为每层最多只能保留2 =2=1路径，此时两种译空间占用相同，将𝐿=1代入式(4–5)得到𝜂=1。对于SC译码，仅保存当前位之前的一条路径，器路径消耗为𝑖，译码结束时占用空间为𝑁bits。从式(4–5)可以看出，当分层数𝑀和保存路径数𝐿越大时，多层SCL+CRC译码算法所带来的器节省。例如，本文仿真结果4–9中采用的分层数𝑀=4，保留路径数𝐿=32，则相对于SCL+CRC译码算法来说，多层校验节省了72.66%路径空间。在码长𝑁一定的情况下，根据码率和能添加的校验冗余比特的个数，一般𝑀𝐿设置越大，说明极化码所应用的信道条件较差，需要保存路径改进SC译的译码，但是多层SL+CRC译码将长路径拆分成短路径进行考虑，实际上是将一个整体区域的最优路径拆分成寻找各局部区域的最优路径，必然带来性能上的损失。多层SL+CRC另外带来了一个好处：SC译码中由于译码的前后关系，前面比特的错误容易引起后面比特的错误，引起错误，期对路径进行筛选可以降低前期短路径出错的概率，错误生。进行，在本文分层译码算法中，CRC总的冗余比特数目不变，因此其校验图4–7SCL+CRC结多层SCL+CRC我们给出多层C编译码系统和未分层C编译码系统的误码率仿真曲线，极化码的码长为𝑁=1024，码率𝑅=12，保留路径数𝐿=32，其误帧率结果如图4–9所示，对于不分层的SL编译码算法，采用一个冗余长度为32的C校验多项式，对于分层数为2的SL，采用两个8比特冗余的CRC校验生成多项式，以保证总的冗余和最终一样，对于4层和8层的同理。结构纠错性能损失了0.3dB。误码性能损失的主要原因除了上一节所分析的内容图4–8多层SCL+CRC结4–9𝑁=1024，码率𝑅=0.5多层SCL+CRC纠错性能表自适应路径数多层SCL+CRC译码算类似节4.2.1，我们给出自适应路径数多层SCL+CRC译码算法步初始化，使𝑆(0){Φ}，𝑃(Φ)1，其中Φ2.比特估计，对位于𝑖=12,···,𝑁的比特进行估计，其过程如节4.1.1，当译码过程进行到每段的段尾（设此时完第𝑖个比特）时，进入下一步；3.路径，对保留路径集合𝑆)中所有比特序列重新编码并计算似然概率，进行CRC校验，如果有一条或者多条保留路径序列通过了CRC校验，则保留通过CC校验并且路径似然概率最高的一条短路径作为当前层的估计值；否则，重新设置𝐿变为原来的两倍，如果𝐿≤𝐿𝑚𝑎𝑥，则回到本步骤开头；若𝐿=𝐿𝑚𝑎𝑥，保留似然概率最高的一条路径作为当前层的段路径估计结果。如果𝑖=𝑁，输出所有估计序列作为译图4–10给出码长为𝑁2048，码率为0.5的保留路径数自适应的极化码SCL+CRC的与未分层的SCL+CRC译码算法性能已经非常接近，其原因是由于设置的𝐿𝑚𝑎𝑥通收设备中最复杂的一个部分就是译，译码算法的复杂度对译的硬件实现有着决定性的影响，SC译码或BP译码已经有了硬件上的实现[36–39]，但是SC译码算法为非ML译码，且因有限长极化码固有的缺陷，其性能受到了其[26]，加SC译码保留路径条数，即SCL译码算法并对其做CRC，但是这种方法成倍地增长了译码的复杂度和路径消耗。通过路径自适应数的算法，SCL的路径条数可以显著减少。针对SCL+CRC，本章性的提出了多层SCL+CRC译码算法多层SCL+CRC、自适应SCL+CRC译码和多层自适应SCL+CRC进行了仿真并分析第五章搭线信道极化码安全1如节2.2所述的信道极化现象发生在递归构造的二次信道𝑊(𝑖)上，随着独立信道𝑊的传信次数𝑁以2的幂次增加，二次信道对称容量使用总次数占𝐼(𝑊)部分趋近于1，剩余部分趋近于0，这个过程实际上是在所有的𝑁个信道𝑊的总容量不组合、结构上的一致性，包含消息向量和冻结向量的极化码编码前向量𝑢𝑁与二次信道𝑊(𝑖)一一对应，因此通过集合论的方法，可以证明极化码达到信道的安全容量[9–11]。另外，本章通过仿真讨论有限长极化码在搭线信道下的表1搭线信道中的极化码应搭线信搭线信道模型如图5–1，模型有三个参与者：发送者Alice，接收者Bob和者Eve。Alice的目标是将消息无错的发送给Bob且防止被Eve获知。搭线窃听信道模型将信道分为两个子信道：主信道（Alice到Bob）和信道（Alice于信道有噪声，𝑌和𝑍都是𝑋(𝒳,𝑊(𝑌,𝑍|𝑋),𝒴 为输入字符集，𝒴和𝒵分别为主信道输出符号集和信道输出符号集图5–1搭线信道模极化码安全容量可考虑一个二元搭线信道，即𝒳={0,1}，主信道转移概率为𝑊𝑚(𝑌|𝑋)，且存在一个条件概率分布𝑊𝑑(𝑍|𝑌)，使得信道转移概率为𝑊𝑒(𝑍|𝑋)称𝑊𝑒为𝑊𝑚的信道。有结论

𝑌

𝑊𝑚(𝑌|𝑋)𝑊𝑑(𝑍|𝑌 定理 如果𝑊𝑒是𝑊𝑚的信道，则𝑊(𝑖)是𝑊(𝑖)的信道，且𝑍(𝑊(𝑖)) 𝑍(𝑊(𝑖)) 搭线信道存在一个安全信道容量𝐶𝑠=max(𝐼(𝑋;𝑌)−𝐼(𝑋;𝑍))，对于退化信道来说，安全容量简化为𝐶𝑠=𝐶𝑚−𝐶𝑒，其中𝐶𝑚和𝐶𝑒分别代表主信道和信设信道𝑊𝑒为主信道𝑊𝑚的信道，则针对信道构造一个极化码，设其信息位指标集为𝒜𝑒，则冻结比特指标集为𝑒；针对主信道的极化码信息位指标集为𝑚，冻结比特指标集为𝑚，由于定理5.1.，则在码长趋近于无穷，信道充分极化的情况下，有𝑒⊂𝑚，则𝑚⊂𝑚，使向量𝒜𝑚∖𝒜𝑒作为消息比特，向量𝑢𝒜𝑒为随机比特，𝑢𝑚为冻结比特。则针对信道或者主信道构造的极化码可以达到搭线信道安全容量。有限长极化码与安全性通信应用分极化码达到搭线信道容量的思想和达到二元对称信道容量的思想是类似有限的情况下（实际应用中，极化码的二次信道并未完全极化，在普通极化码应用中，根据码率𝑅选择巴氏参数𝑍最小或者对称信道容量𝐼最大的部分做为消息比特编码的位置；而在搭线信道下，在对各二次信道做好巴氏参数或对称容的大小排序后，最好的一部分二次信道不能被用来传消息，只能用来传随机序列以防止e对信息的。而随机序列的长度却很难确定。最好的一部分信道实际上由于有限码长下极化不充分的原因（有限长极化码请参考[13,40,1]，其巴氏参数并非大程度上趋近于，且次优的信道其𝑍参数相对较大，有限码长下传输随机序列和信息序列的二次信道总数要小于码率与码长之积𝑁，因此对于主信道的传输速率将大大降低，且必须保证搭线信道中主信道和信道质否输性性法的。如图5–3所示，其中𝐶𝑚表示主信道的对称容量。在有限长极化码应用下，最好的𝑁𝐶𝑚个二次信道并不能全部用来传输信息比特，其中较差的部分用来做冻结比特，因此实际有限长极化码的物理安全应用要受到局限。我们后文考虑在特定情况下使用商定好的密钥来作为冻结比特的极化码通信方法。下一节首先介绍退验。BEC信道特性与密钥分BEC考虑一个物理信道如图5–1，存在一个条件概率分布𝑊𝑍|𝑌(𝑌|𝑍)，则其定𝑊𝑍𝑌|𝑋(𝑍,𝑌|𝑋)=𝑊𝑍|𝑌(𝑍|𝑌)𝑊𝑌|𝑋(𝑌 𝑊𝑍|𝑋(𝑍|𝑋)

𝑊𝑌|𝑋(𝑌|𝑋)𝑊𝑍|𝑌(𝑍|𝑌 们后面的分析。从式(5–2)可以得到𝑃(𝑋,𝑌,𝑍)=𝑃(𝑍,𝑌)𝑃(𝑌,𝑋) 𝑃(𝑌

𝑃(𝑍,𝑌,𝑊𝑍|𝑌,𝑋 𝑃(𝑌, 𝑊𝑍|𝑌,𝑋(𝑍|𝑌,𝑋)=𝑃(𝑍,𝑌)=𝑊𝑍|𝑌(𝑍|𝑌 𝑃(𝑌从式(5–6)可以看出，𝑋→𝑌→𝑍形成马尔可夫链。将条件概率分布𝑊𝑌|𝑋(𝑌看作某个信道的𝑊𝑌|𝑋对于一个二元BEC信道，输入符号集𝒳{01}，输出符号集𝒴𝒵{01𝜃}，𝑋→𝑌→𝑍信道𝑊𝑌|𝑋和信道𝑊𝑍|𝑋为信道𝑊𝑍|𝑌的输出和输出符号集都是{01𝜃}第一个陈述和第二个陈述（𝑋→𝑍为BEC信道，如图5–5）如前所述是正确的；因为𝑌∈𝒴且𝑍∈𝒵，因此可以把信道𝑊𝑌|𝑋(𝑌|𝑋)看作三输入三输出的信道，设主信道和信道的擦除概率分别为𝑃𝑏和𝑃𝑒，本文给出以下结论定理5.2.1 对一个物理BEC搭线信道，如果Bob接收到擦除符号𝜃，则Eve接收到擦除符号的概率为1；如果Bob接收到符号𝑌∈{0,1}，Eve将接收到符号𝑍∈{0,1,𝜃}，且𝑌→𝑍等价于一个BEC，其擦除概率设为𝑃𝑣，其与𝑋→𝑍信道擦除概率𝑃𝑒的关系为𝑃𝑒=𝑃𝑏+(1−𝑃𝑏)𝑃𝑣 5–4𝑋𝑌𝑍的转移路5–5𝑋𝑍的转移证明考虑如图5–4右边的转移关系。从𝑌到𝑍信道有9条转移路径，由式(5–2)， 𝑊𝑍𝑌|𝑋(𝑍=1,𝑌=0|𝑋)=𝑊𝑍|𝑌(𝑍=1|𝑌=0)𝑊𝑌|𝑋(𝑌= 如果Alice发送符号为0，从式(5–7)，𝑊𝑍|𝑌𝑋(𝑍=1,𝑌=0|𝑋=0)= 𝑊𝑍𝑌|𝑋(𝑍=1|𝑌=0|𝑋=𝑃(𝑌== 根据式(5–6)和式(5–8)，𝑌0下𝑍1𝑊𝑍|𝑌(𝑍=1|𝑌= 𝑊𝑍|𝑌𝑋(𝑍=1|𝑌=0,𝑋==

𝑊𝑍|𝑌(𝑍=0|𝑌=1)= 从式(5–3)和式(5–10)，考虑转移概率𝑊𝑍|𝑋(𝑍=1|𝑋=0)，根据前面的第三个陈述，𝑊𝑍|𝑋(𝑍=1|𝑋=0)=0，且𝑊𝑍|𝑋(𝑍=1|𝑋= 𝑊𝑍|𝑌(𝑍=1|𝑌=𝜃)𝑊𝑌|𝑋(𝑌=𝜃|𝑋=+𝑊𝑍|𝑌(𝑍=1|𝑌=1)𝑊𝑌|𝑋(𝑌=1|𝑋=+𝑊𝑍|𝑌(𝑍=1|𝑌=0)𝑊𝑌|𝑋(𝑌=0|𝑋= 𝑊𝑍|𝑌(𝑍=1|𝑌=𝜃)𝑊𝑌|𝑋(𝑌=𝜃|𝑋= 𝑊𝑍|𝑌(𝑍=1|𝑌= 仅需要考虑主信道擦除概率𝑃𝑏>0的情况，则由式(5–11)𝑊𝑍|𝑌(𝑍=1|𝑌=𝜃)=

𝑊𝑍|𝑌(𝑍=0|𝑌=𝜃)= 从式(5–9)、式(5–10)、式(5–12)和式(5–13)可知，图5–4的概率为0，即不存在信道上这样的转移路径，又由 𝑍∈𝒵𝑊𝑍|𝑌 =𝜃)=有𝑊𝑍|𝑌(𝑍=𝜃|𝑌=𝜃)= 𝑊𝑍|𝑌(𝑍𝜃|𝑌0全𝑊𝑍|𝑌(𝑍𝜃|𝑌1全𝑊𝑍|𝑌(𝑍=0|𝑌=0)=1−𝑊𝑍|𝑌(𝑍=1|𝑌=1)=1−𝑊𝑍|𝑌(𝑍=𝜃|𝑌=𝜃)= 𝑊𝑍|𝑌(𝑍=𝜃|𝑌=1)𝑊𝑌|𝑋(𝑌=1|𝑋=+𝑊𝑍|𝑌(𝑍=𝜃|𝑌=𝜃)𝑊𝑌|𝑋(𝑌=𝜃|𝑋=+𝑊𝑍|𝑌(𝑍=𝜃|𝑌=0)𝑊𝑌|𝑋(𝑌=0|𝑋==𝑃𝑣(1−𝑃𝑏)+ 因𝑃𝑏𝑃𝑣(01)0<𝑃𝑒=𝑃𝑣(1−𝑃𝑏)+𝑃𝑏<1−𝑃𝑏+𝑃𝑏= 所以𝑃𝑒∈(0,1) 边为物理搭线信道仿真结果。另外，搭线信道安全容量为主信道容量减对称信道容量[42]。则由定 =𝑃𝑒 反馈模型下的密钥分发方案与安全性本节介绍上一节中的信道模型中的密钥分发方法，并对其进行分析。为了成功进行密钥分发，在模型中引入一个公共无噪声信道，如图5–，公共无噪信道上的信息可以被Alice和e无差错的获取。密钥分发的基本思想是通过多次发送随机序列，Bob反馈被擦除的符号位置并去掉被擦除的符号，Alice将同样位置的信息去掉，这样，Alice和Bob手里的比特序列是相等的，而e尽管也可以去掉同样位置上的序列，但是其手中的序列有一部分以较大的概率是被擦除的。称Alice和Bob手中的序列为长序列（与后文中短序列相对应，为不失一般性，我们对这个序列的变换进行讨论，并将其应用到后面介绍的该模型上的极化码安全通信设一个双射𝐷𝒳𝑁→𝒰𝑁。Alice和Bob 图5–7引入反馈的搭线信道模1Alice产生一串独立均匀分布的二进制序列𝑥𝑁，通过信道发送随机序列1Bob接收到主信道的输出序1𝑦𝑁{𝑦1𝑦2···𝑦𝑁01𝜃}𝑁。设{𝑖|𝑦𝑖1𝜃}，Bob将向量𝑦ℬ{𝜃}|ℬ|替换为任意事先选好的公开序列𝑐|ℬ|∈{01}|ℬ|，1换后的向量𝑦𝑁变为新向量𝑦′𝑁，计算𝑠𝑁=𝐷(𝑦′𝑁)为密钥 Bob通过道发送指标集ℬ给Alice，同时Eve也会获知Alice将𝑋ℬ替换为公开序列𝑐|ℬ|∈{01}|ℬ|得到新的序列𝑥′𝑁计算𝑠′𝑁 𝐷(𝑥′𝑁)，显然𝑥′𝑁𝑦′𝑁，𝑠𝑁𝑠′𝑁 1经过以上过程。Alice和Bob获得了一致密钥𝑠𝑁。密钥是一个𝑁长的二进制序列，但是相对于Eve的信息熵𝐻(𝑠𝑁|𝑧𝑁,𝑐|ℬ|)≤𝑁，其中𝑧𝑁为信道的输出。如1 果构建一个双射𝐷|ℬ|:𝒴𝑁−|ℬ|→𝒯𝑁−|ℬ|，用 替代𝐷并舍弃𝑦𝑖=𝜃,𝑖=1,2,···,𝑁 协商一致的密钥变为𝑡𝑁−|ℬ|，称为短序列，有𝐻(𝑡𝑁−|ℬ||𝑧𝑁)≤𝑁−|ℬ| 1下面我们对密钥的安全性进行分析。长序列随机向量用𝑆𝑁表示，1用𝑌1𝑁−|ℬ|表示。根据数据处理不等式[43]，𝐻(𝐷(𝑋𝑁 𝐻(𝑋𝑁 因为𝐷和𝐷|ℬ|都是双射，𝐻(𝑋𝑁)=𝐻(𝐷−1𝐷(𝑋𝑁))≤𝐻(𝐷(𝑋𝑁 和11 1 1

𝐻(𝑋𝑁)=𝐻(𝐷(𝑋𝑁 𝐻(𝑋𝑁−|ℬ|)= 𝐻(𝑆𝑁|𝑍𝑁, 𝐻(𝐷(𝑌′𝑁)|𝑍𝑁, 𝐻(𝑌′𝑁|𝑍𝑁, 填充的公开比特序列𝑐|ℬ|由Alice和Bob随机选择，它与序列𝑌𝑁∖𝑐|ℬ|1 =𝐻(𝑌′𝑁|𝑍𝑁, 𝐻(𝑌ℬ,𝑐|ℬ||𝑍𝑁, =𝐻(𝑌ℬ|𝑍ℬ)+𝐻(𝑐ℬ|𝑍𝑁, =𝐻(𝑌ℬ𝑐|𝑍ℬ𝑐=𝐻(𝐷|ℬ|(𝑌ℬ𝑐)|𝑍ℬ𝑐=𝐻(𝑌𝑁−|ℬ||𝑍ℬ 式(5–26)说明序列𝑆𝑁和𝑇𝑁−|ℬ|相对Eve具有相等的信息量。假设𝒞𝜃} 定理5.2.1看出，𝒞，且剩余符号𝑍ℬ𝑐为图5–4右边的虚拟信道的输出，当仅考虑输入为𝑌ℬ𝑐∈{01}|ℬ𝑐|时，信道为二元BEC信道，有𝐼(𝑌ℬ𝑐;𝑍ℬ𝑐= (𝑁−|ℬ|)(1 其中，擦除信道信道容量𝐶𝐵𝐸𝐶=1−𝑃𝑣𝐻(𝑆𝑁|𝑍𝑁, =𝐻(𝑌ℬ𝑐|𝑍ℬ𝑐=𝐻(𝑌ℬ𝑐)−𝐼(𝑌ℬ𝑐;𝑍ℬ𝑐==(𝑁−|ℬ|)−(𝑁−|ℬ|)(1𝑃𝑣(𝑁比特之差的期望。当𝑁→∞，有lim1𝐻(𝑆𝑁|𝑍𝑁,𝑁→∞

=𝑃𝑣(1−lim 𝑁→∞ 𝑃𝑣(1 Bob接收序列中，有|ℬ|个比特被擦除，对于确定的|ℬ|，密钥协商失败的概为𝑃

由于𝐸(𝑁−|ℬ|)=𝑁−𝑁𝑃𝑏=𝑁(1−𝑃𝑣)，式(5–30)在平均意义上可以写成𝑃(𝑌ℬ𝑐𝑍ℬ)=𝐴𝑁，其中𝐴=(1𝑃𝑣)1−𝑃𝑏，即一个处于0到1之间的常数，所以当𝑁增大时，密钥协商失败的概率呈指数减小。为了密钥的安全性起见，Alice和Bob可以事先设定一个阈值𝑎，为了保证一个较大的𝑁−|ℬ|的值，当某次密钥协商中如果|ℬ|≥𝑎，则放弃此次协商成功的密钥。在实际过，因Alice和Bob并