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 replaced by super checks corresponding to the shorter and stronger error correcting codes. However, the main feature of our method is to carefully replacing super checks such that harmful structures in the Tanner graph of the LDPC codes called trapping sets are eliminated. The second purpose is to reduce the rate-loss caused by replacing super checks through finding the minimum number of super checks needed for eliminating a certain trapping set. To construct these codes, we first use the knowledge of trapping sets of LDPC codes over the binary symmetric channel (BSC) and systematically replace super checks to disable a trapping set. We then provide upper bounds on the minimum number of super checks needed to eliminate all trapping sets of a certain size in the Tanner graph of an LDPC code. The guaranteed error correction capability of the CH-GLDPC codes is also studied. The results are extended to different classes of LDPC codes and iterative decoders