Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
2009/06/16 by Erdal Arikan, Erdal Arıkan · 133 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Error Correcting Code Techniques #Cellular Automata and Applications #DNA and Biological Computing
paper · doi:10.1109/tit.2009.2021379
Abstract
<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">I(W)</tex></formula></emphasis> of any given binary-input discrete memoryless channel (B-DMC) <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">W</tex></formula></emphasis>. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">N</tex></formula></emphasis> independent copies of a given B-DMC <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">W</tex></formula></emphasis>, a second set of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">N</tex> </formula></emphasis> binary-input channels <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">\WN(i):1≤ i≤ N\</tex> </formula></emphasis> such that, as <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">N</tex></formula></emphasis> becomes large, the fraction of indices <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">i</tex></formula></emphasis> for which <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">I(WN(i))</tex></formula></emphasis> is near <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">1</tex> </formula></emphasis> approaches <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">I(W)</tex></formula></emphasis> and the fraction for which <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">I(WN(i))</tex></formula></emphasis> is near <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">0</tex> </formula></emphasis> approaches <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">1-I(W)</tex></formula></emphasis>. The polarized channels <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">\WN(i)\</tex></formula></emphasis> are well-conditioned for channel coding: one need only send data at rate <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">1</tex></formula></emphasis> through those with capacity near <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">1</tex></formula></emphasis> and at rate <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">0</tex></formula></emphasis> through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">W</tex></formula></emphasis> with <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">I(W)> 0</tex></formula></emphasis> and any target rate <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">R ≪ I(W)</tex></formula></emphasis>, there exists a sequence of polar codes <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">\\Fraktur Cn;n≥ 1\</tex> </formula></emphasis> such that <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">\Fraktur Cn</tex></formula></emphasis> has block-length <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">N=2n</tex> </formula></emphasis>, rate <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">≥ R</tex></formula></emphasis>, and probability of block error under successive cancellation decoding bounded as <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">Pe(N,R) ≤ O(N^-1\over 4)</tex> </formula></emphasis> independently of the code rate. This performance is achievable by encoders and decoders with complexity <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">O(Nlog N)</tex></formula></emphasis> for each. </para>
Cited by
- Polar Codes for q-Ary Channels, q=2r
- Asynchronous Massive Access and Neighbor Discovery Using OFDMA
- Rethinking Control Flow in Spatial Architectures: Insights Into Control Flow Plane Design
- COFFA: A <u>Co</u>-Design <u>F</u>ramework for <u>F</u>used-Grained Reconfigurable <u>A</u>rchitecture Towards Efficient Irregular Loop Handling
- Enhanced Feedback Mechanisms for Resource-Efficient Incremental Redundancy
- Critical-Set-Aided Simplified Blind SCL Recognition of Polar Codes
- Perturbation Power Selection for First-Error Delay Maximization in Enhanced SC Decoding
- From Bit to Block: Capacity Achievement via Code Concatenation
- GII-Polar Codes for Block Fading Channels
- Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps
- Polar Coding for Parallel Gaussian Channel
- On the Analysis of Puncturing for Finite-Length Polar Codes: Boolean Function Approach
- Recursive Quantum Qudit Convolutional Codes Need Not be Catastrophic
- Robust Receiver Design for Non-orthogonal Multiple Access
- Rank-Modulation Rewrite Coding for Flash Memories
- Slicing at the Physical Layer
- Channel State Information Preprocessing for CSI-based Physical-Layer Authentication Using Reconciliation
- Extremality Properties for the Basic Polarization Transformations
- Machine learning discovers new champion codes
- Capacity-Achieving Codes with Inverse-Ackermann-Depth Encoders
- Improving the decoding performance of CA-polar codes
- Decoding of Polar Codes Based on Q-Learning-Driven Belief Propagation
- Enabling Fast Polar SC Decoding with IR-HARQ
- On the Construction of Polar Codes for Channels with Moderate Input Alphabet Sizes
- Stitched Polar Codes
- Quantum Key Distribution Based on Systematic Polar Coding
- Block Length Gain for Nanopore Channels
- Extracting Wyner's Common Information Using Polar Codes and Polar Lattices
- Polar Codes with Memory
- On the Computability of Finding Capacity-Achieving Codes
- SCL Decoding of Non-Binary Linear Block Codes
- Group Probability Decoding of Turbo Product Codes over Higher-Order Fields
- Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep's clothing
- PolarZero: A Reinforcement Learning Approach for Low-Complexity Polarization Kernel Design
- Rate-Compatible Punctured Polar Codes: Optimal Construction Based on Polar Spectra
- Vardøhus Codes: Polar Codes Based on Castle Curves Kernels
- Re-proving Channel Polarization Theorems: An Extremality and Robustness Analysis
- A Study of Neural Polar Decoders for Communication
- Capacity-Achieving Rateless Polar Codes
- Secure Polar Coding for Adversarial Wiretap Channel
- Explicit Polar Codes with Small Scaling Exponent
- Polar-like Codes and Asymptotic Tradeoff among Block Length, Code Rate, and Error Probability
- Progressive Rate-Filling: A Framework for Agile Construction of Multilevel Polar-Coded Modulation
- Polarization for arbitrary discrete memoryless channels
- Convolutional Polar Codes on Channels with Memory using Tensor Networks
- Study of Design of Rate-Compatible Polar Codes Based on Non-Uniform Channel Polarization
- Convolutional Neural Network-aided Bit-flipping for Belief Propagation Decoding of Polar Codes
- On the Arikan Transformations of Binary-Input Discrete Memoryless Channels
- Polar Coding for the General Wiretap Channel
- Shannon-Limit Approached Information Reconciliation for Quantum Key Distribution
- Hardware architectures for Successive Cancellation Decoding of Polar\n Codes
- Low-Complexity LSTM-Assisted Bit-Flipping Algorithm for Successive Cancellation List Polar Decoder
- A hybrid partial sum computation unit architecture for list decoders of polar codes
- On Scaling Rules for Energy of VLSI Polar Encoders and Decoders
- Expansion Coding for Channel and Source Coding
- Parallelism Empowered Guessing Random Additive Noise Decoding
- Capacity-Achieving Polar Codes for Arbitrarily-Permuted Parallel Channels
- Serial Polar Automorphism Ensemble Decoders for Physical Unclonable Functions
- An Incremental Redundancy HARQ Scheme for Polar Code
- Using Deep Neural Networks to Predict and Improve the Performance of\n Polar Codes
- Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
- Low Complexity Belief Propagation Polar Code Decoders
- Decoding Polar Codes via Weighted-Window Soft Cancellation for Slowly-Varying Channel
- Exact Bias of Linear TRNG Correctors -- Spectral Approach
- Hidden Markov Model Decoding for LDPC Codes
- Low-Pathwidth GRAND: Exact Likelihood-Ordered Enumeration for BPSK Transmission over Correlated Gaussian Noise
- Two-Stage Polarization-Based Nonbinary Polar Codes for 5G URLLC
- Sphere Constraint based Enumeration Methods to Analyze the Minimum Weight Distribution of Polar Codes
- Erasure Schemes Using Generalized Polar Codes: Zero-Undetected-Error\n Capacity and Performance Trade-offs
- Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes
- Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity
- A Minimax Converse for Quantum Channel Coding
- On the Road to 6G: Visions, Requirements, Key Technologies, and Testbeds
- Binary Polar Code Kernels from Code Decompositions
- Fast Polarisation-Aware Decoder for Non-Binary Polar Codes
- SA-OOSC: A Multimodal LLM-Distilled Semantic Communication Framework for Enhanced Coding Efficiency with Scenario Understanding
- Achieving Secrecy Capacity of the Gaussian Wiretap Channel with Polar Lattices
- Efficient Low-Memory Fast Stack Decoding with Variance Polarization for PAC Codes
- Enhanced Successive Cancellation List Decoder for Long Polar Codes Targeting 6G Air Interface
- Successive Cancellation Decoding For General Monotone Chain Polar Codes
- Lightweight Error-Correction Code Encoders in Superconducting Electronic Systems
- On the Weight Distribution of Concatenated Code Ensemble Based on the Plotkin Construction
- Polar subcodes for MIMO systems
- Precoded Polar Product Decoder Based on Soft-Output SCL Decoding and Maximization of Generalized Mutual Information
- Capacity-Approaching Polar Codes with Long Codewords and Successive Cancellation Decoding Based on Improved Gaussian Approximation
- A Comprehensive Survey of 5G URLLC and Challenges in the 6G Era
- Concatenated LDPC-Polar Codes Decoding Through Belief Propagation
- 6G Takes Shape
- ORCAS Codes: A Flexible Generalization of Polar Codes with Low-Complexity Decoding
- Orthogonal Sparse Superposition Codes for Ultra-Reliable Low-Latency Communications
- Hardware-friendly IR-HARQ for Polar SCL Decoders
- Industrial Viewpoints on RAN Technologies for 6G
- Long Polar vs. LDPC Codes under Complexity-Constrained Decoding
- Neural Estimation of Information Leakage for Secure Communication System Design
- Polar codes in quantum information theory
- Mutual Information as a Figure of Merit for Optical Fiber Systems
- Improved Bounds on the Finite Length Scaling of Polar Codes
- Twisted-Pair Superposition Transmission
- Performance Analysis of Spatiotemporal 2-D Polar Codes for Massive MIMO with MMSE Receivers
- Polar Coding and Linear Decoding
- Quantized Polar Code Decoders: Analysis and Design
- Lattice Coding for Downlink Multiuser Transmission
- Space-Time Polar Coded Modulation
- Recursive projection-aggregation decoding of Reed-Muller codes
- Low-Complexity Sphere Decoding of Polar Codes based on Optimum Path Metric
- Attaining Capacity with Algebraic Geometry Codes through the (U|U+V) Construction and Koetter-Vardy Soft Decoding
- Polar Codes with exponentially small error at finite block length
- Reliable Wide-Area Backscatter via Channel Polarization
- Enhanced energy-constrained quantum communication over bosonic Gaussian channels. [europepmc]
- An Optimality Summary: Secret Key Agreement with Physical Unclonable Functions. [europepmc]
- Comparison between Different Channel Coding Techniques for IEEE 802.11be within Factory Automation Scenarios. [europepmc]
- Polar Codes for Quantum Key Distribution. [europepmc]
- SC List-Flip Decoding of Polar Codes by Shifted Pruning: A General Approach. [europepmc]
- Adaptive List Flip Decoder for Polar Codes with High-Order Error Correction Capability and a Simplified Flip Metric. [europepmc]
- Performance Comparison of NB-Fi, Sigfox, and LoRaWAN. [europepmc]
- Low complexity symmetric-coded based sphere decoding for low-rate polar codes. [europepmc]
- Intelligent Path-Selection-Aided Decoding of Polar Codes. [europepmc]
- Joint Design of Polar Coding and Physical Network Coding for Two-User Downlink Non-Orthogonal Multiple Access. [europepmc]
- Performance Analysis of Turbo Codes, LDPC Codes, and Polar Codes over an AWGN Channel in the Presence of Inter Symbol Interference. [europepmc]
- 5G V2X Performance Comparison for Different Channel Coding Schemes and Propagation Models. [europepmc]
- Performance Analysis of Artificial Noise-Assisted Location-Based Beamforming in Rician Wiretap Channels. [europepmc]
- Software implementation of systematic polar encoding based PKC-SPE cryptosystem for quantum cybersecurity. [europepmc]
- Non-Negative Decomposition of Multivariate Information: From Minimum to Blackwell-Specific Information. [europepmc]
- Information Theory in Emerging Wireless Communication Systems and Networks. [europepmc]
- A Thermodynamic Study on Information Power in Communication Systems. [europepmc]
- On the Exploration of Quantum Polar Stabilizer Codes and Quantum Stabilizer Codes with High Coding Rate. [europepmc]
- A Novel Embedded Side Information Transmission Scheme Based on Polar Code for Peak-to-Average Power Ratio Reduction in Underwater Acoustic OFDM Communication System. [europepmc]
- Revolutionizing Free-Space Optics: A Survey of Enabling Technologies, Challenges, Trends, and Prospects of Beyond 5G Free-Space Optical (FSO) Communication Systems. [europepmc]
- Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes. [europepmc]
- Quasi-Optimal Path Convergence-Aided Automorphism Ensemble Decoding of Reed-Muller Codes. [europepmc]
- Polar code construction by estimating noise using bald hawk optimized recurrent neural network model. [europepmc]
- Improving Data Communication of Enhanced Loran Systems Using 128- ary Polar Codes. [europepmc]
- Efficient FPGA implementation of polar codes-based information reconciliation for quantum key distribution. [europepmc]
Related