Fast Polar Decoding With Successive Cancellation List Creeper Algorithm

IEEE Access. 2024. Vol. 12. P. 86639–86648.

Timokhin I., Ivanov F.

Polar codes have emerged as a focal point in the field of error-correcting codes, owing to their remarkable capacity-achieving characteristics and their relevance in various modern communication systems. The basic successive cancellation (SC) approach is not optimal to use in terms of the trade-off between performance and decoding complexity. SC-Creeper algorithm performs better with about the same low complexity as the SC version of the algorithm. However, the SC-Creeper algorithm did not have the ability to use the candidate list as a measure to improve performance and refine the search for the true codeword. To compare with successive cancellation list (SCL) approach and the ability to use more computing memory, the SCL-Creeper method was developed, using two additional lists. This method can also be used as a development of Fano algorithms for polar codes (mainly, Fano decoding in polar decoding does not use lists). This paper addresses the challenge of computational complexity in polar code decoding by integrating a list structure with the SC-Creeper algorithm. Building on prior research that introduced the concept of SC-Creeper, the study focuses on enhancing error correction performance while mitigating computational burden. The first chapters describe the polar encoding process and basic decoding technologies, then discuss the basic Creeper algorithm. In the following chapters, the authors describe a modified version of the two-list Creeper approach (that is, the SCL-Creeper version of the algorithm). Extensive simulations and numerical analysis presented in the paper underscore the tangible advantages of this novel decoding strategy. Leveraging the basic list algorithm, renowned for its superior error correction capabilities, the research explores the integration of Creeper to systematically prune unnecessary decoding paths. The resulting SCL-Creeper hybrid approach aims to strike a balance between error correction efficiency and computational complexity. Finally, the optimal selection of parameters for the SCL-Creeper approach and future directions in the research of the list version of the fast Creeper algorithm are discussed.

Keywords: decoding algorithm, polar codes, полярный код, быстрое декодирование

Publication based on the results of: Development of lightweight post-quantum cryptographic systems based on energy-efficient, low-complexity algorithms for decoding polar codes and low-density parity-check codes (2024)