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:2406.01903 · IEEE International Symposium on Information Theory (ISIT)

Reverse PAC Codes: Look-Ahead List Decoding

Xinyi Gu, Mohammad Rowshan, Jinhong Yuan

Published Jul 7, 2024• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit57864.2024.10619652

Related papers

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

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

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 Novel SCL Bit-Flipping Decoding Of Polarization-Adjusted Convolutional (PAC) Codes

Zhang, Wei

Polar codes have attracted the attention of numerous researchers in the past decade due to their excellent performance. However, their performance at short block lengths under standard successive cancellation decoding is far from desirable. An effective method to improve the performance at short lengths is CRC precoding followed by successive-cancellation list decoding. Later, Arikan presented polarization-adjusted convolutional (PAC) codes, which further improve the performance of polar codes. In fact, bit-flipping is another post-processing method that can improve decoding performance. In this paper, we propose a novel SCL Bit-Flipping of PAC Codes. We show that better performance can be achieved using list decoding when the list size is the same for PAC codes (N=128, K=64). The decoding performance of our newly proposed PAC-SCLF with a list size of 32 is 0.3 dB better than that of the traditional PAC-SCL with a list size of 32. We set the maximum number of bit flips to 5. The performance of the list size (L=32) for PAC-SCLF is almost the same as the performance of the list size (L=128) for PAC-SCL.

arXiv:2307.05871•Jul 12, 2023•1 citation

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

On Tail-Biting Polarization-Adjusted Convolutional (TB-PAC) Codes and Small-Sizes List Decoding

Bowen Feng, Yi Yang, Jian Jiao +1 more

Polarization-adjusted convolutional (PAC) coding is a good concatenation of convolutional codes and polar codes. For short block-length codes ($N\leq 128$), PAC codes with a sequential decoding or a list decoding with large list-sizes ($L\geq 128$) can achieve better block-error-rate (BLER) performance than polar codes with CRC-aided list decoding. However, the PAC codes have no BLER performance advantage when the list decoding is with small list-sizes ($L\leq 8$). In this letter, tail-biting PAC (TB-PAC) coding is proposed, in which tail-biting convolutional pre-transformation is applied. A multi-round list decoding with small list-sizes is provided for TB-PAC codes, in which an early-stopping method is designed to control the number of rounds. In each round, the tail-biting bits are assigned various initial path-values and also used as a check at the end, which helps the correct path be distinguishable. The proposed small-sizes list decoding can help the TB-PAC codes achieve much better BLER performance than the polar/PAC codes.

IEEE Communications Letters•Nov 28, 2022•5 citations
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.
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.
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 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.
Polar codes have attracted the attention of numerous researchers in the past decade due to their excellent performance. However, their performance at short block lengths under standard successive cancellation decoding is far from desirable. An effective method to improve the performance at short lengths is CRC precoding followed by successive-cancellation list decoding. Later, Arikan presented polarization-adjusted convolutional (PAC) codes, which further improve the performance of polar codes. In fact, bit-flipping is another post-processing method that can improve decoding performance. In this paper, we propose a novel SCL Bit-Flipping of PAC Codes. We show that better performance can be achieved using list decoding when the list size is the same for PAC codes (N=128, K=64). The decoding performance of our newly proposed PAC-SCLF with a list size of 32 is 0.3 dB better than that of the traditional PAC-SCL with a list size of 32. We set the maximum number of bit flips to 5. The performance of the list size (L=32) for PAC-SCLF is almost the same as the performance of the list size (L=128) for PAC-SCL.
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.
Polarization-adjusted convolutional (PAC) coding is a good concatenation of convolutional codes and polar codes. For short block-length codes (N≤128N\leq 128N≤128), PAC codes with a sequential decoding or a list decoding with large list-sizes (L≥128L\geq 128L≥128) can achieve better block-error-rate (BLER) performance than polar codes with CRC-aided list decoding. However, the PAC codes have no BLER performance advantage when the list decoding is with small list-sizes (L≤8L\leq 8L≤8). In this letter, tail-biting PAC (TB-PAC) coding is proposed, in which tail-biting convolutional pre-transformation is applied. A multi-round list decoding with small list-sizes is provided for TB-PAC codes, in which an early-stopping method is designed to control the number of rounds. In each round, the tail-biting bits are assigned various initial path-values and also used as a check at the end, which helps the correct path be distinguishable. The proposed small-sizes list decoding can help the TB-PAC codes achieve much better BLER performance than the polar/PAC codes.