Pseudocodewords on graph covers and computation trees

The application and study of iterative message-passing decoders has exploded in recent years, due to their amazing efficiency and near-optimal performance. Much of the analysis of these decoders relies on a heuristic link between the local nature of these algorithms and certain graph structures, called graph covers, that are locally indistinguishable. The precise relationship between graph covers and computation trees, which Wiberg proved can be used to exactly model the behavior of iterative message-passing decoders, remains unclear. The focus of this dissertation is to further explore the relationship between graph covers and computation trees, and their related pseudocodewords, so that the plethora of results on graph covers may be more readily applied to computation trees, and hence to the analysis of iterative message-passing decoding algorithms. We show that every graph cover pseudocodeword gives rise to a computation tree pseudocodeword and that, conversely, every computation tree pseudocodeword does indeed arise from a graph cover pseudocodeword. Although these results strengthen the relationship between these different types of pseudocodewords, it is clear that more study is needed, as we show that there is a single graph cover pseudocodeword that simultaneously gives rise to every computation tree pseudocodeword. We also present a completely graphical characterization of certain graph cover pseudocodewords which are known to cause errors in graph cover decoding of cycle codes