List decoding of polar codes

By Ido Tal, Alexander Vardy. IEEE International Symposium on Information Theory. Proceedings, 2011

1,989 citations recorded by the source corpus.

We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, up to L decoding paths are considered concurrently at each decoding stage. Simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of L. Thus it appears that the proposed list decoder bridges the gap between successive-cancellation and maximum-likelihood decoding of polar codes. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the L “best” paths. In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, straightforward implementation still requires O(L · n2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only O(L · n log n) time and O(L · n) space.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/860726bf9c59ea8ed3b91450d25d85f7cfc8b64f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

A Semi-Parallel Successive-Cancellation Decoder for Polar Codes (2013, positive): “A particular scheduling of SC decoding was shown to enable beneﬁcial resource sharing without affecting throughput [12].”
Fast Polar Decoders: Algorithm and Implementation (2013, methodology): “Decoding the (2048, 1723) code using the list-CRC algorithm [4], with a list size of 32 and a 32-bit CRC, reduces the gap with the LDPC code to the point where the two codes have similar performance as shown in Fig.”
CRC-Aided Decoding of Polar Codes (2012, methodology): “In a recent paper [7], Tal and Vardy independently formulate the similar statement on CRC-concatenated polar coding scheme based on SCL decoding.”
An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check (2012, methodology): “A new SC-list decoding algorithm was proposed for polar codes recently [2], which performs better than the simple SC decoder and performs almost the same as the optimal ML (maximum likelihood) decoding at high SNR.”
LLR-Based Successive Cancellation List Decoding of Polar Codes (2013, methodology): “In an extended version of their work [16], Tal and Vardy observe that when the SCL decoder fails, in most of the cases, the correct path (corresponding to uA) is among the L paths the decoder has ended up with.”