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:2411.05433 · International Symposium on Turbo Codes and Iterative Information Processing

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

Malek Ellouze, Romain Tajan, Camille Leroux, Christophe Jégo, Charly Poulliat

Published Aug 18, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1109/istc65386.2025.11154614

Related papers

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

Vera Miloslavskaya, Branka S. Vucetic, Yonghui Li

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.

IEEE Transactions on Communications•Sep 12, 2022•18 citations

Enumeration of Minimum Weight Codewords of Pre-Transformed Polar Codes by Tree Intersection

Andreas Zunker, Marvin Geiselhart, Stephan ten Brink

Pre-transformed polar codes (PTPCs) form a class of codes that perform close to the finite-length capacity bounds. The minimum distance and the number of minimum weight codewords are two decisive properties for their performance. In this work, we propose an efficient algorithm for determining the number of minimum weight codewords of general PTPCs that eliminates all redundant visits to nodes of the search tree, thus reducing the computational complexity typically by several orders of magnitude compared to state-of-the-art algorithms. This reduction in complexity allows, for the first time, the minimum distance properties to be directly considered in the code design of PTPCs. The algorithm is demonstrated for randomly pre-transformed Reed-Muller (RM) codes and polarization-adjusted convolutional (PAC) codes. Furthermore, we design optimal polynomials for PAC codes with this algorithm, minimizing the number of minimum weight codewords.

arXiv:2311.17774•Conference on Information Sciences and Systems•Mar 13, 2024•13 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

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

Evaluate PAC codes via Efficient Estimation on Weight Distribution

Junhua You, Shaohua Wu, Yajing Deng +1 more

In this letter, we introduce an efficient method for estimating weight distributions of polar codes and polarization-adjusted convolutional (PAC) codes. Based on a recursive algorithm of computing the weight enumerating functions of polar cosets, this method focuses on two key objectives: accurately determining the number of low-weight codewords and quickly approximating the distribution of high-weight codewords. Simulation results demonstrate that this hybrid method maintains competitively low complexity while effectively achieving the objectives.

arXiv:2310.08226•Oct 12, 2023•0 citations

A Parity-Consistent Decomposition Method for the Weight Distribution of Pre-Transformed Polar Codes

Yang Liu, Bolin Wu, Yuxin Han +1 more

This paper introduces an efficient algorithm based on the Parity-Consistent Decomposition (PCD) method to determine the WD of pre-transformed polar codes. First, to address the bit dependencies introduced by the pre-transformation matrix, we propose an iterative algorithm to construct an \emph{Expanded Information Set}. By expanding the information bits within this set into 0s and 1s, we eliminate the correlations among information bits, thereby enabling the recursive calculation of the Hamming weight distribution using the \emph{PCD method}. Second, to further reduce computational complexity, we establish the theory of equivalence classes for pre-transformed polar codes. Codes within the same equivalence class share an identical weight distribution but correspond to different \emph{Expanded Information Set} sizes. By selecting the pre-transformation matrix that minimizes the \emph{Expanded Information Set} size within an equivalence class, we optimize the computation process. Numerical results demonstrate that the proposed method significantly reduces computational complexity compared to existing deterministic algorithms.

arXiv:2601.07515•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations
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.
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.
Pre-transformed polar codes (PTPCs) form a class of codes that perform close to the finite-length capacity bounds. The minimum distance and the number of minimum weight codewords are two decisive properties for their performance. In this work, we propose an efficient algorithm for determining the number of minimum weight codewords of general PTPCs that eliminates all redundant visits to nodes of the search tree, thus reducing the computational complexity typically by several orders of magnitude compared to state-of-the-art algorithms. This reduction in complexity allows, for the first time, the minimum distance properties to be directly considered in the code design of PTPCs. The algorithm is demonstrated for randomly pre-transformed Reed-Muller (RM) codes and polarization-adjusted convolutional (PAC) codes. Furthermore, we design optimal polynomials for PAC codes with this algorithm, minimizing the number of minimum weight codewords.
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.
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 letter, we introduce an efficient method for estimating weight distributions of polar codes and polarization-adjusted convolutional (PAC) codes. Based on a recursive algorithm of computing the weight enumerating functions of polar cosets, this method focuses on two key objectives: accurately determining the number of low-weight codewords and quickly approximating the distribution of high-weight codewords. Simulation results demonstrate that this hybrid method maintains competitively low complexity while effectively achieving the objectives.
This paper introduces an efficient algorithm based on the Parity-Consistent Decomposition (PCD) method to determine the WD of pre-transformed polar codes. First, to address the bit dependencies introduced by the pre-transformation matrix, we propose an iterative algorithm to construct an \emph{Expanded Information Set}. By expanding the information bits within this set into 0s and 1s, we eliminate the correlations among information bits, thereby enabling the recursive calculation of the Hamming weight distribution using the \emph{PCD method}. Second, to further reduce computational complexity, we establish the theory of equivalence classes for pre-transformed polar codes. Codes within the same equivalence class share an identical weight distribution but correspond to different \emph{Expanded Information Set} sizes. By selecting the pre-transformation matrix that minimizes the \emph{Expanded Information Set} size within an equivalence class, we optimize the computation process. Numerical results demonstrate that the proposed method significantly reduces computational complexity compared to existing deterministic algorithms.