Linear Multiuser Detection via Iterative Interference Cancellation
From (5.56) we can write the
expression for the sufficient statistic vector y in matrix form as
Equation 5.65
where by (5.57), v ~ Nc(0, s2H). Recall that in linear multiuser detection, a
linear transformation is applied to the sufficient statistic vector y, followed by local decisions for each user.
That is, the multiuser data bits are demodulated according to
Equation 5.66
where W is an MK x MK complex matrix. As discussed in Chapter 2, two popular linear multiuser
detectors are the linear decorrelating (i.e., zero-forcing) detector, which
chooses the weight matrix W to eliminate
the interference completely (at the expense of enhancing the noise), and the
linear MMSE detector, which chooses the weight matrix W to minimize the mean-square error between the
transmitted symbols and the outputs of the linear transformation (i.e., E {||A b – W
y||2}). The corresponding weight matrices for these two linear
multiuser detectors are given, respectively, by
Equation 5.67
Equation 5.68
Since the frame length M is
typically large, direct inversion of the MK x
MK matrices above is too costly for practical
purposes. Moreover, the complexity cannot generally be mitigated over multiple
frames, since the matrices H and A may vary from frame to frame due to mobility,
aperiodic spreading codes, and so on. This complexity can be mitigated, however,
by using iterative methods of equation solving, which we now discuss. We first
consider Gauss–Seidel iteration to obtain the linear multiuser detector output.
This method effectively performs serial interference cancellation on the
sufficient statistic vector y and
recursively refines the estimates of the multiuser signals 
. Denote
such an estimate at the mth iteration as 
.
Also denote 
and 
. The algorithm is listed in Table 5.1.
The convergence properties of this serial interference
cancellation algorithm are characterized by the following result.
Proposition 5.5: (1) If 
and
if H is positive
definite, then xm 
Wdy, as m 
; (2)
if 
, then xm Wmy, as m .
Proof: Consider the following
system of linear equations:
Equation 5.69
The Gauss–Seidel procedure [598] for iteratively solving x from (5.69) is given by
Equation 5.70
Substituting in (5.70)
the notations 
for k = 1, . . ., K, i = 0, . . ., M – 1,
and the elements of the matrix H given in
(5.59), it
then follows that the serial interference cancellation procedure in Table 5.1 is the same as the Gauss–Seidel
iteration (5.70) if we choose .
Then by the Ostrowski–Reich theorem [598], a sufficient condition for the
Gauss–Seidel iteration (5.70) to converge
to the solution of (5.69) (i.e., the
output of the linear decorrelating detector, 
is that
H be positive definite.
Table 5.1. Iterative Implementation of Linear Space-Time
Multiuser Detection Using Serial Interference Cancellation
|
|
Similarly, consider the system of linear equations
Equation 5.71
The corresponding Gauss–Seidel iteration is given by
Equation 5.72
which is the same as the serial interference cancellation
procedure in Table 5.1 with 
. It is seen from (5.58) that the matrix H is positive semidefinite, as 
dt = xH Hx 
0, where 
.
Therefore, (H + s2 A–2) is
positive definite, and by the Ostrowski–Reich theorem, iteration (5.72) converges to the solution to (5.71) [i.e., the output of the linear MMSE
detector, xm (H + s2 A–2)–1 
].
The computational complexity of the iterative serial
interference cancellation algorithm above per user per bit is 
, where
is the total number of iterations. The complexity per user per bit of
direct inversion of the matrices in (5.67) or (5.68) is
(K3M3/KM) = (K2M2). By exploiting the Hermitian (2D + 1)-block Toeplitz structure of the matrix H, this complexity can be reduced to (K2MD) [324]. Since in practice the number of
iterations is a small number (e.g., 
), the iterative method for linear
multiuser detection above achieves significant complexity reduction over the
direct matrix inversion method.
A natural alternative to the serial interference cancellation
method is the following parallel interference
cancellation method,
Equation 5.73
Unlike the serial method, in which the new estimate 
is used to update the subsequent estimates as soon as it is available, in the
parallel method, at the mth iteration,
is updated using the estimates only from the previous iteration. Parallel
interference cancellation corresponds to Jacobi's method [598] for solving the linear system
(5.69) or (5.71):
Equation 5.74
with g[i']=H[i', i'] or g[i'] = H[i', i']+ s2/ A[i', i']2. However, the convergence of Jacobi's
method (5.74) and hence that of the
parallel interference cancellation method (5.73) is not guaranteed in
general. To see this, for example, let D be
the diagonal matrix containing the diagonal elements of H and let H
= D + B be the splitting of H into its diagonal and off-diagonal elements.
Suppose that H = D + B is
positive definite; then a necessary and sufficient condition for the convergence
of Jacobi's iteration is that D - B be
positive definite [598]. In general, this condition may
not be satisfied, and hence the parallel interference cancellation method (5.74) is not guaranteed to produce the
linear multiuser detector output. An analysis of parallel interference
cancellation is found in [53]. Other iterative methods for
solving (5.71), such as
conjugate-gradient techniques, are described in [92].
Sections
