Decision Directed Algorithms for Blind Equalization Based
on Constant Modulus Criteria
Carlos Alexandre R. Fernandes1 , Joao Cesar M. Mota2, G erard Favier1
1Laboratoire I3S
Les Algorithmes/Euclide B - 2000 route des Lucioles, BP 121, 06903 Sophia-Antipolis Cedex, France.
2GTEL/DETI/CT/UFC
Campus do Pici, 60.755-640, 6007 Fortaleza, Brazil
acarlos@i3s.unice.fr, mota@deti.ufc.br
favier@i3s.unice.fr
R esum e { Le but de cet article est de proposer une famille de techniques d? egalisation aveugle de signaux du type QAM.
Les algorithmes propos es sont dirig es par la d ecision et bas es sur des fonctions de co^ut du type Module Constante modi ees.
Deux approches sont consid er ees: l?approche du Gradient Stochastique et l?approche du Normalized Constant Modulus Algorithm
(NCMA). Les simulations num eriques con rment les r esultats attendus et montrent que les techniques propos ees am eliorent les
performances des algorithmes classiques bas es sur la fonction de co^ut CM.
Abstract { A family of techniques aiming to perform blind equalization for Quadrature Amplitude Modulation (QAM) signals
is presented. The proposed algorithms are decision directed and based on modi ed Constant Modulus (CM) criteria. Two
approaches are used to develop the algorithms: the Stochastic Gradient Descent approach and the Normalized Constant Modulus
Algorithm (NCMA) approach. Computer simulations con rm the expected results and show that the proposed algorithms
outperform the conventional CM based algorithms.
1 Introduction
The Constant Modulus Algorithm (CMA), developed in-
dependently by Godard [1] and Treichler [2], is one of the
most used techniques to perform blind equalization and
it works very well for modulations in which all points of
the signal constellation have the same radius, like Phase
Shift Keying (PSK) modulations. However, when the con-
stellation points are characterized by multiple radii, the
estimation error obtained with algorithms based on the
CM criterion does not reach zero, even if the channel is
perfectly equalized. This is one of the reasons for the un-
satisfactory performance of conventional CM algorithms
with QAM signals. It can only achieve a moderate level
of Steady-State Error (SSE). Moreover, we can say that
the speed of convergence is another important drawback
of the CM-type algorithms.
The main contribution of this work is to propose two
new classes of algorithms inspired on the CMA to im-
prove its performance for high level QAM signals. The
considered cost functions can be viewed as modi cations
of the CM criterion. In fact, one of the proposed modi ed
CM cost functions can be viewed as a generalization of the
CM criterion for constellations with multiple radii. The
others can be seen as generalizations of the Modi ed CM
(MCM) criterion, which allows to jointly perform blind
equalization and carrier recovery.
Supported by the Program Alban, the European Union Pro-
gram of high Level Scholarships for Latin America, scholarship n.
E04M049616BR.
It is well-known that the NLMS algorithm outperforms
the LMS algorithm. Thus, we will develop normalized
versions of the algorithms trying to improve their perfor-
mance, specially in the case of high level QAM signals.
Actually, each family is composed of four algorithms with
very desirable properties and advantages over the origi-
nal CM algorithms (CMA and NCMA). Dual-mode ver-
sions of the algorithms are also studied. They start with
a robust algorithm, i. e. not decision directed, and after
switch to a novel one, aiming to avoid an excessive number
of incorrect decisions during initial iterations.
2 Description of the Algorithms
Let us assume that: the transmitted i.i.d. sequence fa(n)g
can take the value of any constellation symbol with equal
probability; the output sequence of the equalizer fy(n)g
is given by (1), where h = [h(0) h(1) : ::: h(N 1) ] is the
impulse response of the Moving-Average (MA) channel,
N is the length of the channel and (n) is an additive
white Gaussian noise (AWGN). The number of taps of
the transversal equalizer is M and w(n) is its tap-weight
vector. ^a(n) is the output of the decision device (estimated
symbol).
y(n) =
MX
i=1
w(i)x(n i); where x(n) =
NX
i=0
h(i)a(n i)+ (n):
(1)
2.1 CMA-type Algorithms
In [3] we proposed a technique inspired by the CMA for
blind equalization of QAM signals: the Decision-Directed
Modulus Algorithm (DDMA). The DDMA can be seen
as a generalization of the CM cost function for multi-
ple radii constellations and it uses the squared magni-
tude of the decided symbol. The DDM cost function is
expressed in Table 1(line 2). Taking the stochastic gradi-
ent of the DDM cost function, we obtain the tap-weight
vector update equation of the Decision-Directed Modulus
Algorithm (DDMA):
w(n + 1) = w(n) e(n)x (n): (2)
where e(n) is given in Table 1 (line 2). The derivative
of ^a(n) relative to w(n) was assumed to be zero. As we
can see, the DDM cost function is able to reach to zero
for any symbol of the constellation. We may say that the
DDM is a "constellation matched" cost function. For PSK
modulations, the DDM and the CM cost functions are
equivalent. The main advantage of the DDMA algorithm
is its great performance with QAM constellations, in terms
of convergence speed and steady-state error (SSE). When
perfect equalization is achieved, the second term of the
DDMA update equation (2) goes to zero while in CMA it
never does so.
In [4] we did an analysis of the minima of the DDM
cost function based on the CMA analysis in [6]. It was
demonstrated, for the case of real signals, that the Wiener
solution is, approximately, a solution of the DDM crite-
rion minimization. It was also shown that the DDMA
has convergence properties that are very similar to that
of the CMA. However, the DDMA uses information of
last decided symbol, which makes the performance of the
DDMA worst if the number of incorrect decisions is too
large. To solve this problem, the initial adjustment of the
tap weight vector can be done by the CMA and when some
switching criterion is achieved, the equalization algorithm
switches to DDMA. In [3], this algorithm was called dual-
mode DDMA (or CMA-DDMA). The dual-mode DDMA
has a better performance than the DDMA, in terms of
convergence speed and SSE.
In [5] it was proposed a very interesting algorithm based
on a decomposition of the CM cost function: the Modi-
ed Constant Modulus Algorithm (MCMA). The MCM
cost function has real and imaginary references instead of
one modulus of reference in the CM cost function. These
in-phase and in-quadrature references make the MCMA
more adapted to QAM signals than the CMA. The MCM
cost function is the CM one decomposed into the real and
imaginary parts (Table 1 - line 3). The MCMA is able
to remove ISI and perform the carrier recovery jointly. It
implicitly corrects phase errors and may outperform the
conventional CMA with almost the same computational
cost.
It is possible to unify the modi cations done in the CM
cost function to create a new cost function that incor-
porates the improvements of the DDMA and MCMA to-
gether. This cost function will be similar to the MCM
cost function, but with variable references to the real and
imaginary parts of the signal. We will call this cost func-
tion of Modi ed DDM (MDDM) cost function (Table 1 -
line 4). Taking the stochastic gradient of the MDDM cost
function, we obtain the tap-weight vector update equation
of the Modi ed DDMA (MDDMA) (eq. 2 and Table 1 -
line 4). The MDDMA is also able to perform jointly blind
equalization and carrier recovery and it has the advan-
tages of both CMA and DDMA. However, the MDDMA
is also decision directed, so it also su ers if the number
of incorrect decisions is too large. In this case, we can
use the same approach as before: a robust algorithm per-
forms the initial adjustments (MCMA in this case) of the
equalizer and after we switch the algorithm.
2.2 NCMA-type Algorithms
The Normalized CMA (NCMA), proposed by a number of
authors, e.g. [7], is based on a particular choice of the step-
size and does not work very well with high QAM constel-
lations. At each iteration a step-size is chosen such that
the updated lter coe cients achieve the desired modulus
when applied to current data vector.
Based on the idea behind the DDMA, we can change
the NCMA constraint (Table 2 - line 2) to develop an
algorithm with good performances for blind equalization
with high QAM signals. The solution to this optimization
problem can be obtained in a similar way of the develop-
ment of the NCMA and leads to the Normalized DDMA
(NDDMA):
w(n + 1) = w(n) + kx(n)k2 e(n)x (n): (3)
where e(n) is shown in Table 2 (line 2). This new algo-
rithm can be seen as a generalization of the NCMA for
multiple radii constellations. The squared magnitude of
the NDDMA constraint can assume any of the squared
magnitude values of the constellation symbols, allowing
more exibility to the algorithm. So the NDDMA should
provide a signi cant performance improvement in relation
to the NCMA, when applied to high level QAM constel-
lations. The NDDMA can also be used as a dual-mode
algorithm, but, in this case, the initial algorithm is the
NCMA (to have less computational complexity).
A next step in the improvement of this family of algo-
rithms is to employ the idea behind the MCMA. For this
we can break the NCMA constraint into two (Table 2 -
line 3), and develop the Normalized MCMA (NMCMA)
in a similar way of NCMA (eq. 3 and Tab. 2 - line3). It is
important to remark that the NMCMA has almost identi-
cal complexity than the NCMA. The NMCMA implicitly
corrects phase errors and is not decision directed, which
means that it is not prejudiced by an incorrect decision.
One can think in using the modi cations done in the
NCMA by the NDDMA and NMCMA to create a new
algorithm that incorporates these improvements together.
But if we try to do this (eq. 3 and Table 2 - line 4), the re-
sulting algorithm is equivalent to the well-known Normal-
ized Least Mean Square - Decision Directed (NLMSDD)
algorithm. So, we can conclude that the NMCMA is more
robust and has a worst performance than the NLMSDD.
Tab. 1: The family of the CMA-type Algorithms
Algorithms Cost Functions Estimation Errors - e(n)
CMA Ef(jy(n)j2 R)2g y(n)(jy(n)j2 R)
DDMA Ef(jy(n)j2 j^a(n)j2)2g y(n)(jy(n)j2 j^a(n)j2)
MCMA Ef(y2R(n) RR)2 + (y2I(n) RI)2g yR(n)(y2R(n) RR) + jyI(n)(y2I(n) RI)
MDDMA Ef(y2R(n) ^a2R(n))2 + (y2I(n) ^a2I(n))2g yR(n)(y2R(n) ^a2R(n)) + jyI(n)(y2I(n) ^a2I(n))
Tab. 2: The family of the NCMA-type Algorithms
Algorithms Constraints Estimation Errors - e(n)
NCMA jwT (n + 1)x(n)j2 = R y(n)( Rjy(n)j 1)
NDDMA jwT (n + 1)x(n)j2 = j^a(n)j2 y(n)(j^a(n)jjy(n)j 1)
NMCMA RefwT (n + 1)x(n)g2 = RR
ImfwT (n + 1)x(n)g2 = RI yR(n)(1
p
RR
jyR(n)j) + jyI(n)(1
p
RI
jyI(n)j)
NLMSDD RefwT (n + 1)x(n)g2 = ^a2R(n)
ImfwT (n + 1)x(n)g2 = ^a2I(n) yR(n)(1 j^aR(n)jjyR(n)j) + jyI(n)(1 j^aI(n)jjyI(n)j)
In this case, we can use the same dual-mode approach as
before. To make the complexity lower, we can start with
the NMCMA and make the switch to the NLMS-DD by
only switching the "reference radii": pRR to j^aRj andp
RI to j^aIj.
3 Simulation results
The proposed family of algorithms was tested by means of
computational simulations. The simulation scenario con-
sists in a transmitted signal with a 16QAM or 64QAM
modulation, an equalizer with 9 taps, a 30dB SNR and
a discrete-time channel with impulse response given by:
h(n) = 0:2798 (n) + 1 (n 1) + 0:2798 (n 2). A PLL
is used to correct phase shift at the output of the equal-
izer, except for the algorithms of the "Modi ed" type,
which perform the carrier recovery by themselves. All
the Mean Squared Error (MSE) curves were obtained via
Monte Carlo simulations using 50 independent data real-
izations and the horizontal line shows the optimum Wiener
MSE.
Fig. (1) shows the learning curve of the CMA-type fam-
ily of algorithms for a 16QAM signal. First, we remark
that the DDMA has a SSE approximately 7dB smaller
than the CMA. As regards the modi ed algorithms, it is
clear from g. (1) that they have provided improvements
on the CMA and on the DDMA (MDDMA converges after
1800 iterations and DDMA after 4500 iterations approx-
imately). In this case, again it was not necessary to em-
ploy the dual-mode algorithms. However, for a 64QAM
signal the dual-mode approach provides very good im-
provements. We can see in g. (2) that the MCMA has
the better performance among all the single-mode algo-
rithms, since decision directed algorithms were penalized
by a high modulation level. Moreover, the DDMA has
a higher convergence speed than the MDDMA and the
Decision Directed Algorithm (DDA), which does not have
an acceptable level of MSE even after 40000 iterations.
However, working in a dual-mode version, the MDDMA
has a very good improvement of its performance, outper-
forming even the dual-mode DDMA and the dual-mode
DDA (MCMA-MDDMA converges after 1500 iterations,
CMA-DDMA after 3200 iterations and the CMA-DDA af-
ter 2700 iteration, approximately).
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
x 104
?20
?15
?10
?5
0
5
10
Iterations
Mean Squared Error ? dB
CMA
MCMA
DDMA
MDDMA
Fig. 1: MSE curves for the LMS-type algorithms -
16QAM.
As regards the normalized algorithms, g. (3) shows the
MSE for NCMA class of algorithms for a 16QAM signal.
One can see that the NMCMA has a worst performance
than the conventional NCMA. However the NDDMA has
improved the performance a lot of the NCMA and the
NLMSDD even more. Once again, it was not necessary to
employ the dual-mode algorithms. However, for a 64QAM
signal ( gure (4)), we see that the NDDMA, the NCMA
and the NLMSDD have not achieved yet a reasonable MSE
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
x 104
?20
?15
?10
?5
0
5
10
Iterations
Mean Squared Error ? dB
CMA
MDDMA
MCMA
MCMA?MDDMA
CMA?DDMA
DDMA
DDA
CMA?DDA
Fig. 2: MSE curves for the LMS-type algorithms -
64QAM.
after 40000 iterations. Moreover the NMCMA does not
su er so much in this case, as it is not decision directed.
Moreover, by working in a dual-mode version, the ND-
DMA and the NLMSDD have a very good improvement
in their performance. It should be highlighted that the
NLMSDD had a better performance when working with
the NMCMA than with the NCMA.
0 0.5 1 1.5 2 2.5 3 3.5 4
x 104
?20
?15
?10
?5
0
5
10
Iterations
Mean Squared Error ? dB
NMCMA
NLMSDD NDDMA
NCMA
Fig. 3: MSE curves for the NLMS-type algorithms -
16QAM.
4 Conclusions
In this paper, we have presented a new family of algo-
rithms characterized by some very desirable properties
when performing blind equalization for QAM signals. Sim-
ulation results con rms the behavior expected, showing a
great improvement of the proposed algorithms in relation
to the conventional ones. Their gain in performance is
very signi cative, with a very reasonable computational
cost (in relation to the original CM algorithms). The SSE
of the proposed algorithms are, in general, very close to
the Wiener MSE. The MDDM based algorithms can per-
form jointly blind equalization and carrier recovery, and
0 0.5 1 1.5 2 2.5 3 3.5 4
x 104
?20
?15
?10
?5
0
5
10
Iterations
Mean Squared Error ? dB
NCMA?NDDMA
NMCMA
NCMA NLMS?DD
NMCMA?NLMSDD
NDDMA
NCMA?NLMSDD
Fig. 4: MSE curves for the NLMS-type algorithms -
64QAM.
have shown to outperform the DDM based algorithms.
Perspectives of this work include a study of convergence
and generalization to nonlinear lter structures.
References
[1] D. N. Godard. Self-recovering equalization and car-
rier tracking in two dimensional data communication
system. IEEE Trans. on Communic., V. 28, pp. 1867{
1875, 1980.
[2] J.R. Treichler and B. Agee. A new approach to mul-
tipath correction of constant modulus signals. IEEE
Transactions on ASSP, V. 31, n. 4, pp. 459{472, 1983.
[3] C. A. R. Fernandes and J. C. M. Mota. New Blind Al-
gorithms Based on Modi ed Constant Modulus Crite-
ria for QAM Constellations. Lecture Notes in Comp.
Science (LNCS), V. 3124, pp. 498 { 503, aug 2004.
[4] C. A. R. Fernandes and J. C. M. Mota. Novos Algo-
ritmos Baseados em Estatisticas de Ordem Superior
de Decisoes Dirigidas para Equalizacao Autodidata.
Proc. of the 21 Simp. Brasileiro de Telecom., B elem
- Brazil, sep 2004.
[5] K. N. Oh and Y. O. Chin. Modi ed Constant Modulus
Algorithm: Blind Equalization and Carrier Phase Re-
covery Algorithm. Proc. of the 1995 Int. Conf. Com-
mun., V. 1, pp. 498{502, 1995.
[6] Z. Ding, R. A. Kennedy, B. D. O. Anderson and C. R.
Johnson Jr. Ill-Convergence of Godard Blind Equal-
izers in Data Communications Systems. IEEE Trans.
on Comm., V. 39, pp. 1313 { 1327, 1991.
[7] K. Hilal and P. Duhamel. A convergence study of the
constant modulus algorithm leading to normalized-
CMA and a block-normalized-CMA. EUSIPCO, pp.
135 { 138, 1992.