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:2211.12230 · IEEE Access

Successive Cancellation Decoding With Future Constraints for Polar Codes Over the Binary Erasure Channel

Min Jang, Jong-Hwan Kim, Seho Myung, Kyeongcheol Yang

Published Jan 1, 2023• 7 citations
arXivHTMLPDF

Abstract

In the conventional successive cancellation (SC) decoder for polar codes, all the future bits to be estimated later are treated as random variables. However, polar codes inevitably involve frozen bits, and their concatenated coding schemes also include parity bits (or dynamic frozen bits) causally generated from the past bits estimated earlier. We refer to the frozen and parity bits located behind a target decoding bit as its future constraints (FCs). Although the values of FCs are deterministic given the past estimates, they have not been exploited in the conventional SC-based decoders, not leading to optimality. In this paper, with a primary focus on the binary erasure channel (BEC), we propose SC-check (SCC) and belief propagation SCC (BP-SCC) decoding algorithms in order to leverage FCs in decoding. We further devise an improved tree search technique based on stack-based backjumping (SBJ) to solve dynamic constraint satisfaction problems (CSPs) formulated by FCs. Over the BEC, numerical results show that a combination of the BP-SCC algorithm and the SBJ tree search technique achieves the erasure recovery performance close to the dependence testing (DT) bound, a bound of achievable finite-length performance.

DOI
10.1109/access.2023.3312577

Related papers

Decoding of Polar Codes with Future Constraints Over the Binary Erasure Channel

Min Jang, Jong-Hwan Kim, Seho Myung +1 more

We address the suboptimality of successive cancellation (SC) decoding for polar codes, which is caused by treating as random variables all the future bits to be estimated later. For a target information bit, we define the frozen and parity bits located behind it as its future constraints (FCs). To incorporate FCs into the sequential decoding of the target bit, we propose two elementary techniques: an SC check (SCC) algorithm and an FC conversion rule enabling belief propagation (BP). Focusing on the binary erasure channel (BEC), we also present a tree search technique based on stack-based backjumping (SBJ) to efficiently solve dynamic constraint satisfaction problems (CSP) formulated by FCs. Numerical results show that the combination of BP and SCC decoding algorithms accompanied with the SBJ technique achieves excellent erasure recovery performance over the BEC, which is close to the dependence testing (DT) achievability bound.

Globecom•Dec 4, 2023•0 citations

A Modified Successive-Cancellation Stack Polar Decoder

Li Chun, Xinhai Tong

Polar codes represent an emerging correcting codes with power to approach the capacity of a discrete memoryless channel.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.In this paper, a modified successive cancellation stack (MSCS) polar decoder is proposed.Unlike the original SC stack polar (SCS) decoders, we propose a modified path that can significantly reduce latency of SCS decoders.Simulation results in the binary-input additive white Gaussian noise channel show that modified algorithm has the slightly performance as the SCS algorithm.Moreover, the time and space complexity of the MSCS decoder is much lower than that of the SCS and can be very close to that of the SC in the high SNR regime.

Advances in computer science research•Jan 1, 2015•1 citation

Successive Cancellation Inactivation Decoding for Modified Reed-Muller and eBCH Codes

Mustafa Cemil Coşkun, Joachim Neu, Henry D. Pfister

A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes.

arXiv:2004.05969•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•19 citations

Insertion/Deletion/Substitution Error Correction by a Modified Successive Cancellation Decoding of Polar Code

Hikari Koremura, Haruhiko Kaneko

This paper presents a successive cancellation (SC) decoding of polar codes modified for insertion/deletion/substitution (IDS) error channels, in which insertions and deletions are described by drift values. The recursive calculation of the original SC decoding is modified to include the drift values as stochastic variables. The computational complexity of the modified SC decoding is O (D3) with respect to the maximum drift value D, and O (N log N) with respect to the code length N. The symmetric capacity of polar bit channel is estimated by computer simulations, and frozen bits are determined according to the estimated symmetric capacity. Simulation results show that the decoded error rate of polar code with the modified SC list decoding is lower than that of existing IDS error correction codes, such as marker-based code and spatially-coupled code.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 31, 2020•7 citations

Successive Cancellation Decoding of Single Parity-Check Product Codes: Analysis and Improved Decoding

Mustafa Cemil Coşkun, Gianluigi Liva, Alexandre Graell i Amat +2 more

A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within 0.7 dB from the random coding union bound are provided.

arXiv:2008.06938•IEEE Transactions on Information Theory•Sep 19, 2022•6 citations

Belief Propagation Bit-Flip Decoder for Polar Codes

Yongrun Yu, Zhiwen Pan, Nan Liu +1 more

The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.

IEEE Access•Jan 1, 2019•69 citations
In the conventional successive cancellation (SC) decoder for polar codes, all the future bits to be estimated later are treated as random variables. However, polar codes inevitably involve frozen bits, and their concatenated coding schemes also include parity bits (or dynamic frozen bits) causally generated from the past bits estimated earlier. We refer to the frozen and parity bits located behind a target decoding bit as its future constraints (FCs). Although the values of FCs are deterministic given the past estimates, they have not been exploited in the conventional SC-based decoders, not leading to optimality. In this paper, with a primary focus on the binary erasure channel (BEC), we propose SC-check (SCC) and belief propagation SCC (BP-SCC) decoding algorithms in order to leverage FCs in decoding. We further devise an improved tree search technique based on stack-based backjumping (SBJ) to solve dynamic constraint satisfaction problems (CSPs) formulated by FCs. Over the BEC, numerical results show that a combination of the BP-SCC algorithm and the SBJ tree search technique achieves the erasure recovery performance close to the dependence testing (DT) bound, a bound of achievable finite-length performance.
We address the suboptimality of successive cancellation (SC) decoding for polar codes, which is caused by treating as random variables all the future bits to be estimated later. For a target information bit, we define the frozen and parity bits located behind it as its future constraints (FCs). To incorporate FCs into the sequential decoding of the target bit, we propose two elementary techniques: an SC check (SCC) algorithm and an FC conversion rule enabling belief propagation (BP). Focusing on the binary erasure channel (BEC), we also present a tree search technique based on stack-based backjumping (SBJ) to efficiently solve dynamic constraint satisfaction problems (CSP) formulated by FCs. Numerical results show that the combination of BP and SCC decoding algorithms accompanied with the SBJ technique achieves excellent erasure recovery performance over the BEC, which is close to the dependence testing (DT) achievability bound.
Polar codes represent an emerging correcting codes with power to approach the capacity of a discrete memoryless channel.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.In this paper, a modified successive cancellation stack (MSCS) polar decoder is proposed.Unlike the original SC stack polar (SCS) decoders, we propose a modified path that can significantly reduce latency of SCS decoders.Simulation results in the binary-input additive white Gaussian noise channel show that modified algorithm has the slightly performance as the SCS algorithm.Moreover, the time and space complexity of the MSCS decoder is much lower than that of the SCS and can be very close to that of the SC in the high SNR regime.
A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes.
This paper presents a successive cancellation (SC) decoding of polar codes modified for insertion/deletion/substitution (IDS) error channels, in which insertions and deletions are described by drift values. The recursive calculation of the original SC decoding is modified to include the drift values as stochastic variables. The computational complexity of the modified SC decoding is O (D3) with respect to the maximum drift value D, and O (N log N) with respect to the code length N. The symmetric capacity of polar bit channel is estimated by computer simulations, and frozen bits are determined according to the estimated symmetric capacity. Simulation results show that the decoded error rate of polar code with the modified SC list decoding is lower than that of existing IDS error correction codes, such as marker-based code and spatially-coupled code.
A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within 0.7 dB from the random coding union bound are provided.
The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.