Polar codes: Reliable communication with complexity scaling polynomially in the gap to Shannon capacity

Speaker: Venkatesan Guruswami , Carnegie Mellon University

Date: Tuesday, February 18, 2014

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Ankur Moitra, CSAIL

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/484

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, toc@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Polar codes: Reliable communication with complexity scaling polynomially in the gap to Shannon capacity

ABSTRACT:

Shannon's monumental 1948 work laid the foundations for the rich fields of
information and coding theory. The quest for *efficient* coding schemes to
approach Shannon capacity has occupied researchers ever since, with
spectacular progress enabling the widespread use of error-correcting codes
in practice. Yet the theoretical problem of approaching capacity arbitrarily
closely with polynomial complexity remained open except in the special case
of erasure channels.

In 2008, Arikan proposed an insightful new method for constructing
capacity-achieving codes based on channel polarization. In this talk, I will
begin by surveying Arikan's celebrated construction of polar codes, and then
discuss our proof (with Patrick Xia) that, for all binary-input symmetric
memoryless channels, polar codes enable reliable communication at rates
within epsilon > 0 of the Shannon capacity with block length (delay),
construction complexity, and decoding complexity all bounded by a
*polynomial* in the gap to capacity, i.e., by poly(1/epsilon). Polar coding
gives the *first explicit construction* with rigorous proofs of all these
properties; previous constructions were not known to achieve capacity with
less than exp(1/epsilon) decoding complexity.

We establish the capacity-achieving property of polar codes via a direct
analysis of the underlying martingale of conditional entropies, without
relying on the martingale convergence theorem. This step gives rough
polarization (noise levels ~ epsilon for the "good channels"), which can
then be adequately amplified by tracking the decay of the channel
Bhattacharyya parameters. Our effective bounds imply that polar codes can
have block length bounded by poly(1/epsilon). The generator matrix of such
polar codes can also be constructed in deterministic polynomial time by
algorithmically computing an adequate approximation of the polarization
process.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones Email at Wednesday, February 12, 2014 at 9:52 AM.