How to Construct Polar Codes

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$.

References in corpus (4)

• Properties and Construction of Polar Codes
• Polar Codes for the m-User MAC
• Universal Bounds on the Scaling Behavior of Polar Codes
• Polar write once memory codes

Cited by in corpus (24)

• Fast Polar Decoders: Algorithm and Implementation
• Improved Successive Cancellation Decoding of Polar Codes
• Polar codes for classical-quantum channels
• Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization
• Fast Low-Complexity Decoders for Low-Rate Polar Codes
• Scalable Successive-Cancellation Hardware Decoder for Polar Codes
• Achieving the Capacity of any DMC using only Polar Codes
• Increasing the Speed of Polar List Decoders
• Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity
• Fast Software Polar Decoders
• Universal Polar Codes
• Polar Coding for the General Wiretap Channel
• Performance of polar codes for quantum and private classical communication
• Entropy-Constrained Maximizing Mutual Information Quantization
• Optimal quantizer structure for binary discrete input continuous output channels under an arbitrary quantized-output constraint
• Single-bit Quantization Capacity of Binary-input Continuous-output Channels
• On the Uniqueness of Binary Quantizers for Maximizing Mutual Information
• Polar Codes: Robustness of the Successive Cancellation Decoder with Respect to Quantization
• Achieving Secrecy Capacity of the Gaussian Wiretap Channel with Polar Lattices
• Approaching the Rate-Distortion Limit with Spatial Coupling, Belief propagation and Decimation
• Polynomial complexity of polar codes for non-binary alphabets, key agreement and Slepian-Wolf coding
• A Reconstruction-Computation-Quantization (RCQ) Approach to Node Operations in LDPC Decoding
• An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check
• Polar Codes for Nonasymmetric Slepian-Wolf Coding