[CPCC] REMINDER: New Decoding for Linear Block Codes 11 AM Fri April 27, 2007

[Ender Ayanoglu]

                                TALK

The Stopping Redundancy Hierarchy and Automorphism Group Decoding of
                         Linear Block Codes

                                 by

                          Olgica Milenkovic
                    University of Colorado, Boulder
                                 and
             Center for Information Theory and Applications
                  University of California, San Diego

                             April 27, 2007
                                 Friday
                                  11 AM
                           Engineering Tower 331


                                 Abstract

In the past decade, the search for efficient and near optimal decoding
algorithms for linear block codes culminated with the rediscovery and
generalization of the notion of sparse codes and iterative message passing
algorithms. Iterative decoders can approach the Shannon limit of reliable
communication with linear-time complexity, provided that they operate on
long, low-density parity-check (LDPC) codes. This is achieved by using
graphical representations of codes, termed Tanner graphs, containing very
few edges.

The performance of linear block codes under iterative decoding, and the
performance of LDPC codes in particular, depends on the structural
properties of their underlying Tanner graphs. For each channel-decoder
pair, there exist vertex configurations in the code graph on which a given
iterative decoder fails. For the binary erasure channel (BEC) and the
iterative edge-removal algorithm, such configurations are known as
stopping sets. One way to mitigate the detrimental influence of stopping
sets is to augment the Tanner graph of the code by introducing redundant
parity-check equations. The most important question that arises in this
setting is to quantify the achievable trade-off between the size of the
vertex set of a Tanner graph of a code and the size of its smallest
stopping set.

In this talk, we introduce the stopping redundancy hierarchy of a code as
a new measure of both performance and complexity of edge-removal decoding.
We derive lower and upper bounds for the stopping redundancy of a linear
code using Lovasz's Local Lemma and Bonferroni-type inequalities, and then
proceed to specialize our findings to cyclic codes. We demonstrate that
augmenting the Tanner graph of a code is, roughly speaking, equivalent to
performing permutation decoding, and we name the resulting procedure
automorphism group decoding. Automorphism group decoding combines
iterative message passing, redundant Tanner graph representations, and
permutation decoding, thereby greatly reducing the number of errors
confined to stopping sets. We conclude the talk by providing a number of
test codes for which linear time-cost automorphism group decoding almost
perfectly matches the performance of maximum likelihood decoding.


                            Speaker's Biography

Olgica Milenkovic received her MS degree in mathematics and PhD in
electrical engineering from the University of Michigan, Ann Arbor, in 2001
and 2002, respectively. In August 2002, she joined the University of
Colorado, Boulder, where she is an Assistant Professor in the Department
of Electrical and Computer Engineering. In the summer of 2005, she was a
Discrete Mathematics and Theoretical Computer Science (DIMACS) Visitor at
Bell Labs, Lucent Technologies. She is currently a Visiting Professor at
the Center for Information Theory and Applications at the University of
California, San Diego. Her research interests include error-control and
constrained coding, analysis of algorithms, combinatorics, probability
theory, and bioinformatics. She is the recipient of the NSF Career Award
and the DARPA Young Faculty Award.