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:2305.02921

On the Closed-form Weight Enumeration of Polar Codes: 1.5ddd-weight Codewords

Mohammad Rowshan, Vlad Drăgoi, Jinhong Yuan

Published May 4, 2023• 4 citations
arXivHTMLPDF

Abstract

The weight distribution of error correction codes is a critical determinant of their error-correcting performance, making enumeration of utmost importance. In the case of polar codes, the minimum weight $\wm$ (which is equal to minimum distance $d$) 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.5\wm$. Our simulations demonstrate the potential for extending this method to higher weights.

DOI
10.48550/arxiv.2305.02921

Related papers

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

On the Weight Distribution of Weights Less than $2w_{\min}$ in Polar Codes

Zicheng Ye, Yuan Li, Huazi Zhang +3 more

The number of low-weight codewords is critical to the performance of error-correcting codes. In 1970, Kasami and Tokura characterized the codewords of Reed-Muller (RM) codes whose weights are less than $2w_{\min}$, where $w_{\min}$ represents the minimum weight. In this paper, we extend their results to decreasing polar codes. We present the closed-form expressions for the number of codewords in decreasing polar codes with weights less than $2w_{\min}$. Moreover, the proposed enumeration algorithm runs in polynomial time with respect to the code length.

arXiv:2308.10024•Aug 19, 2023•0 citations

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

On the Distribution of Weights Less Than 2w minin Polar Codes

Zicheng Ye, Yuan Li, Huazi Zhang +3 more

The number of low-weight codewords is critical to the performance of error-correcting codes. In 1970, Kasami and Tokura characterized the codewords of Reed-Muller (RM) codes whose weights are less than 2wmin, wherewminrepresents the minimum weight. In this paper, we extend their results to decreasing polar codes. We present the closed-form expressions for the number of codewords in decreasing polar codes with weights less than 2wmin. Moreover, the proposed enumeration algorithm runs in polynomial time with respect to the code length.

IEEE Transactions on Communications•May 7, 2024•11 citations

Fast Enumeration of Minimum Weight Codewords of PAC Codes

Mohammad Rowshan, Jinhong Yuan

The number of minimum weight codewords, a.k.a error coefficient, is a good comparative measure for the block error rate (BLER) of a linear block code, in particular in a high SNR regime. The smaller the error coefficient, the lower the BLER. Unlike polar codes, the error coefficient of polarization-adjusted convolutional (PAC) codes cannot be determined easily due to the precoding stage. In this work, we propose an enumeration method that considers the impact of convolutional precoding on the minimum weight codewords of polar codes. This relative enumeration method simplifies the process significantly compared with conventional methods as the complexity analysis shows.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•16 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•24 citations
The weight distribution of error correction codes is a critical determinant of their error-correcting performance, making enumeration of utmost importance. In the case of polar codes, the minimum weight \wm\wm\wm (which is equal to minimum distance ddd) 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.5\wm1.5\wm1.5\wm. Our simulations demonstrate the potential for extending this method to higher weights.
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.
On the Weight Distribution of Weights Less than 2wmin⁡2w_{\min}2wmin​ in Polar Codes
The number of low-weight codewords is critical to the performance of error-correcting codes. In 1970, Kasami and Tokura characterized the codewords of Reed-Muller (RM) codes whose weights are less than 2wmin⁡2w_{\min}2wmin​, where wmin⁡w_{\min}wmin​ represents the minimum weight. In this paper, we extend their results to decreasing polar codes. We present the closed-form expressions for the number of codewords in decreasing polar codes with weights less than 2wmin⁡2w_{\min}2wmin​. Moreover, the proposed enumeration algorithm runs in polynomial time with respect to the code length.
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.
The number of low-weight codewords is critical to the performance of error-correcting codes. In 1970, Kasami and Tokura characterized the codewords of Reed-Muller (RM) codes whose weights are less than 2wmin, wherewminrepresents the minimum weight. In this paper, we extend their results to decreasing polar codes. We present the closed-form expressions for the number of codewords in decreasing polar codes with weights less than 2wmin. Moreover, the proposed enumeration algorithm runs in polynomial time with respect to the code length.
The number of minimum weight codewords, a.k.a error coefficient, is a good comparative measure for the block error rate (BLER) of a linear block code, in particular in a high SNR regime. The smaller the error coefficient, the lower the BLER. Unlike polar codes, the error coefficient of polarization-adjusted convolutional (PAC) codes cannot be determined easily due to the precoding stage. In this work, we propose an enumeration method that considers the impact of convolutional precoding on the minimum weight codewords of polar codes. This relative enumeration method simplifies the process significantly compared with conventional methods as the complexity analysis shows.
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.