Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
2008/07/24 by Erdal Arikan, Erdal Arıkan · 1 voice · 4,464 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Algorithm #Arithmetic #Binary code #Binary number #Binary symmetric channel #Cellular Automata and Applications #Channel (broadcasting) #Channel capacity #Channel code #Computer science #DNA and Biological Computing #Decoding methods #Electronic engineering #Engineering #Error Correcting Code Techniques #Mathematics #Polarization (electrochemistry) #Telecommunications #Theoretical computer science #cs.IT #math.IT
paper · pdf · doi:10.1109/tit.2009.2021379
published in IEEE Transactions on Information Theory 55(7), 3051-3073 (Institute of Electrical and Electronics Engineers) · The version which appears in the IEEE Transactions on Information Theory, July 2009
arxiv published 2008/07/24 · openalex publication_date 2009/06/16 · arxiv created 2009/07/20 · arxiv updated 2016/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract
A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacityI(W)of any given binary-input discrete memoryless channel (B-DMC)W. 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 ofNindependent copies of a given B-DMCW, a second set ofNbinary-input channels\WN(i):1≤ i≤ N\such that, asNbecomes large, the fraction of indicesifor whichI(WN(i))is near1approachesI(W)and the fraction for whichI(WN(i))is near0approaches1-I(W). The polarized channels\WN(i)\are well-conditioned for channel coding: one need only send data at rate1through those with capacity near1and at rate0through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMCWwithI(W)> 0and any target rateR ≪ I(W), there exists a sequence of polar codes\\Fraktur Cn;n≥ 1\such that\Fraktur Cnhas block-lengthN=2n, rate≥ R, and probability of block error under successive cancellation decoding bounded asPe(N,R) ≤ O(N^-1\over 4)independently of the code rate. This performance is achievable by encoders and decoders with complexityO(Nlog N)for each.
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 Co-Design Framework for Fused-Grained Reconfigurable Architecture 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 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 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 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
- On Refined Versions of the Azuma-Hoeffding Inequality with Applications in Information Theory
- 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
- Fast Sequential Decoding of Polar Codes
- Polar Codes for Erasure and Unital Classical-Quantum Markovian Channels
- Performance of Polar Codes for Channel and Source Coding
- Coded Compressive Sensing: A Compute-and-Recover Approach
- Randomness and dependencies extraction via polarization, with applications to Slepian-Wolf coding and secrecy
- Density Evolution Analysis of Sparse-Block IDMA
- Error Detection Based on Generalized Successive Cancellation List Decoding for Polar Codes
- Neural Polar Decoders for Deletion Channels
- Auto-Generation of Pipelined Hardware Designs for Polar Encoder
- Rejection-Sampled Linear Codes for Lossy Compression and Channel Simulation
- Polar Lattices for Lossy Compression
- BiD Codes: Algebraic Codes from 3 × 3 Kernel
- Computationally Efficient Covert Communication
- Discovering the Unequal Importance of Coded Bits in the Decoding of Polar Codes
- Almost-Reed--Muller Codes Achieve Constant Rates for Random Errors
- Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices
- Lower Bounds for Error Coefficients of Griesmer Optimal Linear Codes via Iteration
- Low-Latency Software Polar Encoders and Decoders for Short Blocklengths
- Realization of Stochastic Neural Networks and Its Potential Applications
- Resolution Limits of Non-Adaptive 20 Questions Estimation for Tracking Multiple Moving Targets
- Reed-Muller Codes: Theory and Algorithms
- A Simple Proof of Fast Polarization
- Mutli-Level Autoencoder: Deep Learning Based Channel Coding and Modulation
- Polar Coded Modulation with Optimal Constellation Labeling
- Poset-Markov Channels: Capacity via Group Symmetry
- Binary Polarization Kernels from Code Decompositions
- Pixel-Sensitive and Robust Steganography Based on Polar Codes
- A Locally Differential Private Coding-Assisted Succinct Histogram Protocol
- Neural Polar Decoders for DNA Data Storage
- Quantum-Processing-Assisted Classical Communications
- Towards Weight Distribution-Aware Polar Codes
- The Complete Affine Automorphism Group of Polar Codes
- Segmented Successive Cancellation List Polar Decoding with Tailored CRC
- Code Rate Optimization via Neural Polar Decoders
- Spectral Comb Shaping by Polar Codes
- Scalar Lattices and Probabilistic Shaping for Dithered Wyner-Ziv Quantization
- Polar Coded HARQ Scheme with Chase Combining
- Last-Pair Swapping Polar Codes: A Structure to Improve Polarization under Finite-State Modulation
- On the High-Rate FDPC Codes: Construction, Encoding, and a Generalization
- On decoding algorithms for polar codes
- Polarized Element-pair Code Based FFMA over a Gaussian Multiple-access Channel
- Reed-Muller codes polarize
- Genetic Algorithm-based Polar Code Construction for the AWGN Channel
- ARUM: Polar Coded HARQ Scheme based on Incremental Channel Polarization
- Log-logarithmic Time Pruned Polar Coding on Binary Erasure Channels
- On the Synthetic Channels in Polar Codes over Binary-Input Discrete Memoryless Channels
- Multilevel Polarization of Polar Codes Over Arbitrary Discrete Memoryless Channels
- Generalized Polarization Transform: A Novel Coded Transmission Paradigm
- Reinforcement Learning-Aided Design of Efficient Polarization Kernels
- Design of Polar Codes with Single and Multi-Carrier Modulation on Impulsive Noise Channels using Density Evolution
- Rotation Based Slice Error Correction Protocol for Continuous-variable Quantum Key Distribution and its Implementation with Polar Codes
- Secure Polar Coding with Delayed Wiretapping Information
- On irredundant orthogonal arrays
- On the Weight Spectrum of Pre-Transformed Polar Codes
- On Decoding Using Codewords of the Dual Code
- Molecular Polar Belief Propagation Decoder and Successive Cancellation Decoder
- Interpolation of Quantum Polar Codes and Quantum Reed-Muller Codes
- Asymmetric Error Correction and Flash-Memory Rewriting using Polar Codes
- Expansion coding: Achieving the capacity of an AEN channel
- Polar codes for the m-user multiple access channels
- Convolutional Polar Codes
- Constructing Polar Codes Using Iterative Bit-Channel Upgrading
- Fast Successive-Cancellation Decoding of 2 × 2 Kernel Non-Binary Polar Codes
- Hybrid Mamba-Transformer Decoder for Error-Correcting Codes
- A Dynamic Programming Method to Construct Polar Codes with Improved Performance
- Protograph-Based Low-Density Parity-Check Hadamard Codes
- Low-complexity Receiver for Multi-Level Polar Coded Modulation in Non-Orthogonal Multiple Access
- Achievable rates for concatenated square Gottesman-Kitaev-Preskill codes
- Construction of Capacity-Achieving Lattice Codes: Polar Lattices
- Near-Capacity Detection and Decoding: Code Design for Dynamic User Loads in Gaussian Multiple Access Channels
- Systematic Convolutional Low Density Generator Matrix Code
- The problem with the SURF scheme
- Polar write once memory codes
- Rate-Matching Deep Polar Codes via Polar Coded Extension
- Performance Comparison of Short-Length Error-Correcting Codes
- On Cyclic Polar Codes and The Burst Erasure Performance of Spatially-Coupled LDPC Codes
- A Class of Transformations that Polarize Symmetric Binary-Input Memoryless Channels
- CSI Learning Based Active Secure Coding Scheme For Detectable Wiretap Channel
- Polarization Decomposition and Its Applications
- Channel Upgradation for Non-Binary Input Alphabets and MACs
- Performance of CRC Concatenated Pre-transformed RM-Polar Codes
- Polar Code Moderate Deviation: Recovering the Scaling Exponent
- Polar Coding for Fading Channels: Binary and Exponential Channel Cases
- Speculative Successive Cancellation Decoding of Polar Codes
- Towards Practical Software Stack Decoding of Polar Codes
- Dynamic-SCFlip Decoding of Polar Codes
- Polar Codes in Network Quantum Information Theory
- Construction of a Channel Code from an Arbitrary Source Code with Decoder Side Information
- Semantic-aided Parallel Image Transmission Compatible with Practical System
- Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels
- On Weight Enumeration and Structure Characterization of Polar Codes via Group Actions
- Efficient Polar Coding of Quantum Information
- A Low Complexity Encoding Algorithm for Systematic Polar Codes
- A Deterministic Algorithm for Computing the Weight Distribution of Polar Codes
- Subcode Ensemble Decoding of Polar Codes
- Fast Low-Complexity Decoders for Low-Rate Polar Codes
- Tail-Calibrated Soft-Output GRAND for Finite-Memory Noise-Effect Posteriors
- Space-Time Signal Design for Multilevel Polar Coding in Slow Fading\n Broadcast Channels
- Binary polar codes are optimised codes for bitwise multistage decoding
- Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions
- Threshold-Secure Coding With Shared Key
- Duality between erasures and defects
- A Revisit to Ordered Statistics Decoding: Distance Distribution and Decoding Rules
- Low-latency list decoding of polar codes with double thresholding
- PolarBear: A 28-nm FD-SOI ASIC for Decoding of Polar Codes
- Capacity-achieving Polar-based LDGM Codes
- The Symmetric Convex Ordering: A Novel Partial Order for B-DMCs Ordering the Information Sets of Polar Codes
- Partitioned Successive-Cancellation Flip Decoding of Polar Codes
- SimCommSys: taking the errors out of error‐correcting code simulations
- Fast and Flexible Successive-Cancellation List Decoders for Polar Codes
- On Path Memory in List Successive Cancellation Decoder of Polar Codes
- Source polarization
- Polar Codes for the Two-User Multiple-Access Channel
- A Low-Latency List Successive-Cancellation Decoding Implementation for Polar Codes
- Achieving the Holevo bound via a bisection decoding protocol
- Nested Polar Codes for Wiretap and Relay Channels
- Successive-Cancellation Flip and Perturbation Decoder of Polar Codes
- In-Context Source and Channel Coding
- Polar coding for achieving the capacity of marginal channels in nonbinary-input setting
- Gigabit-rate Quantum Key Distribution on Integrated Photonic Chips
- 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]
- Enhanced energy-constrained quantum communication over bosonic Gaussian channels. [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]
- Software implementation of systematic polar encoding based PKC-SPE cryptosystem for quantum cybersecurity. [europepmc]
Discussions
Related