UC San Diego

High data rate applications are beginning to push the limits of communication and computer systems. While there is a need to design good codes and decoders, it is also important to analyze and optimize the decoding algorithms so that they do not use up too much resources. Graphical behavioral models of codes and sequential computers can serve as the common platform for accomplishing both tasks. In this thesis we use closely related graphical models such as factor graphs and branching programs to analyze convergence and performance of iterative decoding algorithms and time-space complexity of functions and decision problems related to codes. In the first part we look at graph realizations of codes. We give a construction of an analog coding scheme on graphs with an efficient iterative decoder for any given bandwidth expansion over unity. This code does not exhibit the well- known threshold effect and has a graceful degradation of performance with increasing noise -- thus disproving a widely held belief that no single practical coding scheme can achieve this. We then analyze the iterative hard- decision decoding scheme of Gallager applied to arbitrary linear codes, and derive probabilistic necessary and sufficient conditions for progressive improvement of the codeword estimates. Finally we analyze the iterative decoding of product codes using bounded distance component decoders and derive the exact probability of error evolution rules, assuming statistically independent errors. In the second part we consider the general Branching Program (BP) model for non-uniform sequential computation -- perhaps second in importance only to Turing machines. We consider the time-space complexity of encoding arbitrary codes on a time-restricted BP model and derive a sharpened version of the Bazzi-Mitter minimum distance bound. Using a probabilistic technique we then obtain a new quadratic time-space tradeoff for syndrome vector computation of linear codes on a unrestricted BP model and use it to prove a conjecture due to Bazzi-Mitter for self-dual codes. Next we extend our probabilistic techniques to deal with decision branching programs and derive the first quadratic time-space tradeoff for a read restricted decision BP model. The minimum distance bounds along with deep new connections between properties of some well known properties of algebraic codes are then used to give tight time-space tradeoffs for computing and verifying several fundamental operations. These include finite-field multiplication, integer multiplication, circular convolution, matrix-vector product and discrete Fourier transform. Many of these tight bounds are new and the rest match the best previous known bounds. In the last part we consider the problem of estimating the Bayes risk in multiple hypothesis testing. We significantly improve the classical equivocation bound due to Renyi. We also derive a lower bound on equivocation and an upper bound on mutual information of most capacity achieving codes on memoryless channels using a random coding argument