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:1706.05238 · IEEE International Symposium on Information Theory (ISIT)

Successive cancellation decoding of single parity-check product codes

Mustafa Cemil Coşkun, Gianluigi Liva, Alexandre Graell i Amat, Michael Lentmaier

Published Jun 1, 2017• 4 citations
arXivHTMLPDF

Abstract

We introduce successive cancellation (SC) decoding of product codes (PCs) with single parity-check (SPC) component codes. Recursive formulas are derived, which resemble the SC decoding algorithm of polar codes. We analyze the error probability of SPC-PCs over the binary erasure channel under SC decoding. A bridge with the analysis of PCs introduced by Elias in 1954 is also established. Furthermore, bounds on the block error probability under SC decoding are provided, and compared to the bounds under the original decoding algorithm proposed by Elias. It is shown that SC decoding of SPC-PCs achieves a lower block error probability than Elias' decoding.

DOI
10.1109/isit.2017.8006832

Related papers

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

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

A product code with single parity-check component codes can be seen as a special instance 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 the binary erasure channel under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, it is shown that successive cancellation list decoding outperforms belief propagation decoding performed on the code graph over the binary input additive white Gaussian channel. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis.

•Jan 1, 2018•0 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

On the Successive Cancellation Decoding of Polar Codes with Arbitrary Linear Binary Kernels

Zhiliang Huang, Zhang, Shiyi, Zhang, Feiyan +2 more

A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a $l$-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities $W_{G}^{(\cdot)}(\cdot|0)$ and $W_{G}^{(\cdot)}(\cdot|1)$ separately, a $W$-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a $m\times m$ binary kernel, the complexity of straightforward SC decoder is $O(2^{m}N\log N)$. With $W$-expressions, we reduce the complexity of straightforward SC decoder to $O(m^{2}N\log N)$ when $m\leq 16$. Simulation results show that $16\times16$ kernel polar codes offer significant advantages in terms of error performances compared with $2\times2$ kernel polar codes under SC and list SC decoders.

arXiv:1701.03264•Jan 12, 2017•9 citations

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

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

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.

arXiv:2211.12230•IEEE Access•Jan 1, 2023•5 citations

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

Symbol-Based Successive Cancellation List Decoder for Polar Codes

Chenrong Xiong, Jun Ting Lin, Zhiyuan Yan

Abstract—Polar codes is promising because they can provably achieve the channel capacity while having an explicit construc-tion method. Lots of work have been done for the bit-based decoding algorithm for polar codes. In this paper, generalized symbol-based successive cancellation (SC) and SC list decoding algorithms are discussed. A symbol-based recursive channel combination relationship is proposed to calculate the symbol-based channel transition probability. This proposed method needs less additions than the maximum-likelihood decoder used by the existing symbol-based polar decoding algorithm. In addition, a two-stage list pruning network is proposed to simplify the list pruning network for the symbol-based SC list decoding algorithm. Index Terms—Error control codes, polar codes, successive cancellation decoding, list decoding I.

•Aug 16, 2016•18 citations
We introduce successive cancellation (SC) decoding of product codes (PCs) with single parity-check (SPC) component codes. Recursive formulas are derived, which resemble the SC decoding algorithm of polar codes. We analyze the error probability of SPC-PCs over the binary erasure channel under SC decoding. A bridge with the analysis of PCs introduced by Elias in 1954 is also established. Furthermore, bounds on the block error probability under SC decoding are provided, and compared to the bounds under the original decoding algorithm proposed by Elias. It is shown that SC decoding of SPC-PCs achieves a lower block error probability than Elias' decoding.
A product code with single parity-check component codes can be seen as a special instance 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 the binary erasure channel under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, it is shown that successive cancellation list decoding outperforms belief propagation decoding performed on the code graph over the binary input additive white Gaussian channel. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis.
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.
A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a lll-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities WG(⋅)(⋅∣0)W_{G}^{(\cdot)}(\cdot|0)WG(⋅)​(⋅∣0) and WG(⋅)(⋅∣1)W_{G}^{(\cdot)}(\cdot|1)WG(⋅)​(⋅∣1) separately, a WWW-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a m×mm\times mm×m binary kernel, the complexity of straightforward SC decoder is O(2mNlog⁡N)O(2^{m}N\log N)O(2mNlogN). With WWW-expressions, we reduce the complexity of straightforward SC decoder to O(m2Nlog⁡N)O(m^{2}N\log N)O(m2NlogN) when m≤16m\leq 16m≤16. Simulation results show that 16×1616\times1616×16 kernel polar codes offer significant advantages in terms of error performances compared with 2×22\times22×2 kernel polar codes under SC and list SC decoders.
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.
Abstract—Polar codes is promising because they can provably achieve the channel capacity while having an explicit construc-tion method. Lots of work have been done for the bit-based decoding algorithm for polar codes. In this paper, generalized symbol-based successive cancellation (SC) and SC list decoding algorithms are discussed. A symbol-based recursive channel combination relationship is proposed to calculate the symbol-based channel transition probability. This proposed method needs less additions than the maximum-likelihood decoder used by the existing symbol-based polar decoding algorithm. In addition, a two-stage list pruning network is proposed to simplify the list pruning network for the symbol-based SC list decoding algorithm. Index Terms—Error control codes, polar codes, successive cancellation decoding, list decoding I.