© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1404.1736 · IEEE Transactions on Communications

Faulty Successive Cancellation Decoding of Polar Codes for the Binary Erasure Channel

Alexios Balatsoukas‐Stimming, Andreas Peter Burg

Published Nov 8, 2017• 10 citations

Abstract

In this paper, the faulty successive cancellation decoding of polar codes for the binary erasure channel is studied. To this end, a simple erasure-based fault model is introduced to represent errors in the decoder, and it is shown that, under this model, polarization does not happen, meaning that fully reliable communication is not possible at any rate. Furthermore, a lower bound on the frame error rate of polar codes under faulty successive cancellation decoding is provided, which is then used, along with a well-known upper bound, in order to choose a blocklength that minimizes the erasure probability under faulty decoding. Finally, an unequal error protection scheme that can re-enable asymptotically erasure-free transmission at a small rate loss and by protecting only a constant fraction of the decoder is proposed. The same scheme is also shown to significantly improve the finite-length performance of the faulty successive cancellation decoder by protecting as little as 1.5% of the decoder.

DOI: 10.1109/tcomm.2017.2771243

Related papers

An empirical scaling law for polar codes

Satish Babu Korada, Andrea Montanari A, Emre Telatar +1 more

Using scaling laws, we obtain estimates of the block error probability of polar codes under successive cancellation decoding. For the binary erasure channel we present an upper and a lower bound for the scaling parameter. Numerically these two bounds match. We also present a scaling law for general binary discrete memoryless channels.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•62 citations

Universal Bounds on the Scaling Behavior of Polar Codes

Ali Goli, Hamed Hassani, Rudiger L. Urbanke

We consider the problem of determining the trade-off between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter $μ$ such that for any binary memoryless symmetric channel $W$ with capacity $I(W)$, reliable communication requires rates that satisfy $R< I(W)-αN^{-\frac{1}μ}$, where $α$ is a positive constant and $N$ is the block-length. We provide lower bounds on $μ$, namely $μ\geq 3.553$, and we conjecture that indeed $μ=3.627$, the parameter for the binary erasure channel.

arXiv:1205.2876•May 13, 2012•3 citations

Universal bounds on the scaling behavior of polar codes

Ali Goli, Hamed Hassani, Rudiger L. Urbanke

We consider the problem of determining the tradeoff between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter μ such that for any binary memoryless symmetric channel W with capacity I(W), reliable communication requires rates that satisfy R-1/μ, where α is a positive constant and N is the block-length. We provide lower bounds on μ, namely μ ≥ 3.553, and we conjecture that indeed μ = 3.627, the parameter for the binary erasure channel.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•29 citations

Robust decoding schemes for polar coding over compound channels

Mine Alsan, Vincent Y. F. Tan

We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•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

A lower bound on the probability of error of polar codes over BMS channels

Boaz Shuval, Ido Tal

Consider a polar code designed for some binary memoryless symmetric channel. We develop a lower bound on the probability of error of this polar code under successive-cancellation decoding. The bound exploits the correlation between the various codeword bits and improves upon existing lower bounds.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•7 citations

In this paper, the faulty successive cancellation decoding of polar codes for the binary erasure channel is studied. To this end, a simple erasure-based fault model is introduced to represent errors in the decoder, and it is shown that, under this model, polarization does not happen, meaning that fully reliable communication is not possible at any rate. Furthermore, a lower bound on the frame error rate of polar codes under faulty successive cancellation decoding is provided, which is then used, along with a well-known upper bound, in order to choose a blocklength that minimizes the erasure probability under faulty decoding. Finally, an unequal error protection scheme that can re-enable asymptotically erasure-free transmission at a small rate loss and by protecting only a constant fraction of the decoder is proposed. The same scheme is also shown to significantly improve the finite-length performance of the faulty successive cancellation decoder by protecting as little as 1.5% of the decoder.

We consider the problem of determining the trade-off between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter

μ

such that for any binary memoryless symmetric channel

W

with capacity

I(W)

, reliable communication requires rates that satisfy

R< I(W)-αN^{-\frac{1}μ}

, where

α

is a positive constant and

N

is the block-length. We provide lower bounds on

μ

, namely

μ\geq 3.553

, and we conjecture that indeed

μ=3.627

, the parameter for the binary erasure channel.

We consider the problem of determining the tradeoff between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter μ such that for any binary memoryless symmetric channel W with capacity I(W), reliable communication requires rates that satisfy R-1/μ, where α is a positive constant and N is the block-length. We provide lower bounds on μ, namely μ ≥ 3.553, and we conjecture that indeed μ = 3.627, the parameter for the binary erasure channel.

We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.

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.