Solving decision problems by means of message-passing algorithms defined on graphical models has received increasing attention in recent years. The origin of this approach lies in coding theory and can be traced back to work by Gallager in 1963 and Tanner in 1981. The actual breakthrough though was marked by the discovery of turbo codes in 1993, coinciding with advances by Wiberg in graphical modeling of codes. Subsequently, the idea of algorithms defined on graphs found its way into various fields of signal processing as a systematic and unifying method for deriving detection algorithms.
Often, message-passing algorithms are computationally demanding, and their implementation in hardware requires a considerable amount of resources (both, in terms of power and circuit area). Therefore, the idea emerged to use analog electronic circuits for implementing message-passing algorithms. The hope is that such highly application-specific circuits allow to obtain fast and power-efficient implementations. Amongst other things, this hope is based on a natural mapping of primitives of message-passing algorithms to very simple non-linear transistor circuits.
The present thesis is a collection of new methods and ideas in the vast domain of message-passing algorithms and their implementation as analog electronic circuits. Therefore, the work does not represent a complete discourse, but rather a contribution to an ongoing research effort.
In the first part of this work we start by giving a short review of how to model a decision problem by means of factor graphs, a special type of graphical model. Subsequently, we show that the summary-product algorithm - a very popular message-passing algorithm defined on the factor graph - can be used for solving the underlying problem. It is well known that the summary-product algorithm operating on a cycle-free graph provides the desired results. However, on a graph with cycles the algorithm becomes iterative and gives back only approximate results. It often occurs that the sub-optimal algorithm on a loopy graph shows the crucial advantage of being of much lower complexity compared to the computations required to obtain the optimal solution. On the other hand, the approximations provided by the sub-optimal algorithm can be arbitrarily bad, especially if the graph has short cycles. In a next step, we therefore present two methods for devising message-passing algorithms on a loopy graph, which allow to trade off complexity against accuracy in a flexible way. In this context we propose a message update rule for so-called structured messages, which subsumes the well-known sum-product update rule. The application and the effect of the proposed methods is illustrated by means of an example of synchronization on noisy linear-feedback shift register sequences.
In the second part of this thesis we move on to analog circuits. After a short introduction to well-established basics, we propose a new fundamental building block, which enables the implementation of a division operation. This extension of implementable operations seems to naturally match the intermediate-complexity algorithms mentioned previously. This is because the message update computations for such algorithms can contain division operations. Finally, we present an extensive collection of measurement results for two analog integrated implementations of message-passing algorithms, built up solely with MOS transistors. Both networks implement decoding algorithms, the first circuit for a binary [8,4,4] extended Hamming code and the second circuit for a binary [16,5,8] Reed-Muller code. Error rate performance curves for both decoders and for various operating conditions are compared to ideal discrete-time simulation results of the corresponding algorithms. Additionally, we offer a detailed characterization of the transistors used for implementing the Hamming code decoding network.

Keywords:
Factor graphs, message-passing algorithms, summary-product algorithm, sum-product algorithm, structured summary, structured message, analog non-linear transistor circuits, translinear circuits, multiplication matrix, division/multiplication matrix, analog iterative decoder.