How to Construct Polar Codes

DOI10.1109/TIT.2013.2272694MaRDI QIDQ5346305zbMATH OpenOpenAlexFDO

Authors Ido Tal, Alexander Vardy

Publication date 8 June 2017

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

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

Mathematics Subject Classification ID

Channel models (including quantum) in information and communication theory (94A40) Other types of codes (94B60)

Abstract: A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with he code length. Thus the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which "sandwich" the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed, and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed $epsilon>0$ and all sufficiently large code lengths $n$, polar codes whose rate is within $epsilon$ of channel capacity can be constructed in time and space that are both linear in $n$.

Cited in

(15)

• Polar codes with higher-order memory
• Successive cancellation decoding of Reed-Solomon codes
• Shannon-limit approached information reconciliation for quantum key distribution
• Polar sampler: a novel Bernoulli sampler using polar codes with application to integer Gaussian sampling
• Polar Coding for Secret-Key Generation
• Extensions of the method of poles for code construction
• Algorithmic polarization for hidden Markov models
• Interactive function computation via polar coding
• Reed-Muller Codes
• Series of formulas for Bhattacharyya parameters in the theory of polar codes
• Design and decoding of polar codes with large kernels: a survey
• Polar coding for ring-LWE-based public key encryption
• PolarKyber: polished Kyber with smaller ciphertexts, greater security redundancy, and lower decryption failure rate
• A series of short exact formulas for the Bhattacharya parameter of coordinate channels
• Design of polar codes with large kernels

This page was built for publication: How to Construct Polar Codes

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