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.