TITLE:

A PROBABILISTIC DECODING ALGORITHM USING EFFICIENT BELIEF PROPOGATION (No. 15)

DATE:

Friday, April 25th, 2003

TIME:

3:30 PM

LOCATION:

GMCS 214

SPEAKER:

Mike O’Sullivan, Department of Mathematics, San Diego State University

ABSTRACT:

A variety of algorithms from diverse subject areas (artificial intelligence, Bayesian networks, coding theory) use a generalization of the humble distributive law,

a(b+c)=ab+ac, to achieve efficiency. Dr. OSullivan will show how this works in the context of decoding binary error-correcting codes. We start with a simple example of a code that corrects a single bit error. Then we change the decoding problem by considering probabilistic data about the received bits as input. The decoding problem can then be defined as the maximization of a function which is a product of several very simple functions. Under restricted conditions, there is an efficient algorithm, based on the generalized distributive law, that computes the maximum efficiently. These conditions are rarely satisfied, but even when they are not, experimental results show that the algorithm works exceptionally well. In closing, we consider the algorithm as a dynamical system

HOST:

Marcus Greferath

DOWNLOAD: