Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.08188 · IEEE Transactions on Communications

Fast List Decoding of High-Rate Polar Codes

Yang Lu, Minjian Zhao, Ming Lei, Min-Jian Zhao

Published Jul 12, 2024• 7 citations
arXivHTMLPDF

Abstract

Due to the ability to provide superior error-correction performance, the successive cancellation list (SCL) algorithm is widely regarded as one of the most promising decoding algorithms for polar codes with short-to-moderate code lengths. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. To reduce the decoding latency, developing tailored fast and efficient list decoding algorithms of specific polar constituent codes (special nodes) is a promising solution. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming to further speedup the SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) nodes and sequence rate one or single-parity-check (SR1/SPC) nodes. In particular, we develop two classes of fast list decoding algorithms for these nodes, where the first class uses a sequential decoding procedure to yield decoding latency that is linear with the list size, and the second further parallelizes the decoding process by pre-determining the redundant candidate paths offline. Simulation results show that the proposed list decoding algorithms are able to achieve up to 70.7% lower decoding latency than state-of-the-art fast SCL decoders, while exhibiting the same error-correction performance.

DOI
10.1109/tcomm.2024.3427348

Related papers

Fast List Decoding of High-Rate Polar Codes Based on Minimum-Combinations Sets

Yang Lu, Ming-Min Zhao, Ming Lei +2 more

Being able to provide excellent error-correction performance for polar codes with short-to-moderate code length, successive-cancellation list (SCL) is regarded as one of the most promising decoding algorithms. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming at achieving further speedup for SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) and sequence rate-1(SRI) nodes, based on the minimum-combinations set (MCS) which is able to significantly narrow the search space of candidate paths. Typically, SPC nodes can be directly decoded within one round of path splitting procedure, whereas SR1 nodes, as a group of parallel SPC nodes, can also be decode efficiently. Simulation results show that the proposed fast SCL decoder is able to reduce the decoding latency by 68.4% as compared to the state of the art, without any error-correction performance degradation.

International Conference on Communications•Jun 9, 2024•2 citations

Parallel Single Parity Check Nodes for High-Throughput Fast-SSCL Polar Code Decoders

Lucas Johannsen, Claus Kestel, Timo Vogt +1 more

Successive-Cancellation List (SCL) decoding of Polar codes, supported by a Cyclic Redundancy Check, achieves a distinguished error-correction performance at the cost of a high decoding complexity. The parallel decoding of constituent Single Parity Check (SPC) nodes of a Polar factor tree relevantly contributes to the implementation costs of high-throughput, deeply pipelined SCL decoding architectures. In this paper, we present algorithms to reduce the number of considered candidates in SPC nodes. For this purpose, we adapt the partial order-based Rate-1 node candidate generation algorithm to the constraints in SPC nodes and deduce a low-complexity algorithm suitable for efficient hardware implementation. Simulation results show that the presented algorithms preserve the error-correction performance with reduced hardware implementation costs. Additionally, an extended threshold in the candidate selection enables a trade-off between error-correction and implementation costs by a further reduction of the considered candidates. Furthermore, Application-Specific Integrated Circuit (ASIC) implementations of the optimized node and three decoders with a code length of 128 in a 28 nm technology are presented. Regarding area efficiency and energy efficiency, improvements of up to 350.8 % and 84.7 % are achieved for the single SPC node with its sorter, while the presented SCL decoder implementations with list size 8 outperform a state-of-the-art reference decoder by up to 32.4 % and 32.0 %, respectively.

IEEE International Symposium on Future Telecommunication Technologies (SOFTT)•Nov 14, 2022•8 citations

Fast Sequence Repetition Node-Based Successive Cancellation List Decoding for Polar Codes

Yifei Shen, Yuqing Ren, Andreas Toftegaard Kristensen +4 more

Compared with the bit-wise successive cancellation list (SCL) decoding of polar codes, the node-based Fast SCL decoding significantly reduces the decoding latency by identifying special constituent codes and decoding these in parallel. To further reduce the latency of current Fast SCL decoders, we first propose a fast sequence repetition (SR) node-based SCL (Fast SR-SCL) decoding algorithm, which only involves one type of node in the SCL decoding tree. Furthermore, we employ the adaptive path splitting (APS) strategy to terminate the path splitting in the SR node early, without degrading the error-correcting performance. Numerical results show that for 5G uplink codes with a length of 1024 and rates of 1/4, 1/2, and 3/4, our decoder can deliver the same decoding performance while reducing the average latency by 34.5%, 38.0%, and 39.6% compared with the state-of-the-art Fast SCL decoder for a list size L = 8.

International Conference on Communications•May 16, 2022•9 citations

Fast Simplified Successive-Cancellation List Decoding of Polar Codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time- steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.

IEEE Wireless Communications and Networking Conference Workshops (WCNCW)•Mar 1, 2017•86 citations

Fast Successive-Cancellation-Based Decoders of Polar Codes

Maryam Haghighi Ardakani, Muhammad Hanif, Masoud Ardakani +1 more

The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.

IEEE Transactions on Communications•Mar 19, 2019•62 citations

Fast Simplified Successive-Cancellation List Decoding of Polar Codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time-steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.

arXiv:1701.08126•Jan 27, 2017•4 citations
Due to the ability to provide superior error-correction performance, the successive cancellation list (SCL) algorithm is widely regarded as one of the most promising decoding algorithms for polar codes with short-to-moderate code lengths. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. To reduce the decoding latency, developing tailored fast and efficient list decoding algorithms of specific polar constituent codes (special nodes) is a promising solution. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming to further speedup the SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) nodes and sequence rate one or single-parity-check (SR1/SPC) nodes. In particular, we develop two classes of fast list decoding algorithms for these nodes, where the first class uses a sequential decoding procedure to yield decoding latency that is linear with the list size, and the second further parallelizes the decoding process by pre-determining the redundant candidate paths offline. Simulation results show that the proposed list decoding algorithms are able to achieve up to 70.7% lower decoding latency than state-of-the-art fast SCL decoders, while exhibiting the same error-correction performance.
Being able to provide excellent error-correction performance for polar codes with short-to-moderate code length, successive-cancellation list (SCL) is regarded as one of the most promising decoding algorithms. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming at achieving further speedup for SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) and sequence rate-1(SRI) nodes, based on the minimum-combinations set (MCS) which is able to significantly narrow the search space of candidate paths. Typically, SPC nodes can be directly decoded within one round of path splitting procedure, whereas SR1 nodes, as a group of parallel SPC nodes, can also be decode efficiently. Simulation results show that the proposed fast SCL decoder is able to reduce the decoding latency by 68.4% as compared to the state of the art, without any error-correction performance degradation.
Successive-Cancellation List (SCL) decoding of Polar codes, supported by a Cyclic Redundancy Check, achieves a distinguished error-correction performance at the cost of a high decoding complexity. The parallel decoding of constituent Single Parity Check (SPC) nodes of a Polar factor tree relevantly contributes to the implementation costs of high-throughput, deeply pipelined SCL decoding architectures. In this paper, we present algorithms to reduce the number of considered candidates in SPC nodes. For this purpose, we adapt the partial order-based Rate-1 node candidate generation algorithm to the constraints in SPC nodes and deduce a low-complexity algorithm suitable for efficient hardware implementation. Simulation results show that the presented algorithms preserve the error-correction performance with reduced hardware implementation costs. Additionally, an extended threshold in the candidate selection enables a trade-off between error-correction and implementation costs by a further reduction of the considered candidates. Furthermore, Application-Specific Integrated Circuit (ASIC) implementations of the optimized node and three decoders with a code length of 128 in a 28 nm technology are presented. Regarding area efficiency and energy efficiency, improvements of up to 350.8 % and 84.7 % are achieved for the single SPC node with its sorter, while the presented SCL decoder implementations with list size 8 outperform a state-of-the-art reference decoder by up to 32.4 % and 32.0 %, respectively.
Compared with the bit-wise successive cancellation list (SCL) decoding of polar codes, the node-based Fast SCL decoding significantly reduces the decoding latency by identifying special constituent codes and decoding these in parallel. To further reduce the latency of current Fast SCL decoders, we first propose a fast sequence repetition (SR) node-based SCL (Fast SR-SCL) decoding algorithm, which only involves one type of node in the SCL decoding tree. Furthermore, we employ the adaptive path splitting (APS) strategy to terminate the path splitting in the SR node early, without degrading the error-correcting performance. Numerical results show that for 5G uplink codes with a length of 1024 and rates of 1/4, 1/2, and 3/4, our decoder can deliver the same decoding performance while reducing the average latency by 34.5%, 38.0%, and 39.6% compared with the state-of-the-art Fast SCL decoder for a list size L = 8.
Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time- steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.
The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.
Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time-steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.