UC San Diego

Key to the success of modern error correcting codes is the effectiveness of message-passing iterative decoding (MPID). Unlike maximum-likelihood (ML) decoding, the performance of MPID depends not only on the code, but on how the code is represented. In particular, the performance of MPID is potentially improved by using a redundant representation. We focus on Tanner graphs and study combinatorial structures therein that help explain the performance disparity among different representations of the same code. Emphasis is placed on the complexity- performance tradeoff, as more and more check nodes are allowed in the graph. Our discussion applies to MPID as well as linear programming decoding (LPD), which we collectively refer to as graph-based decoding. On an erasure channel, it is well-known that the performance of MPID or LPD is determined by stopping sets. Following Schwartz and Vardy, we define the stopping redundancy as the smallest number of check nodes in a Tanner graph such that smallest size of a non-empty stopping set is equal to the minimum Hamming distance of the code. Roughly speaking, stopping redundancy measures the complexity requirement (in number of check nodes) for MPID of a redundant graph representation to achieve performance comparable to ML decoding (up to a constant factor for small channel erasure probability). General upper bounds on stopping redundancy are obtained. One of our main contribution is a new upper bound based on probabilistic analysis, which is shown to be by far the strongest. From this bound, it can be shown, for example, that for a fixed minimum distance, the stopping redundancy grows just linearly with the redundancy (codimension). Specific results on the stopping redundancy of Golay and Reed-Muller codes are also obtained. We show that the stopping redundancy of maximum distance separable (MDS) codes is bounded in between a Turan number and a single-exclusion (SE) number --- a purely combinatorial quantity that we introduce. By studying upper bounds on the SE number, new results on the stopping redundancy of MDS codes are obtained. Schwartz and Vardy conjecture that the stopping redundancy of an MDS code should only depend on its length and minimum distance. Our results provide partial confirmation, both exact and asymptotic, to this conjecture. Stopping redundancy can be large for some codes. We observe that significantly fewer checks are needed if a small number of small stopping sets are allowed. These small stopping sets can then be dealt with by ̀g̀uessing'' during the iterative decoding process. Correspondingly, the guess-g stopping redundancy is defined and it is shown that the savings in number of required check nodes are potentially significant. Another theoretically interesting question is when MPID of a Tanner graph achieves the same word error rate an ML decoder. This prompts us to define and study ML redundancy. Applicability and possible extensions of the current work to a non-erasure channel are discussed. A framework based on pseudo-codewords is considered and shown to be relevant. However, it is also observed that the polytope characterization of pseudo-codewords is not complete enough to be an accurate indicator of MPID performance. Finally, in a separate piece of work, the probability of undetected error (PUE) for over-extended Reed-Solomon codes is studied through the weight distribution bounds of the code. The resulting PUE expressions are shown to be tight in a well-defined sense