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

International Workshop on Signal Design and its Applications in Communications

Bit-Flipping for Stack Decoding of Polarization-Adjusted Convolutional (PAC) Codes

Mohsen Moradi

Published Aug 1, 2022• 5 citations
Publisher

Abstract

While sequential decoding of polarization-adjusted convolutional (PAC) codes constructed using polar rate profile has low computational complexity, their error-correction per-formance falls far short of the theoretical bounds for finite blocklength codes. In this paper, we use the bit-flipping technique in the stack decoding algorithm of PAC codes in order to improve their error-correction performance. This technique maintains the low memory requirements of stack decoding and polar demapper. Additionally, at high SNR values, the number of visits at each level of the decoding tree is almost one. Numerical findings indicate that this approach is capable of outperforming the stack decoding algorithm.

DOI
10.1109/iwsda50346.2022.9870580

Related papers

Efficient Low-Memory Fast Stack Decoding with Variance Polarization for PAC Codes

Mohsen Moradi, Hessam Mahdavifar

Polarization-adjusted convolutional (PAC) codes have recently emerged as a promising class of error-correcting codes, achieving near-capacity performance particularly in the short block-length regime. In this paper, we propose an enhanced stack decoding algorithm for PAC codes that significantly improves parallelization by exploiting specialized bit nodes, such as rate-0 and rate-1 nodes. For a rate-1 node withN0leaf nodes in its corresponding subtree, conventional stack decoding must either explore all 2N0paths, or, same as in fast list decoding, restrict attention to a constant number of candidate paths. In contrast, our approach introduces a pruning technique that removes candidate paths with small path metrics while ensuring that the probability of pruning the correct path decays exponentially with the threshold. Furthermore, we propose a novel approximation method for estimating variance polarization under the binary-input additive white Gaussian noise (BI-AWGN) channel. Leveraging these approximations, we develop an efficient stack-pruning strategy that selectively preserves decoding paths whose bit-metric values align with their expected means. This targeted pruning substantially reduces the number of active paths in the stack, thereby decreasing both decoding latency and computational complexity. Numerical results demonstrate that for a PAC(128, 64) code, our method achieves up to a 70% reduction in the average number of paths without degrading error-correction performance.

IEEE Open Journal of the Communications Society•Jan 1, 2026•0 citations

Application of Guessing to Sequential Decoding of Polarization-Adjusted Convolutional (PAC) Codes

Mohsen Moradi

Despite the extreme error-correction performance, the amount of computation of sequential decoding of the polarization-adjusted convolutional (PAC) codes is random. In sequential decoding of convolutional codes, the cutoff rate denotes the region between rates whose average computational complexity of decoding is finite and those which is infinite. In this paper, by benefiting from the polarization and guessing techniques, we prove that the required computation in sequential decoding of pre-transformed polar codes polarizes, and this polarization determines which set of bit positions within the rate profile may result in high computational complexity. Based on this, we propose a technique for taming the Reed-Muller (RM) rate-profile construction, and the performance results demonstrate that the error-correction performance of the PAC codes can achieve the theoretical bounds using the tamed-RM rate-profile construction and requires a significantly lower computational complexity than the RM rate-profile construction.

arXiv:2208.04010•IEEE Transactions on Communications•May 29, 2023•11 citations

Efficient Low-Memory Fast Stack Decoding with Variance Polarization for PAC Codes

Mohsen Moradi, Hessam Mahdavifar

Polarization-adjusted convolutional (PAC) codes have recently emerged as a promising class of error-correcting codes, achieving near-capacity performance particularly in the short block-length regime. In this paper, we propose an enhanced stack decoding algorithm for PAC codes that significantly improves parallelization by exploiting specialized bit nodes, such as rate-0 and rate-1 nodes. For a rate-1 node with $N_0$ leaf nodes in its corresponding subtree, conventional stack decoding must either explore all $2^{N_0}$ paths, or, same as in fast list decoding, restrict attention to a constant number of candidate paths. In contrast, our approach introduces a pruning technique that removes candidate paths with small path metrics while ensuring that the probability of pruning the correct path decays exponentially with the threshold. Furthermore, we propose a novel approximation method for estimating variance polarization under the binary-input additive white Gaussian noise (BI-AWGN) channel. Leveraging these approximations, we develop an efficient stack-pruning strategy that selectively preserves decoding paths whose bit-metric values align with their expected means. This targeted pruning substantially reduces the number of active paths in the stack, thereby decreasing both decoding latency and computational complexity. Numerical results demonstrate that for a PAC$(128,64)$ code, our method achieves up to a 70\% reduction in the average number of paths without degrading error-correction performance.

arXiv:2509.07231•Sep 8, 2025•0 citations

Multi-stack decoding Algorithm for Polarization-adjusted Convolutional Codes

Yuze Wu, Zhiliang Huang, Youyan Zhang +1 more

The Polar-Adjusted Convolutional (PAC) codes, improve the error correction ability of the polar code by concatenating convolutional transformation and polar transformation. For the traditional stack decoding algorithm, the ideal performance has not yet been achieved for some PAC codes. In this paper, we adopt a multi-stack decoding algorithm to further improve the error performance of PAC codes. In the multi-stack decoding algorithm, the original single stack is converted into multiple stacks, which expands the exploration path of decoding, obtains more possible decoding results, and improves the decoding performance of PAC codes. Compared to the single-stack decoding, the multi-stack decoding achieves a performance gain of approximately 0.2dB for a PAC code with code length 128 and rate 0.5.

International Conference on Electronic Information Engineering and Computer Science (EIECS)•Sep 22, 2023•1 citation

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

Complexity-efficient Fano Decoding of Polarization-adjusted Convolutional (PAC) Codes

Mohammad Rowshan, Andreas Peter Burg, Emanuele Viterbo

Polarization-adjusted convolutional (PAC) codes are modified polar codes in which a one-to-one convolutional transformation is employed before the classical polar transform. Fano decoding of PAC codes in the Shannon lecture at ISIT2019 showed an outstanding performance at the cost of a high time-complexity, particularly at low SNR regimes. In order to reduce this complexity, an adaptive heuristic metric is proposed that improves the comparability of the variable-length paths and adjusts itself in response to the channel noise level. This metric can significantly reduce the number of nodes visited on average in tree-traversal. Additionally, a partial rewinding of the successive cancellation process is proposed to efficiently compute the intermediate LLRs and partial sums when backtracking occurs in the Fano algorithm. This method avoids storing the intermediate results of the decoding process or restarting (full rewinding) the decoding process.

International Symposium on Information Theory and its Applications•Oct 24, 2020•6 citations
While sequential decoding of polarization-adjusted convolutional (PAC) codes constructed using polar rate profile has low computational complexity, their error-correction per-formance falls far short of the theoretical bounds for finite blocklength codes. In this paper, we use the bit-flipping technique in the stack decoding algorithm of PAC codes in order to improve their error-correction performance. This technique maintains the low memory requirements of stack decoding and polar demapper. Additionally, at high SNR values, the number of visits at each level of the decoding tree is almost one. Numerical findings indicate that this approach is capable of outperforming the stack decoding algorithm.
Polarization-adjusted convolutional (PAC) codes have recently emerged as a promising class of error-correcting codes, achieving near-capacity performance particularly in the short block-length regime. In this paper, we propose an enhanced stack decoding algorithm for PAC codes that significantly improves parallelization by exploiting specialized bit nodes, such as rate-0 and rate-1 nodes. For a rate-1 node withN0leaf nodes in its corresponding subtree, conventional stack decoding must either explore all 2N0paths, or, same as in fast list decoding, restrict attention to a constant number of candidate paths. In contrast, our approach introduces a pruning technique that removes candidate paths with small path metrics while ensuring that the probability of pruning the correct path decays exponentially with the threshold. Furthermore, we propose a novel approximation method for estimating variance polarization under the binary-input additive white Gaussian noise (BI-AWGN) channel. Leveraging these approximations, we develop an efficient stack-pruning strategy that selectively preserves decoding paths whose bit-metric values align with their expected means. This targeted pruning substantially reduces the number of active paths in the stack, thereby decreasing both decoding latency and computational complexity. Numerical results demonstrate that for a PAC(128, 64) code, our method achieves up to a 70% reduction in the average number of paths without degrading error-correction performance.
Despite the extreme error-correction performance, the amount of computation of sequential decoding of the polarization-adjusted convolutional (PAC) codes is random. In sequential decoding of convolutional codes, the cutoff rate denotes the region between rates whose average computational complexity of decoding is finite and those which is infinite. In this paper, by benefiting from the polarization and guessing techniques, we prove that the required computation in sequential decoding of pre-transformed polar codes polarizes, and this polarization determines which set of bit positions within the rate profile may result in high computational complexity. Based on this, we propose a technique for taming the Reed-Muller (RM) rate-profile construction, and the performance results demonstrate that the error-correction performance of the PAC codes can achieve the theoretical bounds using the tamed-RM rate-profile construction and requires a significantly lower computational complexity than the RM rate-profile construction.
Polarization-adjusted convolutional (PAC) codes have recently emerged as a promising class of error-correcting codes, achieving near-capacity performance particularly in the short block-length regime. In this paper, we propose an enhanced stack decoding algorithm for PAC codes that significantly improves parallelization by exploiting specialized bit nodes, such as rate-0 and rate-1 nodes. For a rate-1 node with N0N_0N0​ leaf nodes in its corresponding subtree, conventional stack decoding must either explore all 2N02^{N_0}2N0​ paths, or, same as in fast list decoding, restrict attention to a constant number of candidate paths. In contrast, our approach introduces a pruning technique that removes candidate paths with small path metrics while ensuring that the probability of pruning the correct path decays exponentially with the threshold. Furthermore, we propose a novel approximation method for estimating variance polarization under the binary-input additive white Gaussian noise (BI-AWGN) channel. Leveraging these approximations, we develop an efficient stack-pruning strategy that selectively preserves decoding paths whose bit-metric values align with their expected means. This targeted pruning substantially reduces the number of active paths in the stack, thereby decreasing both decoding latency and computational complexity. Numerical results demonstrate that for a PAC(128,64)(128,64)(128,64) code, our method achieves up to a 70\% reduction in the average number of paths without degrading error-correction performance.
The Polar-Adjusted Convolutional (PAC) codes, improve the error correction ability of the polar code by concatenating convolutional transformation and polar transformation. For the traditional stack decoding algorithm, the ideal performance has not yet been achieved for some PAC codes. In this paper, we adopt a multi-stack decoding algorithm to further improve the error performance of PAC codes. In the multi-stack decoding algorithm, the original single stack is converted into multiple stacks, which expands the exploration path of decoding, obtains more possible decoding results, and improves the decoding performance of PAC codes. Compared to the single-stack decoding, the multi-stack decoding achieves a performance gain of approximately 0.2dB for a PAC code with code length 128 and rate 0.5.
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.
Polarization-adjusted convolutional (PAC) codes are modified polar codes in which a one-to-one convolutional transformation is employed before the classical polar transform. Fano decoding of PAC codes in the Shannon lecture at ISIT2019 showed an outstanding performance at the cost of a high time-complexity, particularly at low SNR regimes. In order to reduce this complexity, an adaptive heuristic metric is proposed that improves the comparability of the variable-length paths and adjusts itself in response to the channel noise level. This metric can significantly reduce the number of nodes visited on average in tree-traversal. Additionally, a partial rewinding of the successive cancellation process is proposed to efficiently compute the intermediate LLRs and partial sums when backtracking occurs in the Fano algorithm. This method avoids storing the intermediate results of the decoding process or restarting (full rewinding) the decoding process.