PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Rate of Channel Polarization

Erdal Arikan, Emre Telatar

arXiv:0807.3806v3cs.IT

TL;DR

The paper asks how rapidly channel polarization can improve polar-code block-error performance for binary-input discrete memoryless channels. It analyzes the reliability supermartingale associated with the polarization process and establishes a subexponential error bound for rates below symmetric capacity.

  • Problem

    The paper studies the rate of channel polarization and seeks stronger block-error guarantees for polar coding on binary-input channels.

  • Method

    The analysis uses the channel sequence’s reliability process {Z_n}, treating it as a bounded supermartingale and applying a bootstrapping argument.

  • Results

    For any binary-input DMC with I(W) > 0, rate R < I(W), and β < 1/2, polar coding under successive cancellation decoding achieves the stated asymptotic block-error guarantee at N = 2^n.

  • Takeaways & Limitations

    The result strengthens prior polar-coding block-error bounds and quantifies the speed at which the polarization process produces highly reliable channels.

Abstract

from arXiv · show

It is shown that for any binary-input discrete memoryless channel $W$ with symmetric capacity $I(W)$ and any rate $R <I(W)$, the probability of block decoding error for polar coding under successive cancellation decoding satisfies $P_e \le 2^{-N^β}$ for any $β<\frac12$ when the block-length $N$ is large enough.

I. INTRODUCTION

The paper studies channel polarization and polar codes for binary-input channels, emphasizing their capacity-achieving construction and tractable reliability analysis. It strengthens prior block-error results through the channel transform and its associated reliability parameters.

  • I. INTRODUCTION: Channel polarization constructs capacity-achieving polar codes for binary-input symmetric channels using a well-defined, noniterative construction rule.The paper motivates polar codes theoretically by their provable capacity achievement and absence of trial-and-error in construction.
  • I. INTRODUCTION: The paper’s aim is to strengthen earlier results on the probability of block decoding error for polar codes.The introduction frames the reliability analysis as an improvement over the results of.
  • I. INTRODUCTION: I(W) is the symmetric capacity of a binary-input DMC, while Z(W) measures channel reliability through an upper bound on single-use ML decision error.The analysis gives Z(W) a central role because it is more readily tractable than I(W).
  • A. A channel transform: The transform produces W− and W+ from W using two independent copies of the channel, with W+ more reliable and W− less reliable than W.The transform preserves symmetric capacity, while the reliability ordering supports the polarization analysis.

B. Polarization process

The polarization process is modeled by a random sequence of transformed channels and associated information and reliability processes. These processes converge, yielding almost-sure polarization and the basis for polar coding under successive cancellation decoding.

  • B. Polarization process: A random channel sequence {W_n} is generated by repeatedly applying the transform W ↦ (W−, W+) according to an i.i.d. Bernoulli sequence.The processes I_n := I(W_n) and Z_n := Z(W_n) track symmetric capacity and reliability along this random construction.
  • B. Polarization process: {I_n} is a bounded martingale and {Z_n} is a bounded supermartingale, with both converging almost surely.The convergence follows from general results for bounded martingales and supermartingales.
  • B. Polarization process: The limiting channels become perfect with probability I(W) and useless with probability 1 − I(W).Equivalently, Z_∞ = 0 with probability I(W) and Z_∞ = 1 with probability 1 − I(W).
  • C. Polar coding: Polar codes use block lengths N = 2^n and support encoding and successive-cancellation decoding complexity O(N log N).These complexity bounds hold uniformly over rates R ∈ [0, 1], although rates above I(W) have no practical relevance.
  • C. Polar coding: For any R < I(W), prior results selected a reliability threshold yielding only polynomially decreasing block error, Pe(N, R) = o(N^-1/4).The threshold was chosen as γ(N, R) = o(N^-5/4), together with the polar-code error bound Pe ≤ Nγ.

D. Summary of results

The paper strengthens prior polar-coding error bounds, proving a block-error exponent for rates below channel capacity and identifying limits on its rate dependence.

  • The result improves prior work by establishing the sharper error-probability guarantee as the paper’s main contribution.
  • For any B-DMC with I(W) > 0, rate R < I(W), and β < 1/2, the best polar-coding block error probability satisfies the paper’s stated bound.The theorem applies at block lengths N = 2^n under successive cancellation decoding.
  • Sharper asymptotic error results with refined dependence on R remain an open problem.
  • The converse analysis considers the complementary regime I(W) < 1 for fixed β > 1/2.

II. PROBLEM RESTATEMENT

The paper restates the polarization problem through a general class of supermartingales, separating the probabilistic core from the original information-theoretic setting.

  • The class Z contains processes starting in (0,1), measurable with respect to the filtration, and satisfying the paper’s prescribed trajectory conditions.
  • The abstract process class excludes z0 = 0 and z0 = 1 because those cases produce trivial processes.
  • Every process in Z is a bounded supermartingale that converges almost surely and in L1 to a limiting random variable.
  • The limit Z∞ is almost surely 0 or 1, derived from convergence in L1 and the vanishing of E[Zn(1 − Zn)].
  • Theorem 2 is proved through an equivalent formulation, with direct and converse parts established in separate sections.

IV. PROOF OF THE DIRECT PART

The direct proof establishes that 2^(-2βn) is asymptotically dominating for every process in Z when β < 1/2. It proceeds by reducing the claim to extremal processes and proving universal domination there.

  • A sequence is asymptotically dominating when it bounds the process in the required limiting probability sense, and universally dominating when every fixed shift remains asymptotically dominating.
  • The proof reduces domination over Z to universal domination over the subclass of extremal processes.
  • For every ρ ∈ (3/4, 1), ρ^n is asymptotically dominating for every extremal process.
  • The sequence {2^(-2nβ)} is shown to be universally dominating for extremal processes, completing the direct-part strategy.

A. Extremal processes

The paper defines extremal processes through a binary recursion and records their Markov and martingale structure. Their limiting distribution is concentrated on 0 and 1 with probabilities determined by the initial value.

  • The extremal process evolves by a binary recursion depending on B_n+1, with separate transformations for B_n+1 = 1 and B_n+1 = 0.
  • The notation {Z(z_0)_n} denotes the extremal process initialized at z_0.
  • An equivalent recursion uses the ±1-valued process X_n = 1 − 2B_n, emphasizing the extremal process’s symmetric form.
  • Every extremal process is a Markov process and a bounded martingale.
  • The limit satisfies P(Z∞ = 0) = 1 − Z_0 and P(Z∞ = 1) = Z_0.

B. A reduction argument

The reduction argument shows that universal domination for extremal processes implies asymptotic domination for all processes in Z. The proof conditions on a small value of the process and uses limiting arguments.

  • If {f_n} is universally dominating over extremal processes, then it is asymptotically dominating over the full class Z.
  • The proof fixes a process in Z and uses the conditional event Z_k ≤ δ to lower-bound P(Z_k+n ≤ f_k+n).
  • The limiting argument applies Fatou’s lemma and the almost-sure convergence of {Z_k} to the 0-1-valued limit Z∞.
  • Letting δ approach zero completes the proof of the reduction proposition.

C. An asymptotically dominating sequence

This section establishes an asymptotically dominating sequence for extremal processes. It derives a bound parameterized by ρ and then uses it to show that ρ^n dominates the process for ρ ∈ (3/4, 1).

  • For any ρ ∈ (3/4, 1), the sequence {ρ_n} is asymptotically dominating over the class of extremal processes.
  • An extremal process with initial value z_0 ∈ (0, 1) is fixed to establish the domination bound.
  • The extremal process is governed by a two-branch recursion based on B_n+1.
  • Lemma 2 defines f_n(ρ) using 1 − √(1 − 4ρ^n) when 1 − 4ρ^n > 0, and 1 otherwise.
  • For ρ ∈ (3/4, 1), the process satisfies Z_n ≺ f_n(ρ).
  • Monotonicity and the limiting probability bound imply the claimed domination by ρ^n.

D. A bootstrapping argument

The argument bootstraps a decay result from extremal processes to the full process class, then establishes the required asymptotic bound using interval-wise behavior.

  • D. A bootstrapping argument: The proof reduces almost-dominance over all processes to uniform dominance over the subclass of extremal processes.This reduction is stated as the bridge used to complete the direct part of Theorem 3.
  • D. A bootstrapping argument: 2^-2nβ is shown to be uniformly dominant for extremal processes for every β < 1/2.The proof first notes that fixed index shifts preserve the sequence up to Θ(2^-2nβ).
  • D. A bootstrapping argument: The construction fixes an extremal process and compares it with a process modified after time m.The modified process is defined using a fixed n and m, with subsequent updates determined by the Bernoulli branch.
  • D. A bootstrapping argument: Partitioning the indices into intervals controls the number of squaring and doubling operations on each interval with high probability.The event G has probability at least 1 − k2^-a_n[1−H(β)], and on G each interval contains at least a_nβ squarings and at most a_n(1−β) doublings.
  • D. A bootstrapping argument: With m = n^3/4 and ρ = 7/8, the reliability parameter satisfies log2 Z_m ≤ −n^3/4 log2(8/7) for sufficiently large n.Combining this estimate with the event probabilities yields Z_n ≺ 2^-2βn.

V. OPEN PROBLEMS

The paper identifies extensions to nonbinary input alphabets and more general mutual-information-preserving transforms, while noting that the current theorem only partially characterizes the desired asymptotics.

  • V. OPEN PROBLEMS: The ultimate goal is to determine an explicit function E(n,R) describing cumulative probabilities for channel-polarization processes.The target is posed for rates R in [0, 1].
  • V. OPEN PROBLEMS: Theorem 3 provides only a partial characterization of E(n,R).The stated limitation leaves the full asymptotic behavior unresolved.
  • V. OPEN PROBLEMS: For input alphabets of size q ≥ 2, an open problem is proving channel polarization to {0, log2 q} before determining its rate.The generalized process retains a conservation law and bounded-martingale structure.
  • V. OPEN PROBLEMS: For q ≥ 3, defining the auxiliary reliability process requires a new channel parameter, and the binary-case relations do not hold for the natural definition.Consequently, the process does not appear likely to facilitate analysis in that setting.
  • V. OPEN PROBLEMS: More general channel transforms preserving mutual information raise the open problem of identifying necessary and sufficient conditions for polarization.A ternary transform is given as an example, with branch capacities summing to three times the original capacity.
Loading 0807.3806v3…