RM码和Polar码的连续消除译码和置信传播译码研究

殷威 张艳 张晓刚 沈秋晨

摘 要 本文比较了无须迭代的連续消除（Successive Cancellation， SC）译码算法和置信传播（Belief Propagation， BP）迭代算法对相同码长和码率的RM码和Polar码的译码性能和译码时间。仿真结果表明SC软判决译码算法可对RM码进行译码，且相比于BP译码算法，SC译码时间平均降低了98.98%。针对BP译码算法译码性能优而译码时间长的特点，本文提出了基于似然值的绝对值差的提前终止迭代准则的改进BP译码算法，降低了该准则的计算复杂度。仿真结果表明本文提出的提前终止准则降低了计算复杂度，从而有效降低了译码时延和能耗，满足了低复杂度和低功耗的译码需求。

关键词 Polar码;RM码;SC译码算法;BP译码算法;提前终止迭代准则

引言

1954年，Muller从线性空间角度，提出可纠正多个差错的二进制线性分组码—Reed-Muller （RM）码[1]。同年，Reed提出大数逻辑译码算法[2]解决其译码问题。RM码构造简单，亦可通过Plotkin结构[3]构造，可采用硬判决[4]或软判决算法对其进行译码。

2008年Arikan提出的基于信道极化的Polar码是经过精准的数学分析，能在广泛的信源和信道编码问题上达到信息论极限的编码方式，相比较之前最好的低密度奇偶校验码（Low-density Parity-check Code， LDPC） 的编码方式，在相同的条件下，Polar码的纠错性能要优于LDPC码，这表明Polar码传输信息具有较高的可靠性。

Polar码的软判决译码方法通常有两种：连续消除 （Successive Cancellation ， SC）译码算法和置信传播（Belief Propagation， BP）译码算法。Forney指出RM码可被认为是图形表示码（codes on graphs），可通过BP译码算法完成译码。Arikan指出Polar码和RM码的关系，并在文献中验证了基于BP译码算法的Polar码的译码性能优于RM码。然而在一定码长范围外，信噪比较高的情况下，BP译码算法的优势不是很明显，故Arikan在文献中对基于网格的最大似然（maximum-likelihood， ML）译码算法的Polar码和RM码的译码性能进行了比较，结果表明由于RM码的最小汉明距离的优势，使其在高信噪比下译码性能更优，而在信噪比较低时，Polar码的译码性能优于RM码。文献中提出的最大后验概率（maximum a-posteriori probability， MAP）译码算法利用了RM码的最小汉明距离的优势，故基于该算法的RM码译码性能优于Polar码。然而未有文章指出SC译码算法对RM码译码的可行性，且未有研究基于SC译码算法下的两种码的译码性能和计算复杂度进行比较。出于该问题，本文分别通过对Polar码和RM码在BP和SC译码算法下的译码性能和计算复杂度进行比较，验证SC译码算法可对RM码译码。通过计算误比特率（bit error rate， BER）和误帧率（frame error rate， FER）比较Polar码和RM码的译码性能，通过计算译码时间比较两种码的计算复杂度。并通过分别比较Polar码和RM码在BP和SC译码算法下的译码时间，验证相比于BP译码算法，SC译码算法满足RM码的快速译码需求，为RM码的快速译码提供了一项工具。

虽然SC译码算法的计算复杂度较低，但该算法因其固有的串行译码特点而造成长延时的问题。不同于SC译码算法，BP译码算法因其并行处理和数据吞吐量高的特点，使该算法适合高吞吐量低延迟的应用。文献提出与传统BP译码算法有相同性能而复杂度较低的缩放最小和BP（scaled min-sum， SMS）译码算法，文献引入了一种基于子因子图冻结的复杂度降低的BP解码器。但以上的BP译码算法仍需要进行多次迭代过程，大大地增加了时延和能耗。在不影响译码性能的基础上，设计合理的提前终止迭代准则可有效地降低BP译码算法的平均迭代次数。提前终止迭代准则已广泛适用于LDPC码和Turbo码。文献提出了基于生成矩阵和基于最小似然值（minimum log-likelihood ratio， minLLR）的提前终止迭代准则，这两种提前终止准则虽在一定程度减少了迭代次数，但其迭代次数仍较高。基于该问题，有学者提出了基于似然值的方差的提前终止迭代准则。该种提前终止迭代准则虽减少了迭代次数，但其运算复杂度较高，在码长越长的情况下，该种提前终止迭代准的时延和能耗会成码长的倍数增加，极大的消耗了能量，增加了译码时间，因此在一定程度减少迭代次数的基础上降低BP译码算法提前终止迭代条件的运算复杂度是很有必要的。本文在基于似然值的方差的提前终止迭代准则的基础上，提出了基于似然值的绝对值差的提前终止迭代准则，在保证减少迭代次数与基于方差的准则一致的基础上，通过降低准则的运算复杂度，有效降低了时延和能耗的问题。并通过计算两种准则的计算复杂度和比较基于两种准则的译码时间验证本文提出的准则具有更低的计算复杂度。

1RM码和Polar码

对于，的RM码一般表示为，对应码字长度为，最小汉明距离为，信息位长度为，因此RM码也可以表示为。对于，可使用Plotkin结构获得：

其中，表示的阶Kronecker积。阶的RM码可被定义为生成矩阵为的线性码，通过选择矩阵中汉明重量大于等于的行向量获得RM码的生成矩阵。

Polar码的参数一般表示为，对应的码字长度为，信息位长度为K，信息比特集合为A，冻结比特（frozen bit）为，其中集合Ac是信息比特集合A的补集。Polar码的编码方式不同于RM码，的Polar码的生成矩阵是矩阵的一个的子矩阵。当信道为二进制擦除信道（Binary Eraser Channel， BEC）时，可以根据以下递归方式计算巴特查理亚（Bhattacharyya）参数，根据的值从矩阵中选择行向量。由于信道的可靠性越高值越小，所以选择参数值较小的信道用于传输信息。

由于对和的排列和与汉明重量的排列相同，所以在和时，Polar码和RM码的生成矩阵一样。当在时，以开始计算，根据式（3）计算出。对进行重新排序，得到序列（32，16，24，28，30，31，8，12，20，14，22，26，15，23，27，4，29，6，10，7，18，11，19，13，21，2，25，3，5，9，17，1），而对应的行向量的汉明重量为（32，16，16，16，16，16，8，8，8，8，8，8，8，8，8，4，8，4，4，4，4，4，4，4，2，4，2，2，2，2，1）。因此的Polar码的生成矩阵与采用矩阵中汉明重量大于等于的行向量组成的RM码的生成矩阵不同，且当码长越长，两种码的生成矩阵差别越大。

2Polar码和RM码的SC译码和BP译码比较

Polar码和RM码的编码具有共同结构，但编码方式具有差别，本章则对Polar码和RM码的SC译码和BP译码性能和译码时间进行比较。

2.1 连续消除译码（SC）算法

编码后的码字经过AWGN信道传输后，接收码字为。SC译码算法通过计算的LLR得出的估计值 。每比特的LLR由下式得到：

SC译码算法具有较低的运算复杂度。

2.2 置信传播（BP）译码算法

文献提出采用BP译码算法对Polar码和RM码进行译码，提高了其译码性能。的Polar码的编译码可由个节点组成的因子图表示，其因子图有层，每层有个基本处理单元（processing elements， PE），其基本处理单元如图1所示。

每个节点（，）包含两种似然信息：向左传递的信息和向右传递的信息，其中表示当前迭代的次数。在译码过程中，这些信息在相邻节点之间进行传递和更新。每个PE中节点信息更新公式如下：

2.3 Polar码和RM码的SC译码和BP译码的比较

本文的仿真平台为Windows 7系统，CPU为Intel（R） Core，利用C++语言进行编程实现。本节展示了基于SC、BP译码算法下的相同码长和码率的RM码和Polar码的译码性能和译码时间仿真与分析。与对应的Polar码的信息位长度为，对应关系如下表所示：

本节给出了码长，和的RM码和Polar码在AWGN信道下的BER和FER仿真结果和基于两种译码算法的译码时间。其中采用二进制移相键控（BPSK）进行调制，仿真结果如附录Ⅰ所示。给出的仿真结果的结论与其他码长和码率的实验结果具有一致性。

表2是（256，93）和（256，163）的RM码和Polar码基于BP、SC译码算法下的时间比较表，图2是（256，93）和（256，163）的RM码和Polar码基于BP、SC译码算法下的性能比较图，其中BP譯码算法的设定的固定迭代次数为60次。由图2看出RM码和Polar码的BER和FER随着码率的增加而变大，说明码率越大，RM码和Polar码的译码性能越差。且在小于0dB时，经过SC译码的RM码和Polar码的译码性能较差;相比于BP译码算法，SC译码算法译码性能较差。由表2中可看出，相比于BP译码算法，基于SC译码算法的Polar（256，93）、Polar（256，163）的译码时间分别降低了98.64%，99.2%;基于SC译码算法的RM（8，3）、RM（8，4）的译码时间分别降低了98.73%，99.34%，平均降低了98.98%。仿真结果表明相比BP译码算法，SC译码算法的译码性能虽较差，但其大大降低了译码时间，译码过程中节省了大量的存储空间、时间和能量，在快速译码方面占有更多优势。

3基于似然值的绝对值差的提前终止迭代准则的改进BP译码算法

BP译码算法的固定次数是根据信噪比最差的情况设定的，但在信噪比未达到最差情况下，BP译码算法运行到固定次数需要消耗大量的能量和时间，则降低了译码效率，而根据不同的信噪比适度地降低迭代次数可达到有效的收敛。

3.1 基于似然值的绝对值差的提前终止迭代准则

早期的迭代准则在现有的LDPC码和Turbo码中具有广泛的应用，根据不同的信噪比范围，提前停止迭代。提前终止准则分为多种类型，其中最重要的是检测类型，用于检测有效输出是否已被译码。若被译码，则表示译码成功，译码器将提前终止迭代。文献中提出的基于生成矩阵的方法就是检测类型的方法，但该种方法仍需要较多的迭代次数。文献中提出的基于似然值的方差的提前终止准则，基于似然值的方差的提前终止准则算法如下所示：

上述的基于似然值的方差的提前终止迭代准则的改进BP译码算法虽减少了迭代次数，但该种算法的计算复杂度仍较高。本文基于这个问题，提出了基于似然值的绝对值差的提前终止准则。基于该终止准则的改进BP译码算法如下：

基于似然值的绝对值差的提前终止迭代改进BP译码算法

3.2 仿真结果与分析

本节对Polar码的基于似然值的绝对值差的提前终止迭代改进BP译码算法进行仿真，选用码长，码率的Polar码，译码过程中设定的固定迭代次数为40。图3展示了本文提出的提前终止迭代准则和基于方差的准则的译码性能比较，图4展示了两种准则在平均迭代次数上的比较。

由图3和图4可看出基于绝对值差的提前终止迭代条件的阈值越小，Polar码的译码性能越优，但其平均迭代次数较多。基于方差的提前终止迭代条件的阈值越大，平均迭代次数越少，但Polar码的译码性能较差。本文选择的基于绝对值差的提前终止迭代条件和的基于方差的提前终止迭代条件进行译码性能和运算复杂度的比较。由图3和图4看出，的基于方差的提前终止迭代条件和的基于绝对值差的提前终止迭代条件的改进BP译码算法的译码性能与平均迭代次数效果大体上一致，表明本文提出的基于似然值的绝对值的提前终止迭代改进BP译码算法没有导致性能丢失，且两种准则的平均迭代次数减少的幅度随着信噪比的增大而明显。提前终止迭代准则可有效地降低能耗和延时问题，但提前终止迭代仍然需要消耗能量，因此需要选择计算复杂度较低的提前终止迭代准则。表3给出了两种提前终止迭代准则的运算复杂度的比较，表4给出了两种提前终止迭代准则的译码时间的比较。

由表3可知本文提出的基于似然值的絕对值差的提前终止迭代算法的运算复杂度比基于似然值的方差的提前终止迭代算法平均减少了至少一半的计算复杂度，即每次迭代过程中减少了次乘法和除法的计算量，仿真结果表明在码长越长的情况下，本文提出的准则运算复杂度更低，在降低时延和能耗方面更具有优势。表4则通过比较基于两种终止准则的译码时间验证了上述结论。在码长的情况下，本文提出的准则的译码时间比基于似然值的方差的提前终止迭代准则平均减少了5.584%，在传输码字越多，码长越长的情况下，本文提出的提前终止准则可节省更多的译码时间，降低更多能耗。

4结束语

本文在描述RM码和Polar码的编码方式差异的基础上，首先通过比较基于无须迭代的SC译码算法和BP迭代译码算法的RM码和Polar码的译码性能和译码时间，验证了无须迭代的SC软判决译码算法对RM码的译码的可行性;其次在基于似然值的方差的提前终止迭代的改进BP译码算法的基础上，提出了基于似然值的绝对值差的提前终止准则。

基于SC、BP译码RM码和Polar码的译码性能和译码时间比较的仿真结果验证了SC译码算法对RM码译码的可行性。表明了在经过AWGN信道下，基于两种相同译码算法的Polar码在译码性能上都可获得更好的误比特性能。相比于SC译码算法，BP译码算法（其中设定的固定迭代次数为60次）虽具有更好的译码性能，但RM码和Polar码在该算法下的译码时间比SC译码算法平均增加了98.98%，所以SC译码算法在计算复杂度和能耗方面具有更大的优势。基于两种提前终止迭代准则的仿真结果表明本文提出的基于似然值的绝对值差的准则与基于方差的提前终止准则在平均减少迭代次数和译码性能上具有一致性，而本文提出的基于绝对值差的准则通过降低运算复杂度降低能量和时间的消耗，减少了时延，是一种功耗和复杂度均低的提前终止迭代准则。

参考文献

[1] Muller，D.E.Application of Boolean algebra to switching circuit design and to error detection[J].Transactions of the I.r.e.professional Group on Electronic Computers，2013，EC-3（3）：6-12.

[2] Reed I S.A class of multiple-error-correcting codes and the decoding scheme[J].Transactions of the IRE Professional Group on Information Theory，2003，4（4）：38-49.

[3] Plotkin M.Binary Codes with Specified Minimum Distance[J]. Information Theory，IRE Transactions on，1960，IT-6（4）：445-450.

[4] Arikan E，Kim H，Markarian G，et al.Performanceof short polar codes under ML decoding[J]. ICT MobileSummit ，2009，（1）：10-12.