Codes on Graphs: Shannon's Challenge and Beyond
Meeting Time: Nov. 17, 2009, 2:00-2:50pm
Abstract:
Whenever information is transmitted across a channel, errors are bound to
occur. It is the goal of coding theory to find efficient ways of adding
redundancy to the information so that errors can be detected and even
corrected. Coding theory began in 1948 with Shannon's groundbreaking
result that efficient, reliable transmission of information is possible.
This result was existential rather than constructive, however, and the
challenge over the past half century has been to actually find the codes
that Shannon proved must exist. In the past 10-15 years, it has been
shown that certain graph-based codes come close to achieving Shannon
capacity. Even with these recent advances, however, it is not clear
whether Shannon's challenge has truly been answered. We will discuss the
current situation as well as what the next big problems are for the field
of coding theory.