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• 5 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

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

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

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•6 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•5 citations

Successive Cancellation Ordered Search Decoding of Modified $\boldsymbol{G}_N$-Coset Codes

Peihong Yuan, Mustafa Cemil Coşkun

A tree search algorithm called successive cancellation ordered search (SCOS) is proposed for $\boldsymbol{G}_N$-coset codes that implements maximum-likelihood (ML) decoding with adaptive complexity for transmission over binary-input AWGN channels. Unlike bit-flip decoders, no outer code is needed to terminate decoding; therefore, SCOS also applies to $\boldsymbol{G}_N$-coset codes modified with dynamic frozen bits. The average complexity is close to that of successive cancellation (SC) decoding at practical frame error rates (FERs) for codes with wide ranges of rate and lengths up to $512$ bits, which perform within $0.25$ dB or less from the random coding union bound and outperform Reed--Muller codes under ML decoding by up to $0.5$ dB. Simulations illustrate simultaneous gains for SCOS over SC-Fano, SC stack (SCS) and SC list (SCL) decoding in FER and the average complexity at various SNR regimes. SCOS is further extended by forcing it to look for candidates satisfying a threshold, thereby outperforming basic SCOS under complexity constraints. The modified SCOS enables strong error-detection capability without the need for an outer code. In particular, the $(128, 64)$ polarization-adjusted convolutional code under modified SCOS provides gains in overall and undetected FER compared to CRC-aided polar codes under SCL/dynamic SC flip decoding at high SNR.

arXiv:2112.10735•Dec 20, 2021•0 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.
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.
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.
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.
Successive Cancellation Ordered Search Decoding of Modified GN\boldsymbol{G}_NGN​-Coset Codes
A tree search algorithm called successive cancellation ordered search (SCOS) is proposed for GN\boldsymbol{G}_NGN​-coset codes that implements maximum-likelihood (ML) decoding with adaptive complexity for transmission over binary-input AWGN channels. Unlike bit-flip decoders, no outer code is needed to terminate decoding; therefore, SCOS also applies to GN\boldsymbol{G}_NGN​-coset codes modified with dynamic frozen bits. The average complexity is close to that of successive cancellation (SC) decoding at practical frame error rates (FERs) for codes with wide ranges of rate and lengths up to 512512512 bits, which perform within 0.250.250.25 dB or less from the random coding union bound and outperform Reed--Muller codes under ML decoding by up to 0.50.50.5 dB. Simulations illustrate simultaneous gains for SCOS over SC-Fano, SC stack (SCS) and SC list (SCL) decoding in FER and the average complexity at various SNR regimes. SCOS is further extended by forcing it to look for candidates satisfying a threshold, thereby outperforming basic SCOS under complexity constraints. The modified SCOS enables strong error-detection capability without the need for an outer code. In particular, the (128,64)(128, 64)(128,64) polarization-adjusted convolutional code under modified SCOS provides gains in overall and undetected FER compared to CRC-aided polar codes under SCL/dynamic SC flip decoding at high SNR.