List Decoding of Polar Codes

Jump to other IT Society Websites:

List Decoding of Polar Codes


Creation Date: May 01, 2015

Published In: May 2015

Paper Type: Journal Article

Book Title: IEEE Transactions on Information Theory



We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arıkan. In the proposed list decoder, L decoding paths are considered concurrently at each decoding stage, where L is an integer parameter. At the end of the decoding process, the most likely among the L paths is selected as the single codeword at the decoder output. Simulations show that the resulting performance is very close to that of maximum-likelihood decoding, even for moderate values of L. Alternatively, if a genie is allowed to pick the transmitted codeword from the list, the results are comparable with the performance of current state-of-the-art LDPC codes. We show that such a genie can be easily implemented using simple CRC precoding. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths for each information bit, and then uses a pruning procedure to discard all but the L most likely paths. However, straightforward implementation of this algorithm requires Ω(Ln2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. In this paper, we utilize the structure of polar codes along with certain algorithmic transformations in order to overcome this problem: we devise an efficient, numerically stable, implementation of the proposed list decoder that takes only O(Ln logn) time and O(Ln) space.

IEEE Explore link:

Award(s) Received:
Latest News
The First Workshop on the Age of Information - Call For Papers
ITSoc BoG contribution for newsletter
Post-Doc Position at King's College London

Upcoming Events

NSF Workshop on Low-Latency Wireless Random-Access at MIT
02-03 Nov 2017 | MIT Grier Room 34-401, 50 Vassar Street, Cambridge, MA, USA
2017 IEEE Information Theory Workshop
06-10 Nov 2017 | Kaohsiung Exhibition Center, Kaohsiung, Taiwan
Fano Memorial in Turin
10 Nov 2017 | Turin, Salone d'onore del Castello del Valentino.