Reliable transmission of data is a central topic in coding theory and information theory. Both of these fields were founded by Claude E. Shannon in his seminal work, where he formalized the problems of communicating information and established their limits. It has been a major problem since then to find explicit coding schemes that achieve these limits.

For channel coding this corresponds to finding codes that achieve channel (Shannon) capacity. Channel polarization is a novel approach to code construction introduced by Arikan, which he used to construct polar codes that provably achieve capacity for any memoryless symmetric channel and have low encoding and decoding complexities.

The focus of this thesis is on constructing a variant of polar codes with an almost optimal speed of convergence to capacity. Let W be a binary-input memoryless symmetric (BMS) channel with Shannon capacity I(W ). Shannon's noisy coding theorem established the existence of capacity-achieving codes (without efficient construction or decoding) which have rate R = I(W ) - δ and blocklength N = O(1/δ²). This quadratic scaling of blocklength N on the gap δ to capacity is known to be the best possible.

We construct, for any sufficiently small δ > 0, a variant of polar codes with rate R = I(W ) - δ and almost-optimal block length N = O(1/δ^2+α), which enables reliable communication on W with quasi-linear time encoding and decoding. This result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length, which resolves a central theoretical challenge associated with the attainment of Shannon capacity.

The codes constructed in this dissertation are a variant of Arıkan's polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.

124 pages

Thesis Committee:
Venkatesan Guruswami (Chair)
Pravesh Kothari
Ryan O'Donnell
Alexander Barg (University of Maryland)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]