Source-linked AI summary
Source Polarization
Erdal Arikan
TL;DR
The paper addresses how source polarization can complement channel polarization for lossless source coding. It develops a direct polarization framework, analyzes its entropy and Bhattacharyya-parameter behavior, and applies it to coding with side information. The results establish source-polarization limits for binary sources and extend those limits to prime-sized non-binary alphabets, while the paper remains mostly focused on binary memoryless sources.
Problem
The paper studies source polarization as a complementary, direct alternative to reducing polar-code source coding to channel polarization through duality.
Method
The paper constructs source-polarization transforms, tracks conditional entropies using a tree process, and analyzes an accompanying supermartingale based on source Bhattacharyya parameters.
Results
The paper establishes source-polarization limits for binary alphabets and states that the same limits hold for memoryless sources over prime-sized alphabets using GF(q) operations and base-q entropy.
Takeaways & Limitations
Source polarization provides a direct basis for polar codes that achieve the lossless source-coding bound, including coding with side information.
Takeaways & Limitations
The paper is restricted mostly to binary memoryless sources, with non-binary generalizations indicated only briefly.
Abstract
from arXiv · showhide
The notion of source polarization is introduced and investigated. This complements the earlier work on channel polarization. An application to Slepian-Wolf coding is also considered. The paper is restricted to the case of binary alphabets. Extension of results to non-binary alphabets is discussed briefly.
I. INTRODUCTION
The paper introduces source polarization as a complement to channel polarization and presents a direct viewpoint for polar-code source coding. Its main scope is binary memoryless sources, with only brief discussion of non-binary generalizations.
- I. INTRODUCTION: Source polarization complements channel polarization and provides a direct, primal viewpoint for lossless source coding with polar codes.Earlier approaches reduced source coding to channel polarization through duality.
- I. INTRODUCTION: The paper focuses mostly on binary memoryless sources and briefly indicates possible generalizations to non-binary sources.
- I. INTRODUCTION: The notation follows earlier work, including u^N for a vector and u_j^i for a sub-vector.The logarithm is base 2 unless otherwise indicated, and Bernoulli variables and their entropy are also specified.
WITH SIDE INFORMATION
Source polarization recursively transforms binary sources with side information so conditional entropies become increasingly polarized while preserving total entropy. The resulting high-entropy indices support lossless source coding at rates above H(X|Y).
- Polarization theorem: Theorem 1 states that, as N grows, the conditional entropy terms polarize for binary sources with arbitrary countable side information.The theorem applies to sources defined by a binary X and an arbitrary countable Y.
- Basic transformation: The basic two-by-two transformation preserves entropy and further polarizes conditional entropies unless they are already 0 or 1.Equality occurs if and only if H(X|Y) equals 0 or 1.
- Recursive transformation: The four-by-four construction recursively applies the basic transformation to independent source copies, using a shuffled output order.This ordering creates paired substructures to which the two-by-two inequalities apply.
- Recursive transformation: Repeating the construction enhances polarization, although no general inequality orders H(U2|Y^4,U1) and H(U3|Y^4,U2).The four-output conditional entropies therefore require the recursive polarization argument rather than a simple pairwise ordering.
- General transformation: For N=2^n, the source transformation is U_N=X_NG_N, with G_N formed from a Kronecker power and bit-reversal permutation.The algebraic form matches the transformations shown in Figures 1 and 2.
- Polarization theorem: A source Bhattacharyya-parameter supermartingale tracks the transformation, while entropy–Bhattacharyya inequalities establish simultaneous polarization.The bounds Z(X|Y)^2 ≤ H(X|Y) and H(X|Y) ≤ log(1+Z(X|Y)) link the two parameters.
- Coding consequence: High-entropy sets select ⌈NR⌉ indices with the smallest Bhattacharyya parameters, and rates R>H(X|Y) yield a convergence rate for coding.The construction uses sets E_X|Y(N,R) ordered by their conditional Bhattacharyya parameters.
III. LOSSLESS SOURCE CODING
The paper presents a direct polar source-coding method that reaches the Slepian-Wolf lossless compression bound for binary sources with side information, using selected high-entropy indices. It provides successive decoding with exponentially decreasing error probability and O(N log N) encoding and decoding complexity.
- Compression method: The method compresses X^N to roughly NH(X|Y) bits while allowing recovery from the compressed word and side information Y^N.It uses a direct source-polarization argument rather than reducing source coding to channel coding through duality.
- Compression method: The encoder computes u^N = x^NG_N and outputs the bits indexed by the high-entropy set E_X|Y.The encoder does not require the realization of Y^N.
- Decoding: The decoder sequentially estimates u^N using the received selected bits and Y^N, then reconstructs x^N through G_N^-1.The likelihood computations are performed recursively for odd and even indices.
- Performance: For any fixed R > H(X|Y) and β < 1/2, the probability of error satisfies P_e = O(2^-N^β).The bound applies to the polar source-coding method described in the section.
- Complexity: Encoding and decoding both have complexity O(N log N).The stated complexity applies to the polar source-coding scheme.
IV. APPLICATION TO CHANNEL CODING: DUALITY
The source-coding construction is used to obtain a capacity-achieving code for binary-input memoryless channels through the duality between channel coding and source coding. The resulting scheme transmits data at rates above the conditional entropy threshold, with O(N log N) complexity.
- Channel-coding construction: The source-coding scheme designs a capacity-achieving code for any binary-input memoryless channel.The block code uses X^N = U^NG_N as the channel input vector and decodes data bits with the source decoder.
- Encoding: The encoder fixes selected bits for the decoder and fills the complementary positions with uniformly chosen data bits before computing X^N = U^NG_N.Approximately floor(NR) data bits are transmitted per round at rate roughly R.
- Decoding: The decoder applies the source decoder to Y^N and estimates the data bits in the complementary index set.The decoded data positions are U_Ec_X|Y.
- Performance: The scheme has complexity O(N log N).This complexity bound is stated for the channel-coding construction.
- Duality: The channel-coding reduction targets the symmetric capacity I(W) by converting the problem into source coding for a source induced by W with uniform input.The paper presents this as a dual approach that also provides an alternative proof of earlier channel-coding results.
V. SLEPIAN-WOLF CODING
The paper extends polar source coding to the Slepian-Wolf setting, where two encoders separately transform correlated binary sources and a common decoder reconstructs both. It achieves all points of the Slepian-Wolf rate region by combining corner-point schemes through time-sharing.
- Problem setting: The Slepian-Wolf setting uses two encoders observing X^N and Y^N separately, with a decoder that reconstructs both sequences.The achievable region requires R_x ≥ H(X|Y), R_y ≥ H(Y|X), and R_x + R_y ≥ H(X,Y).
- Corner-point construction: A polar scheme achieves the corner point (H(X|Y), H(Y)) using high-entropy sets E_Y and E_X|Y.The construction fixes R_y > H(Y) and R_x > H(X|Y).
- Encoding: Encoder 1 sends u_E_X|Y after computing u^N = x^NG_N, while encoder 2 sends v_E_Y after computing v^N = y^NG_N.Each encoder applies a polar transform to its locally observed sequence.
- Decoding: The decoder first reconstructs y^N from encoder 2’s bits, then reconstructs x^N using the estimate y^N as side information.The second decoding stage substitutes the estimated y^N for the actual realization.
- Analysis: The scheme’s analysis is omitted because it essentially consists of two single-user source-coding schemes.The stated construction therefore relies on the previously analyzed single-user method.
- Rate region: Polar coding achieves all points of the Slepian-Wolf rate region by time-sharing between the two corner points.The stated corner points are (H(X), H(X|Y)) and (H(X|Y), H(Y)).
- Alternative direct approach: A direct scheme applying local polar transforms is reported to polarize the sources individually and jointly, but its detailed study is left for future work.This observation is presented as preliminary analysis rather than a completed treatment.
VI. POLARIZATION OF NON-BINARY MEMORYLESS
For prime-sized alphabets, the binary source-polarization limits extend to GF(q) when entropy uses base-q logarithms. General alphabets are more difficult, but added randomness can enable polarization with O(N log N) complexity.
- Prime alphabets: For prime q, the polarization limits remain valid for sources transformed over GF(q) using base-q entropy.The construction uses N = 2^n independent source samples and the same transform with matrix operations in GF(q).
- Arbitrary alphabets: Non-prime alphabet results may fail because a source can remain effectively confined to a polarized subfield.For the four-symbol example, the distribution is preserved by the transform because the source is binary under disguise over the subfield {0, 2}.
- Arbitrary alphabets: The example illustrates why general source-polarization statements over arbitrary alphabets are difficult.The difficulty arises from sources already polarized over a proper subfield that is closed under the transform.
- Arbitrary alphabets: Introducing randomness into the construction can polarize sources over arbitrary alphabets while retaining O(N log N) construction complexity.This extension is attributed to prior work.
A. Proof of Inequality (4)
The proof establishes the binary inequality by analyzing a scalar function whose zeros are controlled through derivative convexity, then applying conditioning and Jensen’s inequality.
- Proof of Inequality (4): Z(X)^2 ≤ H(X) for X ∼ Ber(p), with equality only at p ∈ {0, 1/2, 1}.The proof defines F(p) as the difference between entropy and Z(X)^2.
- Proof of Inequality (4): Strict convexity of dF/dp on [0, 1/2] limits the number of stationary points across the unit interval.The argument bounds the zeros of dF/dp on each half-interval and therefore bounds the zeros of F.
- Proof of Inequality (4): Since F vanishes at p ∈ {0, 1/2, 1} and has at most three zeros, it has no additional zeros.This yields the equality characterization for the binary inequality.
- Proof of Inequality (4): Conditioning on each Y = y applies the binary inequality to the conditional distribution of X.Averaging over Y and using Jensen’s inequality produces inequality (4).
B. Proof of Inequality (5)
The proof uses Rényi-entropy properties to relate the binary conditional quantity to Z(X), then averages over side information with Jensen’s inequality.
- Proof of Inequality (5): Rényi entropy of order α is introduced together with its standard monotonicity property.H_α(X) is strictly decreasing in α unless the distribution is uniform on its support.
- Proof of Inequality (5): For the relevant binary quantity, the entropy relation is expressed as log(1 + Z(X)).The supplied passages display this relation in two closely related forms.
- Proof of Inequality (5): The relation is applied to each sample value Y = y for a jointly distributed pair with binary X.This transfers the single-variable entropy relation to conditional distributions.
- Proof of Inequality (5): Averaging over Y and applying Jensen’s inequality yields inequality (5).The final step aggregates the conditional bounds over the side-information variable.