Decoding of Polar Codes with Finite Memory
Michael L. McGuire, Mihai Sima · 2023
This paper introduces a variation of the Successive Cancellation Stack (SCS) decoding algorithm for polar codes which is able to always return the transmitted data sequence with the highest probability of creating the received signal. The proposed algorithm uses a variation of the Simplified-Memory A Star algorithm to search for the transmitted binary sequence. This algorithm maintains a tree of all sub-sequences which are parents of the currently considered sequences. This tree allows the algorithm to delete sequences from memory while maintaining a record of which sequences it may need to reconsider later in the search. The algorithm is optimal in the sense that it is guaranteed to find the maximum probability sequence. Simulations demonstrate that the mean run-time of this algorithm is comparable to pre-existing decoding algorithms such as the Successive Cancellation List (SCL) algorithm with better error correction performance.