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:1401.3753 · IEEE Transactions on Signal Processing

LLR-Based Successive Cancellation List Decoding of Polar Codes

Alexios Balatsoukas‐Stimming, Mani Bastani Parizi, Andreas Peter Burg

Published Jun 3, 2015• 632 citations
arXivHTMLPDF

Abstract

We show that successive cancellation list decoding can be formulated exclusively using log-likelihood ratios. In addition to numerical stability, the log-likelihood ratio based formulation has useful properties that simplify the sorting step involved in successive cancellation list decoding. We propose a hardware architecture of the successive cancellation list decoder in the log-likelihood ratio domain which, compared with a log-likelihood domain implementation, requires less irregular and smaller memories. This simplification, together with the gains in the metric sorter, lead to$ 56\%$to$137\%$higher throughput per unit area than other recently proposed architectures. We then evaluate the empirical performance of the CRC-aided successive cancellation list decoder at different list sizes using different CRCs and conclude that it is important to adapt the CRC length to the list size in order to achieve the best error-rate performance of concatenated polar codes. Finally, we synthesize conventional successive cancellation decoders at large block-lengths with the same block-error probability as our proposed CRC-aided successive cancellation list decoders to demonstrate that, while our decoders have slightly lower throughput and larger area, they have a significantly smaller decoding latency.

DOI
10.1109/tsp.2015.2439211

Related papers

LLR-based successive cancellation list decoding of polar codes

Alexios Balatsoukas‐Stimming, Mani Bastani Parizi, Andreas Peter Burg

We present an LLR-based implementation of the successive cancellation list (SCL) decoder. To this end, we associate each decoding path with a metric which (i) is a monotone function of the path's likelihood and (ii) can be computed efficiently from the channel LLRs. The LLR-based formulation leads to a more efficient hardware implementation of the decoder compared to the known log-likelihood based implementation. Synthesis results for an SCL decoder with block-length of N = 1024 and list sizes of L = 2 and L = 4 confirm that the LLR-based decoder has considerable area and operating frequency advantages in the orders of 50% and 30%, respectively.

IEEE International Conference on Acoustics Speech and Signal Processing•May 1, 2014•80 citations

Successive cancellation list polar decoder using log-likelihood ratios

Bo Yuan, Keshab K. Parhi

Successive cancellation list (SCL) decoding algorithm is a powerful method that can help polar codes achieve excellent error-correcting performance. However, the current SCL algorithm and decoders are based on likelihood or log-likelihood forms, which render high hardware complexity. In this paper, we propose a log-likelihood-ratio (LLR)-based SCL (LLR-SCL) decoding algorithm, which only needs half the computation and storage complexity than the conventional one. Then, based on the proposed algorithm, we develop low-complexity VLSI architectures for LLR-SCL decoders. Analysis results show that the proposed LLR-SCL decoder achieves 50% reduction in hardware and 98% improvement in hardware efficiency.

arXiv:1411.7282•Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2014•42 citations

Convolutional Polar Codes: LLR-based Successive Cancellation Decoder and List Decoding Performance

Hamid Saber, Yiqun Ge, Ran Zhang +2 more

Recently convolutional polar (cpolar) codes have been proposed. A tensor-network-based successive cancellation (SC) decoding was proposed for them under which cpolar codes were shown to outperform polar codes. In this paper we present the notion of m-bit-channels for cpolar codes and give the recursive construction of m-bit-channels for m=3. Then a log likelihood ratio(LLR)-based SC decoding of complexity order O(Nlog(N)) for cpolar codes is presented. We also present the numerical results for performance evaluation of cpolar codes under SC list (SCL) decoding. Our simulation results show that cpolar codes can achieve the performance of polar codes with a list size reduced by a factor of 4.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•12 citations

Improved Adaptive Successive Cancellation List Decoding of Polar Codes

Xiumin Wang, Jinlong He, Jun Li +3 more

Although the adaptive successive cancellation list (AD-SCL) algorithm and the segmented-CRC adaptive successive cancellation list (SCAD-SCL) algorithm based on the cyclic redundancy check (CRC) can greatly reduce the computational complexity of the successive cancellation list (SCL) algorithm, these two algorithms discard the previous decoding result and re-decode by increasing L, where L is the size of list. When CRC fails, these two algorithms waste useful information from the previous decoding. In this paper, a simplified adaptive successive cancellation list (SAD-SCL) is proposed. Before the re-decoding of updating value L each time, SAD-SCL uses the existing log likelihood ratio (LLR) information to locate the range of burst error bits, and then re-decoding starts at the incorrect bit with the smallest index in this range. Moreover, when the segmented information sequence cannot get the correct result of decoding, the SAD-SCL algorithm uses SC decoding to complete the decoding of the subsequent segmentation information sequence. Furthermore, its decoding performance is almost the same as that of the subsequent segmentation information sequence using the AD-SCL algorithm. The simulation results show that the SAD-SCL algorithm has lower computational complexity than AD-SCL and SCAD-SCL with negligible loss of performance.

Entropy•Sep 17, 2019•3 citations

Iterative Decoding Based on Concatenated Belief Propagation for CRC-Aided Polar Codes

Satoshi Tajima, Takumi Takahashi, Shinsuke Ibi +1 more

This paper proposes a novel iterative decoder based on concatenated belief propagation (BP) for CRC-aided polar codes. Compared to the conventional BP-based decoders for polar codes, soft cancellation (SCAN) decoder can generate a log likelihood ratio (LLR) of coded bit with lower computational complexity without sacrificing the detection capability. Unfortunately, its performance is not as good as that of CRC-aided successive cancellation list decoder (SCLD) although SCAN decoder has advantage of hardware implementation. To compensate the performance gap, we exploit CRC structure for not only error detection but also error correction with the assistance of its error correction capability at a short code length by exchanging LLRs between SCAN decoder and BP decoder on the basis of CRC. Moreover, the sub-optimal criterion for selecting a parity check matrix of CRC for BP decoder is proposed. Finally, computer simulations are conducted to confirm the validity of our proposed method. The proposed method can obtain the gain of about 0.6 dB at BER=10-3compared to the native SCAN decoder without requiring huge memory size as in SCLD.

Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)•Nov 1, 2018•7 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
We show that successive cancellation list decoding can be formulated exclusively using log-likelihood ratios. In addition to numerical stability, the log-likelihood ratio based formulation has useful properties that simplify the sorting step involved in successive cancellation list decoding. We propose a hardware architecture of the successive cancellation list decoder in the log-likelihood ratio domain which, compared with a log-likelihood domain implementation, requires less irregular and smaller memories. This simplification, together with the gains in the metric sorter, lead to56% 56\%56%to137%137\%137%higher throughput per unit area than other recently proposed architectures. We then evaluate the empirical performance of the CRC-aided successive cancellation list decoder at different list sizes using different CRCs and conclude that it is important to adapt the CRC length to the list size in order to achieve the best error-rate performance of concatenated polar codes. Finally, we synthesize conventional successive cancellation decoders at large block-lengths with the same block-error probability as our proposed CRC-aided successive cancellation list decoders to demonstrate that, while our decoders have slightly lower throughput and larger area, they have a significantly smaller decoding latency.
We present an LLR-based implementation of the successive cancellation list (SCL) decoder. To this end, we associate each decoding path with a metric which (i) is a monotone function of the path's likelihood and (ii) can be computed efficiently from the channel LLRs. The LLR-based formulation leads to a more efficient hardware implementation of the decoder compared to the known log-likelihood based implementation. Synthesis results for an SCL decoder with block-length of N = 1024 and list sizes of L = 2 and L = 4 confirm that the LLR-based decoder has considerable area and operating frequency advantages in the orders of 50% and 30%, respectively.
Successive cancellation list (SCL) decoding algorithm is a powerful method that can help polar codes achieve excellent error-correcting performance. However, the current SCL algorithm and decoders are based on likelihood or log-likelihood forms, which render high hardware complexity. In this paper, we propose a log-likelihood-ratio (LLR)-based SCL (LLR-SCL) decoding algorithm, which only needs half the computation and storage complexity than the conventional one. Then, based on the proposed algorithm, we develop low-complexity VLSI architectures for LLR-SCL decoders. Analysis results show that the proposed LLR-SCL decoder achieves 50% reduction in hardware and 98% improvement in hardware efficiency.
Recently convolutional polar (cpolar) codes have been proposed. A tensor-network-based successive cancellation (SC) decoding was proposed for them under which cpolar codes were shown to outperform polar codes. In this paper we present the notion of m-bit-channels for cpolar codes and give the recursive construction of m-bit-channels for m=3. Then a log likelihood ratio(LLR)-based SC decoding of complexity order O(Nlog(N)) for cpolar codes is presented. We also present the numerical results for performance evaluation of cpolar codes under SC list (SCL) decoding. Our simulation results show that cpolar codes can achieve the performance of polar codes with a list size reduced by a factor of 4.
Although the adaptive successive cancellation list (AD-SCL) algorithm and the segmented-CRC adaptive successive cancellation list (SCAD-SCL) algorithm based on the cyclic redundancy check (CRC) can greatly reduce the computational complexity of the successive cancellation list (SCL) algorithm, these two algorithms discard the previous decoding result and re-decode by increasing L, where L is the size of list. When CRC fails, these two algorithms waste useful information from the previous decoding. In this paper, a simplified adaptive successive cancellation list (SAD-SCL) is proposed. Before the re-decoding of updating value L each time, SAD-SCL uses the existing log likelihood ratio (LLR) information to locate the range of burst error bits, and then re-decoding starts at the incorrect bit with the smallest index in this range. Moreover, when the segmented information sequence cannot get the correct result of decoding, the SAD-SCL algorithm uses SC decoding to complete the decoding of the subsequent segmentation information sequence. Furthermore, its decoding performance is almost the same as that of the subsequent segmentation information sequence using the AD-SCL algorithm. The simulation results show that the SAD-SCL algorithm has lower computational complexity than AD-SCL and SCAD-SCL with negligible loss of performance.
This paper proposes a novel iterative decoder based on concatenated belief propagation (BP) for CRC-aided polar codes. Compared to the conventional BP-based decoders for polar codes, soft cancellation (SCAN) decoder can generate a log likelihood ratio (LLR) of coded bit with lower computational complexity without sacrificing the detection capability. Unfortunately, its performance is not as good as that of CRC-aided successive cancellation list decoder (SCLD) although SCAN decoder has advantage of hardware implementation. To compensate the performance gap, we exploit CRC structure for not only error detection but also error correction with the assistance of its error correction capability at a short code length by exchanging LLRs between SCAN decoder and BP decoder on the basis of CRC. Moreover, the sub-optimal criterion for selecting a parity check matrix of CRC for BP decoder is proposed. Finally, computer simulations are conducted to confirm the validity of our proposed method. The proposed method can obtain the gain of about 0.6 dB at BER=10-3compared to the native SCAN decoder without requiring huge memory size as in SCLD.
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.