Equalization
We now turn to the situation in which there is more than one
symbol in the frame of interest (i.e., when M
> 1). In this case we would like to consider the likelihood function of the
observations r(·) conditioned on the entire frame
of symbols, b1[0], b1 [1], ..., b1[M - 1],
which is given by
Equation 1.38
where the superscript H denotes
the conjugate transpose (i.e., the Hermitian transpose), b1 denotes a column vector whose ith component is b1[i], i = 0, 1, ..., M - 1,
y1 denotes a column vector whose
ith component is given by
Equation 1.39
and H1 is an
M x M Hermitian matrix, whose (i,j)th element is the cross-correlation between fi, 1(t) and fj, 1(t):
Equation 1.40
Since the likelihood function depends on r(·) only through the vector y1 of correlator outputs, this vector
is a sufficient statistic for making inferences about the vector b1 of symbols [377].
Maximum-likelihood detection in this situation is given by
Equation 1.41
Note that if H1
is a diagonal matrix (i.e., all of its off-diagonal elements are zero), (1.41) decouples into a set of M independent problems of the single-symbol type (1.22). The solution in this case is
correspondingly given by
Equation 1.42
where
Equation 1.43
However, in the more general case in which there is intersymbol
interference, (1.41) will not decouple
and the optimization must take place over the entire frame, a problem known as
sequence detection.
The problem of (1.41) is
an integer quadratic program which is known to be an NP-complete combinatorial
optimization problem [380]. This implies that the
complexity of (1.41) is potentially quite
high: exponential in the frame length M, which is
essentially the complexity order of exhausting over the sequence alphabet AM. This is a prohibitive degree of
complexity for most applications, since a typical frame length might be hundreds
or even thousands of symbols. Fortunately, this complexity can be mitigated
substantially for practical ISI channels. In particular, if the composite
signaling waveforms have finite duration D, the
matrix H1 is a banded matrix
with nonzero elements only on those diagonals that are no more than D = 
D/T 
diagonals away
from the main diagonal (here · denotes the smallest integer not less than its
argument); that is,
Equation 1.44
This structure of the matrix permits solution of (1.41) with a dynamic program of complexity
order 
, as opposed to the 
complexity of direct search. In most
situations D « M, which
implies an enormous savings in complexity (see, e.g., [380]). This dynamic programming
solution, which can be structured in various ways, is known as a maximum-likelihood sequence detector (MLSD).
MAP detection in this model is also potentially of very high
complexity. The a posteriori probability
distribution of a particular symbol, say b1[i], is
given by
Equation 1.45
Note that these summations have terms and
thus are of complexity similar to those of the maximization in (1.41) in general. Fortunately, like (1.41), when H1 is banded these summations can be
computed much more efficiently using a generalized dynamic programming technique
that results in complexity (see, e.g., [380]).
The dynamic programs that facilitate (1.41) and (1.45)
are of much lower complexity than brute-force computations. However, even this
lower complexity is too high for many applications. A number of lower-complexity
algorithms have been devised to deal with such situations. These techniques can
be discussed easily by examining the sufficient statistic vector y1 of (1.39), which can be written as
Equation 1.46
where n1 is a
complex Gaussian random vector with independent real and imaginary parts having
identical 
distributions. Equation (1.46) describes a linear model, and the goal of
equalization is thus to fit this model with the data vector b1. The ML and MAP detectors are two
ways of doing this fitting, each of which has exponential complexity with
exponent equal to the bandwidth of H1. The essential difficulty of this
problem arises from the fact that the vector b1 takes on values from a discrete
set. One way of easing this difficulty is first to fit the linear model without
constraining b1 to be discrete,
and then to quantize the resulting (continuous) estimate of b1 into symbol estimates. In
particular, we can use a linear fit, My1, as a continuous estimate of b1, where M is an M x M
matrix. In this way, the ith symbol decision
is
Equation 1.47
where [My1]i denotes the ith
component of My1 and where q(·) denotes a quantizer mapping the complex numbers to
the symbol alphabet A. Various choices of the
matrix M lead to different linear
equalizers. For example, if we choose M =
IM, the M x M
identity matrix, the resulting linear detector is the common matched filter,
which is optimal in the absence of ISI. A difficulty with the matched filter is
that it ignores the ISI. Alternatively, if H1 is invertible, the choice 
forces the ISI to zero,
Equation 1.48
and is thus known as the zero-forcing
equalizer (ZFE). Note that this would be optimal (i.e., it would give
perfect decisions) in the absence of AWGN. A difficulty with the ZFE is that it
can significantly enhance the effects of AWGN by placing high gains on some
directions in the set of M-dimensional complex
vectors. A trade-off between these extremes is effected by the minimum-mean-square-error (MMSE) linear equalizer, which chooses M to give an MMSE fit of the model (1.46). Assuming that the symbols are
independent of the noise, this results in the choice
Equation 1.49
where Sb denotes
the covariance matrix of the symbol vector b1.
(Typically, this covariance matrix will be in the form of a constant times IM.) A
number of other techniques for fitting the model (1.46) have been developed, including iterative methods
with and without quantization of intermediate results [decision-feedback
equalizers (DFEs)], and so on. For a more detailed treatment of equalization
methods, see [396].
Sections
