《Polar码的译码算法研究10000字（论文）》

第1章绪论1.1课题的来源及意义1.1.1研究背景从古代到现在，人们的生活中处处都离不开通信。通信是人们传输信息的重要方式。信息传输是把有用的信息从信源经过各种信道传输到信宿，信源、信道和信宿便组成了一个简单的通信系统。数字通信技术抗干扰能力较强，安全性较高，因此近些年来被广泛使用。数字通信系统的模型如图1-1所示。图1-1数字通信系统模型在数字通信系统中，信息在信道中传输时很可能会受到噪声的干扰，此外，信号在传输过程中自身也会逐渐的减弱，从而导致信息在传输的过程中出现错误，使信源端发送的信息和信宿端接收到的信息不同，由此产生了信道编码技术。首先需要往信息序列中添加冗余信息，并对冗余信息和信息序列都进行编码，之后在接收端根据信息序列和冗余信息的关系，便可得出信息序列。相应地产生了信道译码。如果信息在传输时出错，那么冗余比特和信息比特之间将不会再满足之前的约束关系，信道译码根据这个特点可以纠正出在传输过程中出错的信息。自从香农定理被提出后，陆续产生了许多编码方案，其中由Arikan教授提出的Polar码是唯一一个在理论上被证明可以达到二进制离散无记忆信道的信道容量的编码方法。此外，Arikan教授还提出了Polar码的第一种译码方法——SC译码。和其他编码方法相比，Polar码的纠错性能更好，因此在很多领域都被广泛应用。为了能进一步提升Polar码的误码性能，降低其误帧率和误码率，相关学者将此编码和一个外码级联，由于CRC检错能力较强、速度也较快，因此常被用来作为外码。本文也正是在Polar-CRC级联码的基础上进行的，通过进一步研究来得到BER和FER更低的译码方法。1.1.2意义有利于建设更高速、高质量的通信系统。通过对Polar码的译码算法进行研究，能够提高Polar码的误码性能，降低Polar码的误比特率和误帧率，提高数据传输的可靠性，对于建设更高速、高质量的通信系统有着重要的意义。1.2研究现状2008年，Arikan教授提出了SC译码算法，它是Polar码的第一种译码方法。SC译码对于中短码来说，译码性能较差。之后，I.Tal[1]、牛凯[2]等人提出逐次抵消列表(SuccessiveCancellationList,SCL)译码方法。SCL译码算法最终保留L条译码路径，选取概率值最大的那条作为最终的译码结果。若L值较大，会导致译码复杂度较高。因此很多学者对SCL译码算法进行了改进，既保留了其优异的特性，又能降低译码的复杂度[3,4]。有的学者将BP译码算法应用于Polar码，提升了其误码的性能和译码速率[5]。CRC也能辅助Polar码译码。牛凯等人把CRC和Polar码级联[6]，译码时可以用SCL译码方法，之后选取能通过CRC检验的码字作为译码的结果，证明了CRC辅助Polar码译码可以有效降低Polar码的误码率。HuiShen等人将动态的SCL译码方法应用于Polar-CRC级联码的译码之中[7]，有效地降低了译码复杂度。YuanruiRen等人将BP译码算法应用到Polar-CRC级联码的译码之中，由于此译码算法在译码过程中会产生迭代过程，因此若码字能通过CRC校验，那么就停止译码过程[8]。此外，随机共振也能有效提升Polar码的译码性能。由Benzi发现的随机共振现象[9]，原本是用来说明冰川问题的，后来被用来检测微弱的信号。Da-shan等人将随机共振应用于检错码和纠错码级联[10,11]，提出PD方法。赵爽将PD方法应用于Polar-CRC级联码[12]。如果码字不能通过CRC校验时，那么就向输出的序列中加入人工噪声，来进行扰动，从而大大的降低了误码率。1.3本文结构本文一共包含五章，各个章节的内容安排如下：第一章，主要介绍了本课题的研究背景和研究现状。先介绍了本课题的研究背景，包括Polar码的来源及其译码方法，之后简要介绍了Polar码的译码算法的发展历程，最后说明了本文各章的主要内容。第二章，主要介绍了Polar码的基本原理。首先介绍了Polar码的基本概念，之后重点介绍了信道极化原理，并通过仿真展示了信道极化现象，最后介绍了Polar码的编码原理。第三章，主要介绍了Polar码的三种译码算法。这三种译码算法包括SC算法、SCL算法、BP算法，之后介绍了随机共振现象和扰动译码原理，最后介绍了CRC辅助Polar码的扰动译码方法。第四章，主要介绍了Polar-CRC动态扰动译码方法。首先简要分析了已有的CRC辅助Polar码的扰动译码方法的不足，并对不足之处作出了改进，提出了动态扰动译码方法。最后通过仿真实验证明了，新提出的动态扰动译码方法比原方法的误码性能更好。第五章，主要总结全文的内容。第2章Polar码基本原理2.1基本概念本节介绍了后面章节中可能会使用到的基本概念，另外本文中所有的向量、矩阵及其运算都是基于二阶有限域GF(2)。B-DMC信道可以表示为：W:X→Y，输入符号集合X={0,1}，输出符号集合Y是任意值。信道W的转移概率可以表示为W(y|x)，其中xX，yY。WN表示信道W的N次使用，WN:XN→Y WN(信道W的对称互信息可以表示为： I(X其中，q代表输入符号集合中元素的个数。如果信道W的输入输出具有对称性，那么它的对称容量为： I(W)≜I(X;Y)=y∈Yx∈X1其中，X在{0,1}上是等概率分布的。信道W的巴氏参数定义为： Z(W)≜y∈YW(y|0)W(y|1)信道W的对称容量和巴氏参数满足如下的关系： IW≥ IW≤对称容量I(W)是在信道W上进行可靠传输时所支持的最高码率，巴氏参数Z(W)刻画了使用信道W进行信息传输时，ML译码决策的错误概率上限，这两个参数是用来表征信道质量的重要参数。常见的B-DMC信道有二进制对称信道(BinarySymmetricChannel,BSC)和二进制删除信道(BinaryErasureChannel,BEC)。首先介绍BSC信道。BSC信道的输入输出符号集合都是集合{0,1}。如果接收端出错，就将原符号反转，将0（1）变为1（0）。设反转概率为p，那么其转移概率为W(1|0)=W(0|1)=p，W(0|0)=W(1|1)=1-p。BSC信道模型如下：图2-1BSC信道模型根据公式（2-3），此信道的对称容量为： I(W)=plog2然后介绍BEC信道。BEC信道的输入符号集合是集合{0,1}，输出符号集合为{0,1，E},其中E是擦除符号。如果接收端出错，那么就输出擦除符号E，若擦除概率为ε，则BEC信道的转移概率为W(E|0)=W(E|1)=ε，W(0|1)=W(1|0)=1-ε，W(0|0)=W(1|1)=1-ε。BEC信道模型如下图所示：图2-2BEC信道模型根据公式(2-3)，BEC信道的对称容量为： I(W)=1−ε (2-8)2.2信道极化信道极化现象是Polar码编码的基础，它包括信道分裂和信道合并两个过程。信道分裂和信道合并的示意图如下所示：图2-3信道合并和信道分裂示意图如图2-3所示，原始的信道是N个相同且独立的B-DMC信道W，这N个信道的对称容量是相等的，这N个信道W组成了N阶并行信道WN，在经过信道合并后，WN信道变成了虚拟矢量信道WN。信道WN在经过信道分裂之后变成了N个新的比特信道WN信道极化可以总结为：对于任意的N个B-DMC信道W来说，当N趋近于无穷时，几乎所有的比特信道变成了无噪信道或者全噪信道，即对δ（0,1），随着N趋向于无穷大，具有容量I(WN(i))(1-δ，1]的好信道所占比例趋于I(W)，具有容量由此可以得出，N个独立且相同的B-DMC信道在经过信道合并和信道分裂后，被极化成了两种极端信道：I(WN(i))趋于1的好信道和I(WN(i))趋于0的坏信道，并且好信道所占比例趋于原信道W的容量。以ε为0.5的二进制擦除信道为例，图2-4为当N=2N=210，ε=0.5的BEC信道的I(W)分布图N=210，ε=0.5的BEC信道的Z(W)分布图图2-4N=210N=210，εN=210，ε图2-5N=210N=220，εN=220，ε图2-6N=220图2-5和图2-6分别是当N=210和N=22.3Polar码编码原理Polar码是一种线性分组码，编码公式类似于其他的线性分组码，由信息序列乘以生成矩阵，便可得到编码后的码字。Polar码编码公式如下： x1N GN=BN BN=其中，x1N为码字，u1N是需要传输的信息序列，它包括信息比特序列、冻结比特序列，GN令比特信道索引集合为I={1,2,…,N}，信息位所在的索引集合A是I的子集。将信息比特放在集合A中的索引所对应的比特信道,其它的比特信道放置冻结比特，组成输入序列u1 x1N其中，AC是冻结位所在的索引集合，GN(A)根据式(2-12)可以发现，我们可以把需要传输的信息序列按照信息位所在的集合A和冻结位所在的集合AC第3章Polar码译码算法3.1Polar码译码算法Arikan教授提出了Polar码的第一种译码算法——SC译码算法，由于SC译码对于中短码来说，译码性能较差，因此相关学者提出了SCL译码算法，并且使用CRC码来辅助译码，有效提高了Polar码的误码性能。另外，因为Polar码的编码结构可以直接用因子图表示，因此Polar码也可采用置信传播(BeliefPropagation,BP)译码算法。3.1.1SC译码算法SC译码算法是一种串行算法。在对第i个比特进行译码时，需要知道之前的信道输入u1i−1和信道输出序列由于Polar码在编码时，信源比特序列包括信息比特序列和冻结比特序列，因此SC译码时需要对信息位和冻结位进行判决。如果ui是冻结位的比特，就直接将其判决为已知的冻结比特，如果u ui=其中，信息位比特的判决函数为： ℎi(是第i个信息比特的LR函数： L(ui式(3-3)中，指的是前i-1个信息比特的估计值。从式(3-3)中可以得出，判决信息位上的比特需要分别计算其LR值。由于Polar码的编码过程具有递归性，相应地，Polar码译码过程也具有递归性，可以通过递归的方式计算N个比特的LR值，递归公式如下所示： LN(2i−1) LN(2i)(y1N,u1N=1时递归过程就结束了，终止条件是：。由式(3-4)和式(3-5)可以得出，每次的递归计算都可以当做是计算成对的LR值。成对的LR值的计算可以看成是SC译码的一个基本的计算单元，这样的基本计算单元可以表示成图3-1所示的蝶形图。从图3-1中可以得出，LR值只能从右向左单向传递，因此SC译码算法是一种单向传递的串行译码算法。SC译码的复杂度关键在于LR值的计算，一共需要计算N(1+logN)个LR值，因此SC译码的复杂度为O(NlogN)。图3-1SC译码蝶形计算单元3.1.2SCL译码算法SCL译码算法能够有效解决中短码长的Polar码在SC译码算法下性能较差的问题。下面从译码树的角度来分析SCL译码算法。对于一个的Polar码来说，其所有可能的N维输入向量有2K个，和深度是N的二叉树的2K个叶节点相对应。所以Polar码的译码算法相当于从搜索二叉树中找出从根节点到叶节点中符合要求的那一条路径。SC译码在信息位索引所对应的层数中，只选择具有最大似然概率的子节点进行扩展，而SCL译码在每一层中都可以横向进行扩展，可以保留最多L条路径。由此可见，当L为1时，SCL译码算法就是SC译码算法以N=8的Polar码为例，令L=2，译码树如图3-2所示。图3-2SCL译码树示意图译码从根节点开始，逐渐向每个叶节点展开，并且在译码过程中采用不同的方式处理信息位和冻结位。译码开始时路径数为1，遇到冻结位时，原始路径数保持不变，只有在遇到信息位时，才会扩展路径。前三层都是冻结比特，值都赋为0。当译第一个信息位时，当前的译码路径被分成两条路径。在译下一个信息位时，执行相同的处理。当路径数目达到L后，在译下一个信息位时，路径数目变为2L。为了保持译码路径为L，需要对所有路径的度量值进行排序，根据度量值大小来决定删除或者保留哪几条路径，最后保留了L条译码路径，选择具有最大度量值的那一条，然后从叶节点向根节点回溯就得到了最终的译码结果。SCL译码算法的复杂度为O(LNlogN)。当L的值大于2K时，那么译码树中的23.1.3BP译码算法Arikan教授在文章[13]中指出，Polar码的构造和RM码的构造原理相似，它们共用了一个编码矩阵，因此Polar码也可用因子图来表示。RM码作为定义在图上的码，可以用BP译码算法来译码，因此Polar码在译码时也可采用BP译码算法。N=8时Polar码的因子图如图3-3所示，令n=log图3-3N=8时Polar码的因子图图3-4BP译码算法的基本单元和SC译码算法的基本单元不同，BP译码算法的基本单元是可以双向传递信息的。在计算出对数似然比(LogLikelihoodRatio,LLR)值之后，基本单元会将LLR值分别向左和向右传递。我们可以用Ri,j和L Li,j=g( Li,j+N/2=g(式(3-8)和式(3-9)用来计算一个基本单元向右传递的信息。 Ri+1,2j−1=g( Ri+1,2j=g(上述公式中的g(x,y)函数为： g(x,y)=ln(1+xy在使用BP译码算法进行译码时，需要先初始化所有节点的信息。除了R1,j和Ln+1,j这两列节点外，其他的节点信息都初始化为零。由于图3-3中第一列节点连接的是信源序列，因此 R1,j=图3-3中的第(n+1)列连接的是码字序列，因此Ln+1,j Ln+1,j=W(y对所有的节点都初始化后，开始进行迭代循环。每次迭代过程，就是先自左向右计算每个节点的Li,j值（0≤i≤n），再自右向左计算每个节点的Ri,j值（1<i≤n+1）。迭代完成后，用第一列节点的信息，即R1,j和L1,j来估计信源序列，用最后一列节点的信息，即Rn+1,jBP译码算法的性能和迭代次数有关，如果要求误码很低，那么就需要多次迭代，如果迭代次数过大，反而会产生较长时延。此外，Arikan教授还指出，在信道的信噪比较低时，BP译码算法的性能只是略优于SC译码算法，信噪比较高时，BP译码算法的性能反而不如SC译码算法。3.2CRC辅助的扰动译码3.2.1扰动译码原理由于噪声会影响信息的传输，导致接收端有时不能准确获取信息，因此噪声一直被人们认为是信息传输过程中的不利因素。在1981年，Benzi等人在研究古气象问题时发现了随机共振现象，这一重大发现改变了人们对噪声的认知。1983年，有关学者在斯米特触发电路中通过实验证明了随机共振现象是存在的。之后其他学者在其他领域也陆续发现了随机共振现象。在信号处理领域，某些非线性系统中，我们可以利用随机共振现象，在系统中施加噪声，当噪声强度达到合适程度时便会产生随机共振现象，这时部分噪声便可转化为有用的能量，从而增大了输出信号的SNR值，能够让系统产生一个最佳输出。随机共振现象也可应用于信道译码，通过在译码器中施加合适强度的噪声，可以大大降低误码率。Kai-tingShih等人利用此原理，设计了具有级联码的扰动译码方法，示意图如下所示：图3-5级联码的扰动译码的示意图在图3-5中，外码是检错编码，内码是纠错编码，译码时如果内码译码器输出的码字不能通过外码检错时，那么就向输出序列中添加一个加性噪声，之后重复进行上述的译码过程，直到码字可以通过外码检错时或译码次数达到结束条件为止。3.2.2CRC辅助的扰动译码在Polar-CRC级联码中，Polar码作为内码，用来纠错，CRC作为外码，用来检错，此级联码示意图如图3-6所示。对于参数向量为(N,K)的Polar-CRC级联码来说，它的K比特的输入是由n比特的信息序列和m比特的CRC序列组成的。首先n比特的信息比特序列需要先经过m比特的CRC编码器，产生了一个K比特的码字，此码字在通过Polar码编码器后产生了码字x，码字x需要再进行调制和传输过程，之后信道输出序列y。然后对输出序列进行译码，通过Polar码译码器译码后得到码字x，此码字再通过CRC译码器进行校验。如果校验能通过，那么译码就是正确的，反之，译码错误。图3-6Polar-CRC级联码示意图图3-7基于扰动的CRC辅助Polar码译码方法示意图文献[12]中提出了一种基于扰动的CRC辅助中短码长Polar码译码方法，示意图如图3-7所示。信道输出序列y，然后对输出序列进行SC译码，得到码字x，此码字再通过CRC译码器进行校验。如果校验能通过，那么译码就是正确的。如果校验不能通过，需要进行扰动译码，直到有码字能通过CRC校验或译码次数达到最大的扰动次数为止。如果已达到最大次数，码字仍未通过CRC校验，那么就输出候选码字中似然最大的码字。似然值计算公式如下： L(xp式(3-13)中x(xp)是经过扰动后的译码码字x第4章Polar-CRC动态扰动译码4.1CRC辅助的动态扰动译码文献[12]中提出了一种基于扰动的CRC辅助中短码长Polar码译码方法，且证明了此种方法可以降低Polar码的误码率和误帧率，但是此种方法中的加扰噪声方差是固定不变的，作者也没有说明如何确定加扰噪声方差。加扰噪声方差不变，容易产生重复的候选码字，有效候选码字数量变少。另外，由于码字有可能会重复，那么之前未能通过CRC校验的码字，还有可能会出现，导致正确码字出现几率变低。因此加扰噪声方差的大小会对译码结果产生很大的影响。本文基于此种方法作出了改进，提出了Polar-CRC动态扰动译码。此译码方法的激活条件与文献[14]相同。首先需要对输出序列进行SC译码，得到码字x，此码字再通过CRC译码器进行校验。如果校验能通过，那么译码就是正确的。如果校验不能通过，需要进行动态扰动译码。和原来的扰动译码方法不同的一点是，DPD方法利用了文献[7]中的自适应思想，能够动态的改变加扰噪声方差的值。与原扰动方法不同，DPD方法在接收到每帧序列后，会依据经过扰动后的译码结果动态的改变加扰噪声方差的值，这样就降低了候选码字重复率，有效候选码字数量变多，码字更有可能通过CRC校验。如果已达到最大次数，码字仍未通过CRC校验，那么就输出候选码字中对数似然值(loglikelihood,LL)最大的码字。和原扰动方法相比，DPD方法能得到更多的有效候选码字，因此在相同的扰动次数下，其误码率更低。DPD方法的示意图如图4-1所示。图4-1DPD方法的示意图DPD方法步骤如下：（1）将扰动次数pnum初值设为0，最大的允许扰动次数值为T，加扰噪声方差σp2设为（2）通过噪声发生器，产生均值为零、长度为N、方差为σp2的AWGN噪声序列np，我们令yp=y+（3）进行重复码字查找。如果码字x和候选码字表中没有相同的码字，那么执行步骤（4），否则执行步骤（6）。（4）对码字x进行CRC校验。如果码字可以通过CRC校验，那么就输出x，x便是最终的译码结果，译码过程结束；否则执行步骤（5）。（5）计算码字x的LL值，并将码字x添加到候选码字表中，扰动次数值pnum=pnum+1。之后执行步骤（7）。（6）码字x和候选码字表中有相同的码字，因此需要增加加扰噪声方差的值，σp（7）如果扰动次数值pnum已达到最大的允许扰动次数值T，那么执行步骤（8），若还未达到最大的允许扰动次数值，那么就重复步骤（2）。（8）如果已达到最大的允许扰动次数T，码字仍未通过CRC校验，那么就输出候选码字中LL值最大的码字。其中，LL值的计算公式如下所示： L(x)=−4.2仿真分析我们分别采用SC译码算法、CRC辅助Polar码的扰动译码算法和新提出的DPD译码算法对Polar码进行译码，比较Polar码在这三种译码算法下的性能。我们用MATLAB进行仿真，选取(N,K)值分别为(256,128)和(512,256)的Polar码，采用AWGN信道作为仿真信道。另外，我们采用和文献[12]相同的16比特的循环冗余校验码，生成多项式f(x)=x16+图4-2(256,128)Polar码在不同译码算法下的误比特率图4-3(256,128)Polar码在不同译码算法下的误帧率图4-4(512,256)Polar码在不同译码算法下的误比特率图4-5(512,256)Polar码在不同译码算法下的误帧率图4-2和图4-3分别是(256,128)Polar码在这三种译码算法下的误比特率和误帧率的情况。通过观察图4-2和图4-3可知，(256,128)Polar码在DPD算法下的BER和FER比在PD算法和SC译码算法下的BER和FER低。当最大的允许扰动次数T比较小时，增益不太明显，当T较大时，增益比较明显。随着信道SNR和最大的允许扰动次数值的增加，增益越来越明显。图4-4和图4-5分别是(512,256)Polar码在这三种译码算法下的误比特率和误帧率的情况。通过观察图4-4和图4-5可以得出和前面同样的结论。(512,256)Polar码在DPD算法下的BER和FER比在PD算法和SC译码算法下的BER和FER低。当T较小时，增益不太明显，当T较大时，增益比较明显。随着信道SNR和最大的允许扰动次数值的增加，增益越来越明显。第5章结论与展望5.1结论Polar码是首个在理论上被严格证明可以达到香农极限的信道编码方法，它的出现给编码领域提供了更加广泛的研究方向。随着我国5G项目的建设和6G项目的开展，Polar码在通信领域的应用变得更加广泛。Polar码的产生来源于信道极化理论，因此本文首先重点介绍了信道极化理论，然后介绍了Polar码的编码原理。之后介绍了Polar码的三种译码算法，这三种译码算法包括SC算法、SCL算法、BP算法，还介绍了随机共振现象和扰动译码原理。最后介绍了CRC辅助Polar码的扰动译码方法，简要分析了这种译码方法的不足，并对不足之处作出了改进，提出了动态扰动译码方法。最后通过仿真实验证明了，新提出的动态扰动译码方法比原方法的误码性能更好。5.2展望本文的内容还有一些不足之处，还可继续以下的研究：1.改进本文提出的DPD方法。虽然DPD方法比原方法的误码性能更好，但是还有不足之处。DPD方法单一，虽然改进了原扰动译码方法的不足，但是仍不能保证译码码字不重复，因此可以尝试其他的加扰方法来改进DPD方法的不足。2.加扰噪声方差的值还不够精确。加扰噪声方差的值过大或者过小都会对译码的结果造成严重的影响，因此更加精确的确定其与码字参数、信道条件等这些因素的关系，对提升误码性能来说是十分重要的。参考文献[1]TalI,VardyA.ListDecodingofPolarCodes[C]//IEEEInternationalSymposiumonInformationTheory.IEEE,2011.[2]K.Chen,K.Niu,J.R.Lin.Listsuccessivecancellationdecodingofpolarcodes[J].ElectronicsLetters,2012,48(9):500-501.[3]ChenZ,LinJ,WangZ.Reducedcomplexitylistpolardecoderwithanimprovedpathpruningscheme[C]//2017IEEE17thInternationalConferenceonCommunicationTechnology(ICCT).IEEE,2017.[4]DaesungKim,In-CheolPark.AFastSuccessiveCancellationListDecoderforPolarCodesWithanEarlyStoppingCriterion[J].IEEETransactionsonSignalProcessing,2018,66(18):4971-4979.[5]BoY,ParhiKK.Beliefpropagationdecodingofpolarcodesusingstochasticcomputing[C]//IEEEInternationalSymposiumonCircuits&Systems.IEEE,2016.[6]KaiNiu,KaiChen.CRC-AidedDecodingofPolarCodes[J].IEEECommunicationsLetters,2012,16(10):1668-1671.[7]BinLi,HuiShen,DavidTse.AnAdaptiveSuccessiveCancellationListDecode