Theory and Design of Graph-Based Codes for Improved Iterative and Windowed Decoding

Mathematical coding theory addresses the problem of transmitting information reliably and efficiently across noisy channels. This dissertation focuses on graph-based codes, which are codes whose representation, encoding, and/or decoding can be visualized using a sparse graph. We examine a variety of problems for understanding and improving low density parity check (LDPC) codes. While iterative decoding is efficient on these graph-based codes, it is also sub-optimal and sometimes fails to output a codeword. This failure is caused by combinatorial structures in the graph called absorbing sets. We obtain bounds on the sizes of absorbing sets that can exist in certain classes of codes and give a novel connection that links absorbing sets to cosets and syndromes. This connection is used to design an innovative absorbing set search algorithm. In addition, we consider spatially-coupled LDPC (SC-LDPC) codes, a type of code amenable to windowed decoding, which allows information to be decoded sequentially rather than all at once. We examine the inherent properties of the code within a decoding window, which we call a window code. We provide foundational results on the existence and properties of SC-LDPC codes with cycle-free window codes. We provide distance relationships between an SC-LDPC code and its window codes and show that SC-LDPC codes with maximum distance separable (MDS) window codes have bad code rates