Theory Lunch Seminar

  • Ph.D. Student (Algorithms, Combinatorics and Optimization)
  • Computer Science Department
  • Carnegie Mellon University

Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity

Let  be a binary-input memoryless symmetric (BMS) channel with Shannon capacity  and fix any . We construct, for any sufficiently small , binary linear codes of block length  and rate that enable reliable communication on  with quasi-linear encoding and decoding time. Shannon's noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length . This quadratic dependence on the gap  to capacity is known to be the best possible. Our result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel.

Our codes are a variant of Arikan’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.

Joint work with Venkat Guruswami and Min Ye.

For More Information, Please Contact: