List Decoding of Polar Codes

DOI10.1109/TIT.2015.2410251MaRDI QIDQ2978597zbMATH OpenOpenAlexFDO

Authors Ido Tal, Alexander Vardy

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0050

Mathematics Subject Classification ID

Decoding (94B35)

Abstract: We describe a successive-cancellation emph{list} decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Ar{i}kan. In the proposed list decoder, up to $L$ decoding paths are considered concurrently at each decoding stage. Then, a single codeword is selected from the list as output. If the most likely codeword is selected, simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of $L$. Alternatively, if a "genie" is allowed to pick the codeword from the list, the results are comparable to the current state of the art LDPC codes. Luckily, implementing such a helpful genie is easy. Our list decoder 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, a straightforward implementation still requires $Omega(Lcdot{n}^2)$ time, which is in stark contrast with the $O(nlogn)$ 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(Lcdotnlogn)$ time and $O(Lcdotn)$ space.

Cited in

(14)

• Design and decoding of polar codes with large kernels: a survey
• Polar coding for ring-LWE-based public key encryption
• Successive cancellation decoding of Reed-Solomon codes
• List decoding of wavelet codes
• Design of polar codes with large kernels
• Reed-Muller Codes
• Scaling Exponent of List Decoders With Applications to Polar Codes
• List Decoding for Binary Goppa Codes
• Efficient quantum key distribution protocol based on classical-quantum polarized channels
• Shannon-limit approached information reconciliation for quantum key distribution
• List Decoding of Direct Sum Codes
• Unsourced random access
• Polar sampler: a novel Bernoulli sampler using polar codes with application to integer Gaussian sampling
• Recursive descriptions of polar codes

This page was built for publication: List Decoding of Polar Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978597)