Rethinking the minimum distance: Channels with varying sampling rate and interative decoding of LDPC codes

In this dissertation we develop novel coding theoretic approaches for two problems relevant to modern communication systems. In the first part of the thesis we address the issue of reliable communication under varying sampling rate, while in the second part we focus on the analytic understanding of the performance of low density parity check (LDPC) codes in the low bit error rate (BER) region. The underlying theme in both of these somewhat non-standard yet relevant problems is that the notion of a fundamental performance metric, typically taken to be the minimum distance of an additive error correcting code, needs to be rethought when the standard assumptions on the communication no longer hold.; In particular, in the first part of the thesis we investigate the problem of overcoming synchronization errors from a coding theoretic perspective when the timing recovery is inadequate.; In addition, we propose and study number theoretic constructions of sets of strings immune to multiple repetitions. These constructions are also shown to have good cardinalities. We then use these number theoretic constructions to develop a prefixing-based method to improve the immunity of an arbitrary code (a collection of binary strings) to repetition errors. This judiciously chosen prefix is shown to have length that scales logarithmically with the length of string in this collection, and thus has asymptotically negligible redundancy while providing improved immunity to repetition errors. We also provide a decoding algorithm that is a variant of the message passing decoding algorithm, but which can handle repetitions as well as additive errors without requiring additional complexity.; In the second part of the dissertation, we study the performance of iteratively decoded LDPC codes when the frequency of a decoding error is very low. These codes are commonly decoded using highly efficient iterative decoding algorithms, which provide an exponential reduction in complexity over the optimal (but highly impractical) maximum likelihood decoding. These practical iterative decoding algorithms are suboptimal on graphs that are not trees, of which LDPC codes provide a prime example. Nonetheless, LDPC codes, when equipped with these iterative decoding algorithms, are known to perform extremely well in the moderate bit error rate (BER) region.; It is also known that LDPC codes, when decoded iteratively, exhibit a so-called error floor behavior.; In order to gain a better understanding of the low BER performance of LDPC codes, we introduce the notion of a combinatorial object that we call an absorbing set. This object is viewed as a stable point of the bit-flipping algorithm, an algorithm that can be viewed as an asymptotic 1-bit approximation to many message passing decoding algorithms.; As a case study, we analyze the minimal absorbing sets of high rate array-based LDPC codes. We provide a comprehensive analytic description of the minimal absorbing sets for this family of codes, In this study, we demonstrate the existence of absorbing sets whose weight is strictly smaller than the minimum distance of the code. These minimal absorbing sets, rather than minimum distance codewords, are also experimentally shown to dominate the low BER performance. (Abstract shortened by UMI.)...