极化码：主要概念和实用译码算法..doc

极码：主要概念和实用译码算法摘要 极码代表一类新兴的纠错码,他的功率接近一个离散无记忆信道的容量本文旨在说明其生成与解码技术的原则与传统能力编码策略不同,它试图让代码尽可能随机,极性代码遵循不同的原理,这也是由香农通过创建一个典型共同组提出的信道极化，一个概念的核心，就是极性代码，在数字世界中的马太效应之中被直观地阐述，对极性编码的构造方法进行了详细的概述极性码蝴蝶结构介绍中，源位相关，证明SC算法的使用为有效的解码从概念和实践的角度研究了供应链解码技术最先进的解码算法，如BP和一些广义的SC解码，也在一个广泛的框架下解释了仿真结果表明，极性码的级联与CRC码的性能优于Turbo码和LDPC码一些在实际情况下有前途的研究方向在最后也被讨论摘要 1引言 1通道极化 2编码和结构 4编码原则 4通道选择 6连续取消解码 7解码原理 8简单SC译码过程 9更有力的译码算法 10提高的SC译码过程 10CRC-AIDED解码 12置信传播解码 12ML或MAP解码 12优点和缺点 13极性码的缺点 14未来的研究方向 15结论 16附录 16引言在过去的六年中见证了数字通信编码理论的成功克劳德·香农著名的信道编码定理断言代码的存在,信息可以在可靠的噪声信道上传输速率信道容量。

三个基本想法背后的信道编码定理的证明是:(1) .随机选择的代码(2) .对于大型代码长度的联合渐近等分(AEP)之间的传输码字和接收序列3) .最优最大似然(ML)解码或次优联合典型的解码联合AEP在证明过程中扮演着重要的角色,在某种意义上,它保证接收到的序列与共同典型传输码字相似,并且共同典型解码错误的概率消失当然随机编码也很重要,但只是为了便于数学证明好的代码的存在逼近能力与实际编/解码复杂度是编码理论的一个主要挑战幸运的是,在过去的二十年里许多“turbo-like”代码家族,如涡轮码和低密度奇偶校验(LDPC)码,已经被发现实现这一目标关键的问题是如何把实际实现的思想用于信道编码定理的证明在LDPC编码中编码引入随机性窄在涡轮码或伪随机变量之间的连接和检查节点可靠和有效的解码,涡轮码采用迭代BCJR算法(以它的发明者的名字命名的),而LDPC码采用信念传播(BP)算法这两个算法执行仅略次于ML或最大后验概率(MAP)算法鉴于其优秀的性能,涡轮码已经在3 gpp WCDMA和LTE标准先后被采用,并且LDPC码也在IEEE WiMax和802.11 n标准中被采用然而,并没有从理论上严格证明的文献显示,传输通道AEP与这些代码满足联合。

相反,根据含蓄思想(1)和(3)在香农编码定理中的证明,它一直认为独特的方法来设计最优capacity-achievable代码是精心结合伪随机编码和ML / MAP译码算法联合AEP和典型的解码的思想,另一方面,仅视为一种方法被证明了很长一段时间由于最近Arikan[1]发明的极性码使得形势发生变化,它打开了一个新前沿解释的纠错编码来实现任意二进制输入离散无记忆信道的能力(B-DMC)这些新代码家庭植根于一个简洁的效果,叫做通道极化,它可以被看作是数字世界的马太效应起初相同的独立渠道转变成两种稍微不同的可靠性综合频道:好的和坏的通道通过递归地应用这种极化变换产生的渠道,综合频道将显示的可靠性显著差异:“好的变得更好,坏的更糟最后,当代码长度足够大,几乎所有这些合成渠道将趋向两个极端:吵闹的渠道和那些几乎没有噪音的渠道因此,一个自然的编码策略是在无声的渠道传送自由比特(称为信息比特)而在有噪声的渠道分配固定的比特(称为固定比特)回想一下,联合AEP允许我们把所有传输码字和接收序列分成两组,共同典型组（在样本互信息是接近的能力）和无共同典型组（由其余可以忽略不计信息组成）因此,联合组典型的码字可以可靠地通过通道极化产生的无声的渠道传输。

显然,极性编码是一个建设性的联合AEP的实例Arikan的开创性论文[1]提出了一种连续取消(SC)解码作为基线算法其复杂度很低SC解码器的极性代码,我们称之为解码器,可以评估和决定一点消息基于极性编码器的递归结构原则上,SC解码执行一系列交错循序渐进决策的决定在很大程度取决于在前面的步骤中的每一步决策由于其易受误差传播,SC解码显然是一种次优算法然而,SC解码只要代码长度足够大其错误概率可以任意小,并且编码速率小于其能力类似于典型联合解码,这种算法可以渐近获得最优性能,而不需要最优ML /MAP算法或任何形式的迭代除了通道极化的核心概念,解极性代码其他技术关键理也包含在这篇文章中,如施工方法,BP译码,SC解码和它的增强算法本教程文章将引导读者通过概念解释这些重要问题,从实际应用的角度进行一个说明性的阐述对一些相关性的进一步研究的方向也进行了讨论通道极化通道极化可以递归实现将多个独立使用给定的B-DMC转换为一组连续使用合成二进制输入通道极化通道由于链式法则的使用来扩大在源块与接收到的序列之间的交互信息B-DMC作为一个例子,一个二进制消除信道(BEC)在图1a,输入二进制比特x和输出y值0或1。

如果这个BEC擦除的概率是0.5,相应的能力是I(W)= 1 - 0.5 = 0.5结合两个独立使用的BEC,如图1b所示,一个复合通道(W W)获得两个输入位x1,x2,和两个输出位y1,y2很明显相关的能力是2I(W)通过在两个独立的BEC之间使用一个模2运算,一个等价的复合渠道可以获得两个输入位u1,u2和相同的输出比特y1,y2这个通道的能力仍然是2I(W)通过应用交互信息的链式法则,这种复合通道可以分解为两个综合频道:W -频道(绿线所示，输入u1和输出位y1和y2),和W +频道(粉色线所示,输入u2和输出比特u1,y1,y2)通道和通道分割相结合之后,两个独立的bec可靠性转换为相同的两个偏振通道和容量之和两个渠道是不变的,也就是说,+= 2上面的操作被称为单级的变换在[1]Arikan派生的交互信息中两个渠道= 2-,=和证明坏通道W -容量小于给定的BEC ,而好的通道W +有一个更大的能力,也就是说,≤≤特别的,,在这个例子中BEC的情况下(= 0.5),两个极化通道的能力分别是= 0.75和= 0.25此外,四个独立使用给定BEC的,我们可以不断应用单步变换两种用法的和,如图1c所示。

在第二阶段,四个副本的BEC 分为两组,每组两个BEC变成两个偏振通道和自从频道属于不同的组织是相互独立的,我们得到两个独立副本为每个BEC 或在阶段1中相同的操作可以分别申请这两个bec因此通道和(和)来自两个通道()在Arikan推导中，我们使用的通道而不是通道，获得信道和的能力,也就是说,= = 0.0625,= 2- = 0.4375同样,频道和的能力可以分别被认为== 0.5625,= 2- = 0.9375显然的能力与相比进一步减少,而 相对是进一步扩大因此两个渠道相比之下,四个渠道的极化效应变得更加显著通过同样的原理可以不断进行偏振转换 独立使用给定BEC的并且所有的极化通道的能力可以被递归地评估图1 d说明了进化的通道极化编码长度N = ~ ,其中每个节点(黑色圆)表示一个极化通道在一定代码长度,和节点的纵坐标对应通道的能力此外,相邻的两个节点之间的线表示通道极化的演化轨迹例如,当代码长度随N = 至  N = ，一个BEC W演变成两个BEC:和我们用红线标记好的渠道和蓝线标记坏的渠道,如图1d所示好通道相对于坏通道能力的优势可以积累并且极化效应不断提高编码长度增加到N = ~ 。

这种现象是一个典型的马太效应:好的变得更好,坏的变得更糟观察好/坏通道的演化轨迹,我们发现大部分的极化通道的能力倾向于1(好渠道噪声小)或0(坏的通道充满噪音)同样,无噪声通道的误差概率或嘈杂的渠道趋于0或1代码长度N趋于无穷时,马太效应下的极化通道趋于两个极端(对应的能力是0或1)Arikan利用鞅理论证明了随机收敛性质的极化通道的能力[1]尤其是对BEC在这个例子中,无声的渠道的比例正好等于对称能力I(W)= 0.5直观地说,在那些没有噪声的通道传输码字是完全没有错差的传输码字和接收序列的概率是共同典型之一,如同AEP节点所示另一方面,任何随机选择的码字和接收到的序列共同典型只有一个概率约等于,这对于大型的代码长度是可以忽略的这让我们可以断言存在一对一的固定传输码字和接收序列之间的映射,这大约的码字可以可靠地传输这些通道联合典型性,在通道极化的行为,构成了一个关键步骤的信道编码定理的证明作者的最好的知识,这可能是第一个建设性的例子来实现B-DMC的能力编码和结构自从无声的渠道比嘈杂的通道能力的错误概率更高或更低,通道极化现象表明信道编码的新理论,即选择无声的二进制信息渠道传播因为编码速率可以通过添加或删除一个精细偏振通道调整,我们几乎可以不断改变极性码的比率。

与其他编码方案相比,这个比率兼容属性是一个重大优势此外,与传统的代码结构最大化最小汉明间距不同,极性编码的目的是直接地使极化通道的误差概率最小化编码原则一般来说,主要有三种极性编码方案:非系统编码，系统编码和广义连接编码在原来的极性编码中、以非系统编码的形式被使用给定的代码长度,N = 1,2,…,和信息长度K,二进制源块u =(u1,u2、…、uN)由K位信息位和N - K固定位信息代码的码字x速率可以获得如下: (1)其中是生成矩阵,BN 是置换矩阵,是F2的第N个克罗内克符号,并且被称为内核矩阵显然这个编码过程类似于Walsh-Hadamard变换今后,我们将使用一个N = 8, K = 4,R = 1/2的极性代码作为一个例子在这个非系统性的方案下,比特信息被分配给块的来源如图2所示,当固定比特分配给其余的不可靠渠道时，信息比特{u4,u6,u7,u8}被分配到的极化通道误差概率越低每个极化通道与一个特定的行相关联的生成矩阵相关联固定比特通常取固定值0和被假定被编码器和解码器已知对于非系统性极性代码,生成矩阵对应的信息位的行可以由最低的错误概率组成相比之下,Reed-Muller(RM)码生成矩阵的相似,但行选择规则是基于汉明重量的行。

如上[1]所述,RM规则信息比特分配导致渐近在SC解码下不可靠的代码在图2中一个蝴蝶单元可以改变两个独立输入比特(a,b)为两个相关的输出比特,这是由核心矩阵所左右并且与通道极化相适应这个操作还可以递归地应用于整个码字,也就是说,一个码字x在第三阶段分为两个部分,其中每个反过来分裂阶段又分为两部分,这样继续下去,直到在阶段1达到一个单一来源所以极性编码过程中N = 8包含一个信息逆转和蝴蝶操作的三个阶段通常,给定一个代码长度 ,极化变换可以分解成N和每个阶段的蝴蝶操作,导致编码复杂度为根据编码理论,每个线性分组码都可以转化为一个等价的系统代码然后[2]系统的介绍了系统极性编码方案与非系统编码不同，信息比特表现为显然码字的一部分与这些信息比特和固定比特在源块端位,另一位在码字端可以由一些代数运算系统极性编码的主要优势是,他们是更健壮的对抗在SC解码错误传播与原(非系统性)极地代码相比,系统的极性代码具有相同的块错误率(BLER),但优于前者的比特误码率(BER)性能当从广义连接的框架代码观察,极地代码可以分解为一组外部/内部代码[3]即在极地的递归结构代码,第一个l阶段可以被视为外码长度为，剩下的n-l阶段内部编码长度。

这些外部/内部代码都是极性较小的代码的代码长度由于基于块。