The paper considers the joint estimation of multiple constant or time-varying scale factors in linear Gaussian and non-Gaussian models. A recently proposed variational NUP (normal with unknown parameters) representation allows to address such problems by iterated Gaussian message passing in a pertinent factor graph. However, this method requires to adaptively tune a hyperparameter for each scale factor, which hinders its use for estimating multiple scale factors.In this paper, we improve this NUP representation and replace that hyperparameter by one that need not be tuned adaptively. We then show the effectiveness and versatility of the proposed approach by two applications: (i) elastic net regression with automatic estimation of the regularization parameters, and (ii) a state space model with joint estimation of piecewise constant driving noise and piecewise constant observation noise.

This letter explores the capability of continuous-time recurrent neural networks to store and recall precisely timed scores of spike trains. We show (by numerical experiments) that this is indeed possible: within some range of parameters, any random score of spike trains (for all neurons in the network) can be robustly memorized and autonomously reproduced with stable accurate relative timing of all spikes, with probability close to one. We also demonstrate associative recall under noisy conditions. In these experiments, the required synaptic weights are computed offline to satisfy a template that encourages temporal stability.

The paper considers linear state space models with non-Gaussian inputs and/or constraints. As shown previously, NUP representations (normal with unknown parameters) allow to compute MAP estimates in such models by iterating Kalman smoothing recursions. In this paper, we propose to compute such MAP estimates by iterating backward-forward recursions where the forward recursion amounts to coordinatewise input estimation. The advantages of the proposed approach include faster convergence, no “zero-variance stucking”, and easier control of constraint satisfaction. The approach is demonstrated with simulation results of exemplary applications including (i) regression with non-Gaussian priors or constraints on k-th order differences and (ii) control with linearly constrained inputs.

This article presents analytical tools for high-level design of the leapfrog (LF) control-bounded analog-to-digital converter (CBADC). We derive closed-form design equations for parameterizing the analog system for a target signal-to-noise ratio (SNR) and bandwidth. Furthermore, we show how the parameterization can be modified to compensate for finite amplifier gain-bandwidth product (GBWP) and to control the signal swing at different nodes of the system. Behavioral circuit simulations are used to compare the LF CBADC to relevant continuous-time sigma–delta modulators (CT-$\Sigma \Delta $Ms) in terms of nominal performance and sensitivity to component variations, clock jitter, and finite GBWP. Simulations show that the nominal performance of the LF is similar to that of a CT-$\Sigma \Delta \text{M}$of the same loop-filter order and with the same number of quantization levels. The simple, modular structure, analytical stability guarantee, and single-bit quantizers make the LF an interesting alternative to conventional CT-$\Sigma \Delta $Ms.

This paper introduces the partial-inverse problem for linearized polynomials and develops its application to decoding Gabidulin codes and lifted Gabidulin codes in linear random network coding. The proposed approach is a natural generalization of its counterpart for ordinary polynomials, thus providing a unified perspective on Reed–Solomon codes for the Hamming metric and for the rank metric. The basic algorithm for solving the partial-inverse problem is a common parent algorithm of a Berlekamp–Massey algorithm, a Euclidean algorithm, and yet another algorithm, all of which are obtained as easy variations of the basic algorithm. Decoding Gabidulin codes can be reduced to the partial-inverse problem via a key equation with a new converse. This paper also develops new algorithms for interpolating crisscross erasures and for joint decoding of errors, erasures, and deviations in random network coding.

Variations of L1 -regularization including, in particular, total variation regularization, have hugely improved computational imaging. However, sharper edges and fewer staircase artifacts can be achieved with convex-concave regularizers. We present a new class of such regularizers using normal priors with unknown variance (NUV), which include smoothed versions of the logarithm function and smoothed versions of Lp norms with p ≤ 1 . All NUV priors allow variational representations that lead to efficient algorithms for image reconstruction by iterative reweighted descent. A preferred such algorithm is iterative reweighted coordinate descent, which has no parameters (in particular, no step size to control) and is empirically robust and efficient. The proposed priors and algorithms are demonstrated with applications to tomography. We also note that the proposed priors come with built-in edge detection, which is demonstrated by an application to image segmentation.

The paper proposes a new method to determine a binary control signal for an analog linear system such that the state, or some output, of the system follows a given target trajectory. The method can also be used for digital-to-analog conversion.The heart of the proposed method is a new binary-enforcing NUV prior (normal with unknown variance). The resulting computations, for each planning period, amount to iterating forward-backward Gaussian message passing recursions (similar to Kalman smoothing), with a complexity (per iteration) that is linear in the planning horizon. In consequence, the proposed method is not limited to a short planning horizon.

Reliable real-time estimation of the interaural time delay of a sound source is difficult in the presence of noise and reverberation. However, the psychoacoustical precedence effect suggests that accurate estimation is possible by concentrating on the first-arriving sound. This paper introduces a novel real-time estimation method inspired by the precedence effect. First, the arrival of first-arriving sound is detected by performing a hypothesis test based on local approximation of the binaural signal with exponentially decaying sinusoids, which effectively model the shape of a sound onset. After detection, the interaural time delay is directly retrieved from the phase shift of the approximating sinusoids. The local model approximation is done with efficient recursions by parameterization of the model with autonomous linear state-space models, making the algorithm implementable in real-time.

A new method for blind image deblurring is proposed that relies on a smoothed-NUV (normal with unknown variance) prior for images, which promotes piecewise smooth images with crisp edges. The proposed method can use multiple blurred versions of the same image. The variational representation of the prior allows the joint estimation of the image and the blurring kernel(s) to be decomposed into descent steps in reweighted least-squares problems and nonlinear scalar updates of the individual variances of the prior. Specifically, we propose an iteratively reweighted coordinate descent algorithm that has no parameters. Simulation results demonstrate that the proposed approach compares favorably to state-of-the-art methods.

Control-bounded analog-to-digital conversion as described in the work of Loeliger et al. opens opportunities for entirely new analog circuit topologies. The structure of such a converter is shown in Fig. 1. In this paper, we propose such a converter where the analog linear system is a network of N fully connected identical integrators, with uniform sensitivity to noise and mismatch across the network. Nonetheless, the converter achieves a nominal conversion error similar to that of a ΔΣ converter with a N-th order loop filter.

This paper studies the capability of a recurrent neural network model to memorize random dynamical firing patterns by a simple local learning rule. Two modes of learning/memorization are considered: The first mode is strictly online, with a single pass through the data, while the second mode uses multiple passes through the data. In both modes, the learning is strictly local (quasi-Hebbian): At any given time step, only the weights between the neurons firing (or supposed to be firing) at the previous time step and those firing (or supposed to be firing) at the present time step are modified. The main result of the paper is an upper bound on the probability that the single-pass memorization is not perfect. It follows that the memorization capacity in this mode asymptotically scales like that of the classical Hopfield model (which, in contrast, memorizes static patterns). However, multiple-rounds memorization is shown to achieve a higher capacity (with a nonvanishing number of bits per connection/synapse). These mathematical findings may be helpful for understanding the functions of short-term memory and long-term memory in neuroscience.

In prior work, we have shown how the basic concepts and terms of quantum mechanics relate to factorizations and marginals of complex-valued quantum mass functions, which are generalizations of joint probability mass functions. In this paper, using quantum mass functions, we discuss the realization of measurements in terms of unitary interactions and marginalizations. It follows that classical measurement results strictly belong to local models, i.e., marginals of more detailed models. Classical variables that are created by marginalization do not exist in the unmarginalized model, and different marginalizations may yield incompatible classical variables. These observations are illustrated by the Frauchiger-Renner paradox, which is analyzed (and resolved) in terms of quantum mass functions. Throughout, the paper uses factor graphs to represent quantum systems/models with multiple measurements at different points in time.

The paper derives an exact discrete-time state space realization of the popular gammatone filter. No such realization appears to be available in the literature. The proposed realization is computationally attractive: a gammatone filter with exponent N requires less than 6N multiplications and additions per sample. The integer coefficients of the realization can be computed by a simple recursion. The proposed realization also yields a closed-form expression for the frequency response. The proposed primary realization is not quite in a standard form, but it is easily transformed into another realization whose state transition matrix is in Jordan canonical form.

We study Gabidulin codes from a partial-inverse perspective and obtain a key equation with a new converse, as well as a new interpolation formula. The resulting new algorithm is efficient and conceptually simple.

Contextual anomalies arise only under special internal or external stimuli in a system, often making it infeasible to detect them by a rule-based approach. Labelling the underlying problem sources is hard because complex, time-dependent relationships between the inputs arise. We propose a novel unsupervised approach that combines tools from deep learning and signal processing, working in a purely data-driven way. Many systems show a desirable target behaviour which can be used as a proxy quantity removing the need to manually label data. The methodology was evaluated on real-life test car traces in the form of multivariate state message sequences. We successfully identified contextual anomalies during the cars' timeout process along with possible explanations. Novel input encodings allow us to summarise the entire system context including the timing such that more information is available during the decision process.

Most of the algorithms for tomographic reconstruction face the same problem: high computational complexity. In order to tackle this problem, this paper proposes a general multi-resolution approach that enables a flexible choice of reconstruction focus and thus saves computational power in reconstructions. The approach is demonstrated in this paper based on a reconstruction algorithm using a (improper) Markov random field prior with sparsifying NUV terms (nor-mal with unknown variance), where the unknown variances are learned by approximate EM (expectation maximization). The experimental and practical results show that both for simulated and real-world objects the proposed framework yields satisfying results with much lower computational cost.

This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed-Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp-Massey type. Fourth, decoding interleaved Reed-Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: if that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp-Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt-Sidorenko-Bossert bound and the Roth-Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms.

A factor-graph representation of quantum-mechanical probabilities (involving any number of measurements) is proposed. Unlike standard statistical models, the proposed representation uses auxiliary variables (state variables) that are not random variables. All joint probability distributions are marginals of some complex-valued function q, and it is demonstrated how the basic concepts of quantum mechanics relate to factorizations and marginals of q.

The paper considers the problem of joint system identification and input signal estimation of an unknown linear system from noisy observations of the output signal. The input signal is assumed to be sparse, and each individual input pulse may affect the system in its own (and unknown) way. Based on ideas from sparse Bayesian learning, we derive an efficient expectation maximization (EM) algorithm for jointly estimating all unknown quantities. Unlike related prior work, the proposed algorithm does not alternate between estimating the input signal and estimating the system parameters; instead, all unknown quantities are jointly updated in each EM step. We give closed-form expressions for these EM updates, which can be efficiently computed by Gaussian message passing.

Cell depolarization runs essentially in a uniform motion along the muscular tissue, which creates transient electrical potential differences measurable by nearby electrodes. Inferring the depolarization speed and direction from measurements is of great interest for physicians. In cardiology, this is part of the inverse ECG problem which often requires a large number of electrodes and intense computational power even if the simple common model of the single equivalent moving dipole (SEMD) is applied. In this paper, we model a depolarization process as a straight-line movement of a SEMD. We provide an efficient algorithm based on linear state space models that infers the SEMD movement using only 3 measurement channels from a tetrahedral electrode and with the presence of interferences. Our algorithm is tested both on simulated and experimental data.

This semi-tutorial paper introduces the partial-inverse problem for polynomials and develops its application to decoding Reed-Solomon codes and some related codes. The most natural algorithm to solve the partial-inverse problem is very similar to, but more general than, the Berlekamp-Massey algorithm. Two additional algorithms are obtained as easy variations of the basic algorithm: the first variation is entirely new, while the second variation may be viewed as a version of the Euclidean algorithm. Decoding Reed-Solomon codes (and some related codes) can be reduced to the partial-inverse problem, both via the standard key equation and, more naturally, via an alternative key equation with a new converse. Shortened and singly-extended Reed-Solomon codes are automatically included. Using the properties of the partial-inverse problem, two further key equations with attractive properties are obtained. The paper also points out a variety of options for interpolation.

To respond to reverberation effectively, modern speech processing tasks like signal enhancement in digital hearing aids or distant-talking speech recognition often require precise knowledge of the acoustic situation. A common measure is the (frequency-dependent) reverberation time T60. Explicit measurement using sound excitations is not possible for most applications, therefore blind estimation of subband T60from speech signals is employed. Previous approaches are either limited to T60between 0...1.5 s, or require long speech signals and costly computation. We propose an efficient algorithm that estimates T60up to 6 s from short speech signals of no more than 20 s. In experiments with real room impulse responses (RIR) the algorithm exhibits state-of-the-art performance for T60up to 1.5 s and superior performance for longer T60.

The analysis of wave and diffusion fields is a task central to a myriad of applications. Wave fields are encountered in acoustic, radar, and geophysics to name a few. Diffusion fields are found, for example, in physics, chemistry, and biology.

Detecting and inferring the trajectory of a moving magnet from magnetic field measurements is a challenge due to a wide range of time scales and amplitudes of the recorded signals and limited computational power of devices embedding a magnetometer. In this paper, we model the magnetic field measurements using a bank of autonomous linear state space models and provide an efficient algorithm based on local likelihood filtering for reliably detecting and inferring the gesture causing the magnetic field variations.

We use ideas from sparse Bayesian learning for estimating the (weakly) sparse input signal of a linear state space model. Variational representations of the sparsifying prior lead to algorithms that essentially amount to Gaussian message passing. The approach is extended to the case where the state space model is not known and must be estimated. Experimental results with a real-world application substantiate the applicability of the proposed method.

We propose a new model of pulse-based computation based on inner-product filters with linear-system kernels. Each inner-product filter looks for some pulse pattern in its multichannel-input signal by projecting the input signal into a one-dimensional subspace; an output pulse is generated if this projection exceeds some threshold. A layered network of such filters can be used for self-synchronizing multiscale signal parsing. Such a network can be built with computational units that are biologically plausible neurons. The feasibility of the proposed approach is demonstrated with a network that understands Morse code.

The partial-inverse approach is further developed to decoding interleaved Reed-Solomon codes and subfield-evaluation codes beyond half the minimum distance. The resulting decoding algorithm is new, and its decoding capability is shown to be state-of-the-art.

Surprisingly many signal processing problems can be approached by locally fitting autonomous deterministic linear state space models to the data. In this paper, we introduce local statistical models for such cases and discuss the computation both of the corresponding estimates and of local likelihoods for different models.

The partition function of a factor graph and the partition function of the dual factor graph are related to each other by the normal factor graph duality theorem. We apply this result to the classical problem of computing the partition function of the Ising model. In the one-dimensional case, we thus obtain an alternative derivation of the (well-known) analytical solution. In the two-dimensional case, we find that Monte Carlo methods are much more efficient on the dual graph than on the original graph, especially at low temperature.

We propose a new algorithm for decoding Reed-Solomon codes (up to half the minimum distance) and for computing inverses in F[x]/m(x). The proposed algorithm is similar in spirit and structure to the Berlekamp-Massey algorithm, but it works naturally for general m(x).

The paper proposes Monte Carlo algorithms for the computation of the information rate of 2-D source/channel models. The focus of the paper is on binary-input channels with constraints on the allowed input configurations. The problem of numerically computing the information rate, and even the noiseless capacity, of such channels has so far remained largely unsolved. Both problems can be reduced to computing a Monte Carlo estimate of a partition function. The proposed algorithms use tree-based Gibbs sampling and multilayer (multitemperature) importance sampling. The viability of the proposed algorithms is demonstrated by simulation results.

In a typical receiver, symbol synchronization must be established before symbol demodulation. This paper discusses synchronization for an isolated symbol from a filter-bank type multicarrier system. It is shown that accurate symbol timing for a single multicarrier symbol can be obtained using forward-only processing. The proposed receiver computes continuous-time symbol likelihoods along with a timing metric and its time derivative. The timing metric shows a sharp concentration that is used to produce a trigger to sample the matched filter outputs. The paper proposes baseband processing using message passing algorithms derived from factor graphs. Suitable system parameters for which near-optimum synchronization is obtained are identified using computer simulations.

A factor-graph representation of quantum-mechanical probabilities is proposed. Unlike standard statistical models, the proposed representation uses auxiliary variables (state variables) that are not random variables.

The partition function of a factor graph can sometimes be accurately estimated by Monte Carlo methods. In this paper, such methods are extended to factor graphs with negative and complex factors.

Physical wave fields are often described by means of a vector field. Advances in sensor technology enable us to collect an increasing number of measurement at the same location (e.g. direction, polarization, translation, and rotation). One question arising naturally is how to properly process such large and diverse information, possibly from sensors of different kinds. In this paper we propose a technique for the analysis of vector wave fields and show an application to the seismic wave field. The contributions of this paper are the following: i) We provide a framework to perform maximum likelihood parameter estimation of any wave type, modeling jointly all the measurements and parameters; ii) In the same framework, we address wave superposition by gradually decomposing the wave field; iii) We also propose an iterative algorithm for noise variance estimation.

This paper proposes a method to compute the likelihood function for the amplitudes and phase shifts of noisily observed phase-locked and amplitude-constrained sinusoids. The sinusoids are assumed to be coupled based on a set of parameters as, e.g., measurements of a monochromatic wave field. A factor graph is used to formulate the probability density function of the observations given the parameters. The factor graph consists of one second-order state-space model per signal and one additional factor connecting all the final states. Because the parameters appear only in this latter factor, we are able to formulate a sufficient statistic for parameter estimation and signal detection in terms of messages in the factor graph. In special cases, the general form of the sufficient statistic reduces to the discrete Fourier transform. As extensions we provide iterative algorithms for approximate maximum likelihood estimation of the noise variances and the parameters of superposed waves.

A general class of polynomial remainder codes is considered. These codes are very flexible in rate and length and include Reed-Solomon codes as a special case. In general, the code symbols of such codes are polynomials of different degree, which leads to two different notions of weights and of distances. The notion of an error locator polynomial is generalized to such codes. A key equation is proposed, from which the error locator polynomial can be computed by means of a gcd algorithm. From the error locator polynomial, the transmitted message can be recovered in two different ways, which may be new even when specialized to Reed-Solomon codes.

The problem of computing the information rate of noisy two-dimensional constrained source/channel models has been an unsolved problem. In this paper, we propose two Monte Carlo methods for this problem. The first method, which is exact in expectation, combines tree-based Gibbs sampling with importance sampling. The second method uses generalized belief propagation and is shown to yield a good approximation of the information rate.

New decoding algorithms for linear codes are proposed. The first part of the paper considers decoding general binary linear codes by searching multiple trees, which is shown to achieve near maximum-likelihood performance for short block lengths. The second part of the paper considers decoding low-density parity check (ldpc) codes by means of repeated decoding attempts by standard sum-product message passing. Each decoding attempt starts from modified channel output, where some of the bits are clamped to a fixed value. The values of the fixed bits are obtained from multitree search.

An explicit code construction for using low-density lattice codes (LDLC) on the constrained power AWGN channel is given. LDLC lattices can be decoded in high dimension, so that the code relies on the Euclidean distance between codepoints. A sublattice of the coding lattice is used for code shaping. Lattice codes are designed using the continuous approximation, which allows separating the contribution of the shaping region and coding lattice to the total transmit power. Shaping and lattice decoding are both performed using a belief-propagation decoding algorithm. At a rate of 3 bits per dimension, a dimension 100 code which is 3.6 dB from the sphere bound is found.

Monte Carlo methods are considered to compute, first, the partition function of graphical models, and second, the information rate of source/channel models, in both cases for factor graphs with cycles. The convergence of two basic Monte Carlo methods is improved by sampling only a cycle breaking subset of the variables and using exact sum-product computations for the remaining variables. The methods are demonstrated by their application to a two-dimensional Ising model and to a two-dimensional intersymbol interference channel.

Prior work on the computation of information rates of channels with memory is extended to continuous state spaces by means of sequential Monte-Carlo integration (ldquoparticle filteringrdquo).

The classical Blahut-Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs.

The message-passing approach to model-based signal processing is developed with a focus on Gaussian message passing in linear state-space models, which includes recursive least squares, linear minimum-mean-squared-error estimation, and Kalman filtering algorithms. Tabulated message computation rules for the building blocks of linear models allow us to compose a variety of such algorithms without additional derivations or computations. Beyond the Gaussian case, it is emphasized that the message-passing approach encourages us to mix and match different algorithmic techniques, which is exemplified by two different approaches—steepest descent and expectation maximization—to message passing through a multiplier node.

Flash analog-to-digital converters can be built using small (and fast) low-precision comparators with unpredictable thresholds followed by a digital look-up table to correct the output. The look-up table should store digital codes with higher precision than the nominal resolution of the converter. The effective resolution of such a scheme with N comparators is roughly log2(N) - 1 bits. The concept is demonstrated by a chip that achieves almost 7 bit resolution with 256 low-precision comparators

It is shown how particle methods can be viewed as message passing on factor graphs. In this setting, particle methods can readily be combined with other message-passing techniques such as the sum-product and max-product algorithm, expectation maximization, iterative conditional modes, steepest descent, Kaiman filters, etc. Generic message computation rules for particle-based representations of sum-product messages are formulated. Various existing particle methods are described as instances of those generic rules, i.e., Gibbs sampling, importance sampling, Markov-chain Monte Carlo methods (MCMC), particle filtering, and simulated annealing

The information rate of finite-state source/channel models can be accurately estimated by sampling both a long channel input sequence and the corresponding channel output sequence, followed by a forward sum–product recursion on the joint source/channel trellis. This method is extended to compute upper and lower bounds on the information rate of very general channels with memory by means of finite-state approximations. Further upper and lower bounds can be computed by reduced-state methods.

It has been observed that a linear-feedback shift-register (LFSR) sequence can be synchronized by feeding the modulated sequence into a "soft" (or "analog") version of the LFSR. In this correspondence, the "soft LFSR" is derived as forward-only message passing in the corresponding factor graph. A continous-time analog (suitable for realization as a clockless electronic circuit) is then given of both the LFSR and the soft LFSR. A connection is thus established between statistical state estimation and the phenomenon of entrainment of dynamical systems, which opens the prospect of deriving dynamical systems (such as electronic circuits) with strong entrainment capabilities from more powerful message passing algorithms

The problem of separating superimposed action potentials in electromyographic (EMG) signals is considered. Based on a graphical model (factor graph), a new EMG signal decomposition algorithm that uses loopy belief propagation is presented. Results show that the algorithm is capable of decomposing multiple superpositions in simulated and measured EMG signals.

Based on prior work by Eckford, it is shown how expectation maximization (EM) may be viewed, and used, as a message passing algorithm in factor graphs

This paper presents a factor graph approach to turbo equalization. Unlike the existing linear MMSE turbo equalization methods, which operate with truncated windows (sliding or extending window), the proposed is a full-window approach with low complexity. This approach supports a high-speed parallel implementation technique, which makes it an attractive option in practice

It is shown how steepest descent (or steepest ascent) may be viewed as a message passing algorithm with "local" message update rules. For example, the well-known backpropagation algorithm for the training of feedforward neural networks may be viewed as message passing on a factor graph. The factor graph approach with its emphasis on "local" computations makes it easy to combine steepest descent with other message passing algorithms such as the sum/max-product algorithms, expectation maximization, Kalman filtering/smoothing, and particle filters. As an example, parameter estimation in a state space model is considered. For this example, it is shown how steepest descent can be used for the maximization step in expectation maximization.

The classic problem of estimating the parameters of an auto-regressive (AR) model is considered from a graphical model viewpoint. A number of practical parameter estimation algorithms - some of them well known, others apparently new - are derived as "summary propagation" in a factor graph. In particular, we demonstrate the joint estimation of AR coefficients, innovation variance, and noise variance.

The problem of phase estimation in a "turbo receiver" is considered for two different channel models. Several message passing algorithms for phase estimation are derived from the factor graph of the channel models: (1) straight sum-product, applied to a quantized phase model; (2) LMS-type gradient methods; (3) a particle filter. All considered algorithms are suitable for use in a "turbo receiver" with joint iterative decoding and phase estimation.

Prior work on the computation of information rates of channels with memory is extended to continuous state spaces by means of sample-based numerical integration ("particle filtering"). In this paper, the problem of computing the information rate between the input and the output process of a time-variant discrete-time channel with memory and ergodic stochastic process is analyzed and the methods are extended to continuous state spaces.

Factor graphs are graphical models with origins in coding theory. The sum-product and the max-product algorithms, which operate by message passing on a factor graph, subsume a great variety of algorithms in coding, signal processing, and artificial intelligence. The paper aims at extending the field of possible applications to dynamical electrical networks (i.e., networks that contain capacitors and inductors as well as static components). Interestingly, the resulting factor graphs have a structure very much akin to a Kalman filter.

The entropy rate of a finite-state hidden Markov model can be estimated by forward sum-product trellis processing (i.e., the forward recursion of the Baum-Welch/BCJR algorithm) of simulated model output data. This can be used to compute information rates of binary-input AWGN channels with memory.

In 1998, Hagenauer and Loeliger et al. independently proposed to decode error correcting codes by analog electronic networks. In contrast to previous work on analog Viterbi decoders, the work both by Hagenauer and by Loeliger et al. was inspired by turbo-style decoding of codes described by graphs. Large gains, in terms of speed or power consumption, over digital implementations were envisaged. Since 1998, much effort has been spent towards turning these ideas into working chips. While only decoders of "toy" codes have so far been successfully manufactured, extensive simulations of such circuits have not revealed any fundamental problems. Some progress has also been made in analyzing the effects of transistor mismatch. While much remains to be learned, the author feels confident that analog decoders will eventually find their way into applications. The present paper, rather than reporting on circuit details, offers some thoughts on "the bigger picture"- the underlying principles, motivations, and possible directions of future research.

Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of "local" functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph, In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph. Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative "turbo" decoding algorithm, Pearl's (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.

The sum-product algorithm (belief/probability propagation) can be naturally mapped into analog transistor circuits. These circuits enable the construction of analog-VLSI decoders for turbo codes, low-density parity-check codes, and similar codes.

General random coding theorems for lattices are derived from the Minkowski-Hlawka theorem and their close relation to standard averaging arguments for linear codes over finite fields is pointed out. A new version of the Minkowski-Hlawka theorem itself is obtained as the limit, for p/spl rarr//spl infin/, of a simple lemma for linear codes over GF(p) used with p-level amplitude modulation. The relation between the combinatorial packing of solid bodies and the information-theoretic "soft packing" with arbitrarily small, but positive, overlap is illuminated. The "soft-packing" results are new. When specialized to the additive white Gaussian noise channel, they reduce to (a version of) the de Buda-Poltyrev result that spherically shaped lattice codes and a decoder that is unaware of the shaping can achieve the rate 1/2 log/sub 2/ (P/N).

The basic algebraic structure theory of convolutional codes and their trellises is developed simultaneously for codes over groups, rings, and fields. The first part, which covers fundamental notions such as minimality and observability, is semi-tutorial in that most definitions are already standard (within the modern behavioral theory), as are some of the formally stated results. However, some of the pivotal results-emphasizing the role of observability as the basic well-behavedness condition for codes-are new, and several previous results are given simplified proofs. The usefulness of the behavioral approach even for convolutional codes over fields is demonstrated by a new minimality test for encoders as well as by the straightforward derivation of some known minimality criteria for generator matrices from the basic minimality criteria for group trellises. The second part of the paper deals with issues that are specific to codes over rings and groups. The main result is a concise characterization-the first such-of those groups that can appear as the branch group of any group trellis. It is further shown how such groups are "presented" by shift registers. A new large class of noncommutative convolutional codes is also given.

The algebraic construction of linear codes over Zm for m-PSK is considered for the case that m is the product of two distinct primes. By means of the Chinese remainder theorem (CRT), such codes can be constructed from linear codes over the corresponding prime fields. It is shown that, for given component codes, the CRT composition yields PSK codes that are at least as good, and often much better, than the codes obtained from the standard coset coding technique. A lower bound on the minimum Euclidean distance of 6 PSK codes is derived that is based on the Hamming weight distribution of the component codes.>

Finite-length sequences over a finite alphabet with weights are considered. An information-theoretic upper bound on the number of such sequences whose weight does not exceed some given threshold is presented.>

A new decoder for trellis codes is presented. The decoder is based on a graph model consisting of diodes and switches. Such decoders may prove to be well suited for VLSI.>

Recently, linear codes over Z/sub M/ (the ring of integers mod M) have been presented that are matched to M-ary phase modulation. The general problem of matching signal sets to generalized linear algebraic codes is addressed based on these codes. A definition is given for the notion of matching. It is shown that any signal set in N-dimensional Euclidean space that is matched to an abstract group is essentially what D. Slepian (1968) called a group code for the Gaussian channel. If the group is commutative, this further implies that any such signal set is equivalent to coded phase modulation with linear codes over Z/sub M/. Some further results on such signal sets are presented, and the signal sets matched to noncommutative groups and the linear codes over such groups are discussed.>

A reliability metric (RM) for a block code is defined to be a function that operates on both the decoder input (a block of channel output) and the decoder output (the codeword estimate) and produces a real number as a measure of the reliability of the decoder decision. The best RM has the disadvantage of depending on the codeword probabilities. Thus, the ideal RM is defined as the value that would be computed for equally likely codewords. The implementation of the ideal RM is too costly for most applications. The author proposes an easily implemented RM for binary-input memoryless channels (for state-observable channels with a freely evolving state such as some fading channels) when the codewords consist of n 2/sup m/-ary symbols, each of which is transmitted serially by m uses of the channel. Simulation results for some BCH codes and some Reed-Solomon codes used in a simple ARQ system show that the proposed RM performs nearly as well as the ideal RM and much better than a previously proposed practical RM.>