【《Polar码译码算法概述》3600字】

Polar码译码算法概述目录TOC\o"1-3"\h\u18533Polar码译码算法概述 1255151.1Polar码译码算法 1241881.1.1SC译码算法 1282381.1.2SCL译码算法 2193211.1.3BP译码算法 496671.2CRC辅助的扰动译码 6149691.2.1扰动译码原理 6263161.2.2CRC辅助的扰动译码 61.1Polar码译码算法Arikan教授提出了Polar码的第一种译码算法——SC译码算法，由于SC译码对于中短码来说，译码性能较差，因此相关学者提出了SCL译码算法，并且使用CRC码来辅助译码，有效提高了Polar码的误码性能。另外，因为Polar码的编码结构可以直接用因子图表示，因此Polar码也可采用置信传播(BeliefPropagation,BP)译码算法。1.1.1SC译码算法SC译码算法是一种串行算法。在对第i个比特进行译码时，需要知道之前的信道输入u1i−1和信道输出序列由于Polar码在编码时，信源比特序列包括信息比特序列和冻结比特序列，因此SC译码时需要对信息位和冻结位进行判决。如果ui是冻结位的比特，就直接将其判决为已知的冻结比特，如果u ui=其中，信息位比特的判决函数为： hi(是第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译码蝶形计算单元1.1.2SCL译码算法SCL译码算法能够有效解决中短码长的Polar码在SC译码算法下性能较差的问题。下面从译码树的角度来分析SCL译码算法。对于一个的Polar码来说，其所有可能的N维输入向量有2K个，和深度是N的二叉树的2K以N=8的Polar码为例，令L=2，译码树如图3-2所示。图3-2SCL译码树示意图译码从根节点开始，逐渐向每个叶节点展开，并且在译码过程中采用不同的方式处理信息位和冻结位。译码开始时路径数为1，遇到冻结位时，原始路径数保持不变，只有在遇到信息位时，才会扩展路径。前三层都是冻结比特，值都赋为0。当译第一个信息位时，当前的译码路径被分成两条路径。在译下一个信息位时，执行相同的处理。当路径数目达到L后，在译下一个信息位时，路径数目变为2L。为了保持译码路径为L，需要对所有路径的度量值进行排序，根据度量值大小来决定删除或者保留哪几条路径，最后保留了L条译码路径，选择具有最大度量值的那一条，然后从叶节点向根节点回溯就得到了最终的译码结果。SCL译码算法的复杂度为O(LNlogN)。当L的值大于2K时，那么译码树中的21.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(对所有的节点都初始化后，开始进行迭代循环。每次迭代过程，就是先自左向右计算每个节点的Li,j值（0≤i≤n），再自右向左计算每个节点的Ri,j值（1<i≤n+1）。迭代完成后，用第一列节点的信息，即R1,j和L1,j来估计信源序列，用最后一列节点的信息，即Rn+1,jBP译码算法的性能和迭代次数有关，如果要求误码很低，那么就需要多次迭代，如果迭代次数过大，反而会产生较长时延。此外，Arikan教授还指出，在信道的信噪比较低时，BP译码算法的性能只是略优于SC译码算法，信噪比较高时，BP译码算法的性能反而不如SC译码算法。1.2CRC辅助的扰动译码1.2.1扰动译码原理由于噪声会影响信息的传输，导致接收端有时不能准确获取信息，因此噪声一直被人们认为是信息传输过程中的不利因素。在1981年，Benzi等人在研究古气象问题时发现了随机共振现象，这一重大发现改变了人们对噪声的认知。1983年，有关学者在斯米特触发电路中通过实验证明了随机共振现象是存在的。之后其他学者在其他领域也陆续发现了随机共振现象。在信号处理领域，某些非线性系统中，我们可以利用随机共振现象，在系统中施加噪声，当噪声强度达到合适程度时便会产生随机共振现象，这时部分噪声便可转化为有用的能量，从而增大了输出信号的SNR值，能够让系统产生一个最佳输出。随机共振现象也可应用于信道译码，通过在译码器中施加合适强度的噪声，可以大大降低误码率。Kai-tingShih等人利用此原理，设计了具有级联码的扰动译码方法，示意图如下所示：图3-5级联码的扰动译码的示意图在图3-5中，外码是检错编码，内码是纠错编码，译码时如果内码译码器输出的码字不能通过外码检错时，那么就向输出序列中添加一个加性噪声，之后重复进行上述的译码过程，直到码字可以通过外码检错时或译码次数达到结束条件为止。1.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译码，得