一种基于特殊节点并行译码的极化码译码算法_周义森.pdf

2023年第6期一种基于特殊节点并行译码的极化码译码算法周义森（电信科学技术第一研究所有限公司，上海市 200032）摘要极化（Polar）码是 5G 中物理控制信道重要的信道编码方式。为了降低 5G 极化码译码时延，以满足更低时延的技术指标需求，文章研究基于特殊节点并行译码的极化码译码算法，提出一套新的特殊节点分类方法及其译码算法。与经典的基于 FSCL（快速串行抵消列表）算法相比较，所提新算法在误码率性能上几乎与 FSCL 算法一致，且最终能在芯片上软实现，其在不同码率下的译码时延相比 FSCL 降低 20%30%，取得较好的译码时延效果。关键词5G；极化（Polar）码；FSCL（快速串行抵消列表）译码；串行抵消0引言随着2022年3GPP R17国际标准的正式冻结，5G技术迈入新的发展阶段。极化（Polar）码1作为5G重要的信道编码技术，也得到持续的关注和创新。Polar编码器采用可嵌套的码字构造方法和具有可递归的编码构造，能以较低复杂度得以实现。译码器可采用基于SCL（串行抵消列表）译码算法，能获得优良的译码性能。因此，2016年Polar码被3GPP规定为5G物理控制信道的信道编码技术。但是SCL算法实现复杂度相对较高，且不满足5G演进过程所追求的低时延的需求。因此，为了降低SCL算法的译码时延和复杂度，之后涌现出一大批基于SCL算法的改进算法：基于简化路径分裂数的思想，提出基于信道可靠性2或者节点可靠性3自适应调整路径分裂数的算法；基于特殊节点并行译码的思想4-6，提出各种特殊节点分类方法以及分裂策略的算法；基于计算的任意比特并行译码思想7-10，以计算能力换取并行译码效率。其中，基于特殊节点的FSCL（快速串行抵消列表）算法5，相比SCL几乎没有性能的损失，并行译码使时延有很大的降低，成为如今主流的Polar码译码算法。为了满足5G持续演进过程对低时延的性能需求，本文研究Polar主流译码算法FSCL的优化，基于FSCL算法设计低译码时延的Polar码译码算法。1Polar 码译码原理简述1.1信道极化Polar码 的 设 计 理 念 基 于 信 道 极 化（ChannelPolarization）的概念，简单概括其原理如下：对长度为N=2n的Polar码按照一定规则进行信道合并（ChannelCombining）和信道分裂（Channel Splitting）操作，将N个独立的物理信道转化为N个逻辑比特信道。随着N的增大，逻辑比特信道的信道容量会呈现两极分化的现象，一部分信道容量趋于1，另一部分信道容量趋于0。信道极化使得N个独立的信道转化为一部分高可靠性的逻辑比特信道和另一部分为低可靠性的逻辑比特信道，因此，可以利用逻辑比特信道进行数据传输，将需要传递的信息放置在可靠性高的逻辑比特信道中传输，其信息放置位置称为信息位；将发送端和接收端都已知的比特信息放置在可靠性低逻辑比特信道中传输，对应的放置比特位置称为冻结比特位。以上就是Polar码的主要设计理念。论 文 选 粹372023年第6期1.2两种经典译码算法下面将介绍两种经典的Polar码译码方法：SCL和FSCL算法。两种算法的译码流程都可以用一个二叉树图表示，Polar码译码流程示意如图1所示。每个节点都有对应的软比特值和对应码字，译码流程顺序是从根节点出发，依次从上到下，从左到右，遍历二叉树的叶节点。这两种经典的算法同时保留多条路径，相当于在译码过程中，同时存在图1所示的多个译码二叉树，并分别计算每条译码路径可靠性，用PM（路径度量值）表示，最终选择PM最优的路径作为译码结果。图1中各节点有相同的译码流程，各节点译码流程示意如图2所示。图2中按照顺序执行四个步骤：f运算，得到左子节点的软比特值，见公式（1）。左子节点译码。g运算，得到右子节点的软比特值，见公式（2）。右子节点译码以及码字反馈，利用子节点的码字计算母节点的码字，本文称为码字反馈，计算方法和编码方法一致，见公式（3）。SCL算法和FSCL算法不同点在于对 图2中步骤的子节点译码上。SCL算法的译码思想是：对长度为1的节点码字直接译为0和1，分别计算其路径度量。PM的计算一般采用公式（4）和PM增量公式（5）计算。FSCL算法的译码思想是：利用特殊节点构造并行译码，将Polar码识别为R0、R1、Rep、Spc四类节点，每类节点有不同的路径分裂策略对应的PM计算方法，具体方法参考文献5。FSCL算法采用另一种推导得出的PM计算方式，见公式（6）。在制定5G的3GPP规范过程时，华为技术有限公司提交的Polar码提案中，采用SCL算法，证明了Polar码相比其他编码在短码上的优势，能满足5G的设计需求，最后Polar码被作为5G物理控制信道的主要编码方案。之后的FSCL算法5，相比SCL几图1Polar码译码流程示意图注：图中、分别表示节点的软比特值和输出码字，软比特值采用的是LLR（信道对数似然比），下标表示节点长度，上标表示索引号。图2各节点译码流程示意图论 文 选 粹382023年第6期乎没有性能的损失，可并行译码，时延有很大的降低，成为如今主流的Polar码译码算法，也是本文的优化对象。2 新的并行 Polar 码译码算法本文延续特殊节点并行译码的思想，在FSCL算法的基础上，增加新的特殊节点以及对应的译码方法，扩大译码并行度，以此减少了译码时延，实现对FSCL算法的优化。2.1新的节点分类算法各种节点的详细构造见表1。表1各种节点的详细构造表1中，Ac表示节点冻结位位置集合，A表示节点的信息位位置集合，Nv为节点码长，则位置信息集合为Ac/A0,1,2,Nv-1；表中的备注是为了确保节点不会被重复定义。根据各种节点的特点，可以将其分为四个大类。a）高码率节点：信息位较多，码率较高。若直接采用遍历的译码方法则计算复杂度随信息位数呈指数级递增，因此高码率的节点都不采用直接遍历译码，而是根据码字特性来简化译码路径数。表1中的高码率节点有R1、Spc、Spc2、Spc4，其中Spc2、Spc4节点继承了文献6提出的type-3、type-4节点，其节点具有单奇偶校验特性，为便于命名统一，故沿用的时候进行重命名。b）低码率节点：信息码字较少，本文将节点中的信息位限定在4 bit之内，码率较低。信息位较少的情况下，对硬件条件的要求不高，可采用并行遍历式译码，减少了译码时延。低码率节点有R0、Rep、Rep2、Rep4、Rep8，其中Rep2、Rep4、Rep8节点是对文献6提出的type-1、type-2、type-5节点的沿用，它们的码字分别由重复的2 bit、4 bit、8 bit组成，因此这样命名。c）R0融合节点：参考了文献10的定义，对于长度为Nv=2t的Polar码，输入码字为u1Nv，如果的位置都是冻结位，将此节点称为R0融合节点，用R0-NodeX表示。其中，t和t都是正整数，tt；使用一对不加括号的上下标来表示一组矢量数据，例如u1Nv代表的是u1、u2到uNv的数列；NodeX指组成的节点，这里包括所有高码率节点。其码字特点见公式（7），证明见文献10。式中：有2t-t个是NodeX节点的码字。d）Rep融合节点：对于长度为Nv=2t的Polar码，输入码字为u1Nv，如果的位置都是冻结位，的位置是信息位，将此节点称为Rep融合节点，用Rep-NodeX表示。其NodeX节点包括所有高码率和低码率节点，码字特点见公式（8），证明过程是将冻结比特为0代入Polar编码公式（9），由归纳法公式（8）得证。式中：有2t-t-1个是NodeX节点的码字。是长度为Nv的向量。式中：是矩阵Kronecker乘法。论 文 选 粹392023年第6期表4Spc2节点译码路径2.2新的节点译码策略2.2.1高码率节点理论上，高码率节点的路径分裂策略中需要考虑任意数量的码字错误的情况，但是分裂路径数量会随着节点长度指数级增加，会增加实现复杂度。为了减少路径分裂过程产生的计算复杂度，本文简化算法思想是只考虑有限个数的最不可靠码字的错误情况，这种出错情况占大部分情况，会大量减少译码分裂路径数量，达到降低译码时延和计算复杂度的目标。令节点软比特值为1Nv，其硬判决结果是1Nv，每个节点限制只分裂4条路径，具体的每一种高码率节点的路径分裂简化算法如下所述。R1节点考虑最不可靠的两个译码比特，是节点LLR绝对值最小的两个值i1,i2所对应的码字i1,i2，具体的译码路径见表2。表2R1节点译码路径Spc节点考虑最不可靠的3个译码比特，是节点LLR绝对值从小到大排序最小的三个值i1,i2,i3所对应的码字i1,i2,i3，具体的译码路径见表3。表3Spc节点译码路径表 3 中，式中符号表示二元域累加器，下同。Spc2节点考虑最不可靠的4个译码比特，i1,i2,i3,i4所对应的码字i1，i2，i3，i4。将硬判决结果按照序列索引奇偶分成两组，i1,i2分别是偶序列和奇序列中LLR绝对值最小的两个值，i3,i4是除去i1,i2在所有LLR中绝对值最小的两个值。Spc2节点的译码路径见表4。表 4 中，j1=i3mod2+1；k1j1；j2=i4mod2+1；k2=1,2；k2j2。Spc4节点考虑最不可靠的5个译码比特，i1,i2,i3,i4,i5所对应的码字i1,i2,i3,i4,i5。将硬判决结果按照序列索引模4的结果分成4组，i1,i2,i3,i4分别是结果为0、1、2、3序列中LLR绝对值最小的四个值，i5是除去i1,i2,i3,i4所有LLR中绝对值最小的值。Spc4节点的译码路径见表5。表5Spc4节点译码路径2.2.2低码率节点低码率节点因为信息位较少，可以直接遍历每一种节点码字。其译码最关键的步骤是求每种码字所对应的PM，对于每一种低码率节点其码字和对论 文 选 粹402023年第6期应的PM计算方式都是按照一定规律固定的，具体的方法参考FSCL算法和文献6中的描述。2.2.3R0融合节点R0融合节点的码字是NodeX节点码字的重复，因此译出NodeX节点即R0融合节点完成译码。具体的路径分裂步骤如下：软比特值合并。令其软比特值为1Nv，节点长度关系为Nv=kNv，NodeX节点的LLR用1（NodeX）表示，下标表示索引。由于NodeX节点前全是R0节点，采用g运算计算出NodeX节点的输入软比特，等价于软比特值相加，见公式（10）：NodeX节点进行译码。利用NodeX节点的译码策略，得到NodeX节点的码字i（Nodex），以及每条译码路径的路径度量值。由公式（7）得到R0融合节点码字。2.2.4Rep融合节点Rep融 合 节 点 的 码 字 取 决 于Rep节 点 和NodeX节点的码字，具体的路径分裂步骤如下：软比特合并。令其软比特值为1Nv；NodeX节点的长度为Nv，其软比特值用i（Nodex）表示；Rep节点的长度为Nv，其软比特值用1（Rep）表示；节点长度关系为Nv=2kNv。根据f运算和g运算规律，分别计算出临时软比特中间变量（公式11、12和Rep节点输入软比特（公式13）为：Rep节点分裂，得到NodeX节点的输入软比特。令Rep的信息比特是0，即公式（8）中U为全零序列，有：令Rep的信息比特是1，即公式（8）中U为全1序列，有：其PM增量见公式（6）。NodeX节点进行译码。利用NodeX节点的译码策略，得到NodeX节点的码字i（Nodex）以及每条译码路径的路径度量值。由公式（8）可得到Rep融合节点码字。2.3译码性能分析2.3.1BLER（误码率）性能分析实验的仿真信道采用AWGN（加性高斯白噪声）信道，调制方式采用QPSK（正交相移键控）调制。仿真实验设定随机生成信源信息，采用5G物理控制信道的编码方案编码；然后经过QPSK调制，随机进行信道加噪后，通过公式（16）可求得译码器输入软比特值，每种译码算法的输入是相同的；使用（K，N）表示不同码型，K是信息位数，N是总码长；每种算法都最大保存8条幸存路径；之后每种译码算法分别译码，统计其错误次数和总译码次数，然后反复以上步骤。当算法错误次数达到1000次后，使用错误次数除以总译码次数得到此算法的BLER。式中：llr是接收到的信道软比特值，y是接收到的信道信号，2是高斯白噪声平均功率。将本文设计的新算法与FSCL算法，分别在K=56、N=512，K=110、N=512，K=164、N=512进 行 仿真，仿真结果发现：两种算法的译码BLER性能曲线几乎是完全重合的，在部分情况下新算法的性能还更好一点。这表明新算法不会造成BLER性能损失，满足优化的前提条件。2.3.2时延性能分析为验证算法的译码时延，本文将采用宸芯科技CX8910芯片平台对新算法和FSCL算法进行实现验证。这是一款5G SDR（软件定义的无线电）通用芯片，芯片包含了CEVA XC4500 DSP（数字信号处理器）。此处理器结合了典型的数字信号处理能力和先进的矢量处理功能，能够实现通常只能由专用硬件才能完成的高复杂度的基带处理，且采用完全可编程的架构，可以在开发平台上软实现各种通信算法，以及可进行相对应的软仿真测试。Polar码译码算法是基于XC4500 DSP处理器实现及完成验证的。论 文 选 粹412023年第6期表6新算法和FSCL算法对不同码型的软仿时延对比图3详细列举了新算法和FSCL算法的译码流程，其中node_index变量指的是图1译码二叉树图中的节点索引号，按照从上到下，从左到右的顺序编号，每个索引号都对应一个节点类型；g_ func_flag变量是执行g运算的标志位。可以发现，node_index变量是整个算法的控制条件，它对应着实际Polar码译码过程中从根节点出发、自上到下、从左到右的一个译码流程。还需要注意的是，该算法的执行前提是已知所需译码的Polar码的特殊节点信息。在实际应用中，会提前计算好在通信链路中会遇见的所有Polar码码型的节点信息，将其存储在内存中，以牺牲一部分内存换取计算复杂度的减少。该算法中省略了一些函数具体的实现细节，例如f运算和g运算、不同特殊节点译码函数等，它们都尽可能采用矢量计算模块，并行处理以减少译码时延。用新算法和FSCL算法的实现程序分别对不同码型的Polar码进行译码，新算法和FSCL算法输入软比特向量相同，分别统计两种算法所消耗的芯片运行指令数。新算法和FSCL算法对不同码型的软仿时延对比见表6。从实验结果可以发现，相比FS-CL，新算法在不同码型下，译码时延有20%30%的下降，新算法的时延优化有明显的效果。3 结束语本文针对FSCL算法带来的时延较大的问题，设计了新的译码算法，并完成新算法在CX8910芯片上软实现，实验表明新算法获得了显著的译码时延优化。译码时延对5G通信系统而言是一个非常重要的参数，它影响着通信系统整体的通信时延、多用户接入数等指标。R17版本中最受人关注的技术之一是RedCap，它是5G轻量级中高速物联网技术，具有低时延、高可靠等优异性能，且功耗、成本、复杂度更低。未来5G Advance的演进方向之一是进一步降低终端复杂程度以支持中高速物联网应用，因此对Polar码来说未来的工作除了研究译码时延，还包括研究其译码实现复杂度降低等。除此之外，Polar码作为一种实现简单且优异的传输性能编码方案，在其他移动通信系统、卫星通信等领域都具有广阔的应用前景，也有很高的研究价值。参考文献1ARIKAN E.Channelpolarization:A method forconstructingcapacity-achievingcodesforsymmetricbinary-input论 文 选 粹图3新算法和FSCL算法的译码流程422023年第6期（上接第 36 页）行业中游运营商及上游基础设施方将成为技术产品及工艺革新的操刀人，只有被普遍证明安全适配、产品技术应用及行业生态链相对成熟且总体经济指标优异的数据中心技术架构和产品工艺，才能成为国内市场青睐的主流方案。部分采取过于激进和过于保守的战略决策的投建方，极有可能遭遇经济效益的严重下滑或投资战略路线的滞后偏离，最终被迫淘汰出局。以上这些趋势分析均值得国内各投建方高度重视。参考文献1第一太平戴维斯.亚太数据中心 R.2022.2中国数据中心工作组.2021 年中国数据中心市场报告R.2021.3中商情报网.2022 年中国数据中心产业链上中下游市场剖析 R.2022.4王大晓，刘彬，浦培林，等.金融行业数据中心规划建设及技术发展趋势探讨 J.建筑电气，2022，41（7）：64-68.5中国信息通信研究院.全球数字经济白皮书（2022 年）R.2022.6张海南，田亚玲，张阳，等.中国数据中心节能技术发展现状与趋势 J.中国基础科学，2020，22（6）：10-14陈凤（1983），男，工程师，硕士，主要从事于数据中心规划设计和节能挖潜研究工作。收稿日期：2023-02-17memoryless channelsJ.IEEE Transactions on InformationTheory,2009,55（7）：3051-3073.2LI B,SHEN H,TSE D.An adaptive successive cancellationlist decoder forpolar codes with cyclic redundancy checkJ.IEEE Communications Letters,2012,16（12）：2044-2047.3GAO C,LOU R,DAI B,et al.Path splitting selectingstrategy-aided successive cancellation list algorithm for po-lar codes J.IEEE Communications Letters,2019,23（3）：422-425.4HASHMI S A，CONDO C,GROSS W J.Fast simplifiedsuccessive-cancellation list decoding of polar codes C.IEEEWirelessCommunicationsandNetworking ConferenceWorkshops，20175SARKIS G,GIARD P,VARDY A,et al.Fast list decodersfor polar codesJ.IEEE Journal on Selected Areas in Com-munications,2016,34（2）：318-328.6ARDAKANI M H,HANIF M,ARDAKANI M,et al.Fastsuccessive-cancellation-based Decoders of Polar Codes J.IEEE Transactions on Communications,2019，67（7）：4562-4574.7YUANB，PARHIKK.Low-latencysuccessive-cancellation list decoders for polar codes withmultibitdecisionJ.IEEE transactions on very largescaleintegration(VLSI)systems,2015,23(10):2268-2280.8YUAN B,PARHI K K.Reduced-latency LLR-based SC listdecoder for polar codesC/The 25th edition,ACM,2015.9HAN J,LIU R,WANG R.Simplified multi-bit SC listdecoding for polar codesC/2016 IEEE InternationalConference on Acoustics,Speech and Signal Processing(ICASSP),2016.10HU H J,LIU R K,FENG B P.Flexible and simplifiedmulti-bit successive-cancellation list decoding for polarcodes C.2019 IEEE International Workshop on SignalProcessing Systems（SiPS），2019.周义森（1997），男，硕士研究生，主要研究方向为移动通信技术、Polar 编译码技术研究。收稿日期：2022-12-22论 文 选 粹43