PaperlayerView exact revision on arXiv

Source-linked AI summary

Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels

Erdal Arikan

arXiv:0807.3917v5cs.IT

TL;DR

The paper addresses the longstanding challenge of explicitly constructing capacity-achieving codes for binary-input memoryless channels with low encoding and decoding complexity. It introduces channel polarization and proves that polar codes approach symmetric capacity with O(N log N) complexity under successive cancellation decoding.

  • Problem

    Explicitly constructing provably capacity-achieving code sequences with low encoding and decoding complexity remains an open goal for binary-input discrete memoryless channels.

  • Method

    Channel polarization synthesizes N channels from N independent copies of a binary-input memoryless channel, enabling polar-code construction from the resulting polarized channels.

  • Results

    Polar coding achieves rates approaching I(W), while recursive construction provides low-complexity encoding and decoding algorithms.

  • Takeaways & Limitations

    Polar codes provide an explicit capacity-achieving construction for binary-input memoryless channels with encoding and decoding complexity O(N log N).

  • Takeaways & Limitations

    The exact asymptotic rate of channel polarization remains unknown, because the paper establishes only an ad hoc asymptotic-rate result sufficient for its capacity theorem.

Abstract

from arXiv · show

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 $\{W_N^{(i)}:1\le i\le N\}$ such that, as $N$ becomes large, the fraction of indices $i$ for which $I(W_N^{(i)})$ is near 1 approaches $I(W)$ and the fraction for which $I(W_N^{(i)})$ is near 0 approaches $1-I(W)$. The polarized channels $\{W_N^{(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 $\{{\mathscr C}_n;n\ge 1\}$ such that ${\mathscr C}_n$ has block-length $N=2^n$, rate $\ge R$, and probability of block error under successive cancellation decoding bounded as $P_{e}(N,R) \le \bigoh(N^{-\frac14})$ independently of the code rate. This performance is achievable by encoders and decoders with complexity $O(N\log N)$ for each.

N ) is near 1 approaches I(W ) and the fraction for which I(W (i) … 1) Channel combining:

The paper constructs polar codes by recursively combining and splitting B-DMCs into polarized coordinate channels, enabling explicit capacity-achieving codes with successive-cancellation decoding and O(N log N) complexity. As N grows, nearly all synthesized channels have symmetric capacity near 0 or 1, with the near-1 fraction approaching I(W).

  • N ) is near 1 approaches I(W ) and the fraction for which I(W (i): The fraction of synthesized channels with capacity near 1 approaches I(W), while the fraction with capacity near 0 approaches 1 − I(W).These polarized channels support sending data through near-1 channels and no data through the remaining channels.
  • N ) is near 1 approaches I(W ) and the fraction for which I(W (i): The paper proves that for I(W) > 0 and any R < I(W), polar codes have N = 2^n, rate ≥ R, and P_e(N,R) ≤ O(N^-1/4).The bound is independent of code rate, and encoders and decoders each have complexity O(N log N).
  • I. INTRODUCTION AND OVERVIEW: The paper targets explicit capacity-achieving code sequences for B-DMCs with low encoding and decoding complexity, addressing a limitation of Shannon’s random-coding existence proof.The stated goal is to meet this construction challenge for the class of B-DMCs.
  • A. Preliminaries: I(W) is the highest reliable communication rate when a B-DMC’s binary input letters are used with equal frequency.The paper uses I(W) as the symmetric-capacity measure of rate.
  • B. Channel polarization: Channel polarization manufactures N channels from N independent copies of W whose symmetric capacities tend toward 0 or 1 except for a vanishing fraction.The operation has separate channel-combining and channel-splitting phases.
  • 1) Channel combining:: Channel combining recursively merges two independent copies of W_N/2 to produce W_N for block-lengths N = 2^n.The recursion starts with W_1 = W and constructs a vector channel W_N.
  • 1) Channel combining:: The combining transform maps s_2i−1 = u_2i−1 ⊕ u_2i and s_2i = u_2i, followed by the reverse-shuffle permutation.The resulting vector becomes the input to the two recursive W_N/2 copies.
  • 1) Channel combining:: The overall linear mapping from synthesized-channel inputs to raw-channel inputs is represented by G_N, which equals B_N F^⊗n for N = 2^n.B_N is the bit-reversal permutation matrix, and F specifies the channel-combining operation.

2) Channel splitting: … 2) A successive cancellation decoder:

The paper defines split channels through successive cancellation and proves that their capacities polarize, enabling polar codes that use only reliable coordinates. It then specifies GN-coset codes and an efficient successive cancellation decoder for these constructions.

  • 2) Channel splitting:: Channel splitting defines W_N^(i) as the effective channel observed when the ith decision element estimates u_i after receiving y^N and prior decisions.A genie supplies earlier decisions correctly, and u_1^N is assumed a-priori uniform.
  • 3) Channel polarization:: For any B-DMC and fixed δ ∈ (0, 1), the fraction of split channels with capacity in (1 − δ, 1] approaches I(W), while the fraction in [0, δ) approaches 1 − I(W).The limits hold as N grows through powers of two.
  • 3) Channel polarization:: For a BEC with ε = 0.5, computed capacities illustrate polarization toward values near 0 and 1, with erratic behavior at intermediate indices.The recursive computation is valid only for BECs; no efficient algorithm is known for calculating all capacities for a general B-DMC.
  • 4) Rate of polarization:: For any B-DMC with I(W) > 0 and fixed R < I(W), sets A_N exist with |A_N| ≥ NR and Z(W_N^(i)) ≤ O(N^-5/4) for every i ∈ A_N.The result is stated using Bhattacharyya parameters because that form supports the coding results.
  • C. Polar coding: Polar coding accesses each coordinate channel individually and sends data only through those whose Bhattacharyya parameters Z(W_N^(i)) are near 0.The construction restricts block-lengths to powers of two, N = 2^n.
  • 1) GN-coset codes:: GN-coset codes use an information set A for free source bits and fix u_Ac as frozen bits, with parameter vector (N, K, A, u_Ac) and rate K/N.The codeword mapping is generated using the corresponding rows of G_N.
  • 2) A successive cancellation decoder:: The successive cancellation decoder estimates u_i in order from 1 to N, setting the frozen coordinates to their known values and decoding the information coordinates.A block error occurs when the estimated vector differs from the transmitted vector, equivalently when the information vector is decoded incorrectly.
  • 2) A successive cancellation decoder:: SC decision functions are suboptimal relative to exact ML decisions because future frozen bits are treated as random variables, but recursive formulas make them efficiently computable.The recursive structure also supports performance analysis.

3) Code performance: … II. RECURSIVE CHANNEL TRANSFORMATIONS

The paper develops polar codes by recursively decomposing blockwise channel transformations, selecting channel-specific information sets, and establishing capacity-achieving performance with efficient encoding and decoding. It also relates polar coding to Reed–Muller, multilevel, and spectral code constructions.

  • 3) Code performance:: Polar-code information sets are chosen from K-subsets using Bhattacharyya parameters, yielding an explicit block-error bound and defining the polar-code construction.The frozen vector remains unspecified and may be chosen freely.
  • 4) Polar codes:: Polar codes are channel-specific designs intended to achieve the symmetric capacity I(W) of any given B-DMC W.A polar code for one channel need not be a polar code for another.
  • 5) Coding theorems:: For fixed R < I(W), Theorem 3 bounds block error probability under successive cancellation decoding for polar coding over any given B-DMC W.The stated performance is defined using the polar coding rule and averaging over frozen-bit choices.
  • 5) Coding theorems:: For symmetric B-DMCs, Theorem 4 extends the result to any fixed frozen vector in GN-coset code sequences with K = ⌊NR⌋ and R < I(W).For symmetric channels, I(W) equals the Shannon capacity.
  • 6) Complexity:: O(N log N) is the encoding complexity for GN-coset codes as a function of block-length N.The same complexity applies to successive cancellation decoding, independently of code rate and frozen-vector selection.
  • D. Relations to previous work: Polar and Reed–Muller codes are alternative rules for selecting the information set of GN-coset codes with the same block-length N and dimension K.RM codes belong to the GN-coset-code class because GN and F ⊗n have the same rows in a different order.
  • D. Relations to previous work: Polar codes are multilevel |u|u + v| constructions formed by expurgating rows of GN according to a channel-specific criterion.The structure of GN preserves the multilevel form regardless of how expurgation is performed.
  • II. RECURSIVE CHANNEL TRANSFORMATIONS: The blockwise transformation of N independent copies of W recursively decomposes into single-step channel transformations arranged in butterfly patterns.Each step doubles the number of channel types while halving the number of independent copies.

III. TRANSFORMATION OF RATE AND RELIABILITY · A. Local transformation of rate and reliability

The paper analyzes the local channel transform to show how it preserves symmetric capacity while separating channel rates and improving reliability. It then extends these properties to the recursively generated polarized channels and identifies the BEC as the equality case governing extremal behavior.

  • A. Local transformation of rate and reliability: The local transform preserves symmetric capacity while ordering the outputs as I(W′) ≤ I(W′′).Equality in the ordering holds only when I(W) is 0 or 1.
  • A. Local transformation of rate and reliability: For non-extreme W, the transform separates rates according to I(W′) < I(W) < I(W′′), thereby helping polarization.The transform leaves both capacities equal to I(W) only for perfect or completely noisy channels.
  • A. Local transformation of rate and reliability: Reliability can only improve under the single-step transform, with equality iff W is a BEC.The BEC is therefore singled out for its extremal reliability behavior.
  • A. Local transformation of rate and reliability: If W is a BEC with erasure probability ǫ, its transformed channels are BECs with erasure probabilities 2ǫ − ǫ2 and ǫ2.Conversely, if either transformed channel is a BEC, then W is also a BEC.
  • III. TRANSFORMATION OF RATE AND RELIABILITY: For N = 2^n and every index i, the recursive channel-splitting transform is rate-preserving and reliability-improving.The result is obtained as a special case of the local propositions, with cumulative relations following by repeated application of the single-step relations.
  • III. TRANSFORMATION OF RATE AND RELIABILITY: Channel splitting moves rates and reliabilities away from the center, while equality in the rate relations occurs only when I(W) equals 0 or 1.The corresponding cumulative reliability equality conditions are tied to the BEC.
  • A. Local transformation of rate and reliability: For a BEC, the transformed reliability parameters can be computed recursively, because Z(W_N^(i)) equals the erasure probability of W_N^(i).The recursive relations follow from the local BEC transform and its capacity-erasure correspondence.

IV. CHANNEL POLARIZATION · A. Proof of Theorem 1 · B. Proof of Theorem 2

The paper proves channel polarization by analyzing recursive channel transformations through martingale and supermartingale processes. It then establishes a polarization rate using bounds on the Bhattacharyya process, while noting that the resulting asymptotic-rate bound is ad hoc.

  • IV. CHANNEL POLARIZATION: The recursive channel construction is represented as a binary tree whose nodes correspond to synthesized channels generated by upper and lower transformations.A random path selects each upper or lower branch with probability 1/2, producing the processes K_n, I_n, and Z_n.
  • A. Proof of Theorem 1: The symmetric-capacity process {I_n} is a martingale that converges almost everywhere to I_∞ with E[I_∞] = I_0.The boundedness 0 ≤ I_n ≤ 1 yields uniform integrability and enables the convergence result.
  • A. Proof of Theorem 1: The Bhattacharyya process {Z_n} is a supermartingale converging almost everywhere to a limit Z_∞ that takes values in {0, 1}.The proof uses uniform integrability and shows E[Z_n(1−Z_n)] → 0, forcing the limit to be binary.
  • A. Proof of Theorem 1: The limiting capacity is binary, with P(I_∞ = 1) = I_0 and P(I_∞ = 0) = 1 − I_0.This follows from I_∞ = 1 − Z_∞ almost everywhere and E[I_∞] = I_0.
  • A. Proof of Theorem 1: As N tends to infinity, the synthesized capacities cluster around 0 and 1 except for a vanishing fraction.This establishes the channel-polarization conclusion of Theorem 1.
  • A. Proof of Theorem 1: For any B-DMC W, I(W) + Z(W) ≥ 1, with equality if and only if W is a BEC.The BEC minimizes Z(W) among channels with a given symmetric capacity and minimizes the capacity required for a given reliability level.
  • B. Proof of Theorem 2: Theorem 2 quantifies polarization by combining the recursive bounds on Z_{i+1} with a high-probability count of favorable branch choices.The argument uses Lemma 1 and Chernoff’s bound to obtain the desired asymptotic estimate.
  • B. Proof of Theorem 2: For n ≥ n1(δ), the proof concludes that |A_N| ≥ N(I_0 − δ) with N = 2^n, while the exact asymptotic polarization rate remains unresolved.The paper describes the bound as ad hoc but sufficient for proving a capacity theorem for polar coding.

V. PERFORMANCE OF POLAR CODING · A. A probabilistic setting for the analysis · B. Proof of Proposition 2

The section analyzes polar coding through a probabilistic ensemble of GN-coset codes and proves Proposition 2. It establishes the block-error decomposition and bound that support the paper’s main coding theorem.

  • V. PERFORMANCE OF POLAR CODING: Polar coding is analyzed over GN-coset codes with fixed (N, K, A) and freely varying frozen vector u_Ac.This ensemble formulation precedes specialization to polar codes.
  • A. A probabilistic setting for the analysis: The probabilistic setting treats the data vector and frozen vector as independent uniform random variables, averaging performance over the code ensemble.The frozen vector ranges over X^(N−K), while the data and frozen parts are uniformly distributed over their respective ranges.
  • A. A probabilistic setting for the analysis: The main event is block error under successive cancellation decoding, defined by an incorrect estimate of the data vector u_A.Errors in the frozen part are excluded because the decoder reproduces U_Ac with probability one.
  • B. Proof of Proposition 2: The block-error event is decomposed as E = ∪i∈A B_i, where B_i denotes the first successive-cancellation decision error at stage i.This converts block-error analysis into a union of first-error events.
  • B. Proof of Proposition 2: Each first-decision error event is contained in a corresponding event E_i defined through the single-bit decision rule h_i.The containment enables an upper bound on the probability of each stage’s error event.
  • B. Proof of Proposition 2: An upper bound on P(E_i) is obtained by summing the product-channel probability over the event E_i.The resulting expression is equivalent to equation (13).
  • B. Proof of Proposition 2: The proof of Proposition 2 is completed, after which the paper’s main coding theorem follows readily.The proposition supplies the central technical step for the performance analysis.

C. Proof of Theorem 3 … B. Proof of Theorem 4

The proofs establish polar-code performance through information-set selection and extend the analysis to symmetric channels. A numerical example shows capacity convergence with increasing block-length, but also that slow polarization limits practical near-capacity SC decoding.

  • C. Proof of Theorem 3: For any rate R < I(W), an information set of size at least NR exists, and the polar coding rule yields the required error bound.The rule minimizes the sum in the relevant bound, and combining this fact with Proposition 2 proves Theorem 3.
  • D. A numerical example: The numerical study examines how quickly polarization takes hold and what SC-decoding performance polar codes achieve outside the asymptotic regime.It addresses the previously unresolved exact asymptotic polarization rate through numerical evidence.
  • D. A numerical example: For a BEC with erasure probability 1/2, Figure 7 measures rate-versus-reliability trade-offs using polar codes at block-lengths N ∈{210, 215, 220}.The curves use threshold-defined information sets, with R(η) as code rate and B(η) as an upper bound on block-error probability under SC decoding.
  • D. A numerical example: The example provides empirical evidence of capacity achievement as block-length increases, while showing that polarization is too slow for practical near-capacity SC decoding.Capacity achievement is already established theoretically; the numerical result highlights the practical limitation.
  • VI. SYMMETRIC CHANNELS: Theorem 4 strengthens Theorem 3 for symmetric channels, beginning by showing that channel combining and splitting preserve the relevant symmetry properties.If W is symmetric, then the combined channel WN and split channels WN^(i) are also symmetric.
  • B. Proof of Theorem 4: For symmetric B-DMCs, the SC error events have a symmetry property, yielding error bounds that are independent of the frozen vector.Theorem 4 follows by combining Theorem 2 with Proposition 2, as in the proof of Theorem 3.
  • B. Proof of Theorem 4: The analysis does not claim that the entire error event is independent of the transmitted frozen vector because the decision rules break ties in favor of ûi = 0.Randomizing tie-breaking would make the error event independent of the frozen vector.

C. Further symmetries of the channel W (i)

The section exploits symmetries of the synthesized channels W_N^(i) to partition outputs into orbits and reduce their effective representation. It also gives channel-specific reductions for BSCs and BECs and states a simplified calculation of Z(W_N^(i)) for symmetric B-DMCs.

  • Orbit-based reduction: Output symmetries partition Y^N into equivalence classes, allowing W_N^(i) to be represented using one representative from each orbit.The orbit representatives form a reduced effective output alphabet for the synthesized channel.
  • BSC specialization: For a BSC, each orbit has 2^(N−i) elements and there are 2^i orbits, reducing W_N^(i)'s apparent output alphabet size from 2^(N+i−1) to 2^i.In particular, W_N^(1) has effectively two outputs and is itself a BSC.
  • BEC specialization: For a BEC, the synthesized channels remain BECs, each with an effective output alphabet size of three.This provides a further reduction beyond the general symmetry-based representation.
  • Bhattacharyya parameters: For any symmetric B-DMC W, Proposition 15 states that the parameters {Z(W_N^(i))} can be calculated using a simplified formula.The section notes that the formula specializes further for a BSC.

VII. ENCODING · A. Formulas for GN · B. Analysis by bit-indexing

The section derives algebraic and recursive forms of the polar-code generator matrix GN and analyzes encoding through bit-indexed permutations. It identifies BN as bit reversal, establishes equivalent generator factorizations, and characterizes row Hamming weights.

  • VII. ENCODING: The encoding analysis replaces the schematic construction of GN with explicit algebraic expressions and recursive formulas suited to efficient implementation.The derivation assumes N = 2^n and uses Kronecker products, identity matrices, and reverse-shuffle operators.
  • A. Formulas for GN: The generator matrix is factored using reverse-shuffle operations and a recursively defined permutation BN, which is shown inductively to be a permutation matrix.The factorization follows by repeatedly applying the Kronecker-product identity (AC) ⊗ (BD) = (A ⊗ B)(C ⊗ D).
  • B. Analysis by bit-indexing: Bit-indexing represents vector positions by binary expansions of i − 1 and matrix entries by paired binary index sequences.For i = 1 + Σ bj2^(n−j), the vector element ai is denoted ab1...bn, with an analogous notation for matrix entries.
  • B. Analysis by bit-indexing: Under bit-indexing, the Kronecker product and kernel F obtain componentwise descriptions that expose the encoding operation’s dependence on binary indices.The kernel entries satisfy Fb,b′ = 1 ⊕ b′ ⊕ bb′, while the Kronecker-product entries are indexed by concatenated bit sequences.
  • B. Analysis by bit-indexing: The reverse-shuffle operator RN cyclically rotates bit indexes of a row vector to the right by one position.It maps the element at position b1...bn to the element previously at b2...bnb1.
  • B. Analysis by bit-indexing: The recursively constructed BN is the bit-reversal operator, mapping each bit-indexed position b1...bn to bn...b1.The result is established inductively, with the B8 example showing how reverse shuffling and I2 ⊗ B4 produce bit reversal.
  • B. Analysis by bit-indexing: For N = 2^n, Proposition 16 gives GN = BNF ⊗n and GN = F ⊗nBN, with GN invariant under bit reversal.This follows because F ⊗n commutes with BN, which is itself a symmetric permutation matrix.
  • B. Analysis by bit-indexing: The rows of GN and F ⊗n indexed by b1...bn have Hamming weight 2^wH(b1,...,bn).Here wH(b1,...,bn) denotes the Hamming weight of the binary index sequence.

C. Encoding complexity … B. Refinement of the decoding algorithm

The paper establishes O(N log N) encoding and SC decoding complexity for polar-code constructions. It refines decoding by sharing likelihood-ratio computations, yielding N(1 + log N) calculations and supporting parallel implementations.

  • C. Encoding complexity: O(N log N) bounds the encoding complexity for block-lengths N = 2^n.The bound follows from a recurrence for worst-case encoding complexity.
  • C. Encoding complexity: O(N log N) is achieved by the encoder implementation using BN and F ⊗n.The implementation has O(N) complexity for BN and O(N log N) for F ⊗n.
  • VIII. DECODING: O(N log N) is the worst-case complexity established for successive cancellation decoding.The analysis uses a single-processor random-access-memory model and time complexity.
  • A. A first decoding algorithm: O(N^2) bounds the initial SC decoder when decision elements compute likelihood ratios privately.Pooling scratch-pad results enables the more efficient O(N log N) implementation.
  • B. Refinement of the decoding algorithm: N(1 + log N) is the total number of likelihood-ratio calculations required by the refined decoder.The count comes from reusing shared LR values across recursively smaller block-lengths.
  • B. Refinement of the decoding algorithm: 32 nodes represent the N(1+logN) LR requests in the refined decoder graph for N = 8.The example uses parameters (8, 5, {3, 5, 6, 7, 8}, (0, 0, 0)) and schedules computations depth-first.
  • B. Refinement of the decoding algorithm: Disjoint computational subtrees can run independently, while right-to-left scheduling starts computations as soon as right-side results finish.These structures support a high degree of parallelism and maximize exploitable parallel computation.

IX. CODE CONSTRUCTION

Code construction selects an information set of size K by ranking or estimating polarized-channel reliability parameters. Exact construction is generally inefficient, except for the BEC, motivating approximate statistical methods that exploit polarization and can use SC-decoder computations.

  • Problem formulation: The construction algorithm takes (W, N, K) and outputs an information set A of size K whose channels have the smallest possible aggregate reliability parameter.The frozen vector is excluded from construction because, for symmetric channels, its choice does not affect performance.
  • Exact construction: Exact construction would compute all {Z(W_N^(i))} and sort them, but no efficient algorithm is available for general symmetric channels.Available computational shortcuts for symmetric channels still do not yield an efficient algorithm.
  • Exact construction: O(N) computes all {Z(W_N^(i))} for the BEC using recursive formulas.The BEC is identified as the exception to the general difficulty of exact construction.
  • Approximate construction: Approximate construction turns selection into deciding whether each index i belongs to A_γ for a threshold γ, then varying γ until the desired size K is reached.This decision problem can be approached by statistically estimating the reliability parameters.
  • Approximate construction: As N grows, polarization makes threshold decisions easier because the reliability parameters increasingly cluster near 0 or 1.Monte Carlo estimates can be computed with O(N log N) complexity per sample using the decision statistics of an SC decoder with an empty information set.

X. A NOTE ON THE RM RULE … C. Iterative decoding of polar codes

The paper shows that RM information-set selection can be asymptotically unreliable under a specified SC decoder, while also surveying polarization-rate results, generalizations, robustness, and iterative-decoding directions. These discussions identify stronger bounds, broader constructions, and more powerful decoding as open research areas.

  • X. A NOTE ON THE RM RULE: The RM rule selects information indices by generator-row Hamming weight, including all indices with weight at least r and enough weight-r−1 indices to reach K.The rule applies to N = 2^n and sets frozen bits to zero.
  • X. A NOTE ON THE RM RULE: For fixed positive rate on a BEC, r(N)/n approaches 1/2, forcing the selected channel capacity I(W_0^{n−r−1r}) to approach zero as N grows.This concerns a sequence with K = floor(NR) and N increasing to infinity.
  • X. A NOTE ON THE RM RULE: Under SC decoding that randomizes over frozen-bit choices, RM assigns one information bit to a decision element whose channel capacity approaches zero, making the code sequence asymptotically unreliable.The result is specific to this SC decision metric and does not establish that RM codes are bad under every SC decoder or other decoding algorithms.
  • XI. CONCLUDING REMARKS: The concluding discussion reviews further results, generalizations, and open problems, including the unresolved question of how quickly polarization occurs with block length N.Recent work provides propositions strengthening the paper’s polarization-rate and error-probability results.
  • A. Rate of polarization: Polar coding is robust to channel-model mismatch when the design channel W is degraded from the actual channel W′, with performance at least as good on W′ as on W.This suggests graceful degradation from channel-modeling errors.
  • B. Generalizations: The polarization construction generalizes to q-ary channels by combining m copies through a kernel F_m, yielding block length N = m^n and O(N log N) encoding and SC-decoding complexity for unidirectional kernels.A sequence of kernels can further support block lengths N = product from i=1 to n of m_i while maintaining recursive channel formulas and O(N log N) complexity.
  • B. Generalizations: Further variants combine distinct DMCs or alter the connection structure, but their ability to produce channel polarization remains uncertain and is left for further research.The paper conjectures polarization may be common under sufficiently dense, suitably split constructions.
  • C. Iterative decoding of polar codes: Because SC decoding requires impractically large block lengths, the paper motivates more powerful iterative methods, including belief propagation enabled by the sparse graph of F^⊗n.A cited work proposes BP decoding for polar codes, and the factor graph for F^⊗3 is illustrated.

APPENDIX … C. Proof of Proposition 4

The appendix proves channel-capacity inequalities and recursive identities, then establishes Proposition 4 using mutual-information decompositions and characterizes its equality cases.

  • A. Proof of Proposition 1: Proposition 1’s proof identifies the right-hand side of (1) with Gallager’s E0(1, Q) for uniform input and uses I(W) ≥ E0(1, Q).This quantity is the symmetric cutoff rate of the channel.
  • A. Proof of Proposition 1: For any B-DMC W, Lemma 2 establishes I(W) ≤ d(W), where d(W) is the variational distance between W(y|0) and W(y|1).The proof bounds the relevant maximization by 2δ and derives the lemma’s claim.
  • B. Proof of Proposition 3: The proof of Proposition 3 derives identities (22) and (23) by reindexing the inner and outer sums and applying definition (5).The transformed variables range over the same set, allowing terms to be factored and definition (5) reused.
  • C. Proof of Proposition 4: For Proposition 4, the proof constructs uniformly distributed (U1, U2), transformed inputs (X1, X2) = (U1 ⊕ U2, U2), and outputs generated through two independent uses of W.An invertible mapping f converts (Y1, Y2) into ˜Y, defining W′′ through P˜Y U1|U2.
  • C. Proof of Proposition 4: Using independence, the chain rule, and the invertible input transformation, the proof shows I(X1X2; Y1Y2) = 2I(W).The equality follows from I(X1; Y1) + I(X2; Y2), with each term equal to I(W).
  • C. Proof of Proposition 4: The proof establishes I(W′′) ≥ I(W), and combines this with (24) to prove (25).Equality in (25) holds if and only if I(U2; Y1U1|Y2) = 0.
  • C. Proof of Proposition 4: Equality reduces to two cases: no y2 satisfies W(y2|0)W(y2|1) > 0, implying I(W) = 1, or W(y1|0) = W(y1|1) for all y1, implying I(W) = 0.The condition is obtained by substituting the channel factorization into the equality criterion and considering all four values of (u1, u2).

D. Proof of Proposition 5 … F. Proof of Lemma 1

The proofs establish key identities and equality conditions for the channel parameter Z(W), characterize when the transformed channel remains a BEC, and derive the finite-level probability bound needed for Lemma 1.

  • D. Proof of Proposition 5: Proposition 5 derives the identity Z(W′′) = Z(W)^2 and establishes the corresponding inequality for Z(W′).The proof expands the channel expressions using shorthand transition probabilities and applies an algebraic identity.
  • 1. Also,: Equality in the Proposition 5 inequality holds exactly when W is a BEC.The equality conditions reduce to either zero transition products or equal transition probabilities, and taking y1 = y2 yields the converse.
  • 1. Also,: The proof of the second inequality represents W′ as a channel mixture and uses convexity of Z(W) in the transition probabilities.Lemma 4 supplies the convexity step through a reformulation of Z(W) and Minkowsky’s inequality.
  • 1. Also,: The resulting bounds imply Z(W′) = Z(W′′) only when Z(W) is 0 or 1, equivalently when I(W) is 1 or 0.This follows from 0 ≤ Z(W) ≤ 1, Z(W′′) = Z(W)^2, and Proposition 1.
  • E. Proof of Proposition 6: A transformed channel W′ is a BEC if and only if the original channel W is a BEC.If W is a BEC, f(y1, y2) is erased exactly when either input output is erased; the converse follows by choosing y2 = y1.
  • E. Proof of Proposition 6: When W is a BEC with erasure probability ε, W′ has erasure probability 2ε − ε^2.The transformed output is an erasure whenever at least one of y1 or y2 is an erasure symbol.
  • F. Proof of Lemma 1: For any ζ > 0 and δ > 0, the proof of Lemma 1 obtains a finite m0 such that P[Tm(ζ)] ≥ I0 − δ/2 for all m ≥ m0.Paths in Ω0 eventually satisfy Zn(ω) ≤ ζ, and monotone convergence transfers P(Ω0) = I0 to the sets Tm(ζ).
Loading 0807.3917v5…