Accelerating the convergence of message passing on loopy graphs using eigenmessages

The field of error correcting codes was revolutionized by the introduction of the Turbo codes and low density parity check (LDPC) codes in the 1990's. These codes demonstrated dramatic performance improvements over any previously known codes, but with a certain amount of latency attached to their decoding algorithms due to the inevitable presence of loops in the graphs associated with these codes.; In this thesis we present the "eigenmessage algorithm" for accelerating the convergence of message-passing algorithms used for decoding LDPC codes. In the eigenmessage step, elements of a message along an edge of cycle are expressed as a linear combination of that message itself, giving rise to an eigenequation, whose solution---the eigenmessage---is equivalent to the fixed point of the closed loop message-passing algorithm, where the other edges incident on nodes in the cycle are held fixed. The decoding algorithm iterates among eigenmessage steps for the cycles in the graph and conventional message passing for edges not in cycles. The eigenmessage algorithm results in faster convergence (approximately 60--80 percent fewer iterations for the codes examined) without any compromise in error performance compared with conventional message-passing algorithms.