PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Length Scaling of Polar Codes

S. Hamed Hassani, Kasra Alishahi, Rudiger Urbanke

arXiv:1304.4778v4cs.IT

TL;DR

The paper asks how finite-length scaling of polar codes compares with the optimal inverse-square rate-gap behavior at fixed error probability. It analyzes the dynamics of unpolarized channels and derives universal bounds for BMS channels. Under a fixed sum-of-Bhattacharyya-parameters requirement, the blocklength has lower exponent 3.579 and upper exponent 6 in the rate gap.

  • Problem

    The paper asks whether capacity-achieving polar codes also have optimal finite-length scaling as R approaches I(W) at fixed error probability.

  • Method

    The paper analyzes the dynamics and speed of channel polarization, using unpolarized-channel behavior to derive bounds for BMS channels.

  • Results

    3.579 and 6 are the lower and upper scaling exponents for blocklength under the fixed sum-of-Bhattacharyya-parameters requirement.

  • Takeaways & Limitations

    Polar codes require a larger blocklength order than the best possible codes, whose finite-length benchmark has exponent 2.

Abstract

from arXiv · show

Consider a binary-input memoryless output-symmetric channel $W$. Such a channel has a capacity, call it $I(W)$, and for any $R<I(W)$ and strictly positive constant $P_{\rm e}$ we know that we can construct a coding scheme that allows transmission at rate $R$ with an error probability not exceeding $P_{\rm e}$. Assume now that we let the rate $R$ tend to $I(W)$ and we ask how we have to "scale" the blocklength $N$ in order to keep the error probability fixed to $P_{\rm e}$. We refer to this as the "finite-length scaling" behavior. This question was addressed by Strassen as well as Polyanskiy, Poor and Verdu, and the result is that $N$ must grow at least as the square of the reciprocal of $I(W)-R$. Polar codes are optimal in the sense that they achieve capacity. In this paper, we are asking to what degree they are also optimal in terms of their finite-length behavior. Our approach is based on analyzing the dynamics of the un-polarized channels. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of sub-channels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given value $P_{\rm e}>0$, then the required block-length $N$ scales in terms of the rate $R < I(W)$ as $N \geq \fracα{(I(W)-R)^{\underlineμ}}$, where $α$ is a positive constant that depends on $P_{\rm e}$ and $I(W)$, and $\underlineμ = 3.579$. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like $N \leq \fracβ{(I(W)-R)^{\overlineμ}}$, where $β$ is a constant that depends on $P_{\rm e}$ and $I(W)$, and $\overlineμ=6$.

I. INTRODUCTION

The introduction frames finite-length scaling as the relationship between blocklength and rate at fixed error probability, and asks how polar codes compare with optimal codes. It connects this question to the speed of channel polarization and develops universal scaling bounds for BMS channels.

  • Polar codes achieve capacity for a wide class of channels, including binary-input memoryless output-symmetric channels.
  • Fixed-error scaling asks how the required blocklength varies with rate, a practically relevant alternative to studying error exponents.The practical goal is to find the shortest code meeting a prescribed error probability at a target rate.
  • Θ(1/(I(W)-R)^2) is the benchmark order for the shortest blocklength achievable by general codes at fixed error probability.
  • The paper relates polar-code scaling to the dynamics and speed of channel polarization, especially the behavior of channels that remain unpolarized.
  • The construction recursively assigns split channels to an infinite binary tree, producing the sub-channels used by polar codes.

E. Polar Codes

Polar codes select the most reliable sub-channels for information transmission and use their polarization behavior to study finite-length performance. The section formulates the unresolved scaling questions and motivates analytical bounds based on the probability of remaining unpolarized.

  • Polar codes select N·R sub-channels with the smallest error probabilities as the good indices for transmission.Equivalent constructions may use Bhattacharyya parameter or entropy, but error-probability ordering supports union-type SC-decoding bounds.
  • The SC-decoded block error probability is bounded using the reliability of the selected sub-channels, and these bounds vanish for every R<I(W) as blocklength grows.
  • Pr(Z_n∈[a,b]) measures the fraction of sub-channels that remain insufficiently polarized and therefore retain relatively large Bhattacharyya parameters.
  • The central scaling question is how the blocklength N required for error probability below P_e depends on rate R for a fixed channel W.
  • The BEC permits closed-form polarization recursions, whereas other BMS channels require approximation methods to study the unpolarized-channel probability.

III. HEURISTIC DERIVATION FOR THE BEC

The BEC analysis models polarization through the polar operator and its finite-dimensional approximations, leading to a scaling assumption characterized by an exponent μ and function q. Numerical recursion estimates 1/μ ≈ 0.2757.

  • Polar operator: The polar operator T maps bounded functions on [0,1] to bounded functions and its iterates describe polarization dynamics.The analysis studies the limiting behavior and convergence speed of T^n(g).
  • Finite-dimensional approximation: Finite-dimensional discretization approximates T by an L × L matrix T_L whose dominant eigenvalue is 1.The discretized operator enables numerical study of subdominant eigenvalues and convergence rates.
  • Scaling assumption: The scaling assumption posits that Pr(Z_n ∈[a,b]) decays as 2^-n/μ with a positive limiting rescaled function q(z,a,b).The exponent μ is called the scaling exponent of polar codes for the BEC.
  • Numerical estimate: The resulting recursion estimates 1/μ ≈ 0.2757 for the BEC.The estimate is obtained by iterating a discretized functional recursion for q.

IV. ANALYTICAL APPROACH: FROM BOUNDS FOR THE BEC TO UNIVERSAL BOUNDS FOR BMS CHANNELS

This section establishes analytical bounds on the speed of polarization, first for the BEC and then for general BMS channels. Two complementary approaches use operator test functions and compositions of the polarization maps.

  • Scope: The section replaces the heuristic BEC picture with rigorous lower and upper bounds on polarization speed.The full heuristic picture is not proved, but the resulting bounds are intended to be useful.
  • BEC bounds: For the BEC, the polarization probability decays at a rate governed by an exponent μ whose reciprocal is numerically about 0.2757.The reported numerical value is approximately μ ≈ 3.627.
  • BEC bounds: The analysis seeks explicit lower and upper values for μ rather than assuming that the limiting exponent exists.The paper frames these bounds as analytical estimates of the speed of polarization.
  • Approaches: Two approaches are used: eigenvalue bounds from test functions and asymptotic analysis of compositions of z^2 and 2z−z^2.The second approach provides a good lower bound on μ.

1) First Approach:

The first analytical approach bounds polarization speed by selecting test functions for the polar operator and translating decay bounds into probabilities of remaining unpolarized. Polynomial and non-polynomial choices trade analytical tractability against nontrivial upper bounds.

  • Test-function framework: Test-function bounds analyze how quickly T^n(f) decays and convert that decay into bounds on Pr(Z_n ∈[a,b]).The framework defines recursive functions and sequences a_m and b_m to obtain lower and upper decay bounds.
  • Test-function choice: Indicator test functions are unsuitable for this technique because they yield trivial or undefined bounds.For f(z)=1{z∈[a,b]}, the text reports b_m=∞ and an undefined a_m.
  • Test-function choice: Polynomial test functions preserve tractability because T^n(f) remains polynomial, allowing bounds to be computed through polynomial roots.The basic choice f(z)=z(1−z) vanishes at z=0 and z=1.
  • Upper-bound limitation: Polynomial choices give b_m=1, so non-polynomial functions are needed for nontrivial upper bounds despite losing Sturm-chain tractability.The paper highlights this as a central computational limitation of the approach.

2) Second Approach:

The second approach studies random maps associated with channel polarization, showing that almost every realization develops a threshold and that these maps converge toward step-function behavior. This supports asymptotic analysis of the probability that the process remains away from the polarized endpoints.

  • The process Z_n is represented by repeatedly applying randomly selected maps from the set of n-step maps.
  • Almost every realization has a threshold point governing the asymptotic behavior of its sequence of polarization maps.
  • As n grows, the maps associated with a random realization converge point-wise to a step function.
  • The inverse-image intervals of map thresholds become short and are distributed nearly uniformly over [0,1].
  • The analysis yields precise asymptotic behavior for averages over z, although the corresponding point-wise heuristics cannot all be made rigorous.

B. Speed of Polarization for General BMS Channels

For general BMS channels, the paper bounds polarization speed by combining channel-process inequalities with suitable test functions and concavity arguments. These bounds are then connected to finite-length polar-code performance.

  • For BMS channels, the entropy process H_n is a martingale used to derive universal lower bounds on polarization speed.
  • A suitable integer m is one for which the recursively defined function f_m is concave on [0,1].
  • The paper verifies concavity through m = 10 and conjectures that it holds for every m.
  • For suitable m, the quantity a_m lower-bounds the polarization speed of H_n for every BMS channel.
  • The resulting polarization-speed bounds are used to relate channel dynamics rigorously to finite-length performance of polar codes.

C. Universal Bounds on the Scaling Behavior of Polar Codes

The paper bounds the blocklength required by polar codes under a strong reliability condition based on the sum of sub-channel error measures. The universal lower-bound exponent is 3.579, with improvements suggested by larger concavity orders, while polar codes remain less efficient than the optimal exponent 2.

  • The sum of individual sub-channel errors is used as a proxy for block-error probability under the strong reliability condition.
  • μ = 3.579 is the universal exponent in the lower-bound scaling result for polar-code blocklength.
  • μ_16 = 3.614 is obtained by increasing the concavity order, and the paper conjectures convergence to μ_∞ = 3.627.
  • The blocklength must be at least the lower-bound expression when the strong reliability condition is satisfied.
  • The optimal random-linear-ensemble exponent is μ = 2, so reliable polar-code transmission requires a larger blocklength at a given rate.

2) Universal Upper Bounds:

The section derives universal upper bounds on polar-code blocklength by bounding polarization speed for BMS channels and tracking sub-channels with small Bhattacharyya parameters. It concludes that polynomial blocklength in the reciprocal gap to capacity suffices under a fixed error requirement.

  • Proof strategy: The construction uses analytical polarization-speed bounds and a suitable choice of n1 to obtain enough highly polarized descendants.The proof combines bounds on the polarization process with counting arguments over descendants of A.
  • Scaling bound: For any BMS channel, the required blocklength N scales at most polynomially in the reciprocal gap I(W)−R.The bound follows from universal upper bounds on the speed of polarization.
  • Error criterion: The upper bound remains valid when Pe is replaced by the sum of Bhattacharyya values of the channels selected for information transmission.That sum is an upper bound on the block error probability under successive cancellation decoding.
  • Construction: The proof tracks sub-channels branching from a level-n0 set A containing more than an R fraction of sub-channels.The descendants are selected so their Bhattacharyya-parameter sum is below Pe while retaining at least rate R.
  • Construction: The resulting polar code has block error probability at most Pe at blocklength Ñ.The construction chooses Ñ = 2^(n0+n1) and establishes the required error bound through the selected sub-channels.

V. CONCLUSION

The conclusion gives lower and upper finite-length scaling bounds for polar codes under successive cancellation decoding, then compares them with optimal codes and identifies improving the scaling exponent as an open direction.

  • Main bounds: For fixed Pe measured by the sum of Bhattacharyya parameters, polar-code blocklength satisfies N ≥ α/(I(W)−R)^3.579.The constant α depends on Pe and I(W).
  • Main bounds: Polar codes require larger blocklength than the best possible codes, whose scaling exponent is 2.The comparison is presented as an explanation for the long blocklengths observed in numerical experiments.
  • Main bounds: A matching-direction bound gives N ≤ β/(I(W)−R)^6 for the same Bhattacharyya-sum requirement.The constant β depends on Pe and I(W).
  • Open directions: The paper identifies improving the finite-length performance and scaling exponent as an important theoretical and practical open question.Suggested approaches include better decoding algorithms, altered code constructions, concatenation, and larger kernels.
  • Open directions: Larger kernels may improve scaling but introduce decoding complexity of O(2^ℓN log N).The conclusion highlights the need to balance scaling exponent and reasonable complexity.

APPENDIX A PROOFS

The appendix passage states that a proof step follows directly from Markov's inequality.

  • Proof step: Markov's inequality is used to prove the stated bound.No further proof details are included in the passage.

1) Proof of Lemma 6:

This appendix proof develops interval-based dynamics for the polarization process, constructing paths and mappings that establish the required probability relations.

  • Conclusion: The argument combines interval inclusions, symmetry, and probability relations to establish the lemma's claimed bounds.The final steps derive the target relations from earlier interval-transition estimates.
  • Path mapping: A is defined as paths ending in one interval, while B is defined as paths ending in another interval.The proof decomposes A into disjoint sets Ak and constructs a one-to-one correspondence with a subset of B.
  • Path mapping: The recursive algorithm chooses branch values so the process eventually enters a target interval and remains there.Once the trajectory reaches the relevant interval, the proof shows subsequent iterates stay within it.
  • Process dynamics: The proof uses increasing maps t0 and t1 and their compositions to control polarization-process trajectories.The construction tracks how values move between specified intervals under recursively chosen binary branches.
  • Reverse process: The reverse process is analyzed using inverse maps and symmetric Bernoulli variables, with Lebesgue measure shown to be invariant.The passage also states that this invariant measure is unique and ergodic.

4) Proof of Lemma 17:

The proof derives a contradiction by combining bounds on the process and its expectations, ultimately exceeding the channel capacity.

  • The argument combines inequalities involving H_n and conditional expectations to obtain a lower bound on E[1 − H_n].
  • The resulting bound gives E[1 − H_n] > I(W), contradicting the martingale identity E[1 − H_n] = I(W).

APPENDIX B AUXILIARY LEMMAS

The appendix develops auxiliary lemmas for analyzing stochastic processes associated with polarization, using run decompositions, embeddings, and asymptotic probability bounds.

  • The appendix introduces lemmas for the Bhattacharyya process Z_n and a generic stochastic process with Bernoulli-driven updates.
  • The final step sets N = 2^n and defines a set A together with its complement for the subsequent bound.
  • The process X_n is transformed into A_n = −log X_n, whose updates are doubling or decrementing according to the Bernoulli variable.
  • Bernoulli sequences are represented through runs, yielding a one-to-one description of realizations and an iid geometric run sequence under B_1 = 1.
  • The proof handles finite-run distributions by embedding finite events into longer sequences and using their monotonicity across n.
  • Bounds are derived separately for B_1 = 1 and B_1 = 0, then combined to complete the lemma with c_2 = 2^˜c.
Loading 1304.4778v4…