Pseudocodeword Connections

Monday, April 16, 2007 - 1:30pm - 2:20pm
EE/CS 3-180
Judy Walker (University of Nebraska)
The term pseudocodeword is used in relationship to decoding
linear block codes in at least three different ways. In linear
programming decoding (introduced by Feldman), any vertex of the
fundamental polytope is called a pseudocodeword. In a rigorous
formulation (as first proposed by Wiberg) of min-sum or sum-product
decoding, any valid configuration of any computation tree is called a
pseudocodeword. And, using a more intuitive interpretation of iterative
message-passing decoding, any valid configuration on any finite cover of
the Tanner graph corresponds to a pseudocodeword (this is made precise
through Graph Cover Decoding, proposed by Vontobel and Koetter). Though
some justification of the triple-use of the term has been given, these
three notions of pseudocodeword are indeed distinct. In this talk, we
will describe the connections and disconnections involved.