Maximum-Likelihood Multiuser Sequence Detector
We now use the sufficient statistic above to derive the
maximum-likelihood detector for symbols in b. The maximum-likelihood sequence decision rule
chooses b that maximizes the log-likelihood
function (5.48). Using (5.46), the second integral in (5.48) can be computed as
Equation 5.58
where H denotes the
following MK x MK
block Jacobi matrix:
Equation 5.59
(
denotes
the Kronecker matrix product), 
, and recall that 
.
Substituting (5.49) and
(5.58) into (5.48), the log-likelihood function W(b) can then be written
as
Equation 5.60
For any integer n satisfying 1
n MK, denote its
modulo-K decomposition with remainder k(n) = 1, . . . , K, by
n = h(n)K + k(n) [518]. Then we can write
Equation 5.61
Equation 5.62
where in (5.62) the
vectors xn and fn have
dimensions DK + K –1, given, respectively, by
where 
denotes the kth column of matrix H[j], and 
, denotes
the (k, k')th
entry of H[j]. Substituting (5.61) and (5.62)
into (5.60), the log-likelihood function
can then be decomposed as follows:
Equation 5.63
where 
and
Equation 5.64
with the state vector recursively defined according to xn+1 =
[xn[2], . . . , xn[DK + K – 1], xn]T and x1 = 0(DK+K–1), where 0m denotes a
zero vector of dimension m.
Given the additive decomposition (5.63) of the log-likelihood function, it is
straightforward to apply the dynamic programming to compute the sequence 
that
maximizes W(b)
(i.e., the maximum-likelihood estimate of the transmitted multiuser symbol
sequences). Since the dimensionality of the state vector is DK + K – 1, the computational complexity of the
maximum-likelihood sequence detector is on the order of 
(2(D+1)K). Note that in the
absence of multipath (i.e., L = 1 and D = 1), if the users are numbered according to their relative
delays in ascending order (i.e., 0 t1,1 ··· t1,K < T), the
matrix H[–1] becomes strictly upper
triangular. In this case, the dimension of the state vector is reduced to K – 1 and the computational complexity of the
corresponding maximum likelihood sequence detection algorithm is (2K) [324, 518]. However, in the presence of
multipath, even if the multipath delays are still within one symbol interval
(i.e., D = 1), the matrix H[–1] no longer has an upper
triangular structure in general. Hence the dimension of the state vector in this
case is 2K – 1 and the complexity of the dynamic
programming is (22K). Even though the (2(D+1)K) complexity is
generally much lower than the (2KM) complexity of brute-force maximization of (5.60) (D is
typically only a few symbols, while the frame length M can be hundreds or even thousands of symbols), this
complexity is still prohibitively high if the number of users is even moderate
(say a dozen). Thus, it is of interest to find low-complexity alternatives.
Sections
