Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization

Seyed Hamed Hassani, Ryuhei Mori, Toshiyuki Tanaka, Rüdiger L. UrbankeIEEE Trans. Information Theory 2011 · DOI · OpenReview

Abstract

This paper investigates the asymptotic behavior of the channel polarization process in the large block-length regime for binary-input memoryless symmetric (BMS) channels $W$. We analyze the cumulative distribution of the Bhattacharyya process $\{Z_n\}$ and its sensitivity to the transmission rate $R$. By applying a Central Limit Theorem (CLT) approach to the log-reliability of bit-channels, we refine the existing asymptotic bounds established by Arıkan and Telatar. Our analysis extends to general $\ell \times \ell$ kernel matrices, characterizing the block error probability for successive cancellation (SC) decoding. Furthermore, we establish asymptotic lower bounds for maximum a posteriori (MAP) decoding, identifying a performance gap between SC and MAP decoders when the kernel size $\ell > 2$.

Introduction

Polar codes represent a landmark in information theory, being the first class of error-correcting codes to provably achieve the capacity of symmetric channels with efficient encoding and decoding. The fundamental mechanism, channel polarization, transforms $N$ independent copies of a noisy channel into a set of synthesized channels that are either nearly noiseless or completely noisy as $N \to \infty$.

While the initial work by Arıkan demonstrated that the probability of error vanishes as $O(2^{-N^\beta})$, these early bounds were "rate-independent," failing to capture how the speed of polarization varies as the transmission rate $R$ approaches the channel capacity $I(W)$. This paper provides a fine-grained asymptotic analysis that explicitly incorporates the rate $R$, revealing a Gaussian-like scaling behavior in the distribution of polarized channels.

Methodology

As a theoretical study, this research utilizes mathematical models of BMS channels, such as the Binary Erasure Channel (BEC), to validate its findings. The authors treat channel polarization as a stochastic process, specifically focusing on the evolution of the Bhattacharyya process $\{Z_n\}$.

Generalizing the Kernel

While standard polar codes utilize a $2 \times 2$ kernel, this analysis generalizes to any $\ell \times \ell$ polarizing kernel matrix $G$. The quality of these kernels is determined by their "partial distances," from which two pivotal parameters are derived:

  1. The Exponent $E(G)$: The mean of the log-partial distances.
  2. The Second Exponent $V(G)$: The variance of the log-partial distances.

The CLT Approach

By applying Central Limit Theorem (CLT) arguments to the log-reliability parameters, the authors show that in the log-domain, the distribution of channel qualities behaves like a normal distribution as the number of polarization steps $n$ grows. This allows for a much more precise characterization of the "transition region" between good and bad channels.

Key Insights and Results

Gaussian Scaling and Rate Dependence

The most significant finding is that the cumulative distribution of channel reliabilities follows a $Q$-function (the tail of a Gaussian distribution). This implies that the transition from reliable to unreliable channels follows a predictable scaling law.

Theorem 3 (The Main Result): For a rate $R < I(W)$, the reliability $Z_n$ satisfies: $$\lim_{n \to \infty} \mathbb{P}\left(Z_n \leq 2^{-\ell^{n E(G) + \sqrt{n V(G)} Q^{-1}\left(\frac{R}{I(W)}\right) + o(\sqrt{n})}}\right) = R$$ This formula explicitly links the code's exponent, the transmission rate, and the Gaussian $Q$-function, refining the original Arıkan and Telatar bounds by adding a rate-dependent correction term of order $\sqrt{n}$.

SC vs. MAP Decoding

The study also compares Successive Cancellation (SC) decoding with optimal Maximum A Posteriori (MAP) decoding.

  • For the standard $2 \times 2$ kernel, the SC upper bound and the MAP lower bound coincide asymptotically.
  • For larger kernels ($\ell > 2$), a performance gap emerges, indicating that SC decoding may not fully capture the potential of higher-order kernels.

Efficient Channel Selection

Practically, the authors demonstrate that selecting the best channels for a code does not require exhaustive calculation. One only needs to examine a small prefix of the channel indices (of order $\Theta(\log \log n)$ bits) in a channel-dependent way; the remaining indices can be chosen using a simpler, channel-independent rule.

Discussion and Limitations

While this work provides a rigorous "fine-grained" look at polarization, it primarily addresses the large-$N$ (asymptotic) regime. In real-world applications with moderate block lengths, these asymptotic effects may be influenced by finite-length constraints. Furthermore, the identified gap between SC and MAP decoding for $\ell > 2$ suggests that kernel optimization remains an open challenge. Future work may focus on finding kernels that minimize this gap or developing decoders that better exploit the structure of larger kernels.

Summary updated

Abstract

For a binary-input memoryless symmetric channel $W$, we consider the asymptotic behavior of the polarization process in the large block-length regime when transmission takes place over $W$. In particular, we study the asymptotics of the cumulative distribution $\mathbb{P}(Z_n \leq z)$, where $\{Z_n\}$ is the Bhattacharyya process defined from $W$, and its dependence on the rate of transmission. On the basis of this result, we characterize the asymptotic behavior, as well as its dependence on the rate, of the block error probability of polar codes using the successive cancellation decoder. This refines the original bounds by Ar{\i}kan and Telatar. Our results apply to general polar codes based on $\ell \times \ell$ kernel matrices. We also provide lower bounds on the block error probability of polar codes using the MAP decoder. The MAP lower bound and the successive cancellation upper bound coincide when $\ell=2$, but there is a gap for $\ell>2$.
BibTeX
@article{hassani2011rate,
  author = {Seyed Hamed Hassani and Ryuhei Mori and Toshiyuki Tanaka and Rüdiger L. Urbanke},
  title = {{Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization}},
  journal = {IEEE Transactions on Information Theory},
  year = {2011},
  doi = {10.1109/tit.2012.2228295},
}
Figure