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

IEEE Transactions on Information Theory

A Deterministic Algorithm for Computing the Weight Distribution of Polar Code

Hanwen Yao, Arman Fazeli, Alexander Vardy

Published Feb 8, 2023• 24 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2023.3243191

Related papers

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•26 citations

A Parity-Consistent Decomposition Method to Determine the Weight Distribution of Polar Codes

Ying Liu, Bolin Wu, Yuxin Han +1 more

This paper introduces a novel parity-consistent decomposition (PCD) method for accurately determining the weight distribution (WD) of polar codes. In the PCD method, polar codes are represented as a union of a new type of polar cosets, characterized by the property that any two adjacent bits in the uncoded sequence are either both information bits or both frozen bits. This representation reduces the number of polar cosets compared to the existing automorphism-based (AUT) method. We introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD method is organized within a tree structure, which facilitates the evaluation of its computational complexity. We then investigate the transitivity of the action of lower triangular affine (LTA) transformations on a code set composed of the new polar cosets. This transitivity property enables a further reduction in the number of cosets that need to be computed. Furthermore, we propose a pruning algorithm to determine the partial weight distribution (PWD) of polar codes based on the tree structure of the PCD method. Given an upper bound on the Hamming weight for the PWD, we update the Hamming weight threshold for each code in the tree and remove the codes whose minimum Hamming weights exceed their corresponding thresholds. Numerical results demonstrate the superiority of the PCD method over existing methods.

IEEE Transactions on Communications•Jan 1, 2026•1 citation

Algebraic properties of polar codes from a new polynomial formalism

Magali Bardet, Vlad Drăgoi, Ayoub Otmani +1 more

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.

arXiv:1601.06215•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•155 citations

A Parity-Consistent Decomposition Algorithm to Determine the Weight Distribution of Polar Codes

Yang Liu, Bolin Wu, Yuxin Han +1 more

This paper introduces a novel parity-consistent decomposition (PCD) algorithm for accurately determining the weight distribution (WD) of polar codes. In the PCD algorithm, polar codes are represented as a union of a new type of polar cosets, which avoids fixing two adjacent information bits as 0 and 1. This representation reduces the number of polar cosets compared to the existing automorphism-based algorithm. Furthermore, we introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD algorithm is organized within a tree-like structure, which facilitates the evaluation of its computational complexity. Comparative analysis with the automorphism-based method demonstrates that the PCD algorithm significantly reduces computational complexity.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•3 citations

On the Closed-Form Weight Enumeration of Polar Codes: 1.5 d -Weight Codewords

Vlad Drăgoi, Mohammad Rowshan, Jinhong Yuan

The weight distribution of an error correction code is a critical determinant of its error-correcting performance. In the case of polar codes, the minimum weight wmin(equal to the minimum distanced) is the only weight for which an explicit enumerator formula is currently available. Having closed-form weight enumerators for polar codewords with weights greater than the minimum weight not only simplifies the enumeration process but also provides valuable insights towards constructing better polar-like codes. In this paper, we contribute towards understanding the algebraic structure underlying higher weights by analyzing Minkowski sums of orbits. Our approach builds upon the lower triangular affine (LTA) group of decreasing monomial codes. Specifically, we propose a closed-form expression for the enumeration of codewords with weight 1.5wmin. The key insight for code design is that the enumeration of codewords with weight wmin and 1.5wminrelies on the set of maximum degree monomials. This set corresponds to the indices of minimum weight rows of the polar transformGNbelonging to the information setI. Consequently, reducing the cardinality of this set can lead to a reduction of the number of codewords in both weight categories.

IEEE Transactions on Communications•May 6, 2024•18 citations

Improved Permutation-Based Successive Cancellation Decoding of Polar Codes

Mikhail Kamenev

Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.

International Siberian workshops and tutorials on electron devices and materials•Jun 30, 2021•8 citations
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.
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.
This paper introduces a novel parity-consistent decomposition (PCD) method for accurately determining the weight distribution (WD) of polar codes. In the PCD method, polar codes are represented as a union of a new type of polar cosets, characterized by the property that any two adjacent bits in the uncoded sequence are either both information bits or both frozen bits. This representation reduces the number of polar cosets compared to the existing automorphism-based (AUT) method. We introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD method is organized within a tree structure, which facilitates the evaluation of its computational complexity. We then investigate the transitivity of the action of lower triangular affine (LTA) transformations on a code set composed of the new polar cosets. This transitivity property enables a further reduction in the number of cosets that need to be computed. Furthermore, we propose a pruning algorithm to determine the partial weight distribution (PWD) of polar codes based on the tree structure of the PCD method. Given an upper bound on the Hamming weight for the PWD, we update the Hamming weight threshold for each code in the tree and remove the codes whose minimum Hamming weights exceed their corresponding thresholds. Numerical results demonstrate the superiority of the PCD method over existing methods.
Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.
This paper introduces a novel parity-consistent decomposition (PCD) algorithm for accurately determining the weight distribution (WD) of polar codes. In the PCD algorithm, polar codes are represented as a union of a new type of polar cosets, which avoids fixing two adjacent information bits as 0 and 1. This representation reduces the number of polar cosets compared to the existing automorphism-based algorithm. Furthermore, we introduce a recursive decomposition method for this new polar coset, which facilitates efficient recursive computation of the WD of polar codes. The PCD algorithm is organized within a tree-like structure, which facilitates the evaluation of its computational complexity. Comparative analysis with the automorphism-based method demonstrates that the PCD algorithm significantly reduces computational complexity.
The weight distribution of an error correction code is a critical determinant of its error-correcting performance. In the case of polar codes, the minimum weight wmin(equal to the minimum distanced) is the only weight for which an explicit enumerator formula is currently available. Having closed-form weight enumerators for polar codewords with weights greater than the minimum weight not only simplifies the enumeration process but also provides valuable insights towards constructing better polar-like codes. In this paper, we contribute towards understanding the algebraic structure underlying higher weights by analyzing Minkowski sums of orbits. Our approach builds upon the lower triangular affine (LTA) group of decreasing monomial codes. Specifically, we propose a closed-form expression for the enumeration of codewords with weight 1.5wmin. The key insight for code design is that the enumeration of codewords with weight wmin and 1.5wminrelies on the set of maximum degree monomials. This set corresponds to the indices of minimum weight rows of the polar transformGNbelonging to the information setI. Consequently, reducing the cardinality of this set can lead to a reduction of the number of codewords in both weight categories.
Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.