Stuart Geman
Professor Stuart Geman (Brown University)
Most decoding algorithms employ nearest-neighbor decoding. In most cases
this is suboptimal. Motivated by the problem of reading some new
two-dimensional barcodes from camera images, I will explore a
code representation that permits maximum-likelihood decoding.
Maximum-likelihood decoding achieves the minimum attainable error
rate when code words are uniformly distributed. The idea is to view
the set of code words as the language (set of sentences) associated with
a context-free grammar. Variations on standard parsing algorithms are
then available for 1) maximum likelihood decoding, 2) computation of the
probability that a given decoding is correct, and 3) decoding from channels
that are characterized by Markov (instead of independent) noise. Very large
codes can be feasibly decoded through a "thinning algorithm" that trades
information rate (encoded bits divided by transmitted bits)
for exponential improvements in decoding efficiency. Results
from coding theory, formal grammars, etc. will be introduced as needed so as
to make the talk more or less self contained.