Rüdiger Urbanke: EXIT Functions and the Area Theorem in Coding Theory

Friday, October 30, 2015 - 1:30pm to 4:30pm
Pizza at 1:15p
Hewlett G882
Rüdiger Urbanke, EPFL

Abstract: An EXIT function measures the ``response’’ of a code to
a particular channel. The area theorem refers to the fact that if you
integrate this function over a family of channels (from perfect channel
to useless channel) then this integral is equal to the rate of the code,
irrespective of what code you pick. Therefore, no code can universally
be ``better'' than any other code (of the same rate). Two codes of the
same rate simply will have different characteristics.

EXIT functions started out as convenient engineering tool to approximate the
behaviour of iterative coding systems. But they are much more powerful.

I will discuss two applications. The first concerns spatially-coupled
codes. These are codes that use the ideas of nucleation and crystallisation, familiar
from heat packs, hail, and super-cooled water, in order to build low-complexity
universal capacity-achieving codes.

[In case you are curious, see https://www.youtube.com/watch?v=pTdiTe3x0Bo for
a super cool super-cooled water experiment.]

The second one concerns the questions whether classical families of codes,
such as Reed-Muller codes and extended BCH codes are capacity-achieving.

In both cases, EXIT functions and the area theorem play a crucial role.