RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

ADAPTIVE EQUALIZATION:
A TUTORIAL
Kevin Banovic

October 14, 2005

Department of Electrical and Computer Engineering,

University of Windsor, Windsor, Ontario, Canada N9B 3P4
 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Adaptive Equalization

ƒ Adaptive equalizers compensate for signal distortion

attributed to intersymbol interference (ISI), which is
caused by multipath within time-dispersive channels.
ƒ Typically employed in high-speed communication
systems, which do not use differential modulation
schemes or frequency division multiplexing
ƒ The equalizer is the most expensive component of a data
demodulator and can consume over 80% of the total
computations needed to demodulate a given signal [01]

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 2

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Adaptive Equalization

s(k) r(k) FIR y(k) Decision s(k)

Channel
Equalizer Device

Equalizer e(k) Error

Adjustment Computation

Training
Sequence
Decision-Directed
Training Mode Mode
Symbol
Statistics
Blind Mode

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 3

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Adaptive Equalization

ƒ The following quantities are defined for a linear equalizer

with a real input signal:
ƒ Equalizer tap coefficient vector:
T
£ ¤
f (k) = f0 (k) f1 (k) . . . f(Lf −1) (k)

ƒ Equalizer input samples in the tapped delay line:

£ ¤T
r(k) = r0 (k) r1 (k) . . . rLf −1 (k)
£ ¤T
= r0 (k) r0 (k − 1) . . . r0 (k − Lf + 1)

ƒ Equalizer output: (Lf = equalizer length)

Lf −1
X
y(k) = fi (k) · r0 (k − i) = f T (k)r(k)
i=0

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 4

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Adaptive Equalization

ƒ Error signal:

e(k) = d(k) − y(k)

= d(k) − f T (k)r(k)

where ‘d(k)’ is the desired signal

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 5

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Minimum Mean-Squared-Error (MMSE) Equalization

ƒ The mean-squared-error cost function is defined as [02]:

M SE
© 2 ª
J = E e (k)
© 2 2
ª
= E d (k) − 2d(k)y(k) + y (k)
© 2 ª © T
ª © T T
ª
= E d (k) − 2E d(k)f (k)r(k) + E f (k)r(k)r (k)f (k)

ƒ When the filter coefficients are fixed, the cost function can
be rewritten as follows:
MSE
© 2 ª T T
© T
ª
J = E d (k) − 2f E {d(k)r(k)} +f E r(k)r (k) f
| {z } | {z }
p R
© 2 ª
= E d (k) − 2f T p + f T Rf

ƒ Where ‘p’ is the cross-correlation vector and ‘R’ is the

input signal correlation matrix
KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 6
 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Minimum Mean-Squared-Error (MMSE) Equalization

ƒ The gradient of the MSE cost function with respect to the

equalizer tap weights is defined as follows:
M SE
· M SE M SE M SE
¸
∂J ∂J ∂J ∂J
∇f J MSE = = ...
∂f ∂f0 ∂f1 ∂fLf −1
= −2p + 2Rf

ƒ The optimal equalizer taps ‘fo’ required to obtain the

MMSE can be determined by replacing ‘f’ with ‘fo’ and
setting the gradient above to zero:

0 = 2Rfo − 2p → fo = R−1 p

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 7

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Minimum Mean-Squared-Error (MMSE) Equalization

ƒ Finally, the MMSE is expressed as follows:

© 2 ª
ξmin = E d (k) − 2foT p + foT Rfo
© 2 ª £ −1 ¤T £ −1 ¤T £ −1 ¤
= E d (k) − 2 R p p + R p R R p
© 2 ª
= E d (k) − 2pT R−1 p + pT R−1 p
© 2 ª
= E d (k) − pT R−1 p

Questions:
Why is the MSE cost function so popular?
Is the calculation of ‘fo’ practical?

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 8

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Method of Steepest Descent

ƒ In practical situations, an analytic description of the cost

surface is not available
ƒ However, points can be estimated by time-averaging and
search algorithms are used to descend the surface
ƒ The method of steepest descent is a gradient search
algorithm that adjusts the equalizer tap weights in
direction of the negative gradient as follows [02][03]:
¡ M SE
¢
f (k + 1) = f (k) + µ · −∇f J

Where µ is constant stepsize that controls the speed and

accuracy of the equalizer tap adaptation.

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 9

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Method of Steepest Descent

ƒ For convergence, µ is chosen as follows [02][03]:

1
0<µ<
λmax

Where λmax is the maximum eigenvalue of ‘R’

ƒ At the minimum, this method requires a noisy estimate of
the gradient during each iteration, which hinders its
application in real applications
ƒ However, it serves as the basis for an entire class of
practical algorithms, including the algorithms to follow

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 10

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Least-Mean-Squares Algorithm (LMS)

ƒ The least-mean-squares (LMS) algorithm simplifies the

gradient calculation by using instantaneous quantities
instead of expected quantities [02]
ƒ Let us define the following estimates of ‘p’ and ‘R’:
R̂ = r(k)rT (k)
p̂ = d(k)r(k)

ƒ Substituting these estimates, the gradient becomes:

∇f J LM S = −2p̂ + 2R̂f (k)
¡ T
¢
= −2 (d(k)r(k)) + 2 r(k)r (k) f (k)
¡ T
¢
= −2r(k) d(k) − r (k)f (k) = −2e(k)r(k)
| {z }
e(k)

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 11

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Least-Mean-Squares Algorithm (LMS)

ƒ The LMS equalizer tap adjustment is as follows:

¡ LM S
¢
f (k + 1) = f (k) + µ · −∇f J
= f (k) + µ · e(k)r(k)

ƒ The LMS algorithm has two modes of operation: a

training mode and a tracking or decision-directed mode
ƒ In the following example uses Proakis channel B [04], a
stepsize of 5x10-3, and a 2-tap LMS equalizer
0.815

0.404 0.404

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 12

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Least-Mean-Squares Algorithm (LMS)

MSE Surface
1.8

1.6

1.4

1.2

1
f1

0.8

0.6

0.4

0.2

−0.4 −0.2 0 0.2 0.4 0.6 0.8 1 1.2 1.4

f0

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 13

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Least-Mean-Squares Algorithm (LMS)

Smoothed squared−error history

4 MSE bound

−2
dB

−4

−6

−8

−10

−12
0 1000 2000 3000 4000 5000
iteration number

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 14

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Least-Mean-Squares Algorithm (LMS)

Questions:
What is the relationship between steady-state MSE, the
time-to-convergence and the stepsize?

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 15

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Generalized Sato Algorithm (GSA)

ƒ The generalized Sato algorithm is the first of three blind

algorithms that we will be discussing
ƒ Blind algorithms achieve channel equalization without the
transmission of a training sequence
ƒ The generalized Sato equalizer tap update for complex
signals is defined as [05][06]:
f (k + 1) = f (k) + µ · (csgn(y(k))γ − y(k)) r∗ (k)
| {z }
−∇f J GSA =eGSA (k)

Where ‘csgn(·)’ is the complex sign operator, ‘γ’ is a constant

of the source signal, and ‘*’ is the complex conjugate
operator

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 16

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Constant Modulus Algorithm (CMA)

ƒ The CMA is a carrier-phase independent blind algorithm

that is based on the signal modulus
ƒ The CMA equalizer tap update is defined as [07][08][09]:

f (k + 1) = f (k) + µ · y(k)(γ 2 − |y(k)|2 ) r∗ (k)

| {z }
−∇f J CM A =eCM A (k)

ƒ As illustrated in the figure to follow, the CMA requires

phase-recovery after convergence in order to rotate the
constellation

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 17

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Constant Modulus Algorithm (CMA)

Sent Signal Constellation Received Signal Constellation
2 2

1 1
Im{s(n)}

Im{s(n)}
0 0

−1 −1

−2 −2
−2 0 2 −2 0 2
Re{s(n)} Re{s(n)}
Equalized Output (CMA) Equalized Output with Carrier Recovery
2 2

1 1
Im{s(n)}

Im{s(n)}

0 0

−1 −1

−2 −2
−2 0 2 −2 0 2
Re{s(n)} Re{s(n)}

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 18

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Multimodulus Algorithm (MMA)

ƒ The MMA minimizes dispersion of the equalizer output

around separate straight contours
ƒ The MMA equalizer tap update is defined as [10]:
fR (k + 1) = fR (k) + µ · yR (k)(γ 2 − yR
2
(k)) r∗ (k)
| {z }
MMA =eMMA (k)
−∇f JR R

fI (k + 1) = fI (k) + µ · yI (k)(γ 2 − yI2 (k)}) r∗ (k)

| {z }
−∇f JIMMA =eMMA
I (k)

f (k + 1) = fR (k + 1) + j · fI (k + 1)

Where ‘R’ and ‘I’ correspond to the real and imaginary

components, respectively

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 19

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Simulation of Blind Algorithms

MSE Curves for Blind Algorithms
10

Stepsize: µ=10−3
SNR: 30dB
Signal: 16−QAM
Channel: SPIB #2
0 Lf: 16
MSE (dB)

−10 GSA CMA

MMA

−20

−30
0 0.5 1 1.5 2
samples 4
x 10

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 20

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Blind Equalization

Questions:
What are the advantages of blind equalization?
Drawbacks?

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 21

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

Equalization Tutorials

ƒ For more information on adaptive equalization in general,

check out the following tutorials:
ƒ Adaptive Equalization [11]
ƒ Equalization in High-Speed Communication Systems [12]

ƒ For more information on blind equalization, check out the

following tutorials:
ƒ Blind Equalization for Broadband Access [13]
ƒ A comparative performance study of several blind
equalization algorithms [06]

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 22

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

References

[01] J.R. Treichler, M.G. Larimore and J.C. Harp, “Practical Blind Demodulators
for High-order QAM signals", Proceedings of the IEEE special issue on Blind
System Identification and Estimation, vol. 86, pp. 1907-1926, Oct. 1998
[02] B. Widrow and S.D. Sterns, Adaptive Signal Processing, Prentice Hall, New
York, 1985.
[03] P.S.R. Diniz, Adaptive Filtering, Kluwar Academic Publishers, Norwell,
Massachusetts, 2002.
[04] J.G. Proakis, Digital Communications, McGraw Hill, New York, 2001
[05] Y. Sato, “A method of self-recovering equalization for multilevel amplitude-
modulation systems", IEEE Trans. on Communications, Vol. 23, June 1975,
pp. 679-682.
[06] J.J. Shynk, R.P. Gooch, G. Krishnamurthy, and C.K. Chan, "A comparative
performance study of several blind equalization algorithms", SPIE, Vol. 1565,
pp. 102-117, 1991

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 23

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

References

[07] D.N. Godard, “Self-recovering equalization and carrier tracking in two-

dimensional data communication systems”, IEEE trans. on comm., Vol 28,
No. 11, November 1980
[08] J. R. Treichler and B. G. Agee, "A new approach to multipath correction of
constant modulus signals", IEEE Trans. on Acoust., Speech, Signal
Processing, Vol. ASSP-31, No. 2, April 1983, pp. 459-472.
[09] R. Johnson, Jr., P. Schniter, T.J. Endres, J.D. Behm, D.R. Brown, and R.A.
Casas, ”Blind equalization using the constant modulus criterion: a review”,
Proceedings of the IEEE, Vol. 86, No. 10, Oct. 1998, pp. 1927-1950.
[10] J. Yang, J.J. Werner and G.A. Dumont, “The Mulitimodulus Blind
Equalization and Its Generalized Algorithms", IEEE Journal on selected
areas in communication, Vol 20, No. 5, June 2002, pp. 997-1015.
[11] S.U.H. Qureshi, "Adaptive equalization", Proceedings of the IEEE, Vol. 73,
No. 9, September 1985, pp. 1349-1387.
[12] J. Liu and X. Lin, "Equalization in High-Speed Communication Systems",
IEEE Circuits and Systems Magazine, 2004, pp. 4-17.

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 24

 RESEARCH CENTRE FOR INTEGRATED MICROSYSTEMS – UNIVERSITY OF WINDSOR

References

[13] J.-J. Werner, J. Yang, D. Harman, and G.A. Dumont, "Blind Equalization for
Broadband Access", IEEE Communications Magazine, 1999, pp. 87-93.
[14] Signal Processing Information Base. [Link]
[15] P. Schniter, Adaptive Linear Identifier (ALI) Laboratory,
[Link]

KEVIN BANOVIC EQUALIZATION TUTORIAL Slide 25