This project addresses fundamental questions in the area of iterative decoding of capacity achieving codes, including low density parity check (LDPC) codes and turbo codes. Specifically, it aims to find a unifying theory of pseudocodewords of codes on graphs, by introducing a new decoder for such codes. Currently, there are three notions of pseudocodeword in the literature: graph cover pseudocodewords, which correspond to codewords in codes defined by finite covers of the Tanner graph of the original code; linear programming pseudocodewords, which are rational points in the fundamental polytope of the parity check matrix of the code; and computation tree pseudocodewords, which are valid configurations on computation trees for the Tanner graph of the code. While most of the research in the literature has focused on graph cover pseudocodewords and linear programming pseudocodewords (and, in particular, Vontobel and Koetter have shown that these two notions are essentially the same), Wiberg proved that it is computation tree pseudocodewords that actually are the impediments to correct decoding. The new decoding algorithm proposed in this project provides a precise link between computation tree pseudocodewords and the other two notions of pseudocodewords, thus allowing existing results on graph cover and linear programming pseudocodewords to be modified to apply to computation tree pseudocodewords. This in turn provides an explanation for the empirical performance results for capacity achieving codes.
Claude Shannon's famous 1948 paper ""A Mathematical Theory of Communication"" and its channel coding theorems spawned the body of research referred to as Coding Theory. The 1993 discovery of turbo codes and the 1996 re-discovery of low density parity check codes represent a major milestone in coding theory. These two classes of codes come equipped with iterative message-passing decoding algorithms under which they can achieve realistic bit error rates with signal-to-noise ratios that are only slightly above the minimum established by Shannon's theorems. As such, these codes are sometimes considered to have solved, in the engineering sense, the coding problem for the additive white Gaussian noise and similar channels. However, the decoding algorithms for these codes are far from completely understood, and the codes which perform best in simulations thus far are randomly constructed. Therefore, the coding problem remains very much unsolved in the mathematical sense. The primary goal of this project is a better understanding of the decoding algorithms, with an aim toward methods of constructing codes which are guaranteed to perform well.
