|
 TITLE: Local Optimality in Tanner Codes
SPEAKER: Guy Even (Tel-Aviv University)
DATE: 11:00 AM - 12:00 NOON, Friday, June 10, 2011
LOCATION: Tioga, 3U
ABSTRACT:
We present a new combinatorial characterization for local optimality
of a codeword in Tanner codes. This characterization is based on a
linear combination of subtrees in the computation trees. The degrees
of local code nodes may be as high as the distance of the local codes,
and the height of the subtree is arbitrary (may be even greater than
the girth).
We prove that local optimality certifies both ML-optimality and
LP-optimality, as one would expect. It is also possible, given a
codeword and an LLR vector, to efficiently test whether the codeword
is locally optimal.
We present two applications of the new characterization of local
optimality. (I) In the case of regular Tanner codes, we present an
analysis of LP-decoding failure. (II) In the case of irregular LDPC
codes, we present a weighted min-sum message passing decoding
algorithm that succeeds if a locally optimal codeword exists.
(Joint work with Nissim Halabi.)
BIOGRAPHY:
Guy Even is with the School of Electrical Engineering in Tel-Aviv
University since 1997. He is interested in algorithms and their
applications in various fields. He has published papers on the theory
of VLSI, approximation algorithms, micro-architectures for floating
point arithmetic, online algorithms, frequency assignment in wireless
networks, scheduling, packet-routing, and decoding algorithms for
error correcting codes.
|
|
|
printable version
