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

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.