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 Information Theory Workshop (ITW)

Fast Enumeration of Minimum Weight Codewords of PAC Codes

Mohammad Rowshan, Jinhong Yuan

Published Nov 1, 2022• 16 citations
Publisher

Abstract

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.

DOI
10.1109/itw54588.2022.9965901

Related papers

On the Minimum Weight Codewords of PAC Codes: The Impact of Pre-Transformation

Mohammad Rowshan, Jinhong Yuan

The minimum Hamming distance of a linear block code is the smallest number of bit changes required to transform one valid codeword into another. The code’s minimum distance determines the code’s error-correcting capabilities. Furthermore, The number of minimum weight codewords, a.k.a. error coefficient, gives a good comparative measure for the block error rate (BLER) of linear block codes with identical minimum distance, in particular at a high SNR regime under maximum likelihood (ML) decoding. A code with a smaller error coefficient would give a lower BLER. Unlike polar codes, a closed-form expression for the enumeration of the error coefficient of polarization-adjusted convolutional (PAC) codes is yet unknown. As PAC codes are convolutionally pre-transformed polar codes, we study the impact of pre-transformation on polar codes in terms of minimum Hamming distance and error coefficient by partitioning the codewords into cosets. We show that the minimum distance of PAC codes does not decrease; however, the pre-transformation may reduce the error coefficient depending on the choice of convolutional polynomial. We recognize the properties of the cosets where pre-transformation is ineffective in decreasing the error coefficient, giving a lower bound for the error coefficient. Then, we propose a low-complexity enumeration method that determines the number of minimum weight codewords of PAC codes relying on the error coefficient of polar codes. That is, given the error coefficient Awmin of polar codes, we determine the reduction X in the error coefficient due to convolutional pre-transformation in PAC coding and subtract it from the error coefficient of polar codes, Awmin - X. Furthermore, we numerically analyze the tightness of the lower bound and the impact of the choice of the convolutional polynomial on the error coefficient based on the sub-patterns in the polynomial’s coefficients. Eventually, we show how we can further reduce the error coefficient in the cosets.

IEEE Journal on Selected Areas in Information Theory•Jan 1, 2023•22 citations

Improved Convolutional Precoder for PAC Codes

Xinyi Gu, Mohammad Rowshan, Jinhong Yuan

Convolutional precoding in polarization-adjusted convolutional (PAC) codes, a recently introduced variant of polar codes, has demonstrated an effective reduction in the number of minimum weight codewords (a.k.a error coefficient) of polar codes. This reduction has the potential to significantly improve the error correction performance. From a codeword formation perspective in cosets, this reduction has a limitation in the PAC coding which depends on the rows of the generator matrix involved in the formation of codewords. To overcome this limitation, capitalizing on the understanding of the decomposition of minimum-weight codewords, this paper introduces a novel precoding scheme that strategically disrupts the formation of a majority of minimum-weight codewords. This scheme significantly enhances the error coefficient without compromising the minimum distance of the code. Through numerical analysis, we demonstrate a noteworthy reduction in error coefficients compared to PAC codes and polar codes, resulting in a remarkable improvement in the block error rate of short codes.

Globecom•Dec 4, 2023•6 citations

Reverse PAC Codes: Look-Ahead List Decoding

Xinyi Gu, Mohammad Rowshan, Jinhong Yuan

Convolutional precoding in polarization-adjusted convolutional (PAC) codes is a recently introduced variant of polar codes. It has demonstrated an effective reduction in the number of minimum weight codewords (a.k.a error coefficient) of polar codes. This reduction has the potential to significantly improve the error correction performance. From a codeword formation perspective, this reduction has limitations. Capitalizing on the understanding of the decomposition of minimum-weight codewords, this paper studies reverse precoding that can effectively reduce minimum-weight codewords more than in PAC codes. We propose a look-ahead list decoding for the reverse PAC codes, which has the same order of complexity as list decoding in PAC codes. Through numerical analysis, we demonstrate a notable reduction in error coefficients compared to PAC codes and polar codes, resulting in a remarkable improvement in the block error rate, in particular at high code rates.

arXiv:2406.01903•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•7 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

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
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 minimum Hamming distance of a linear block code is the smallest number of bit changes required to transform one valid codeword into another. The code’s minimum distance determines the code’s error-correcting capabilities. Furthermore, The number of minimum weight codewords, a.k.a. error coefficient, gives a good comparative measure for the block error rate (BLER) of linear block codes with identical minimum distance, in particular at a high SNR regime under maximum likelihood (ML) decoding. A code with a smaller error coefficient would give a lower BLER. Unlike polar codes, a closed-form expression for the enumeration of the error coefficient of polarization-adjusted convolutional (PAC) codes is yet unknown. As PAC codes are convolutionally pre-transformed polar codes, we study the impact of pre-transformation on polar codes in terms of minimum Hamming distance and error coefficient by partitioning the codewords into cosets. We show that the minimum distance of PAC codes does not decrease; however, the pre-transformation may reduce the error coefficient depending on the choice of convolutional polynomial. We recognize the properties of the cosets where pre-transformation is ineffective in decreasing the error coefficient, giving a lower bound for the error coefficient. Then, we propose a low-complexity enumeration method that determines the number of minimum weight codewords of PAC codes relying on the error coefficient of polar codes. That is, given the error coefficient Awmin of polar codes, we determine the reduction X in the error coefficient due to convolutional pre-transformation in PAC coding and subtract it from the error coefficient of polar codes, Awmin - X. Furthermore, we numerically analyze the tightness of the lower bound and the impact of the choice of the convolutional polynomial on the error coefficient based on the sub-patterns in the polynomial’s coefficients. Eventually, we show how we can further reduce the error coefficient in the cosets.
Convolutional precoding in polarization-adjusted convolutional (PAC) codes, a recently introduced variant of polar codes, has demonstrated an effective reduction in the number of minimum weight codewords (a.k.a error coefficient) of polar codes. This reduction has the potential to significantly improve the error correction performance. From a codeword formation perspective in cosets, this reduction has a limitation in the PAC coding which depends on the rows of the generator matrix involved in the formation of codewords. To overcome this limitation, capitalizing on the understanding of the decomposition of minimum-weight codewords, this paper introduces a novel precoding scheme that strategically disrupts the formation of a majority of minimum-weight codewords. This scheme significantly enhances the error coefficient without compromising the minimum distance of the code. Through numerical analysis, we demonstrate a noteworthy reduction in error coefficients compared to PAC codes and polar codes, resulting in a remarkable improvement in the block error rate of short codes.
Convolutional precoding in polarization-adjusted convolutional (PAC) codes is a recently introduced variant of polar codes. It has demonstrated an effective reduction in the number of minimum weight codewords (a.k.a error coefficient) of polar codes. This reduction has the potential to significantly improve the error correction performance. From a codeword formation perspective, this reduction has limitations. Capitalizing on the understanding of the decomposition of minimum-weight codewords, this paper studies reverse precoding that can effectively reduce minimum-weight codewords more than in PAC codes. We propose a look-ahead list decoding for the reverse PAC codes, which has the same order of complexity as list decoding in PAC codes. Through numerical analysis, we demonstrate a notable reduction in error coefficients compared to PAC codes and polar codes, resulting in a remarkable improvement in the block error rate, in particular at high code rates.
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.
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.