Ido Tal and Alexander Vardy awarded the IEEE Communications Society and Information Theory Society Joint Paper Award for 2017

Jump to other IT Society Websites:
The paper "List Decoding of Polar Codes" IEEE Transactions on Information Theory, Vol. 61, No. 5, pp 2213 – 2226, May 2015 by Ido Tal and Alexander Vardy has been awarded the 2017 IEEE Communications Society and Information Theory Society Joint Paper Award for 2017.

Ido Tal is an Assistant Professor at the Technion-Israel Institute of Technology and Alexander Vardy is a Professor at the University of California, San Diego.

The abstract of the paper is given below.

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.