3.4 Nonlinear Group -Blind Multiuser Detection for Synchronous CDMA In Section 3.2 we developed linear receivers for detecting a group of  users' data bits in the presence of unknown interfering users. In this section we develop nonlinear methods for joint detection of the desired users' data. The basic idea is to construct a likelihood function for these users' data and then to perform a local search over such a likelihood surface, starting from the estimate closest to the unconstrained maximizer of the likelihood function, and along mutually orthogonal directions where the likelihood function drops at the slowest rate. The techniques described in this section were developed in [456]. Consider the signal model (3.2). Since the transmitted symbols b  {+1, “1} K   , for the convenience of the development in this section, we write (3.2) in terms of real-valued signals. Specifically, denote (recall that S is real valued) Equation 3.99 
where u [ i ] ~ N ( , ( s 2 /2) I 2 N ) is a real-valued noise vector. Then (3.2) can be written as Equation 3.100 
For notational simplicity in what follows , we drop the symbol index i . In this case the maximum-likelihood estimate of the transmitted symbols (of all users) is given by Equation 3.101 
where q is the stationary point of l ( b ): Equation 3.102 
In (3.101) the Hessian matrix of the log-likelihood function is given by Equation 3.103 
It is well known that the combinatorial optimization problem (3.101) is computationally hard (i.e., it is NP-complete) [519]. We next consider a local-search approach to approximating its solution. The basic idea is to search the optimal solution in a subset W of the discrete parameter set { “1, +1} K that is close to the stationary point q . More precisely, we approximate the solution to (3.101) by Equation 3.104 
In the slowest-descent method [453, 454], the candidate set W consists of the discrete parameters chosen such that they are in the neighborhood of Q ( Q  K ) lines in , which are defined by the stationary point q and the Q eigenvectors of  corresponding to the Q smallest eigenvalues. The basic idea of this method is explained next. 3.4.1 Slowest-Descent Search The basic idea of the slowest-descent search method is to choose the candidate points in W such that they are closest to a line ( q + m g ) in , originating from q and along a direction g , where the likelihood function p ( y b ) drops at the slowest rate. Given any line in , there are at most K points where the line intersects the coordinate hyperplanes (e.g., q 1 and q 2 in Fig. 3.10 for K = 2). The set of intersection points corresponding to a line defined by q and g can be expressed as Equation 3.105 
where q i and g i denote the i th elements of the respective vectors q and g . Each intersection point q i has only its i th component equal to zero (i.e.,  = 0). For simplicity we do not consider lines that simultaneously intersect more than one coordinate hyperplane since this event occurs with probability zero. Figure 3.10. One-to-one mapping from { q , q 1 , . . ., q K } to  for K = 2. Each intersection point q i is of equal distance from its two neighboring candidate points. b i is chosen to be one of these two candidate points that is on the opposite side of the i th coordinate hyperplane with respect to b* .  Any point on the line except for an intersection point has a unique closest candidate point in {+1, “1} K . An intersection point is of equal distance from its two neighboring candidate points [e.g., q 1 is equidistant to b 1 and b 2 in Fig. 3.10(a)]. Two neighboring intersection points share a unique closest candidate point [e.g., q 1 and q 2 share the nearest candidate point b 2 in Fig. 3.10(a)]. Define Equation 3.106 
as the candidate point closest to q , which is also the decision given by the decorrelating multiuser detector in a coherent channel. By carefully selecting one of the two candidate points closest to each intersection point to avoid choosing the same point twice, one can specify K distinct candidate points in {+1, “1} K that are closest to the line ( q + m g ). To that end, consider the following set: Equation 3.107 
It is seen that (3.107) assigns to each intersection point q i a closest candidate point b i that is on the opposite side of the i th coordinate hyperplane from b * [cf. Fig. 3.10(a) and (b)]. We next show that the K points in (3.107) are distinct. To see this, we use proof by contradiction. Suppose that otherwise the set in (3.107) contains two identical candidate points, say b 1 = b 2 . It then follows from the definitions in (3.105) and (3.107) that Equation 3.108 
Equation 3.109 
Consider the case q 1 > 0 and q 2 > 0. By (3.108) and (3.109) we have Equation 3.110 
Equation 3.111 
Hence, (3.110) and (3.111) contradict each other. The same contradiction arises for the other three choices of polarities for q 1 and q 2 . In general, the slowest-descent search method chooses the candidate set W in (3.104) as follows: Equation 3.112 
where q k and  denote the k th elements of the respective vectors q and g q . Hence, { b q, m } m contains the K closest neighbors of q in { “1, +1} K along the direction of g q . Note that  represents the Q mutually orthogonal directions where the likelihood function p ( y b ) drops most slowly from the peak point q . Intuitively, the maximum-likelihood solution  in (3.101) is probably in this neighborhood. The multiuser detection algorithm based on the slowest-descent-search method is summarized as follows ( assuming that the signature waveforms S and the complex amplitudes A of all users are known). Algorithm 3.3: [Slowest-descent-search multiuser detector] -
Compute the Hessian matrix given by (3.103) and its Q smallest eigen-vectors g 1 , . . . , g Q . -
Compute the stationary point q given by (3.102). -
Solve the discrete optimization problem defined by (3.104) and (3.112) by an exhaustive search [over ( KQ + 1) points]. The first step involves calculating the eigenvectors of a K x K symmetric matrix, the second step involves inverting a K x K matrix, and the third step involves evaluating the likelihood values at KQ + 1 points. Note that the first two steps need to be performed only once if a block of M data bits need to be demodulated. Hence the dominant computational complexity of the algorithm above is  ( KQ ) per bit for K users. Simulation Examples For simulations, we assume a processing gain N = 15, the number of users K = 8, and equal amplitudes of user signals (i.e., A k =1, k =1, . . ., K ). The signature matrix S and the user phase offsets {  A k }  are chosen at random and kept fixed throughout the simulations. Figure 3.11 demonstrates that the slowest-descent method with only one search direction ( Q = 1) offers a significant performance gain over the linear decorrelator. Searching one more direction ( Q = 2) results in some additional performance improvement. Further increase in the number of search directions only results in a diminishing improvement in performance. Figure 3.11. Performance of a slowest-descent-based multiuser detector in a synchronous CDMA system. N = 15, K = 8. The spreading waveforms S and complex amplitudes A of all users are assumed known to the receiver. The bit-error-rate (BER) curves of a linear decorrelator and slowest-descent detector with Q = 1 and Q = 2 are shown.  3.4.2 Nonlinear Group-Blind Multiuser Detection In group-blind multiuser detection, only the first users' signals need to be demodulated. As before, denote as  and  matrices containing, respectively, the first and the last K “ columns of S . Similarly define the quantities  ,  , and  , and  . Then (3.2) can be rewritten as (again, we drop the symbol index i for convenience) Equation 3.113 
Equation 3.114 
Let  denote the decorrelating detectors of the desired users, given by Equation 3.115 
where [ X ] :, n 1: n 2 denotes columns n 1 to n 2 of the matrix X . It is easily seen that satisfies Equation 3.116 
In group-blind multiuser detection, the undesired users' signals are first nulled out from the received signal by the following projection operation: Equation 3.117 
where the second equality in (3.117) follows from (3.114) and (3.116). Denote  Then (3.117) can be written as Equation 3.118 
Note that the covariance matrix of v is given by Equation 3.119 
with Equation 3.120 
In what follows we consider nonlinear estimation of from (3.118) based on the slowest-descent search. We also discuss the problem of estimating and from the received signals. The maximum-likelihood estimate of based on y in (3.118) is given by Equation 3.121 
where the Hessian matrix is given by Equation 3.122 
and  is the stationary point of  : Equation 3.123 
As before, we approximate the solution to (3.121) by Equation 3.124 
where  contains Q + 1 closest neighbors of  along the slowest-descent directions of the likelihood function p ( y ), given by Equation 3.125 
Equation 3.126 
Estimation of and To implement the local-search-based group-blind multiuser detection algorithm above, we must first estimate the decorrelator matrix and the complex amplitudes . Note that the decorrelating detectors for the desired users are simply the group-blind linear decorrelating detectors discussed in Section 3.2. For example, based on the eigendecomposition (3.37) of the autocorrelation matrix of the received signal, is given in terms of the signal subspace parameters by (3.38). We next consider estimation of the complex amplitudes of the desired users. Consider the decorrelator output (3.117); we now have [recall that  )] Equation 3.127 
where  . Since b k {+1, “1}, it follows from (3.127) that the decorrelator outputs corresponding to the k th user form two clusters centered, respectively, at A k and “ A k . Let  ; a simple estimator of A k is given by  with Equation 3.128 
Equation 3.129 
where { ·} denotes the sample average operation. Note that the foregoing estimate of the phase f k has an ambiguity of p , which necessitates differential encoding and decoding of data. Finally, we summarize the nonlinear group-blind multiuser detection algorithm for synchronous CDMA as follows. Algorithm 3.4: [Nonlinear group-blind multiuser detector ”synchronous CDMA] -
Compute the signal subspace: Equation 3.130 
Equation 3.131 
-
Form the linear group-blind decorrelating detectors: Equation 3.132 
Equation 3.133 
where  is given by the mean of the N - K eigenvalues in  . -
Estimate the complex amplitudes : Equation 3.134 
Equation 3.135 
Equation 3.136 
Equation 3.137 
Equation 3.138 
Equation 3.139 
Let Equation 3.140 
-
Compte the Hessian Equation 3.141 
and the Q smallest eigenvectors g 1 , . . . , g Q of  . -
Detect each symbol by solving the following discrete optimization problem using an exhaustive search (over Q + 1 points ): Equation 3.142 
Equation 3.143 
Equation 3.144 
Equation 3.145 
-
Perform differential decoding: Equation 3.146 
It is seen that compared with linear group-blind detectors discussed in Section 3.2, the additional computation incurred by the nonlinear detector involves a complex amplitude estimation step for all desired users and a likelihood search step, both of which have computational complexities linear in . Simulation Examples In this simulation we assume a processing gain N = 15, number of users K = 8, number of desired users = 4, and equal amplitudes of user signals. The signature matrix S and the user phase offsets are chosen at random and kept fixed throughout simulations. Figure 3.12 demonstrates the considerable performance gain offered by the nonlinear group-blind multiuser detector developed above over the group-blind linear detector. Again, it is seen that it suffices for the nonlinear group-blind detector to search along only one (i.e., the slowest-descent) direction ( Q = 1). Figure 3.12. Performance of a slowest-descent-based group-blind multiuser detector in a synchronous CDMA system. N = 15, K = 8, = 4. Only the spreading waveforms of the desired users are assumed known to the receiver. The BER curves of a linear group-blind detector and slowest-descent (nonlinear) group-blind detector with Q = 1 and Q = 2 are shown.   | 