Codes on Graphs and Analysis of Iterative Algorithms for Reconstructing Sparse Signals and Decoding of Check-Hybrid GLDPC Codes

The necessity for fast and efficient algorithms in different fields of communications and signal processing have led to developing low-complexity iterative algorithms. In the fields of compressed sensing and channel coding, which are the main focus of this dissertation, designing low-complexity iterative algorithms with excellent performance has been of interest for many years. Recently, there has been a significant interest to understanding the failures of the iterative reconstruction and decoding algorithms. Knowing the failures of the algorithms may improve the performance either by designing new algorithms or by providing new conditions on the input of the algorithms under which the previous failures of algorithms are disabled. In the first part of this dissertation, we consider an iterative reconstruction algorithm called the interval-passing algorithm (IPA) which was originally introduced to reconstruct non-negative signals from binary measurement matrices. We first modify the IPA to reconstruct signals from non-negative measurement matrices and compare the performance of the IPA with two reconstructing algorithms, the verification algorithm and the linear programming technique for recovery of signals. The results show that the IPA is a good trade-off between a very simple verification algorithm and the complex linear programming technique. We also show the failures of the IPA on some subgraphs in the Tanner graph corresponding to the measurement matrix called stopping sets and analyze the failures and successes of the IPA on subsets of stopping sets. We provide sufficient conditions under which the IPA succeeds the recovery of the signal. Reconstruction performance of the IPA using different LDPC measurement matrices is given to show the effect of stopping sets. In the second part of the dissertation, a method for constructing a class of codes called the check-hybrid generalized LDPC (CH-GLDPC) is provided. In CH-GLDPC codes, some single parity-checks are rep