List Decoding of Polar Codes

List Decoding of Polar Codes

31 May 2012 | Ido Tal Alexander Vardy
This paper presents a successive-cancellation list (SCL) decoder for polar codes, which improves upon the classic successive-cancellation (SC) decoder. The SCL decoder maintains up to L decoding paths at each stage, allowing it to select the most likely codeword from the list. Simulation results show that this approach achieves performance close to maximum-likelihood (ML) decoding, even for moderate values of L. With a "genie" that selects the correct codeword from the list, the performance of polar codes becomes comparable to state-of-the-art low-density parity-check (LDPC) codes. The SCL decoder doubles the number of decoding paths at each step and prunes them to retain only the L most likely paths. However, a naive implementation requires Ω(L·n²) time, which is inefficient compared to the O(n log n) complexity of the SC decoder. To address this, the paper introduces an efficient implementation that reduces the time complexity to O(L·n log n) and space complexity to O(L·n), leveraging the structure of polar codes. The paper also discusses the implementation details of the SCL decoder, including the use of data structures to manage multiple decoding paths and the "lazy-copy" technique to reduce memory usage. The key idea is to share arrays among paths and only copy them when necessary, ensuring efficient memory usage and performance. The SCL decoder is implemented with low-level functions to manage path activation, cloning, and termination, as well as mid-level functions to perform the recursive calculations required for decoding. The normalization of probabilities is also addressed to prevent floating-point underflow, ensuring accurate and reliable decoding. Overall, the SCL decoder significantly improves the performance of polar codes, making them competitive with LDPC codes, while maintaining a manageable computational complexity.This paper presents a successive-cancellation list (SCL) decoder for polar codes, which improves upon the classic successive-cancellation (SC) decoder. The SCL decoder maintains up to L decoding paths at each stage, allowing it to select the most likely codeword from the list. Simulation results show that this approach achieves performance close to maximum-likelihood (ML) decoding, even for moderate values of L. With a "genie" that selects the correct codeword from the list, the performance of polar codes becomes comparable to state-of-the-art low-density parity-check (LDPC) codes. The SCL decoder doubles the number of decoding paths at each step and prunes them to retain only the L most likely paths. However, a naive implementation requires Ω(L·n²) time, which is inefficient compared to the O(n log n) complexity of the SC decoder. To address this, the paper introduces an efficient implementation that reduces the time complexity to O(L·n log n) and space complexity to O(L·n), leveraging the structure of polar codes. The paper also discusses the implementation details of the SCL decoder, including the use of data structures to manage multiple decoding paths and the "lazy-copy" technique to reduce memory usage. The key idea is to share arrays among paths and only copy them when necessary, ensuring efficient memory usage and performance. The SCL decoder is implemented with low-level functions to manage path activation, cloning, and termination, as well as mid-level functions to perform the recursive calculations required for decoding. The normalization of probabilities is also addressed to prevent floating-point underflow, ensuring accurate and reliable decoding. Overall, the SCL decoder significantly improves the performance of polar codes, making them competitive with LDPC codes, while maintaining a manageable computational complexity.
Reach us at info@study.space
[slides] List decoding of polar codes | StudySpace