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 Communications

Computing the Partial Weight Distribution of Punctured, Shortened, Precoded Polar Codes

Vera Miloslavskaya, Branka S. Vucetic, Yonghui Li

Published Sep 12, 2022• 18 citations
Publisher

Abstract

The problem of computing the Hamming weight distribution of linear codes is considered in this paper. A novel method to enumerate all codewords up to a certain Hamming weight for binary linear block codes in general and in particular for the punctured, shortened, precoded polar codes is introduced. The proposed approach performs a recursive decomposition of the codes using construction X4 that is typically used to combine codes of different lengths. This allows to enumerate the low-weight codewords of the overall code as combinations of the low-weight codewords of the component codes. Numerical results show that the proposed approach can efficiently compute the exact partial weight distribution of the 5G New Radio punctured/shortened polar codes with CRC11 and pure polar codes. In the former and latter cases, the low-weight codeword number is up to 106 and 108, respectively. Besides, randomly punctured and shortened polar codes and randomly precoded polar codes are also considered. To the best of the authors’ knowledge, this is the first method able to solve these problems.

DOI
10.1109/tcomm.2022.3205967

Related papers

Computing the Low-Weight codewords of Punctured and Shortened Pre-Transformed Polar Codes

Malek Ellouze, Romain Tajan, Camille Leroux +2 more

In this paper, we present a deterministic algorithm to count the low-weight codewords of punctured and shortened pure and pre-transformed polar codes. The method first evaluates the weight properties of punctured/shortened polar cosets. Then, a method that discards the cosets that have no impact on the computation of the low-weight codewords is introduced. A key advantage of this method is its applicability, regardless of the frozen bit set, puncturing/shortening pattern, or pre-transformation. Results confirm the method’s efficiency while showing reduced computational complexity compared to state-of-the-art algorithms.

arXiv:2411.05433•International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•1 citation

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

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

MacWilliams Identities for Probabilistic Weight Distribution of Polar Codes

Fengyi Cheng, Aijun Liu, Biao Cai +1 more

The problem of estimating the probabilistic Hamming weight distribution (HWD) is consider for polar codes. Two previous computationally recursive algorithm are reviewed and extended to the whole rate range. For low code rate, the imprecise assumption of previous works can be rectified by calculating HWD of the corresponding dual code. Based on MacWilliams Identities, the HWD of polar codes can be enumerated. By regarding as concatenation of two subcodes, the high rate one and low rate one, the HWD of medium code rate can be derived. The estimated result yields much accurate asymptotic performance bound.

International Conference on Information Science and Control Engineering•Dec 1, 2019•1 citation

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

On the Weight Spectrum of Rate-Compatible Polar Codes

Zicheng Ye, Yuan Li, Zhichao Liu +4 more

The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration into polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our discoveries provide an accurate approximation on the performance of rate-compatible polar codes.

arXiv:2410.19242•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation
The problem of computing the Hamming weight distribution of linear codes is considered in this paper. A novel method to enumerate all codewords up to a certain Hamming weight for binary linear block codes in general and in particular for the punctured, shortened, precoded polar codes is introduced. The proposed approach performs a recursive decomposition of the codes using construction X4 that is typically used to combine codes of different lengths. This allows to enumerate the low-weight codewords of the overall code as combinations of the low-weight codewords of the component codes. Numerical results show that the proposed approach can efficiently compute the exact partial weight distribution of the 5G New Radio punctured/shortened polar codes with CRC11 and pure polar codes. In the former and latter cases, the low-weight codeword number is up to 106 and 108, respectively. Besides, randomly punctured and shortened polar codes and randomly precoded polar codes are also considered. To the best of the authors’ knowledge, this is the first method able to solve these problems.
In this paper, we present a deterministic algorithm to count the low-weight codewords of punctured and shortened pure and pre-transformed polar codes. The method first evaluates the weight properties of punctured/shortened polar cosets. Then, a method that discards the cosets that have no impact on the computation of the low-weight codewords is introduced. A key advantage of this method is its applicability, regardless of the frozen bit set, puncturing/shortening pattern, or pre-transformation. Results confirm the method’s efficiency while showing reduced computational complexity compared to state-of-the-art algorithms.
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.
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.
The problem of estimating the probabilistic Hamming weight distribution (HWD) is consider for polar codes. Two previous computationally recursive algorithm are reviewed and extended to the whole rate range. For low code rate, the imprecise assumption of previous works can be rectified by calculating HWD of the corresponding dual code. Based on MacWilliams Identities, the HWD of polar codes can be enumerated. By regarding as concatenation of two subcodes, the high rate one and low rate one, the HWD of medium code rate can be derived. The estimated result yields much accurate asymptotic performance bound.
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.
The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration into polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our discoveries provide an accurate approximation on the performance of rate-compatible polar codes.