Scaling Exponent of List Decoders With Applications to Polar Codes

DOI10.1109/TIT.2015.2453315MaRDI QIDQ2977281zbMATH OpenOpenAlexFDO

Authors

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/1304.5220

Mathematics Subject Classification ID

Decoding (94B35) Other types of codes (94B60) Error probability in coding theory (94B70)

Abstract: Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed and the trade-off between block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under $mMAP$ decoding with list size $L$ for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under $mMAP$ decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.

Recommendations

• List Decoding of Polar Codes
• On list size exponents in rate-distortion coding
• On the Finite Length Scaling of <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math> </inline-formula>-Ary Polar Codes
• Finite-Length Scaling for Polar Codes
• Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors
• Near-Optimal Finite-Length Scaling for Polar Codes Over Large Alphabets
• Polar Codes: Characterization of Exponent, Bounds, and Constructions
• An Information-Theoretic Perspective on Successive Cancellation List Decoding and Polar Code Design
• Improved Bounds on the Finite Length Scaling of Polar Codes
• Explicit list-decodable codes with optimal rate for computationally bounded channels

Cited in

(2)

• Finite-Length Scaling for Polar Codes
• On the Finite Length Scaling of <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math> </inline-formula>-Ary Polar Codes

This page was built for publication: Scaling Exponent of List Decoders With Applications to Polar Codes

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