PaperlayerView exact revision on arXiv

Source-linked AI summary

How to Construct Polar Codes

Ido Tal, Alexander Vardy

arXiv:1105.6164v3cs.IT

TL;DR

Straightforward polar-code construction is intractable because bit-channel output alphabets grow exponentially with code length. The paper replaces these channels with efficiently computed degraded and upgraded approximations, which closely sandwich the originals and support near-capacity construction with favorable complexity.

  • Problem

    Exponential bit-channel output-alphabet growth makes straightforward evaluation and ranking intractable despite polar codes having an explicit construction.

  • Method

    The paper uses degrading and upgrading quantizations to replace each bit-channel with a smaller-alphabet lower or upper approximation while controlling memory and fidelity.

  • Results

    For fixed ε > 0 and β < 1/2, sufficiently large codes achieve R ≥ I(W) − ε and Pblock ≤ 2^-nβ with O(n · µ2 log µ) construction time; a corollary gives O(n log^2 n log log n).

  • Takeaways & Limitations

    The approximations are typically very close in practice, enabling efficient polar-code construction with rates near channel capacity.

Abstract

from arXiv · show

A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with he code length. Thus the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which "sandwich" the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed, and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed $ε> 0$ and all sufficiently large code lengths $n$, polar codes whose rate is within $ε$ of channel capacity can be constructed in time and space that are both linear in $n$.

I. INTRODUCTION

The paper addresses the intractable output-alphabet growth that makes general polar-code construction difficult by introducing efficiently computable degrading and upgrading approximations. These bounds are typically very close, while the analysis establishes near-capacity construction with linear-time complexity for fixed parameters.

  • Motivation: Exponential output-alphabet growth makes straightforward evaluation of polar bit-channels intractable for all but the shortest codes.The construction is explicit, but each bit-channel’s output alphabet grows exponentially with code length.
  • Method: Degrading and upgrading quantizations replace each current channel with a smaller-alphabet channel that provides lower and upper error-probability bounds.The approximations preserve an ordering: the degrading channel is below the original, while the upgrading channel is above it.
  • Method: The approximation runtime for all n polar bit-channels is O(n · µ2 log µ), with larger µ generally providing better fidelity.The parameter µ controls the approximation fidelity and can be chosen as an arbitrary integer.
  • Empirical behavior: For n = 1,048,576 on BSC(0.11), 1,048,444 of 1,048,576 bit-channels are provably classified, leaving 132 uncertain cases with very small bound gaps.The computation uses µ = 256 and a 10^-9 bit-channel error threshold.
  • Empirical behavior: For n = 2^20 and target block-error bound 10^-6, the bounds yield rates 0.9732 and 0.9737 for BSC and 0.9580 and 0.9587 for binary-input AWGN.The lower achievable and upper impossible rates differ only slightly in both examples.
  • Theory: For fixed ε > 0 and β < 1/2, sufficiently large codes achieve rate R ≥ I(W) − ε and Pblock ≤ 2^-nβ with O(n · µ2 log µ) construction time.The required µ0 is independent of n, so fixing µ = µ0 makes the running time linear in n.
  • Theory: A corollary removes dependence on the fidelity parameter, giving construction time O(n log^2 n log log n) while retaining the same asymptotic rate and error guarantees.The result applies for all sufficiently large code lengths.
  • Scope: The theorem does not specify how large n must be for the stated rate and block-error guarantees to hold.The paper identifies this threshold as a central question and notes related polynomial bounds from later work.

II. POLAR CODES

Polar-code construction selects the best bit-channels produced by recursive channel transformations. Although the channels are explicitly defined, their exponentially large output alphabets make direct ranking impractical, motivating approximation methods.

  • Polar bit-channels: A length-n polar code transforms n independent uses of a binary-input symmetric channel into n binary-input polar bit-channels.Each bit-channel includes the channel output and previously decoded input bits in its output.
  • Construction criterion: The decision error probability is defined under maximum-likelihood decisions with uniformly distributed input bits and arbitrary tie breaking.This is the error criterion used for successive cancellation decoding.
  • Construction criterion: Constructing a dimension-k polar code amounts to selecting the k best bit-channels, ranked here directly by probability of decision error.The selected channels form the information set, while the remaining channels are frozen.
  • Construction difficulty: Each bit-channel’s output alphabet is exponential in n, making straightforward evaluation of the ranking criterion intractable except for very short codes.The section identifies circumventing this explosion as the main construction objective.
  • Polar bit-channels: The bit-channels are constructed recursively through Arıkan channel transformations whose output alphabets grow by roughly squaring at each application.This gradual growth underlies the later approximation strategy.

III. CHANNEL DEGRADATION AND UPGRADATION

The paper formalizes degraded and upgraded channels as ordered approximations of a BMS channel, preserving useful inequalities for error probability, Bhattacharyya parameter, and capacity. Equivalent channels can also be normalized without changing these relations.

  • Definitions: A channel Q is degraded with respect to W when an intermediate channel can post-process W’s outputs to produce Q.The relation is written Q ≼ W.
  • Definitions: An upgraded channel Q′ is one that can be degraded to W through an intermediate channel.The relation is written Q′ ≽ W.
  • Relations: Degrading and upgrading are transitive and reflexive, while a channel equivalent to W is both degraded and upgraded with respect to W.The paper therefore treats equivalence as a symmetric, transitive, and reflexive relation.
  • Monotonicity: Under degradation, error probability increases while capacity and related channel-quality quantities obey the corresponding monotonicity inequalities.The paper identifies equation (15) as the key relation for its construction analysis.
  • Channel normalization: Replacing a self-conjugate output symbol by two new symbols yields an equivalent BMS channel with no self-conjugate symbols.Repeating the construction removes all such symbols without changing channel equivalence.
  • Channel normalization: The construction assumes BMS channels with finite output alphabets and later removes self-conjugate symbols while preserving the relevant channel relations.Likelihood ratios are then associated with each output symbol for subsequent quantization procedures.

IV. HIGH-LEVEL DESCRIPTION OF THE ALGORITHMS

The algorithms approximate each polar bit-channel with a manageable-alphabet degraded or upgraded channel, preserving the relevant ordering relations through recursive transformations. These approximations support conservative code construction and bracket the exact achievable rate.

  • Approximation procedures: A degrading merge outputs a BMS channel Q with Q ≼ W and alphabet size at most µ; upgrading_merge satisfies the analogous upgraded relation.These properties define the required interfaces for the two merging functions.
  • Approximation procedures: Algorithms A and B recursively construct degraded and upgraded approximations of each bit-channel while reducing every intermediate alphabet to at most µ.The recursive constructions reduce intermediate channels from at most 2µ^2 symbols to at most µ.
  • Correctness: The degradation and upgrading relations are preserved by the channel transformations, so Algorithm A yields a degraded approximation and Algorithm B an upgraded approximation of the corresponding bit-channel.Proposition 6 establishes this by induction using Lemma 5.
  • Code construction: The degraded construction selects indices using computable upper bounds on bit-channel error probabilities, while the upgraded construction supplies the corresponding opposite rate bound.The resulting rates satisfy Rupgraded ≥ Rexact ≥ Rdegraded.
  • Complexity: The total approximation time is O(n · µ^2 log µ), while a more detailed analysis reduces the all-bit-channel construction cost relative to the naive O(nmτ) bound.The approximation parameter µ controls fidelity and computational cost.

V. MERGING FUNCTIONS

The paper specifies degrading_merge and upgrading_merge as alphabet-reduction interfaces, initially treating their concrete implementations heuristically before analyzing them formally.

  • Merging functions: The merging functions reduce a channel’s output alphabet while producing either a degraded or upgraded version of the original channel.Their formal analysis is deferred to a later section.

A. Degrading-merge function

The degrading_merge function repeatedly merges adjacent likelihood-ratio-ordered symbol pairs to obtain a degraded channel with a prescribed alphabet bound. A linked-list and heap implementation makes this reduction efficient, with total running time O(L · log L).

  • Motivation and complexity: The method is sub-optimal in capacity compared with Kurkoski and Yagi’s strategy, but has lower stated complexity.The paper contrasts O(µ^2 log µ) for its implementation with O(µ^5) for the cited degrading method.
  • Single merge: Merging two output symbols by Lemma 7 produces a channel Q degraded with respect to W.The merged probabilities add the two symbols’ conditional probabilities.
  • Merge selection: The algorithm repeatedly chooses the adjacent pair whose merge yields the largest resulting capacity and continues until the alphabet size is at most µ.Only L−1 adjacent pairs are considered at each stage rather than all possible pairs.
  • Implementation: The data structure stores adjacent likelihood-ratio pairs and their capacity penalties, with linked-list pointers tracking neighbors and heap operations selecting the minimum penalty.The fields a, b, a′, and b′ store the four conditional probabilities used by calcDeltaI.
  • Implementation: The degrading_merge implementation runs in O(L · log L) time after sorting likelihood-ratio pairs and updating the heap during merges.The heap supports constant-time getMin and logarithmic-time updates.
  • Merge ordering: For symmetric channels, merging same-sign likelihood-ratio symbols has capacity penalty at least as small as merging opposite-sign symbols.Theorem 8 states I(ȳ_i,ȳ_j)=I(y_i,y_j) ≥ I(y_i,ȳ_j)=I(ȳ_i,y_j).

B. Upgrading-merge functions

The paper develops two upgrading merge methods that reduce a BMS channel’s output alphabet while preserving an upgraded relation to the original channel. The second method is generally more faithful, but the first remains useful when likelihood-ratio conditions make the second unstable or inapplicable.

  • First upgrading method: The first upgrading method merges two output-symbol pairs and produces an upgraded channel Q′ with an alphabet smaller by 2.The construction introduces an intermediate channel P to establish Q′ ≽ W.
  • Second upgrading method: The second method redistributes probability across higher- and lower-likelihood-ratio symbol pairs before merging them.It applies Lemma 11 to three symbols and constructs Q′ by modifying the corresponding output probabilities.
  • Second upgrading method: Lemma 11 guarantees that the resulting channel Q′ is upgraded with respect to W.An intermediate channel P verifies the upgrading relation.
  • Comparison of methods: The first method is required when likelihood ratios are repeated or numerically too close, because the second method can become undefined or unstable.Floating-point subtraction is a stated source of numerical instability in these cases.
  • Implementation: The upgrading procedure first removes nearly equal adjacent likelihood ratios, then repeatedly chooses the three-symbol merge with the smallest capacity increase.The preliminary threshold uses ε = 10^-3, and the process continues until the output alphabet reaches the target size µ.
  • Complexity: Approximating one bit-channel takes O(m · µ^2 log µ) time, while approximating all n bit-channels takes O(n · µ^2 log µ) time.The latter bound accounts for the 2n − 2 distinct channels that must be approximated.

VI. CHANNELS WITH CONTINUOUS OUTPUT ALPHABET

The continuous-output construction transforms a BMS channel with real-valued outputs into a finite-output channel using likelihood-ratio-based partitions. The assumptions and notation are chosen to cover the BAWGN channel.

  • Continuous-output setting: The section provides degrading and upgrading transforms from continuous-output BMS channels to channels with a specified finite output alphabet.These transforms enable the finite-alphabet construction algorithms to be applied afterward.
  • Channel assumptions: The underlying channel is assumed to have real outputs with conditional probability-density functions f(y|0) and f(y|1).Symmetry and an additional notational condition are imposed on the channel.
  • Scope: The assumptions in this section hold for the BAWGN channel after relabeling input 0 as −1.
  • Likelihood-ratio representation: The likelihood ratio λ(y) is defined for y ≥ 0 and satisfies λ(y) ≥ 1 under the stated symmetry convention.Infinite and zero-density cases receive explicit definitions.
  • Likelihood-ratio partition: The partition uses µ = 2^ν output symbols and relies on the capacity function C[λ] being strictly increasing for λ ≥ 1.The resulting sets A_i must be sufficiently well behaved, as they are for the BAWGN channel.

A. Degrading transform

The degrading transform partitions the continuous output space into likelihood-ratio regions and replaces each region with a representative output pair. The resulting finite channel is degraded with respect to the original channel, with a bounded capacity loss.

  • Construction: The degrading transform applies a continuous analogue of the pair-merging operation across ν likelihood-ratio regions.The degraded approximation Q has a finite output alphabet of paired symbols.
  • Construction: The channel Q is explicitly defined by aggregating the original density over each partition set A_i.The construction uses the density f(y|0) in the region probabilities.
  • Guarantee: Q is a BMS channel satisfying Q ≼ W, so it is degraded with respect to the continuous-output channel W.An intermediate channel P from real outputs to the finite alphabet establishes the degradation relation.
  • Capacity loss: The capacity loss from degrading Q relative to W is bounded by Lemma 16.The preceding proof derives the bound by comparing capacities over the partition regions.

B. Upgrading transform

The upgrading transform constructs a finite-alphabet BMS channel that is upgraded with respect to the original channel, while bounding the capacity increase caused by approximation. It uses likelihood-ratio-based symbol transformations and repeated operations to obtain a manageable representation.

  • Upgrading transform: The upgraded output alphabet is paired as Z′ = {z1, z̄1, z2, z̄2, …, zν, z̄ν}.The construction assigns paired symbols to likelihood-ratio intervals.
  • Upgrading transform: Q′ is a BMS channel satisfying Q′ ≽ W, so it is an upgraded approximation of W.The proof supplies an intermediate channel whose cascade with Q′ recovers W.
  • Upgrading transform: The procedure applies a renaming channel followed by a likelihood-ratio reducing channel to realize the upgraded approximation.P1 maps output symbols into interval representations, while P2 redistributes mass using pα.
  • Upgrading transform: The resulting output density is shown to equal the original density f(y|0), with the other cases handled similarly.The proof verifies this by analyzing the concatenation Q′, P1, and P2 over each interval Ai.
  • Upgrading transform: The upgrading operation increases capacity by at most 1/ν.The capacity difference is bounded using the upgraded relation and a direct bound on the approximation loss.

VII. VARIATIONS OF OUR ALGORITHMS

The paper develops variations of its construction algorithms, including a specialized algorithm for upper-bounding bit-channel error probabilities. This specialization supports practical code construction and yields bounds that improve on the original algorithm.

  • Algorithm D: Algorithm D specializes Algorithm A to compute only the upper bound on each bit-channel’s error probability.It uses the Bhattacharyya parameter and takes a BMS channel, alphabet bound µ = 2^ν, code length n = 2^m, and index i as input.
  • Algorithm D: Algorithm D’s bound is always at least as good as Algorithm A’s bound.The theorem compares the outputs p̂A and p̂D for the same channel, length, index, and fidelity parameter.
  • Algorithm D: The algorithm tracks successive channel transformations W^(j) determined by the binary digits of the bit-channel index.Starting from W^(0) = W, each iteration applies one of two transformations until W^(m) equals the target bit-channel.
  • Numerical comparison: Table I compares lower bounds from Algorithm B with upper bounds from Algorithms A and D for fixed channel, length, and rate settings.The table uses W = BSC(0.11), n = 2^20, and rate k/n = 445340/2^20 = 0.42471.
  • Numerical comparison: The paper states that Algorithm D’s upper bound is always superior in the reported table comparison.This improvement is obtained by specializing the calculation to the probability-of-error attribute needed for channel selection.

VIII. ANALYSIS

The analysis proves that the proposed construction is essentially optimal for moderate fidelity parameters and establishes asymptotic capacity-achieving performance with efficient computation. The theorem does not specify how large the code length must be before these guarantees apply.

  • VIII. ANALYSIS: The construction is essentially optimal for moderate values of the fidelity parameter µ.Algorithm D constructs the code, while Algorithm B gauges the gap from the optimal construction.
  • VIII. ANALYSIS: For β < 1/2, the fraction of polar bit-channels with error probability below 2^−nβ tends to channel capacity as n grows.For β > 1/2, that fraction is strictly less than capacity, so the restriction in Theorem 1 cannot be relaxed.
  • Theorem 1: The construction algorithm runs Algorithm D on all n bit-channels, sorts their error bounds, and selects the largest information set whose summed bounds are below 2^−nβ.The selected rows form the generator matrix, and the total running time is O(n · µ^2 log µ).

APPENDIX A PROOF OF THEOREM 8

The appendix analyzes capacity loss from merging probability pairs and derives properties that support the upgrading construction. Its lemmas establish nonnegativity, order-sensitive merge behavior, and monotonicity of the merge penalty.

  • Merge penalty: The capacity contribution of a probability pair is defined through C(a,b), and merging two pairs incurs penalty Δ = C(a1,b1) + C(a2,b2) − C(a1+a2,b1+b2).This penalty measures the capacity difference caused by replacing two symbols with their merged symbol.
  • Merge penalty: Merging probability pairs cannot increase capacity, so the merge penalty is nonnegative.This property is formalized in Lemma 23 and used repeatedly in later monotonicity arguments.
  • Merge order: The total capacity loss is invariant to whether the first or second adjacent pair is merged before the remaining pair.Lemma 24 equates the two possible orders of merging three probability pairs.
  • Notation: A probability pair is represented by a probability sum π = a + b and likelihood ratio λ = a/b.The representation can be converted back using a = λπ/(λ + 1) and b = π/(λ + 1) when λ is finite.
  • Monotonicity: The merge penalty increases monotonically with either input probability sum.Lemma 25 reduces the proof to one argument using symmetry and then converts between the likelihood-ratio and probability-pair representations.
  • Application: The appendix uses these properties to prove an ordering relation among symbol mutual informations, including I(yj,yk) ≥ I(yi,yk) under the stated likelihood-ratio conditions.The ordering follows from the merge-penalty lemmas and supports the structural claims used by the upgrading procedure.

APPENDIX B PROOF OF THEOREM 13

The appendix proves Theorem 13 by reducing its claim to monotonicity properties of a capacity-difference expression. It treats separately the cases λ3 < ∞ and λ3 = ∞, using positivity of an intermediate term in the finite case.

  • Preliminary step: The proof begins by validating the notation Δ[λ1; λ2, π2; λ3] and establishing that its arguments suffice to calculate the capacity difference.This preliminary lemma supports the subsequent proof of Theorem 13.
  • Case λ3 < ∞: For λ3 < ∞, the proof fixes λ2 and π2 and rewrites the claim in terms of f(λ1, λ3).The resulting function must be shown decreasing in λ1 and increasing in λ3 under λ1 < λ2 < λ3.
  • Case λ3 < ∞: To prove that f(λ1, λ3) decreases in λ1, the argument reduces the derivative condition to positivity of the term inside square brackets.The proof then states that the relevant term is positive for λ3 > λ1.
  • Case λ3 < ∞: The proof of increase in λ3 follows by the same argument after changing variable names.Thus both required monotonicity directions are handled in the finite-λ3 case.
  • Case λ3 = ∞: The appendix then starts the second case, λ3 = ∞, again fixing λ2 and π2 and treating Δ as a function of λ1.The supplied passage introduces this case but does not include its remaining calculations.
  • Monotonicity objective: The proof’s monotonicity objective is to show that h(λ1) is decreasing in λ1, with the relevant expression identified as negative.This statement appears as part of the monotonicity analysis accompanying Theorem 13.
Loading 1105.6164v3…