基于简化序列重复节点的极化码快速串行抵消译码算法_郭锐.pdf

2023 年 5 月 Journal on Communications May 2023 第 44 卷第 5 期 通 信 学 报 Vol.44 No.5基于简化序列重复节点的极化码快速串行抵消译码算法 郭锐，刘洋（杭州电子科技大学通信工程学院，浙江 杭州 310018）摘 要：为了进一步降低串行抵消（SC）译码算法的译码时延，在序列重复（SR）节点的基础上，根据 SR 源节点的类型与译码复杂度，对不同类型的拓展类广义奇偶校验（EG-PC）节点进行分解、合并和简化，并使用快速简化串行抵消（Fast-SSC）译码对 Rate-C 节点进行裁剪处理，提出了基于简化 SR 节点的极化码快速 SC 译码算法（SSRFSC）。实验数据表明，在相近的译码性能下（在误帧率为 103时，约有 0.1 dB 的性能损失），与基于 SR节点的快速 SC（SRFSC）译码算法相比，所提算法的译码时延最多减少了 28%；与 Fast-SSC 译码算法相比，译码时延最多减少了 49%。关键词：极化码；快速简化串行抵消；简化序列重复节点；译码时延 中图分类号：TN911.22 文献标志码：A DOI:10.11959/j.issn.1000436x.2023088 Simplified sequence repetition nodes-based fast successive cancellation decoding algorithm for polar code GUO Rui,LIU Yang School of Communication Engineering,Hangzhou Dianzi University,Hangzhou 310018,China Abstract:In order to reduce the decoding latency of the successive cancellation(SC)decoding algorithm further,a kind of fast SC decoding algorithm based on simplified sequence repetition(SR)nodes,namely simplified sequence repetition node-based fast SC(SSRFSC),was proposed to optimize decoding latency issues of SC decoding algorithm.Different types of extended class of generalized parity-check(EG-PC)nodes were decomposed,merged and simplified based on the type of SR source node and decoding complexity,and Rate-C node was trimmed using fast simplified successive cancellation(Fast-SSC)decoding.Experimental results show that the decoding latency of the proposed algorithm can be reduced by up to 28%compared to the latest simplified sequence repetition(SRFSC)decoding algorithm when achieving similar decoding performance(approximately 0.1dB performance loss at frame error rate of 103).Moreover,compared to the Fast-SSC decoding algorithm,the decoding latency of proposed algorithm can be reduced by up to 49%.Keywords:polar code,Fast-SSC,simplified SR node,decoding latency 0 引言 极化码是目前唯一一种通过严格的数学证明可以达到二进制离散无记忆信道容量的编码方法1。由于具有显式的结构以及较低的编译码复杂度等优点，极化码在最新的 5G 移动通信标准中被批准作为 5G 增强型移动带宽（eMBB,enhanced mobile broadband）控制信道的编码方案2-3。虽然串行抵消（SC,successive cancellation）译码算法为极化码提供了一种较低复杂度的译码方案，但 SC 串行译码的特性导致译码时延较高，从而限制了其在低时延通信场景中的应用4。因此，解决极化码译码时延的问题受到了广泛关注5。文献6-7提出了一种低时延的 SC 译码算法，收稿日期：20230118；修回日期：20230410 基金项目：浙江省重点研发计划基金资助项目（No.2023C03014）Foundation Item:The Key Research and Development Program of Zhejiang Province(No.2023C03014)第 5 期 郭锐等：基于简化序列重复节点的极化码快速串行抵消译码算法 159 在 SC 译码的每个阶段，针对下一个阶段可能需要的输入信息和中间值，先根据当前的输入信息和中间值，对其所有可能性及可靠性进行预估计，从而减少时延和数据依赖，提高吞吐量，但是需要在硬件结构中增加一些额外的逻辑单元和存储单元。此外，相对于按顺序进行单比特判决的传统 SC 译码，出现了一种在 SC 译码树的中间节点上同时进行多比特判决的改进思路。文献8-10采用穷举搜索译码算法进行多比特判决，避免了遍历 SC 译码树时计算中间对数似然比（LLR,log-likelihood ratio）所导致的时延。但是穷举搜索译码算法的复杂性较高，一般只适用于码长较短的极化码。文献11提出了一种简化串行抵消（SSC,sim-plified successive cancellation）译码算法，使用Rate-0和Rate-1这2种节点对SC译码树进行裁剪，可以在不完全遍历 SC 译码树的情况下进行译码，一定程度上降低了译码时延且不会产生译码性能的损失。文献12提出了基于重复（REP,repetition）节点和单奇偶校验（SPC,single parity-check）节点的快速简化串行抵消（Fast-SSC,fast simplified successive cancellation）译码算法，大幅降低了译码时延。文献13确定了 5 种新节点类型（即 Type-I、Type-II、Type-III、Type-IV 和 Type-V），进一步提高了译码的并行性。然而，上述所有研究都需要为每一类节点设计一个独立的译码方法，这不可避免地增加了算法实现的复杂性。为此，文献14创造性地提出了多节点模式的思想，将 REP、SPC 和 Type-IType-V 节点的特点进行拓展和推广，提出了广义 REP（G-REP,gene-ralized repetition）节点和广义奇偶校验（G-PC,generalized parity-check）节点，并给出了该类节点的识别和通用译码规则以进一步减少译码时延。文献15分析了短码长极化码中出现最多的7种节点，并提出了并行处理这些节点的有效算法。然而，其中一些节点的译码会导致显著的性能损失。文献16-17在多节点模式的启发下对文献14中的G-REP节点进一步推广，以降低 SC 译码树遍历的深度为目的，提出了序列重复（SR,sequence repetition）节点，该类节点通常位于 SC 译码树的更高层级且包含现有的大多数节点类型，具有更通用的冻结位和信息位排列模式；进而提出了基于 SR 节点的快速串行抵消（SRFSC,SR node-based fast SC）译码算法。但是在没有硬件资源限制的条件下，SRFSC 译码算法与文献13-14中的方法相比，仅能在一定程度上降低译码时延。目前，各类最新的极化码快速 SC 译码算法普遍存在的问题是译码复杂度和时延较高，并且缺少一种通用的译码算法以达到低时延高效率译码的目的。多节点模式的思想以及 SR 节点的发现为解决这些问题提供了新的思路。在 SRFSC 译码中，拓展类广义奇偶校验（EG-PC,extended class of generalized parity-check）节点和 Rate-C 节点作为源节点译码过程较复杂，并且 EG-PC 节点在 SC 译码树中有相当高的占比，两者均是 SRFSC 产生译码时延的重要原因。针对这一问题，本文根据不同情况对 EG-PC 节点进行分解、合并或简化，并结合 Fast-SSC 译码算法对 Rate-C 节点进行裁剪处理，提出了简化 SR 节点以及基于简化 SR 节点的快速 SC（SSRFSC,sim-plified sequence repetition node-based fast SC）译码算法。实验数据表明，与SRFSC译码算法相比，SSRFSC的译码时延最多可减少 28%；与 Fast-SSC 译码算法相比，译码时延最多可减少 49%。1 极化码 SC 与 Fast-SSC 译码算法 1.1 极化码编译码基本原理 极化码利用信道极化现象，使用 K 个相对可靠的信道来传输信息，称为信息位，本文用 A表示这些信息位索引组成的集合；而其余NK个相对不可靠的信道则用来传输提前约定好的已知信息（2nN为极化码码长），称为冻结位，冻结位索引组成的集合用cA表示。为了更方便地表示相关信息，本文使用|Q表示集合Q中元素的数量，并为每个比特信道分配了标志md，含义如下 0,1,cmmAd其他(1)其中，m表示比特信道的索引，码长2nN，信息位长度等于K的极化码编码过程为 1100NNNxuG(2)其中，10011()NNu uuu表示输入的比特向量。生成矩阵NG由极化码核心矩阵21011F的n阶克罗内克积计算而得，即2nNGF。SC 译码是一种传统的极化码译码算法。在 SC译码树中，对数似然比以向量的形式位于根节点处，并向子节点传递。在译码时，对于层级j的某个节点160 通 信 学 报 第 44 卷 jN，其 LLR 向量优先向左子节点传播，得到 LLR向量11,L1,L1,L1,L(1 2 2)jjjjj ，传递的计算过程为 11,L11(,2)sgn()sgn(2)min(|,|2|)jjjjjjjjjjmfmmmmmm(3)式(3)定义了F函数，jN的右子节点会接收到相应的LLR向量1,R jm，可以通过G函数求得，计算过程为 11,R11,L(,2)2(12)jjjjjjjjmgmmmmm(4)其中，112jm，最终节点jN处的硬判决向量j 的计算式为 11,L1,R11,R ,2 2,jjjjjjmmmmm其他(5)1.2 Fast-SSC 等相关算法 对于某些信息位和冻结位具有特定排列模式的节点，文献6-7对其进行了归类，并提出了针对这些节点的高效译码算法，称为Fast-SSC译码算法，从而可以直接计算其返回的硬判决比特向量，不需要再向译码树更深处遍历。在Fast-SSC中，这些特殊节点可以描述如下。在第0层级，Rate-0节点，每个比特都是冻结位；Rate-1节点，每个比特都是信息位；REP节点，除了最后一位是信息位外，其余位置都是冻结位；SPC节点，除了第一位是冻结位外，其余位置都是信息位。上述4种特殊节点的二叉树结构如图1所示，其中灰色节点表示既存在信息位又存在冻结位的混合速率节点。文献13将其中部分节点合并，在二叉树的更高层引入了5种新的节点（Type-IType-