HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.de

S

Series in
Signal and Information Processing, Vol. 19
edited by HansAndrea Loeliger
Junli Hu
On Gaussian
Approximations in Message
Passing Algorithms with Application to Equalization
1. Auflage/1^{st} edition 2008.
VIII, 104 Seiten/pages, € 64,00.
ISBN 3866282125, 9783866282124
Data estimation appears in many areas of the signal processing: digital
communication, data extraction in biomedical applications, parameter estimation
and tracking in control systems, and data save and read on magnetic storage
devices. Depending on the system model and estimation criteria, we use
different algorithms or their combinations for this challenging task.
Based on a graphical model, the factor graphs, we initiate the discussionby addressing the data estimation in digital
communication, which is also known as equalization. We generalize the
discretetime system model, used in the communication to other applications by
recognizing that we can often describe a data source by a sequence of discrete
valued, e.g. binary, random variable. This sequence is sent through a discretetime channel model and at the channel output, we
get a sequence of observations which is corrupted by an additive white Gaussian
noise process. The equalization means, given the observation and the system
model, including the knowledge on the stochastic processes of the input source
and the noise at the output, we estimate the input sequence.
In the factor graph notation, we describe two wellknown algorithms: the
BCJR and the Kalman filtering or LMMSE (linear
minimum mean squared error) algorithms. The BCJR algorithm delivers the maximum
aposteriori (MAP) estimation, which is the optimum for the above system
setting. However, its exponential computational complexity is prohibitive for
many applications, when the alphabet size of the discrete input source and/or
the channel order is large. The LMMSE algorithm does not give the exact MAP
estimation for the discrete data input. The equalization result, expressed in
the error percentage of the estimated symbol, has usually a huge gap to that by
the BCJR algorithm. The complexity of the LMMSE estimation is cubic in the
channel order. Therefore, it is widely used in many applications.
As one of the main contributions, we propose a Gaussian approximation
for a discrete random variable. This is inspired by the assumed density
filtering (ADF) and the expectation propagation (EP), both discussed by Th. Minka in his thesis. We apply this new Gaussian
approximation to the Kalman filtering and get an
iterative scheme. We can show that this iterative Kalman
filter delivers a much better result than the pure LMMSE solution, when the
input data sequence is uncoded. The complexity
remains the cubic in the channel order. In some uncoded
cases, it almost close the gap of the result to the
one by the BCJR algorithm. For coded input data, this new approximation method
does not seem to help much. Therefore, it is suitable to some applications,
e.g., some biomedical applications, where we have only prior knowledge over the
input stochastic process. To applications in the communication, where the input
data are mostly coded, this new approximation is not very interesting.
In another contribution, we study the multiplier (scalar product) node
in a factor graph. We propose two Gaussian approximations: one for the forward
message of the scalar output variable, the other for the backward message of
one of the input vectors. The approximation of the backward message is compared
with the sumproduct message and the traditional expectation maximization (EM)
approximation. The Gaussian approximation of the forward message is compared
with the true distribution of the output random variable experimentally.
Keywords: Gaussian Approximation, Message Passing Algorithm, Equalization, Kalman Filtering.
Reihe "Series
in Signal and Information Processing" im HartungGorre Verlag
Buchbestellungen in Ihrer
Buchhandlung, bei www.amazon.de
oder direkt:
HartungGorre Verlag /
D78465 Konstanz
Telefon: +49 (0) 7533
97227 Telefax: +49 (0) 7533 97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de