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.