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

Evaluate PAC codes via Efficient Estimation on Weight Distribution

Junhua You, Shaohua Wu, Yajing Deng, Qinyu Zhang

Published Oct 12, 2023• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2310.08226

Related papers

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

Approximate Weight Distribution of Polarization-Adjusted Convolutional (PAC) Codes

Sadra Seyedmasoumian, Tolga M. Duman

Polarization-adjusted convolutional (PAC) codes combine polar and convolutional transformations to enhance the distance properties of polar codes. They offer a performance very close to the finite-length information-theoretic bounds for short blocklengths. In this paper, we develop a method of computing the weight distribution of PAC codes in an approximate form by employing a probabilistic technique. We demonstrate that the results well match the exact weight distributions for small codes that can be computed using a brute-force algorithm. We also present a way of employing the results (along with a union bound on the code performance) to design specific PAC codes or, more precisely, to determine suitable rate profiles via simulated annealing. Numerical examples illustrate that the PAC codes with the designed rate profiles offer superior performance.

arXiv:2202.12885•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•15 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•26 citations

On Convolutional Precoding in PAC Codes

Mohammad Rowshan, Emanuele Viterbo

In polarization-adjusted convolutional (PAC) codes, a convolutional transform is employed as a precoding stage before the polar transform. It turned out that the precoding stage improves the weight distribution of polar codes according. That could be the main reason for the superiority of error correction performance of PAC codes relative to polar codes. In this work, we explicitly show why the convolutional precoding reduces the number of minimum-weight codewords. Furthermore, we show where the precoding stage is not effective in the improvement of weight distribution. Eventually, to evaluate the FER gain obtainable from reducing the number of min-weight codewords, we assess the performance and the number of minimum-weight codewords resulted from an irregular convolutional precoding process.

arXiv:2103.12483•IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•26 citations

An SC-Fano Based Enumerator of Low-Weight Codewords for Polar/PAC Codes

Xingyu Zhou, Shaohua Wu, Junhua You +2 more

The maximum likelihood (ML) decoding performance of linear codes is strongly influenced by the weight distribution, especially the number of low-weight codewords. In this work, we propose a successive cancellation (SC) code weight analyzer for polar codes and polarization-adjusted convolutional (PAC) codes. By feeding raw BPSK codewords into the SC analyzer under a noiseless channel, the SC metrics are shown to effectively characterize the weight of codewords. This insight motivates a bit-flipping strategy for efficient enumeration of lowweight codewords. Furthermore, we present an SC-Fano based enumerator that accurately accounts the low-weight codewords of polar codes and PAC codes without restrictions on rateprofiling. The results demonstrate that the proposed enumerator significantly reduces computation time for short to moderate block lengths compared to state-of-the-art methods.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 23, 2025•0 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
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.
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.
Polarization-adjusted convolutional (PAC) codes combine polar and convolutional transformations to enhance the distance properties of polar codes. They offer a performance very close to the finite-length information-theoretic bounds for short blocklengths. In this paper, we develop a method of computing the weight distribution of PAC codes in an approximate form by employing a probabilistic technique. We demonstrate that the results well match the exact weight distributions for small codes that can be computed using a brute-force algorithm. We also present a way of employing the results (along with a union bound on the code performance) to design specific PAC codes or, more precisely, to determine suitable rate profiles via simulated annealing. Numerical examples illustrate that the PAC codes with the designed rate profiles offer superior performance.
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 polarization-adjusted convolutional (PAC) codes, a convolutional transform is employed as a precoding stage before the polar transform. It turned out that the precoding stage improves the weight distribution of polar codes according. That could be the main reason for the superiority of error correction performance of PAC codes relative to polar codes. In this work, we explicitly show why the convolutional precoding reduces the number of minimum-weight codewords. Furthermore, we show where the precoding stage is not effective in the improvement of weight distribution. Eventually, to evaluate the FER gain obtainable from reducing the number of min-weight codewords, we assess the performance and the number of minimum-weight codewords resulted from an irregular convolutional precoding process.
The maximum likelihood (ML) decoding performance of linear codes is strongly influenced by the weight distribution, especially the number of low-weight codewords. In this work, we propose a successive cancellation (SC) code weight analyzer for polar codes and polarization-adjusted convolutional (PAC) codes. By feeding raw BPSK codewords into the SC analyzer under a noiseless channel, the SC metrics are shown to effectively characterize the weight of codewords. This insight motivates a bit-flipping strategy for efficient enumeration of lowweight codewords. Furthermore, we present an SC-Fano based enumerator that accurately accounts the low-weight codewords of polar codes and PAC codes without restrictions on rateprofiling. The results demonstrate that the proposed enumerator significantly reduces computation time for short to moderate block lengths compared to state-of-the-art methods.
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.