Abstract:

The performance of iterative message-passing
decoding on a Tanner graph of a linear block code over
the erasure channel is determined by graphically
defined subsets of bit nodes called stopping sets.

The stopping distance of the Tanner graph is the smallest
size of a stopping set, and the stopping redundancy is
the smallest number of check nodes in any Tanner graph
describing the code for which the stopping distance
equals the minimum distance of the code.

In this talk, we present several general upper bounds on
the stopping redundancy, derived by constructive as well
as probabilistic methods. Both finite-length and asymptotic
properties of the bounds are considered. Specializing to
maximum distance-separable (MDS) codes, we compare several
improved upper bounds derived by exploiting the close
connections between the stopping redundancy and combinatorial
quantities such as covering numbers, Turan numbers, and
newly introduced single-exclusion numbers.

Finally, we comment upon two generalizations of the stopping
redundancy: the "maximum-likelihood (ML) redundancy"
and the "guess-g stopping redundancy."

Joint work with Junsheng Han. Portions of this presentation reflect 
joint work with Ronny Roth and Alex Vardy.