Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels

By E. Arıkan. IEEE Transactions on Information Theory, 2008

4,373 citations recorded by the source corpus.

A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity I(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 of N independent copies of a given B-DMC W, a second set of N binary-input channels {WN(i)1 les i les N} such that, as N becomes large, the fraction of indices i for which I(WN(i)) is near 1 approaches I(W) and the fraction for which I(WN(i)) is near 0 approaches 1-I(W). The polarized channels {WN(i)} are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC W with I(W) > 0 and any target rate R< I(W) there exists a sequence of polar codes {Cfrn;nges1} such that Cfrn has block-length N=2n , rate ges R, and probability of block error under successive cancellation decoding bounded as Pe(N,R) les O(N-1/4) independently of the code rate. This performance is achievable by encoders and decoders with complexity O(N logN) for each.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/de2b197c1db668eccf6623b39f4862824fac7ef4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Systematic Polar Coding (2011, methodology): “The decoder used in the simulations was a successive cancellation (SC) decoder, as described in [1].”
A Simplified Successive-Cancellation Decoder for Polar Codes (2011, background): “Given these three parameters, a polar codeword x may be obtained by mapping a binary N -tuple b whose ith component is set (“frozen”) to zero for all i ∈ [N ] ∖ A, forming x = bGn, where Gn denotes the generator matrix for polar codes of block-length 2 (as defined in [1]).”
Polar codes are optimal for lossy source coding (2009, methodology): “Polar codes, introduced by Arıkan in [15], are the first provably capacity achieving codes for arbitrary symmetric binary-input discrete memoryless channels (B-DMC) with lo w encoding and decoding complexity.”
Minimizing Additive Distortion in Steganography Using Syndrome-Trellis Codes (2011, background): “One promising direction towards replacing the random linear codes while keeping the optimality of the construction has recently been proposed by Arikan [35], who introduced the so-called polar codes for the channel coding problem.”
Polar Codes for Channel and Source Coding (2009, methodology): “Using the factor graph representation between ¯ u and ¯ x shown in Figure 1, Arıkan showed that this decoder can be implemented in complexity O(N log N ).”
Efficient Design and Decoding of Polar Codes (2012, methodology): “Polar codes were recently shown to achieve the capacity of discrete input memoryless output symmetric channels [1].”
High-Reliability and Low-Latency Wireless Communication for Internet of Things: Challenges, Fundamentals, and Enabling Technologies (2019, neutral): “ity for symmetric binary-input memoryless channels [60].”
On deep learning-based channel decoding (2017, methodology): “The codewords are now obtained by x = uG N , where u contains k information bits and N − k frozen positions, for details we refer to [19].”
How to Construct Polar Codes (2011, methodology): “…a binary input alphabet X , an output alphabet Y n × X i , and transition probabilities deﬁned as follows. be the Let G polarization kernel matrix of [3], given by Let G ⊗ m be the m -fold Kronecker product of G and let B n be the n × n bit-reversal premutation matrix deﬁned in [3, Section VII-B].”
CRC-Aided Decoding of Polar Codes (2012, methodology): “We use the same notations defined in [1].”
An Adaptive Successive Cancellation List Decoder for Polar Codes with Cyclic Redundancy Check (2012, background): “olar codes are a major breakthrough in coding theory [1].”
Rate-Splitting Multiple Access: Fundamentals, Survey, and Future Research Trends (2022, background): “Remark 6: The PHY layer transceiver architecture described in [36] employs polar codes [142] for channel coding and the modulation formats 4-QAM, 16-QAM, 64-QAM and 256-QAM.”
Short Block-length Codes for Ultra-Reliable Low-Latency Communications (2018, background): “Polar codes as introduced in [7], are binary linear codes that can provably achieve the capacity of a binary-input discrete memoryless channel using low-complexity encoding and decoding as the code length tends to infinity.”
Nonlinear Transform Source-Channel Coding for Semantic Communications (2021, methodology): “In this case, to ensure reliable transmission of the side information, channel coding (CE and CD) should adopt advanced capacity-approaching codes, such as low-density parity-check (LDPC) codes [28] or polar codes [29].”
Polarization for arbitrary discrete memoryless channels (2009, methodology): “This last observation is the basis of what lets [ 1 ] conclude that polar codes achieve the symmetric capacity.”
A performance comparison of polar codes and Reed-Muller codes (2008, methodology): “Results in [ 1 ] show that if one uses polar code construction rules that are tailored to the specific channel on which the code will be used, one may expect better performance at the expense of more complexity in code construction (but not in encoding and decoding of the resulting code).”
On the rate of channel polarization (2008, methodology): “The aim of this paper is to strengthen the results of [ 1 ] on the probability of block decoding error for polar codes.”