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.
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.
In the Shannon Lecture at the 2019 International Symposium on Information Theory (ISIT), Professor Arikan proposed a new coding scheme called polarization-adjusted convolutional (PAC) codes. These codes exhibit excellent error-correction performance for short-to-medium block lengths. Currently, the mainstream decoding algorithms for PAC codes mainly include sequential decoding and list decoding. Fano decoding, a type of sequential decoding, offers good error-correction performance; however, its time complexity is relatively high due to the presence of extensive backtracking processes. In this paper, a fast Fano decoding algorithm based on backtracking optimization mechanism for PAC codes is proposed. The improved algorithm we put forward mitigate the time complexity of the decoding process from two aspects: path backtracking and threshold updating strategy. It enhances the error-correcting performance of the Fano decoding algorithm by introducing the first error node metric and the second error node metric. With the efforts in the above aspects, our decoding algorithm achieves good performance in both complexity and error-correction capability.
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.
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 N0 leaf nodes in its corresponding subtree, conventional stack decoding must either explore all 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) code, our method achieves up to a 70\% reduction in the average number of paths without degrading error-correction performance.
The decoding complexity of polarization-adjusted convolutional (PAC) codes and Polar codes is significantly affected by the efficiency of partial-sum updates. In this letter, we propose a fast partial-sum update method for the successive-cancellation decoding (SCD) of PAC and Polar codes by exploiting the Pascal-triangle structure of the Polar generator matrix. Simulation results show that the proposed method reduces the number of partial-sum updates compared with conventional SCD, particularly for short code lengths and in the low-rate regime. Compared with representative fast decoding methods, the proposed method also shows a complexity advantage in the low-rate regime.
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.
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.