PARTICLE FILTER ALGORITHMS FOR JOINT BLIND EQUALIZATION/DECODING OF

CONVOLUTIONALLY CODED SIGNALS

Claudio J. Bordin Jr. and Luiz A. Baccal a
Escola Polit ecnica, Universidade de S ao Paulo, 05508-900, S ao Paulo - SP, Brazil.
E-mail: bordin,[email protected]
ABSTRACT
This work introduces the use of particle lters for joint blind
equalization/decoding of convolutionally coded signals trans-
mitted over frequency selective channels. As in the equali-
zation-only case, we show how to evaluate the optimal im-
portance function recursively via a bank of Kalman lters.
Numerical simulation investigations using both stochastic
and deterministic particle selection strategies show the out-
standing superiority of the deterministic joint equalization/-
decoding method over approaches that perform blind equal-
ization using particle lters prior to optimal decoding.
1. INTRODUCTION
Either because of slow convergence or excessive complex-
ity, blind equalization still remains a practical challenge de-
spite the many approaches developed in the last two decades
(see [1] for a review). In this context, particle lters [2] - nu-
merical techniques for the solution of Bayesian estimation
problems - can play a major role as a compromise solution,
that balances robustness and convergence speed with com-
plexity of implementation.
Though not exactly new in an equalization-only setting
[3], particle lters failed to attract much attention until re-
cently, possibly due to the scarcity of theoretical results cou-
pled with the need for sufciently powerful computers that
are only now becoming more widely available. The im-
portance of particle lters is derived from their generality
which allows them to handle elaborate signal models that
are otherwise practically intractable (CDMA signal recep-
tion [4] for example).
As opposed to previous works [3] addressing equaliza-
tion-only scenarios, we here propose the idea of using par-
ticle lters to jointly blind equalize and decode convolu-
tionally coded signals transmitted over frequency selective
channels, in an extension of Punskayas work [5]. A fur-
ther innovative aspect is our use of noncoherently noncatas-
trophic codes [6] to successfully deal with the phase ambi-
guities inherent to the blind equalization problem.
Claudio J Bordin Jr. was supported by the FAPESP grant 02/11457-7.
After stating the estimation problem (Sec. 2) and over-
viewing particle lters (Sec. 3), we show how to obtain the
densities applicable to solving the joint blind equalization/de-
coding problem (Sec. 4). This is followed in Section 5 by
numerical illustrations leaving our conclusions to Section 6.
2. SIGNAL MODEL AND PROBLEM STATEMENT
Consider a convolutionally coded digital communication sys-
tem that transmits BPSK symbols over an additive noise
frequency selective channel. Denoting the transmitted bit
sequence by x
k
and the code rate by 1/R, the transmitted
(binary) symbol sequence c
k
is obtained as
c
Rm+n
=

l=0
x
ml
p
n
l

mod 2, 0 n < R, (1)

where K is the convolutional code constraint length and p
n
l
the code generator coefcients. The standard transmitted
BPSK signal is obtained by s
k
= 2 c
k
1.
We assume a linear and time-invariant FIR transmission
channel and perfect receiver synchronization, so that baud
rate samples y
k
of the received signal are expressed by the
base-band equivalent model
y
k
=
L1

l=0
h
l
s
kl
+ v
k
, (2)
where h
l
is the channel impulse response, L its duration in
symbol intervals and v
k
the additive noise assumed to be
zero-mean white circular gaussian of variance
2
v
.
In this work, we aim at obtaining MAP estimates x
k
of
the transmitted bits given the observed data, i.e.,
x
k
= arg max
x
k
p(x
k
|y
0:k+d
), (3)
where d 0 and y
0:k
(y
0
, . . . , y
(k+1)R1
). In next sec-
tions we describe how particle lters can be employed to
obtain estimates of the posterior densities p(x
k
|y
0:k+d
) for
the considered signal model.
III - 497 0-7803-8874-7/05/$20.00 2005 IEEE ICASSP 2005

3. PARTICLE FILTERS
Many estimation problems in discrete-time signal process-
ing, including blind equalization, can be stated as that of
tracking the state x
k
of a dynamic system

x
k+1
= f
k
(x
0
, . . . , x
k
, u
k
)
y
k
= g
k
(x
0
, . . . , x
k
, v
k
)
(4)
from the observation of its output y
0:k
sequence, where f
k
and g
k
, in full generality, may be nonlinear, time-varying
functions and u
k
and v
k
stand respectively for system driv-
ing and observation noise.
The Bayesian solution to (4) involves nding the poste-
rior density p(x
k
|y
0:k
), which can be accomplished in closed-
form only in a few restrictive cases. Particle lters pro-
vide iterative approximations to p(x
0:n
|y
0:n
) (from which
p(x
n
|y
0:n
) can be obtained by marginalization) via a weight-
ed sum of Dirac measures which approximates densities of
arbitrary shape [2].
3.1. Principles
Most particle ltering algorithms rest on the importance sam-
pling principle, whereby the probability density p(x
0:k
|y
0:k
)
can be consistently approximated [2] as the weighted sum
of Dirac measures
p(x
0:k
|y
0:k
) =

M
i=1
w
(i)
k

x
0:k
(x
(i)
0:k
)

M
i=1
w
(i)
k
, (5)
where x
(i)
0:k
, 1 i M, are independent samples (par-
ticles) from an arbitrary density (x
(i)
0:k
|y
0:k
) > 0 (impor-
tance function), with
x
0:k
(x
(i)
0:k
) denoting Dirac measures
in the variable x
0:k
centered in x
(i)
0:k
, and where w
(i)
k

(x
(i)
0:k
|y
0:k
)/p(x
(i)
0:k
|y
0:k
).
The key to the renewed interest in particle ltering comes
from the seminal work of Gordon et al. [7] showing that if
the importance function (x
0:k
|y
0:k
) can be factored as
(x
0:k
|y
0:k
) = (x
k
|x
0:k1
, y
0:k
)(x
0:k1
|y
0:k1
), (6)
each element of the sequence x
(i)
0:k
can be sampled sequen-
tially from the densities (x
m
|x
(i)
0:m1
, y
0:m
), 0 m
k. Likewise the weights w
(i)
k
can be sequentially updated,
since from Bayess law it follows that
p(x
0:k
|y
0:k
) = p(x
0:k1
|y
0:k1
)
p(x
k
, y
k
|x
0:k1
, y
0:k1
)
p(y
k
|y
0:k1
)
,
(7)
which in combination with (6) produces
w
(i)
n
w
(i)
k1
p(x
(i)
k
, y
k
|x
(i)
0:k1
, y
0:k1
)
(x
(i)
k
|x
(i)
0:k1
, y
0:k
)
. (8)
The choice of the importance function, though essen-
tially arbitrary, impacts the algorithm performance: one can
show that (x
k
|x
0:k1
, y
0:k
) = p(x
k
|x
0:k1
, y
0:k
) is opti-
mal in minimizing the conditional variance of the (unnor-
malized) weights w
(i)
k
hence improving algorithm perfor-
mance. After some iterations, due to a phenomenon known
Table 1. Stochastic Particle Filtering Algorithm
For k = 0, . . . , n,
For i = 1, . . . , M
-Draw x
(i)
k
from (x
k
|x
(i)
0:k1
, y
0:k
).
-Update the weights as in (8).
-Normalize the weights.
-Estimate p(x
0:k
|y
0:k
) as in (5).
as degeneracy, particle lters can lead to particles x
(i)
0:k
that
have negligible weights w
(i)
k
what severely compromise (5)s
estimation. To overcome this, the use of a selection scheme
is mandatory when sample quality falls below a predened
threshold.
Most particle lter algorithms in the literature employ
stochastic selection (namely, multinomial or residual resam-
pling [2]). Recently, [5] proposed algorithms that employ
deterministic selection, hence the name deterministic par-
ticle lters. Despite the lack of rigorous convergence re-
sults, their chief interest is their excellent performance in
certain situations. Motivation for them comes from observ-
ing that the optimal importance function can be expressed
as
p(x
k
|x
0:k1
, y
0:k
) =
p(x
k
, y
k
|x
0:k1
, y
0:k1
)

x
k
p(x
k
, y
k
|x
0:k1
, y
0:k1
)
, (9)
i.e., to determine p(x
k
|x
0:k1
, y
0:k
), one must evaluate the
termp(x
k
, y
k
|x
0:k1
, y
0:k1
) for each possible value of x
k
.
Hence, supposing that u
k
is a discrete vector variable with
D different possible values, at each iteration, the particle l-
ter discards M(D 1) candidates x
(i)
k
(D 1 for each
particle). Thus the idea of performing particle selection at
each iteration [8] as described in Table 2 comes to the fore.
As a nal remark, it is worth mentioning the particle l-
tering algorithms described so far can be easily extended to
provide xed-lag smoothed estimates, since for d > 0 [9]:
p(x
0:k
|y
0:k+d
)

M
i=1
w
(i)
k+d

x
0:k
(x
(i)
0:k
)

M
i=1
w
(i)
k+d
. (10)
4. BLIND EQUALIZATION AND DECODING
All densities needed to obtain estimates of p(x
0:k
|y
0:k
) via
both the stochastic particle lter (employing an optimal im-
III - 498

Table 2. Deterministic Particle lter Algorithm
For k = 0, . . . , n
For i = 1, . . . , M
For j = 1, . . . , D
-Calculate w
(i,j)
= w
(i)
k
p(x
k
= x
(j)
, y
k
|
x
0:k1
, y
0:k1
).
-Determine (I, J)
t
, the sequence of M pairs (i, j)
corresponding to the M largest w
(i,j)
.
For t = 1, . . . , M
-Make x
(t)
0:k1
= x
(It)
0:k1
and x
(t)
k
= x
(Jt)
.
-Make w
(t)
k
= w
(I,J)t
.
-Normalize the weights so that

M
i=1
w
(i)
k
= 1.
-Estimate p(x
0:k
|y
0:k
) as in (5).
portance function) and the deterministic particle lter de-
scribed in Sec. 3.1 can be obtained from p(x
k
, y
k
|x
0:k1
,
y
0:k1
) using (9). Assuming that x
k
is an IID sequence one
can show that
p(x
k
, y
k
|x
0:k1
, y
0:k1
) = p(y
k
|x
0:k
, y
0:k1
) p(x
k
) . (11)
Moreover, as the bit sequence x
k
uniquely denes the
transmitted symbol sequence s
k
, (11) implies (assuming that
x
k
= 0 for k < 0) that
p(y
k
|x
0:k
, y
0:k1
) = p(y
k
|S
0:(k+1)R1
, y
0:k1
) , (12)
where S
k
[ s
k
. . . s
kL+1
]
T
, and (s
0
, . . . , s
(k+1)R1
)
is the symbol sequence corresponding to the bit sequence
x
0:k
. The density on the r.h.s. of (12) further decomposes
as
p(y
k
|S
0:(k+1)R1
, y
0:k1
) =
R(k+1)1

j=Rk
p(y
j
|S
0:j
, y
0:j1
) .
(13)
In (13) we exploited the fact that p(y
j
|S
0:j
, y
0:j1
) = p(y
j
|
S
0:k
, y
0:j1
), k > j. In order to determine p(y
j
|S
0:j
, y
0:j1
)
note that using denitions above, (2) can be rewritten as

S
j+1
= AS
j
+ e
1
s
j+1
y
j
= h
H
S
j
+ v
j
(14)
where A is a (L L) shift matrix (all entries zero, ex-
cept the rst subdiagonal, whose entries are ones), e
1
=
[ 1 0 0 ]
T
and h = [ h
0
h
L1
]
T
.
From (14) one can see that y
j
is conditionally gaussian
given S
j
and h. Assuming that the parameter h has gaussian
prior distribution, and exploiting the fact it is conditionally
gaussian given S
0:j
and y
0:j1
, it can be integrated out [4],
resulting in
p(y
j
|S
0:j
, y
0:j1
) = N
C

y
j
|

h
H
j1
S
j
; S
H
j

j1
S
j
+
2
v

,
(15)
where

h
j
and
j
, respectively the conditional mean and
variance of h are obtained by means of conventional Kalman
lter iterations:

h
j
=

h
j1
+
y
j
S
H
j

h
j1
S
H
j

j1
S
j
+
2
v

j1
S
j
. (16)

j
=
j1

j1
S
j
S
H
j

j1
S
H
j

j1
S
j
+
2
v
. (17)
From(11)-(17), one can see that evaluating (11) for each
particle requires the evaluation of 2R Kalman lter steps.
Thus, if M particles are employed, the proposed algorithms
require the evaluation of 2MR Kalman lter steps per bit,
twice the complexity of an equalization-only algorithm (op-
erating at the symbol rate).
5. SIMULATIONS
We implemented blind equalization and decoding algorithms
employing particle lters for the signal model in Section 2,
and evaluated their performance using Monte Carlo simula-
tions that measured the bit error rates (BER) over 200 inde-
pendent realizations. In our illustrative simulations, we used
the channel h = [ 0.41 0.82 0.41 ]
T
and adopted two
R = 3 noncoherently noncatastrophic convolutional codes
[6] with constraint length K = 3 and K = 4 (with co-
efcients given in octal notation by (7,5,2) and (17,12,4),
respectively) in order to avoid phase ambiguities.
To compute the mean BER the algorithms processed
150 message bits in each realization, and employed a xed
smoothing lag of 25 samples. The particles initial states
S
(i)
1
were drawn from IID equiprobable 1 r.v., and we as-
sumed that
(i)
1
= I and h
(i)
1
N
C
(h|0; I). The BER
obtained by the proposed algorithms
1
as a function of the
SNR (signal-to-noise ratio) using M = 100 particles and
the (17,12,4) code is shown in Fig. 1. For comparison, we
also showthe performance obtained i) by the optimal MLSE
equalizer (Viterbi) followed by a hard-decision decoder and
ii) by a particle lter based blind equalization-only algo-
rithm [4] (employing differential encoding) followed by an
optimal soft decoder (based on the BCJR algorithm [10]).
As one can readily verify, the deterministic joint algo-
rithm outperformed all the others. The stochastic algorithm,
in turn, performed on average equivalently to the concate-
nated scheme, failing (i.e., obtaining BER of about 50%)
in some realizations even at high SNR.
Figure 2 depicts the bit error performances of the pro-
posed (deterministic) joint equalization and decoding algo-
rithm employing M = 50 and M = 100 particles and the
1
For the stochastic algorithm, we adopted that a multinomial resam-
pling step that is carried out whenever the effective sample size[2] falls
below 20%.
III - 499

-3 -2 -1 0 1 2 3 4 5 6
10
-4
10
-3
10
-2
10
-1
10
0
SNR (dB)
B
E
R
viterbi
separate det.
separate sto.
joint det.
joint sto.
Fig. 1. Performance of the proposed joint equalization and
decoding algorithms and of an alternative separate scheme
using deterministic and stochastic particle lters as a func-
tion of the SNR.
(17,12,4) (square) and (7,5,2) (circle) codes. As one can
verify, the performances obtained with M = 100 particles
are very similar for both codes. With M = 50, however, the
performance of the (17,12,4) code is worse, arguably be-
cause the number of possible states that need to be sampled
is larger in this case.
6. CONCLUSIONS
After introducing the novel use of particle ltering algo-
rithms for joint blind equalization and message decoding
over frequency selective channels that employ convolutional
codes, this work showed that deterministic particle lter-
ing is the best alternative, greatly outperforming both joint
stochastic particle lters and methods that equalize and de-
code messages separately.
7. REFERENCES
[1] Z. Ding and Y. Li, Eds., Blind Equalization and Iden-
tication, Marcel Dekker, New York, 2001.
[2] A. Doucet, J. de Freitas, and N. Gordon, Eds., Se-
quential Monte-Carlo Methods in Practice, Springer-
Verlag, Berlin, Germany, 2000.
[3] J. S. Liu and R. Chen, Blind deconvolution via se-
quential imputations, Journal of the American Statis-
tical Association, vol. 90, no. 430, pp. 567576, june
1995.
[4] P. M. Djuri c, J. H. Kotecha, J. Zhang, Y. Huang,
T. Ghirmai, M. F. Bugallo, and J. Miguez, Particle
-3 -2 -1 0 1 2 3 4 5 6
10
-4
10
-3
10
-2
10
-1
SNR (dB)
B
E
R
50 part.
100 part.
Fig. 2. Performance of the proposed (deterministic) joint
equalization algorithm employing M = 50 and M = 100
particle for the codes (17,12,4) (square) and (7,5,2) (circle)
as a function of the SNR.
ltering, IEEE Signal Processing Magazine, vol. 20,
no. 5, pp. 1938, september 2003.
[5] E. Punskaya, Sequential Monte Carlo Methods for
Digital Communications, Ph.D. thesis, University of
Cambridge, 2003.
[6] Y. Kofman, E. Zehavi, and S. Shamai, nd-
convolutional codes - part ii: Structural analysis,
IEEE Transactions on Information Theory, vol. 43, no.
2, pp. 576589, march 1997.
[7] N. J. Gordon, D. J. Salmond, and A. F. M. Smith,
Novel-approach to nonlinear non-gaussian bayesian
state estimation, IEE Proceedings-F Image & Signal
Processing, vol. 140, no. 2, pp. 107113, april 1993.
[8] B. Dong, X. Wang, and A. Doucet, A new class of
soft mimo demodulation algorithms, IEEE Transac-
tions on Signal Processing, vol. 51, no. 11, pp. 2752
2763, november 2003.
[9] T. Clapp, Statistical Methods for the Processing of
Communication Data, Ph.D. thesis, University of
Cambridge, 2000.
[10] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, Optimal
decoding of linear codes for minimizing symbol error
rate, IEEE Transactions on Information Theory, vol.
20, no. 2, pp. 284287, march 1974.
III - 500