Optimal channel codes and concentration of measure
Speaker: Yury Polyanskiy , LIDS, MIT
Date: October 17 2011
Time: 4:15PM to 5:15PM
Location: ** 32-144 ** JUST this time
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: Under the assumption of vanishing probability of error, it is known
classically that a capacity-achieving sequence of codes
must necessarily have empirical distribution which is close to the
capacity-achieving one.
In this work the result is extended to the practically more relevant
case of non-vanishing errors. Surprisingly, in this regime the
question becomes much more delicate and reveals connections with
concentration of measure phenomenon. For example, it is shown that
Lipschitz functions of channel outputs concentrate sharply around
their expected value, which in turn is independent of the employed
code.
Thus despite the fact that only very few capacity-achieving
codes are actually known, it is possible to predict exactly what kind
of interference such codes will cause to others. For the benefit of a
wider audience, in the beginning of the talk I will give a brief
overview of the channel coding setup as traditionally studied in
information theory.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in October 2011
