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:1406.7036 · IEEE Transactions on Very Large Scale Integration (VLSI) Systems

Low-Latency Successive-Cancellation List Decoders for Polar Codes With Multibit Decision

Bo Yuan, Keshab K. Parhi

Published Jan 19, 2015• 117 citations
arXivHTMLPDF

Abstract

Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.

DOI
10.1109/tvlsi.2014.2359793

Related papers

A Low-Latency Successive Cancellation Hybrid Decoder for Convolutional Polar Codes

Yu Wang, Shikai Qiu, Lirui Chen +4 more

By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•1 citation

Hardware And Latency Efficient Architecture for Successive Cancellation List Decoding of Polar Codes

M Lakshmi, Narayanan G Lakshmi

In order to achieve a magnificent error-correcting performance Successive Cancellation List (SCL) decoding is a powerful and excellent method which considers L decoding paths at each decoding stage concurrently. However, the conventional SCL decoder uses L copies of Successive Cancellation (SC) decoder for a list size of L thereby resulting in a massive increase in the hardware as the list size increases which is one of the major drawbacks of SCL decoder. One more drawback of SCL decoder architecture is the long latency of the architecture. Using the proposed efficient utilization of existing hardware architecture, there is a reduction in the number of Merged Processing Elements (MPE) by 39% for a list size of 2 and 45% for a list size of 4 when compared to the existing architectures and a vast reduction compared to conventional SCL decoder. The partial pipelining considered in this work can reduce the latency compared to conventional SCL multi-bit architecture to a greater extent.

TEQIP III Sponsored International Conference on Microwave Integrated Circuits, Photonics and Wireless Networks (IMICPW)•May 1, 2019•1 citation

Fast Multibit Decision Method for Successive-Cancellation List Polar Decoder

Seo Lin Jeong, Seung Yong Kim, Jung Hyun Bae +1 more

SC and SCL are the decoding algorithms for polar codes that have the disadvantage of high latency due to serial operations. Several algorithms, such as Fast-SSC, multibit decision, have been proposed to improve the latency with additional circuits, however, areas become larger. This paper proposes an efficient multibit decision algorithm to improve latency based on the SCL algorithm. In addition, we propose the combined nodes that combine node types of the fast-SSC algorithm to increase area efficiency and reduce the number of decoding cycles.

International SoC Design Conference•Oct 6, 2019•0 citations

In Situ Multi-Bit Decision for Successive Cancellation List Decoding of Polar Codes

Jaehyeon Park, Jaeyoung Lee, In‐Cheol Park

Polar codes are the first capacity-achieving error-correction code which has attracted much research attention. Among many decoding methods, successive cancellation list decoding (SCLD) is considered as a representative decoding method that can achieve a good error-correcting performance. However, the long latency of SCLD is a significant matter that hinders practical applications, which is mainly caused by two features of the SCLD process: tree traversal and path-splitting. To alleviate the main reasons, a new multi-bit SCLD algorithm is proposed in this paper to decode several bits simultaneously without conducting any tree traversal and path-splitting when a node in the decoding tree holds a specific condition. In addition, a path ignoring (PI) technique is proposed to mitigate the condition of the multi-bit SCLD, which results in an additional reduction of latency. The proposed multi-bit decoding method and the PI technique play a significant role in reducing the number of path-splitting cases, by 96% compared to the conventional SCLD method. Simulation results show that compared to the conventional SCLD with list sizes 8 and 16, the proposed multi-bit decoding associated with the PI technique reduces the overall decoding cycles by 77% and 79%, respectively, with almost no degradation of error-correcting performance.

IEEE Access•Jan 1, 2022•5 citations

High-Speed Architecture for Successive Cancellation Decoder With Split-g Node Block

Sujanth Roy James, G. Lakshminarayanan, Seok‐Bum Ko

Polar codes are one of the recently developed error correcting codes, and they are popular due to their capacity achieving nature. The architecture of the successive cancellation (SC) decoder algorithm is composed of a recursive processing element (PE). The PE comprises various blocks that include signed adder, subtractor, comparator, multiplexers, and few logic gates. Therefore, the latency of the PE is a primary concern. Hence, a high-speed architecture for implementing the SC decoding algorithm for polar codes is proposed. In the proposed work, a novel restructuring of the 2bit-SC (2b-SC) precomputation decoder architecture is carried out to reduce the latency by 20% while reducing the hardware complexity. Compared to the 2b-SC precomputation decoder, the proposed architecture also has 19% increased throughput for (1024, 512) polar codes with 45% reduction in the gate count.

IEEE Embedded Systems Letters•Sep 2, 2020•9 citations

Large-Small Sorting for Successive Cancellation List Decoding of Polar Codes

Kyungpil Lee, In‐Cheol Park

The successive cancellation list (SCL) decoding is used to achieve good error-correcting performance for practical finite-length polar codes. However, the metric sorting that is repeatedly performed in SCL decoding increases the overall decoding latency as the list size increases, making it difficult to apply the SCL decoding to the applications with limited processing time. To reduce the latency of the metric sorting, this paper proposes a new sorting method derived by analyzing path extension cases encountered in SCL decoding. The proposed method can avoid unnecessary sorting operations by adaptively determining the sorting size, and can be combined with other metric sorting methods. Simulation results show that the proposed method significantly reduces the decoding latency for various list sizes and code rates without degrading the error-correcting performance. The proposed method also becomes more effective as the code rate or the list size increases. Combined with the state-of-the-art sorting method, the proposed method reduces the average SCL decoding latency for a (1024, 512) polar code by 33.1% when the list size is 8.

IEEE Access•Jan 1, 2020•4 citations
Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.
By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.
In order to achieve a magnificent error-correcting performance Successive Cancellation List (SCL) decoding is a powerful and excellent method which considers L decoding paths at each decoding stage concurrently. However, the conventional SCL decoder uses L copies of Successive Cancellation (SC) decoder for a list size of L thereby resulting in a massive increase in the hardware as the list size increases which is one of the major drawbacks of SCL decoder. One more drawback of SCL decoder architecture is the long latency of the architecture. Using the proposed efficient utilization of existing hardware architecture, there is a reduction in the number of Merged Processing Elements (MPE) by 39% for a list size of 2 and 45% for a list size of 4 when compared to the existing architectures and a vast reduction compared to conventional SCL decoder. The partial pipelining considered in this work can reduce the latency compared to conventional SCL multi-bit architecture to a greater extent.
SC and SCL are the decoding algorithms for polar codes that have the disadvantage of high latency due to serial operations. Several algorithms, such as Fast-SSC, multibit decision, have been proposed to improve the latency with additional circuits, however, areas become larger. This paper proposes an efficient multibit decision algorithm to improve latency based on the SCL algorithm. In addition, we propose the combined nodes that combine node types of the fast-SSC algorithm to increase area efficiency and reduce the number of decoding cycles.
Polar codes are the first capacity-achieving error-correction code which has attracted much research attention. Among many decoding methods, successive cancellation list decoding (SCLD) is considered as a representative decoding method that can achieve a good error-correcting performance. However, the long latency of SCLD is a significant matter that hinders practical applications, which is mainly caused by two features of the SCLD process: tree traversal and path-splitting. To alleviate the main reasons, a new multi-bit SCLD algorithm is proposed in this paper to decode several bits simultaneously without conducting any tree traversal and path-splitting when a node in the decoding tree holds a specific condition. In addition, a path ignoring (PI) technique is proposed to mitigate the condition of the multi-bit SCLD, which results in an additional reduction of latency. The proposed multi-bit decoding method and the PI technique play a significant role in reducing the number of path-splitting cases, by 96% compared to the conventional SCLD method. Simulation results show that compared to the conventional SCLD with list sizes 8 and 16, the proposed multi-bit decoding associated with the PI technique reduces the overall decoding cycles by 77% and 79%, respectively, with almost no degradation of error-correcting performance.
Polar codes are one of the recently developed error correcting codes, and they are popular due to their capacity achieving nature. The architecture of the successive cancellation (SC) decoder algorithm is composed of a recursive processing element (PE). The PE comprises various blocks that include signed adder, subtractor, comparator, multiplexers, and few logic gates. Therefore, the latency of the PE is a primary concern. Hence, a high-speed architecture for implementing the SC decoding algorithm for polar codes is proposed. In the proposed work, a novel restructuring of the 2bit-SC (2b-SC) precomputation decoder architecture is carried out to reduce the latency by 20% while reducing the hardware complexity. Compared to the 2b-SC precomputation decoder, the proposed architecture also has 19% increased throughput for (1024, 512) polar codes with 45% reduction in the gate count.
The successive cancellation list (SCL) decoding is used to achieve good error-correcting performance for practical finite-length polar codes. However, the metric sorting that is repeatedly performed in SCL decoding increases the overall decoding latency as the list size increases, making it difficult to apply the SCL decoding to the applications with limited processing time. To reduce the latency of the metric sorting, this paper proposes a new sorting method derived by analyzing path extension cases encountered in SCL decoding. The proposed method can avoid unnecessary sorting operations by adaptively determining the sorting size, and can be combined with other metric sorting methods. Simulation results show that the proposed method significantly reduces the decoding latency for various list sizes and code rates without degrading the error-correcting performance. The proposed method also becomes more effective as the code rate or the list size increases. Combined with the state-of-the-art sorting method, the proposed method reduces the average SCL decoding latency for a (1024, 512) polar code by 33.1% when the list size is 8.