The Fast Successive Cancellation List Decoding Algorithm for Parity-Check Polar Codes

LI Jun-yi; XING Li-juan; LI Zhuo

doi:10.12263/DZXB.20240496

您当前的位置：

首页 >

文章列表页 >

The Fast Successive Cancellation List Decoding Algorithm for Parity-Check Polar Codes

Advances and Future of Coding Theory and Technology | 更新时间：2025-12-10

- The Fast Successive Cancellation List Decoding Algorithm for Parity-Check Polar Codes
- ACTA ELECTRONICA SINICA Vol. 53, Issue 7, Pages: 2210-2221(2025)
- 作者机构：
  
  西安电子科技大学通信工程学院，陕西西安 710071
- 作者简介：
- 基金信息：
  
  Project 111 Fund(B08038)
- DOI：10.12263/DZXB.20240496
  CLC： TN911.22;
- Received：29 May 2024，
  
  Revised：2024-11-14，
  
  Published：25 July 2025
- 稿件说明：
移动端阅览
李俊毅, 邢莉娟, 李卓. 奇偶校验极化码的快速串行抵消列表译码算法[J]. 电子学报, 2025, 53(07): 2210-2221.

LI Jun-yi, XING Li-juan, LI Zhuo. The Fast Successive Cancellation List Decoding Algorithm for Parity-Check Polar Codes[J]. Acta Electronica Sinica, 2025, 53(07): 2210-2221.
李俊毅, 邢莉娟, 李卓. 奇偶校验极化码的快速串行抵消列表译码算法[J]. 电子学报, 2025, 53(07): 2210-2221. DOI：10.12263/DZXB.20240496

LI Jun-yi, XING Li-juan, LI Zhuo. The Fast Successive Cancellation List Decoding Algorithm for Parity-Check Polar Codes[J]. Acta Electronica Sinica, 2025, 53(07): 2210-2221. DOI：10.12263/DZXB.20240496

摘要

为了缩短奇偶校验极化码串行抵消列表（Parity-Check Successive Cancellation List，PC-SCL）译码算法的时延，本文提出了快速奇偶校验串行抵消列表（Fast Parity-Check Successive Cancellation List，Fast-PC-SCL）译码算法.该算法首先分析并研究了奇偶校验极化码（Parity-Check Polar，PC-Polar）中存在的2类特殊节点——奇偶校验重复（PC-REPetition，PC-REP）类节点和单奇偶校验（PC-Single-Parity-Check，PC-SPC）类节点，并通过理论证明了PC-REP类节点具有码字序列周期性重复、PC-SPC类节点具有码字和为特定值的性质.其次根据上述性质，给出了这2类节点的码字列表估计方法，使得包含这2类节点的极化码在译码时可以通过并行执行来大幅度缩短译码的时间延迟.最后结合这2类节点的码字列表估计方法，提出了Fast-PC-SCL译码算法.该算法可以在不完全遍历串行抵消（Successive Cancellation，SC）译码树的情况下进行译码，同时充分保留PC比特校验的效果.与PC-SCL译码算法相比，在不损失性能的前提下，该算法显著缩短了译码时延.实验数据表明，最多可缩短55.13%的时间延迟.

Abstract

To reduce the latency of the parity-check successive cancellation list (PC-SCL) decoding algorithm for parity-check polar codes

a fast parity-check successive cancellation list (Fast-PC-SCL) decoding algorithm is proposed. Firstly

the algorithm analyzes and studies two types of special nodes in parity-check polar (PC-Polar) codes: PC-Repetition (PC-REP) nodes and PC-single parity-check (PC-SPC) nodes

and theoretically proves that PC-REP nodes exhibit cyclic repetition of codeword sequences

while PC-SPC nodes have the property of the sum of codewords equals a specific value. Secondly

based on these properties

codeword list estimation methods are given for these two types of nodes. This enables the decoding of these nodes to be executed in parallel

significantly reducing decoding latency. Finally

by combining the codeword list estimation methods for these two types of nodes

the Fast-PC-SCL decoding algorithm is presented. This algorithm can decode without completely traversing the successive cancellation (SC) decoding tree

while fully retaining the effect of PC bit checks. Compared to the PC-SCL algorithm

it significantly reduces decoding latency without sacrificing performance. Experimental data shows that it can reduce latency by up to 55.13%.

关键词

Keywords

references

ARIKAN E . Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels [J ] . IEEE Transactions on Information Theory , 2009 , 55 ( 7 ): 3051 - 3073 .

3GPP. NR; Multiplexing and channel coding: 3GPP TS 38.212 [S/OL ] . ( 2022-09-21 )[ 2024-05-29 ] . https://itecspec.com/archive/3gpp-specification-ts-38-212/ https://itecspec.com/archive/3gpp-specification-ts-38-212/ .

TAL I , VARDY A . List decoding of polar codes [J ] . IEEE Transactions on Information Theory , 2015 , 61 ( 5 ): 2213 - 2226 .

ALAMDAR-YAZDI A , KSCHISCHANG F R . A simplified successive-cancellation decoder for polar codes [J ] . IEEE Communications Letters , 2011 , 15 ( 12 ): 1378 - 1380 .

SARKIS G , GROSS W J . Increasing the throughput of polar decoders [J ] . IEEE Communications Letters , 2013 , 17 ( 4 ): 725 - 728 .

SARKIS G , GIARD P , VARDY A , et al . Fast polar decoders: Algorithm and implementation [J ] . IEEE Journal on Selected Areas in Communications , 2014 , 32 ( 5 ): 946 - 957 .

HASHEMI S A , CONDO C , GROSS W J . Simplified successive-cancellation list decoding of polar codes [C ] // 2016 IEEE International Symposium on Information Theory (ISIT) . Piscataway : IEEE , 2016 : 815 - 819 .

HASHEMI S A , CONDO C , GROSS W J . Fast simplified successive-cancellation list decoding of polar codes [C ] // 2017 IEEE Wireless Communications and Networking Conference Workshops (WCNCW) . Piscataway : IEEE , 2017 : 1 - 6 .

HASHEMI S A , CONDO C , GROSS W J . Fast and flexible successive-cancellation list decoders for polar codes [J ] . IEEE Transactions on Signal Processing , 2017 , 65 ( 21 ): 5756 - 5769 .

HANIF M , ARDAKANI M . Fast successive-cancellation decoding of polar codes: Identification and decoding of new nodes [J ] . IEEE Communications Letters , 2017 , 21 ( 11 ): 2360 - 2363 .

ARDAKANI M H , HANIF M , ARDAKANI M , et al . Fast successive-cancellation-based decoders of polar codes [J ] . IEEE Transactions on Communications , 2019 , 67 ( 7 ): 4562 - 4574 .

CONDO C , BIOGLIO V , LAND I . Generalized fast decoding of polar codes [C ] // 2018 IEEE Global Communications Conference (GLOBECOM) . Piscataway : IEEE , 2018 : 1 - 6 .

ZHENG H T , HASHEMI S A , BALATSOUKAS-STIMMING A , et al . Threshold-based fast successive-cancellation decoding of polar codes [J ] . IEEE Transactions on Communications , 2021 , 69 ( 6 ): 3541 - 3555 .

WANG T , QU D M , JIANG T . Parity-check-concatenated polar codes [J ] . IEEE Communications Letters , 2016 , 20 ( 12 ): 2342 - 2345 .

PARK J , KIM I , SONG H Y . Construction of parity-check-concatenated polar codes based on minimum Hamming weight codewords [J ] . Electronics Letters , 2017 , 53 ( 14 ): 924 - 926 .

ZHOU Y C , ZHENG Y J , WANG Z F . Fast successive-cancellation decoding of 5G parity-check polar codes [J ] . IEEE Communications Letters , 2021 , 27 ( 1 ): 37 - 40 .

HiSilicon . 3GPP TSG RAN WG1 meeting AH NR R1-1700088: Summary of Polar Code Design for Control Channels [R ] . Spokane : HiSilicon , 2017 .

BALSER M , SILVERMAN R A . Coding for constant-data-rate systems-part II multiple-error-correcting codes [J ] . Proceedings of the IRE , 2007 , 43 ( 6 ): 728 - 733 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Polarizing Matrix Extension-Based Joint Source-Channel Coding in HARQ Systems

Research on the Application of Polar Codes in Underwater Acoustic Communication

An Algorithm for Rate-Compatible Punctured Polar Codes Based on Hierarchical Permutation Structure

Related Author

NIU Kai

WANG Wei

XING Li-juan

LI Zhuo

ZHANG Ze-dong

王留洋

覃团发

孙友明

Related Institution

The Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing University of Posts and Telecommunications

State Key Laboratory of Integrated Service Networks, Xidian University

State Key Laboratory of Integrated Service Networks， Xidian University

⁰