PaperlayerView exact revision on arXiv

Source-linked AI summary

Polarization for arbitrary discrete memoryless channels

Eren Sasoglu, Emre Telatar, Erdal Arikan

arXiv:0908.0302v1cs.IT

TL;DR

The paper asks whether binary-input channel polarization can extend to arbitrary discrete memoryless channels and thereby support capacity-approaching polar coding. It develops prime-alphabet, decomposed, and randomized constructions, showing polarization for q-ary and arbitrary DMCs, while preserving the reported error behavior and enabling approaches to true capacity.

  • Problem

    Binary channel polarization must be generalized to arbitrary finite input alphabets and to true, rather than only symmetric, channel capacity.

  • Method

    The paper adapts channel combining and splitting for prime q, decomposes composite alphabets, and uses random permutations or field operations for general q.

  • Results

    The proposed transformations polarize prime-input channels and, with randomization, all discrete memoryless channels; the randomized choice is needed only during code construction.

  • Takeaways & Limitations

    Nonuniform input distributions implemented through an expanded channel allow symmetric-capacity polarization methods to approach the true capacity of arbitrary discrete memoryless channels.

Abstract

from arXiv · show

Channel polarization, originally proposed for binary-input channels, is generalized to arbitrary discrete memoryless channels. Specifically, it is shown that when the input alphabet size is a prime number, a similar construction to that for the binary case leads to polarization. This method can be extended to channels of composite input alphabet sizes by decomposing such channels into a set of channels with prime input alphabet sizes. It is also shown that all discrete memoryless channels can be polarized by randomized constructions. The introduction of randomness does not change the order of complexity of polar code construction, encoding, and decoding. A previous result on the error probability behavior of polar codes is also extended to the case of arbitrary discrete memoryless channels. The generalization of polarization to channels with arbitrary finite input alphabet sizes leads to polar-coding methods for approaching the true (as opposed to symmetric) channel capacity of arbitrary channels with discrete or continuous input alphabets.

I. POLARIZATION

Binary channel polarization repeatedly transforms a channel into split subchannels that become almost perfect or almost pure noise, with the perfect-channel fraction approaching symmetric capacity. A martingale-based proof also establishes polarization and the associated error-probability behavior.

  • Construction: Polar codes use repeated applications of W 7→(W −, W +) to produce 2^n binary-input channels.The construction combines and splits channels recursively, generating all sign sequences after n levels.
  • Polarization: Except for a vanishing fraction, the synthesized channels are either almost perfect, with I(W^s) ≥ 1 − δ, or almost pure noise, with I(W^s) ≤ δ.This is the core polarization phenomenon.
  • Polarization: The fraction of almost perfect channels approaches the symmetric capacity because the split-channel mutual informations sum to 2^nI(W).The conservation identity follows inductively from I(W −) + I(W +) = 2I(W).
  • Proof strategy: A new Bhattacharyya-parameter proof is introduced because it generalizes to q-ary inputs, unlike the earlier binary-only lemma.The parameter relates channel reliability to mutual information through inequalities used in the polarization proof.
  • Error behavior: For any fixed rate below I(W), almost all good channels have Bhattacharyya parameters below 2^(−2^{nβ}) for β < 1/2 when n is sufficiently large.The Bhattacharyya parameter upper-bounds uncoded-transmission error probability, yielding the stated polar-code error behavior.

II. POLARIZATION FOR q-ARY INPUT CHANNELS

The paper adapts channel combining, splitting, and reliability measures to q-ary inputs, establishing the ingredients needed to extend polarization beyond binary channels. The average Bhattacharyya distance supplies an error-probability bound for q-ary channels.

  • q-ary construction: The q-ary construction modifies the binary transformation and Bhattacharyya parameter so the polarization lemmas apply to nonbinary input alphabets.This is intended to establish the q-ary analogue of the polarization condition and symmetric-capacity result.
  • Definitions: The input alphabet size is denoted q, and mutual information is normalized with logarithm base q so that 0 ≤ I(W) ≤ 1.The quantity I(W) is the symmetric capacity under uniformly distributed inputs.
  • Reliability measure: For each pair of input letters, the paper defines a Bhattacharyya distance and averages these pairwise distances to obtain a q-ary reliability measure.The restricted channel W^{x,x′} is formed by limiting the input alphabet to the selected pair.
  • Error bound: The average Bhattacharyya distance upper-bounds the maximum-likelihood error probability for one use of a q-ary channel.The bound is derived by averaging the conditional error probabilities over input letters.
  • Reliability measure: The q-ary mutual-information and Bhattacharyya relationships are summarized in Proposition 3, whose proof is deferred to the appendix.These relationships provide the analytic link needed for the generalized polarization argument.

A. Special case: Prime input alphabet sizes

For prime-sized input alphabets, a group-based modification of the binary polarization construction yields channel polarization with the same polarization rate and error-probability behavior as the binary case.

  • A. Special case: Prime input alphabet sizes: Prime input alphabets admit polarization through a construction analogous to the binary case, using a group operation on the input alphabet.The alphabet can be represented as the integers modulo q when q is prime.
  • A. Special case: Prime input alphabet sizes: The construction combines two independent copies of the channel and splits them into synthesized channels using the transformed inputs.The combined channel is defined by W2(y1, y2 | u1, u2) = W(y1 | u1 + u2)W(y2 | u2).
  • A. Special case: Prime input alphabet sizes: Theorem 1 states that this transformation polarizes all q-ary input channels when q is prime.The result establishes polarization in the sense of the binary proposition.
  • A. Special case: Prime input alphabet sizes: The resulting polar codes have the same rate of polarization as binary polar codes, including the stated block-error behavior.Theorem 1 explicitly identifies the rate with the binary case and refers to equation (5).
  • A. Special case: Prime input alphabet sizes: The prime-alphabet proof relies on relating the average Bhattacharyya parameter to a maximum pairwise Bhattacharyya distance.Lemma 4 supplies the needed implication when Zmax(W) is close to one.
  • A. Special case: Prime input alphabet sizes: The proof uses repeated squaring behavior for the Bhattacharyya parameter and bounds the minus-channel parameter by qZmax(W).For the plus branch, Zmax(W+) = Zmax(W)^2; the corresponding minus-branch bound is Zmax(W−) ≤ qZmax(W).

B. Arbitrary input alphabet sizes

The binary-style transformation is not sufficient for arbitrary alphabet sizes, but randomized permutations polarize all discrete memoryless channels while preserving the construction’s practical complexity order.

  • B. Arbitrary input alphabet sizes: The prime-alphabet proof depends critically on primality, and the same transformation can fail to polarize some composite-alphabet channels.A quaternary example shows both synthesized channels can remain statistically equivalent to the original channel.
  • B. Arbitrary input alphabet sizes: A fixed permutation does not generally ensure Z(W+) = Z(W)^2 because the relevant inner sum may depend on the input pair.This dependence prevents the binary proof from carrying over directly.
  • B. Arbitrary input alphabet sizes: Randomizing uniformly over input-alphabet permutations makes the average value of Z(W+) equal to Z(W)^2.The random permutation is chosen independently of the uniformly distributed inputs and revealed to the receiver.
  • B. Arbitrary input alphabet sizes: The randomized construction defines synthesized channels whose outputs include the channel observations together with the permutation and, for W+, the other input.The underlying combined channel uses W2(y1, y2 | u1, u2) = W(y1 | u1 + u2)W(y2 | π(u2)).
  • B. Arbitrary input alphabet sizes: For each internal recursion node, a suitable permutation can be found so that the plus-channel parameter satisfies Z(W+) ≤ Z(W)^2.At least one suitable transformation exists for every channel, so randomness is needed during code construction rather than encoding or decoding.
  • B. Arbitrary input alphabet sizes: Searching over permutations contributes worst-case complexity q!(N − 1) for a construction of size N.This counts testing all q! permutations at each of the N − 1 internal nodes.

A. Reduction of randomness

Randomization can be reduced while preserving polarization: a permutation fixing 0 suffices, and prime-power alphabets need only q−1 random values. The resulting transformation polarizes q-ary channels.

  • Randomness reduction: A uniformly chosen permutation fixing 0 yields Z(W +) = Z(W)^2 and polarizes the channel transformation.This reduces the randomness needed from permutations over q! possibilities.
  • Randomness reduction: For prime-power q, choosing R uniformly from the q−1 nonzero field elements is sufficient for polarization.The field structure enables this reduction, while prime q requires no randomization.
  • Randomized transformation: The mutual-information split preserves the total information, with 2I(W) = I(W −) + I(W +).The random variable R is included in the channel outputs of the split construction.
  • Randomized transformation: The randomized q-ary transformation defines W − and W + using modulo addition, multiplication by R, and the revealed random variable R.These channels are specified by transition expressions involving W(y1|u1 + u2) and W(y2|r · u2).
  • Further reduction: For odd-characteristic fields, the range of R can be reduced to (q −1)/2 elements by pairing each r with −r.Uniform selection over one representative from each pair still gives Z(W +) = Z(W)^2.

B. A method to avoid randomness

Composite input alphabets can avoid randomness by decomposing the channel into prime-sized component channels and polarizing them separately.

  • B. A method to avoid randomness: If q factors as q = ∏_{i=1}^L q_i, the uniformly distributed input can be represented by independent components with prime-sized alphabets.The component channels W^(i) incorporate the preceding components as additional inputs or side information.
  • B. A method to avoid randomness: Each decomposed channel W^(i) is polarized separately, using successive cancellation that decodes the components in order.All channels derived from W^(1) are decoded first, followed by those derived from W^(2), and so on.
  • B. A method to avoid randomness: Because every component alphabet has prime size, the multi-level construction requires no randomization.The construction replaces a composite-alphabet channel with a sequence of prime-input channels.

C. Equidistant channels

Equidistant channels have uniform pairwise Bhattacharyya parameters, and the deterministic polar transform preserves this property while polarizing them for any finite input size.

  • C. Equidistant channels: An equidistant channel has the same Z(W{x,x′}) for every pair of distinct input letters.The paper characterizes these channels as having a high degree of symmetry.
  • C. Equidistant channels: The deterministic mapping (u1, u2) 7→ (u1 + u2, u2) preserves equidistance in both W + and W −.This mapping polarizes equidistant channels regardless of the input alphabet size.

D. How to achieve channel capacity using polar codes

Non-uniform input distributions can be embedded into a uniformly driven expanded channel, allowing symmetric-capacity polar coding to approach the true capacity of arbitrary discrete memoryless channels.

  • D. How to achieve channel capacity using polar codes: A distribution PX can be induced from a uniform distribution on X′ when mPX(x) is an integer for every x.A deterministic map f : X′ → X assigns expanded input letters to the original channel inputs.
  • D. How to achieve channel capacity using polar codes: The constructed channel W′ preserves the mutual information of W under the chosen input distribution PX.W′ uses transition probabilities W′(y|x′) = W(y|f(x′)).
  • D. How to achieve channel capacity using polar codes: Using a rational PX that approximates the capacity-achieving distribution extends symmetric-capacity polarization to approach true channel capacity.Prime m can be used in the construction to avoid randomization.

E. Channels with continuous alphabets

The polarization method extends to channels with continuous output alphabets and can approximate desired continuous input distributions, including under constraints such as Gaussian channels with power limits.

  • The method applies to channels with continuous output alphabets with only minor notational changes.
  • For continuous input alphabets, the method of Section III-D can approximate any desired continuous input distribution.The passage includes additive Gaussian noise channels with input power constraints as an example.

A. Proof of Proposition 3

The proof establishes bounds for arbitrary input alphabet sizes by reducing the general case to binary-case results and using mutual-information and concavity arguments. It also handles permuted transformations uniformly.

  • A. Proof of Proposition 3: The proof reduces the general input-alphabet case to the established binary case and uses the symmetric cutoff rate bound to show it cannot exceed I(W).
  • A. Proof of Proposition 3: Mutual-information decomposition expresses the relevant terms through a genie-provided side-information pair whose value is log(q/2).The chain rule separates information in the side information from conditional information through the channel.
  • A. Proof of Proposition 3: Concavity arguments convert the expectation over pairwise channel parameters into the required bound, completing the proof of the corresponding proposition.The argument uses concavity of x 7→ 1 − x^2 and the identity Z(W) = E[Z(W_{X1,X2})].
  • A. Proof of Proposition 3: The proof bounds channel parameters using Kullback–Leibler divergence together with inequalities based on ln(x) ≤ x − 1 and an upper bound on W_x(y).
  • A. Proof of Proposition 3: The stronger result is shown for every permutation π, which implies the proposition and bounds the transformed Bhattacharyya parameter relative to Z(W).The upper bound uses direct summation estimates, while the reverse inequality follows from concavity of Z(W_{x,x′}) in W.
Loading 0908.0302v1…