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:1908.06652 · IEEE Transactions on Communications

Weight Distributions for Successive Cancellation Decoding of Polar Codes

Rina Polyanskaya, M. N. Davletshin, Nikita Polyanskii

Published Sep 1, 2020• 25 citations
arXivHTMLPDF

Abstract

In this paper, we derive the exact weight distributions that emerge during each stage of successive cancellation decoding of polar codes. Though we do not compute the distance spectrum of polar codes, the results allow us to get an estimate of the decoding error probability and to show a link between the first nonzero components of the weight distribution and the partial order between the synthetic channels. Also, we establish the minimal distance between two cosets associated with two paths that differ in two positions. This can be regarded as a first step toward analyzing the weight distributions for successive cancellation list decoding.

DOI
10.1109/tcomm.2020.3020959

Related papers

On Distance Properties of Convolutional Polar Codes

Ruslan Morozov, Peter Trifonov

A lower bound on the minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of the generalized cosets of the codes generated by the bottom rows of the polarizing matrix. Moreover, a construction of convolutional polar subcodes is proposed, which provides improved performance under successive cancellation list decoding. For sufficiently large list size, the decoding complexity of convolutional polar subcodes appears to be lower compared with Arikan polar subcodes with the same performance. The error probability of successive cancellation list decoding of convolutional polar subcodes is lower than that of Arikan polar subcodes with the same list size.

arXiv:1901.06341•IEEE Transactions on Communications•Apr 4, 2019•9 citations

A Deterministic Algorithm for Computing the Weight Distribution of Polar Codes

Hanwen Yao, Arman Fazeli, Alexander Vardy

We present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distributions that arise in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, we can compute the entire weight distribution of certain polar cosets in time$O(n^{2})$. Any polar code can be represented as a disjoint union of such cosets; moreover, this representation extends to polar codes with dynamically frozen bits. This implies that our methods can be also used to compute the weight distribution of polar codes with CRC precoding, of pol-arization-adjusted convolutional (PAC) codes and, in fact, general linear codes. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call the mixing factor. To reduce the exponential complexity of our algorithm, we make use of the fact that polar codes have a large automorphism group, which includes the lower-triangular affine group LTA$(m,2)$. We prove that LTA$(m,2)$acts transitively on certain subsets of polar codes, thereby drastically reducing the number of polar cosets we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of any polar code of length up to$n=128$.

arXiv:2102.07362•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•27 citations

A Deterministic Algorithm for Computing the Weight Distribution of Polar Code

Hanwen Yao, Arman Fazeli, Alexander Vardy

In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code lengthn, we can compute the weight distribution of anypolar cosetsin timeO(n2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call themixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at lengthn= 128.

IEEE Transactions on Information Theory•Feb 8, 2023•27 citations

Symbol-based successive cancellation list decoder for polar codes

Chenrong Xiong, Jun Lin, Zhiyuan Yan

Polar codes is promising because they can provably achieve the channel capacity while having an explicit construction 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.

arXiv:1405.4957•SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2014•20 citations

Scaling exponent of list decoders with applications to polar codes

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

Motivated by the significant performance gains which polar codes experience when they are decoded with successive cancellation list decoders, we study how the scaling exponent changes as a function of the list size L. In particular, we fix the block error probability Peand we analyze the tradeoff between the blocklength N and the back-off from capacity C-R using scaling laws. By means of a Divide and Intersect procedure, we provide a lower bound on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the blocklength grows large. We show that, although list decoding can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected. This result applies in particular to polar codes, since their minimum distance tends to infinity as N increases. Some considerations are also pointed out for the genie-aided successive cancellation decoder when transmission takes place over the binary erasure channel.

IEEE Information Theory Workshop (ITW)•Sep 1, 2013•16 citations

A geometric proof of the polarization property

Ilya I. Dumer

We analyze successive cancellation (SC) decoder by using two random functions. The first function is related to the likelihoods of 0 and 1 in each code position, while the second gives the difference between their posterior probabilities. We then study the second power moments of both functions. We show that these moments are being squared in channel transformations, while their product tends to 0 for growing lengths $n$. This gives an elementary proof of polarization properties of SC decoding. We also derive a simple ordering of decoding channels with construction complexity of order $n\log n$.

•Jun 21, 2017•0 citations
In this paper, we derive the exact weight distributions that emerge during each stage of successive cancellation decoding of polar codes. Though we do not compute the distance spectrum of polar codes, the results allow us to get an estimate of the decoding error probability and to show a link between the first nonzero components of the weight distribution and the partial order between the synthetic channels. Also, we establish the minimal distance between two cosets associated with two paths that differ in two positions. This can be regarded as a first step toward analyzing the weight distributions for successive cancellation list decoding.
A lower bound on the minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of the generalized cosets of the codes generated by the bottom rows of the polarizing matrix. Moreover, a construction of convolutional polar subcodes is proposed, which provides improved performance under successive cancellation list decoding. For sufficiently large list size, the decoding complexity of convolutional polar subcodes appears to be lower compared with Arikan polar subcodes with the same performance. The error probability of successive cancellation list decoding of convolutional polar subcodes is lower than that of Arikan polar subcodes with the same list size.
We present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distributions that arise in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, we can compute the entire weight distribution of certain polar cosets in timeO(n2)O(n^{2})O(n2). Any polar code can be represented as a disjoint union of such cosets; moreover, this representation extends to polar codes with dynamically frozen bits. This implies that our methods can be also used to compute the weight distribution of polar codes with CRC precoding, of pol-arization-adjusted convolutional (PAC) codes and, in fact, general linear codes. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call the mixing factor. To reduce the exponential complexity of our algorithm, we make use of the fact that polar codes have a large automorphism group, which includes the lower-triangular affine group LTA(m,2)(m,2)(m,2). We prove that LTA(m,2)(m,2)(m,2)acts transitively on certain subsets of polar codes, thereby drastically reducing the number of polar cosets we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of any polar code of length up ton=128n=128n=128.
In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code lengthn, we can compute the weight distribution of anypolar cosetsin timeO(n2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call themixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at lengthn= 128.
Polar codes is promising because they can provably achieve the channel capacity while having an explicit construction 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.
Motivated by the significant performance gains which polar codes experience when they are decoded with successive cancellation list decoders, we study how the scaling exponent changes as a function of the list size L. In particular, we fix the block error probability Peand we analyze the tradeoff between the blocklength N and the back-off from capacity C-R using scaling laws. By means of a Divide and Intersect procedure, we provide a lower bound on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the blocklength grows large. We show that, although list decoding can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected. This result applies in particular to polar codes, since their minimum distance tends to infinity as N increases. Some considerations are also pointed out for the genie-aided successive cancellation decoder when transmission takes place over the binary erasure channel.
We analyze successive cancellation (SC) decoder by using two random functions. The first function is related to the likelihoods of 0 and 1 in each code position, while the second gives the difference between their posterior probabilities. We then study the second power moments of both functions. We show that these moments are being squared in channel transformations, while their product tends to 0 for growing lengths nnn. This gives an elementary proof of polarization properties of SC decoding. We also derive a simple ordering of decoding channels with construction complexity of order nlog⁡nn\log nnlogn.