The application of nonlinear programming for multiuser detection in CDMA

In this paper, a heuristic algorithm based on a nonlinear nonconvex programming relaxation of the CDMA maximum likelihood (ML) problem is presented. Simulation results have shown that the BER performances of a detection strategy based on the heuristic algorithm are similar to that of the detection strategy based on the semidefinite relaxation. Furthermore, average CPU time of the heuristic algorithm is significantly lower than that of the randomized rounding algorithm based on a semidefinite relaxation. This approach provides good approximations to the ML performance.     

Noncoherent multiuser detection for CDMA systems with nonlinearmodulation: a non-Bayesian approach

This paper considers the problem of multiuser detection for a system in which each user employs nonlinear modulation, with an emphasis on noncoherent detection techniques which do not require knowledge of the users' channel parameters at the receiver. Our goals are to gain fundamental insight into the capabilities of multiuser detection in such a setting, and to provide practical algorithms that perform better than conventional matched-filter reception. We begin by providing fundamental performance benchmarks by considering coherent maximum-likelihood (ML) detection, which requires knowledge of the users' channel parameters, as well as noncoherent detection, formulated in a non-Bayesian generalized likelihood ratio test (GLRT) framework. The asymptotic performance of each detector, as the noise level vanishes, is characterized, yielding simple geometric criteria for near-far resistance. In general, both the ML and GLRT detectors have complexity which is exponential in the number of users. We, therefore, propose the more practical sequential decision projection (SDP) detector which has complexity which is quadratic in the number of users. It is shown that the SDP detector has nonzero asymptotic efficiency if the users' powers are suitably disparate     

A PDA-Kalman approach to multiuser detection in asynchronous CDMA

The probabilistic data association (PDA) method for multiuser detection in synchronous code-division multiple-access (CDMA) communication channels is extended to asynchronous CDMA, where a Kalman filter or smoother is employed to track the correlated noise arising from the outputs of a decorrelator. The estimates from the tracker, coupled with an iterative PDA, result in impressively low bit error rates. Computer simulations show that the new scheme significantly outperforms the best decision feedback detector. The algorithm has O(K/sup 3/) complexity per time frame, where K is the number of users.     

Blind multiuser detection in uplink CDMA with multipath fading: a sequential EM approach

We consider joint channel estimation and data detection in uplink asynchronous code-division multiple-access systems employing aperiodic (long) spreading sequences in the presence of unknown multipath fading. Since maximum-likelihood (ML) sequence estimation is too complex to perform, multiuser receivers are proposed based on the sequential expectation-maximization (EM) algorithm. With the prior knowledge of only the signature waveforms, the delays and the second-order statistics of the fading channel, the receivers sequentially estimate the channel using the sequential EM algorithm. Moreover, the snapshot estimates of each path are tracked by linear minimum mean-squared error filters. The user data are detected by a ML sequence detector, given the channel estimates. The proposed receivers that use the exact expressions have a computational complexity O(2/sup K/) per bit, where K is the number of users. Using the EM algorithm, we derive low-complexity approximations which have a computational complexity of O(K/sup 2/) per bit. Simulation results demonstrate that the proposed receivers offer substantial performance gains over conventional pilot-symbol-assisted techniques and achieve a performance close to the known channel bounds. Furthermore, the proposed receivers even outperform the single-user RAKE receiver with Nyquist pilot-insertion rate in a single-user environment.     

Group-blind multiuser detection for uplink CDMA

Previously developed blind techniques for multiuser detection in code division multiple access (CDMA) systems lead to several near-far resistant adaptive receivers for demodulating a given user's data with the prior knowledge of only the spreading sequence of that user. In the CDMA uplink, however, typically the base station receiver has the knowledge of the spreading sequences of all the users within the cell, but not that of the users from other cells. In this paper, group-blind techniques are developed for multiuser detection in such scenarios. These new techniques make use of the spreading sequences and the estimated multipath channels of all known users to suppress the intracell interference, while blindly suppressing the intercell interference. Several forms of group-blind linear detectors are developed based on different criteria. Moreover, group-blind multiuser detection in the presence of correlated noise is also considered. In this case, two receiving antennas are needed for channel estimation and signal separation. Simulation results demonstrate that the proposed group-blind linear multiuser detection techniques offer substantial performance gains over the blind linear multiuser detection methods in a CDMA uplink environment     

Blind multiuser detection: a subspace approach

A new multiuser detection scheme based on signal subspace estimation is proposed. It is shown that under this scheme, both the decorrelating detector and the linear minimum-mean-square-error (MMSE) detector can be obtained blindly, i.e., they can be estimated from the received signal with the prior knowledge of only the signature waveform and timing of the user of interest. The consistency and asymptotic variance of the estimates of the two linear detectors are examined. A blind adaptive implementation based on a signal subspace tracking algorithm is also developed. It is seen that compared with the previous minimum-output-energy blind adaptive multiuser detector, the proposed subspace-based blind adaptive detector offers lower computational complexity, better performance, and robustness against signature waveform mismatch. Two extensions are made within the framework of signal subspace estimation. First, a blind adaptive method is developed for estimating the effective user signature waveform in the multipath channel. Secondly, a multiuser detection scheme using spatial diversity in the form of an antenna array is considered. A blind adaptive technique for estimating the array response for diversity combining is proposed. It is seen that under the proposed subspace approach, blind adaptive channel estimation and blind adaptive array response estimation can be integrated with blind adaptive multiuser detection, with little attendant increase in complexity     

Semidefinite programming relaxation approach for multiuser detection of QAM signals

A semidefinite programming (SDP) relaxation approach is proposed to solve multiuser detection problems in systems with M-ary quadrature amplitude modulation (M-QAM). In the proposed approach, the optimal M-ary maximum likelihood (ML) detection is carried out by converting the associated M-ary integer programming problem into a binary integer programming problem. Then a relaxation approach is adopted to convert the binary integer programming problem into an SDP problem. This relaxation process leads to a detector of much reduced complexity. A multistage approach is then proposed to improve the performance of the SDP relaxation based detectors. Computer simulations demonstrate that the symbol-error rate (SER) performance offered by the proposed multistage SDP relaxation based detectors outperforms that of several existing suboptimal detectors.     

Space-time multiuser detection in multipath CDMA channels

The problem of multiuser detection in multipath CDMA channels with receiver antenna array is considered. The optimal space-time multiuser receiver structure is first derived, followed by linear space-time multiuser detection methods based on iterative interference cancellation. Blind adaptive space-time multiuser detection techniques are then proposed, which require prior knowledge of only the spreading waveform and the timing of the desired user's signal. Single-user-based space-time processing methods are also considered and are compared with the multiuser approach. It is seen that the proposed multiuser space-time processing techniques offer substantial performance gains over the single-user-based methods, especially in a near-far situation     

Breadth-first maximum likelihood detection in multiuser CDMA

In this letter, we derive a recursive, additive metric for complexity-constrained maximum likelihood detection for multiuser CDMA using breadth-first detection algorithms. The metric requires linear filtering of the matched-filtered received signal vector. It is shown that a class of filters fulfilling certain requirements lead to identical performance     

Iterative multiuser detection for CDMA with FEC: near-single-userperformance

This paper introduces an iterative multiuser receiver for direct sequence code-division multiple access (DS-CDMA) with forward error control (FEC) coding. The receiver is derived from the maximum a posteriori (MAP) criterion for the joint received signal, but uses only single-user decoders. Iterations of the system are used to improve performance, with dramatic effects. Single-user turbo code decoders are utilized as the FEC system and a complexity study is presented. Simulation results show that the performance approaches single-user performance even for moderate signal-to-noise ratios     

Turbo multiuser detection for differentially modulated CDMA

In this letter, we study differentially modulated, iteratively decoded CDMA. The iterative multiuser receiver proposed consists of an additional soft-input soft-output (SISO) differential decoder, when compared to turbo multiuser detectors for absolutely modulated systems. Algorithms for iterative decoding with and without phase information at the receiver are developed. The resulting turbo receivers with differential modulation outperform coherent receivers with absolute modulation at moderate to high signal to noise ratios due to the interleaver gain associated with recursive inner encoders in serially concatenated encoding structures.     

Subspace blind adaptive detection for multiuser CDMA

Direct adaptive realizations of the linear minimum mean-square error (MMSE) receiver for direct-sequence code-division multiple access possess the attractive feature of not requiring any explicit information of interference parameters such as timing, amplitudes, or spreading sequences; however, they need a training sequence for the desired user. Previously, a new blind adaptive receiver was proposed based on an anchored least mean-squared (LMS) algorithm that requires only the spreading code and symbol timing of the desired user but obviates the need for a training sequence. In this work, it is analytically demonstrated that the blind LMS algorithm always provides (nominally) faster convergence than the training driven LMS-MMSE receiver of but at the cost of increased tap-weight fluctuations or misadjustment. Second, the property that the optimal MMSE or minimum-output energy filter coefficients lies in the signal subspace is exploited to propose a new efficient blind adaptive receiver requiring fewer adaptive coefficients. Improved detector characteristics (superior convergence rates and steady-state signal-to-interference-plus-noise ratios) is indicated by analysis and supported by simulation     

Genetic-algorithm-assisted multiuser detection in asynchronous CDMA communications

In an asynchronous direct-sequence code-division multiple-access, a specific bit of the reference user is interfered by two asynchronously arriving surrounding bits of all the other users supported by the system. Hence, for optimum multiuser detection, the entire input bit sequence influencing the current bit decisions must be considered, which results in a high detection delay as well as a high receiver complexity. Suboptimal multiuser-detection methods have been proposed based on a truncated observation window, in which the so-called "edge" bits are tentatively estimated by some other means. Using a similar approach, a multiuser detector is developed in this contribution that invokes genetic algorithms (GAs) in order to estimate both the desired bits as well as the edge bits within the truncated observation window. Using computer simulations, we showed that by employing GAs for improving the estimation reliability of the edge bits, our proposed multiuser detector is capable of achieving a near-optimum bit-error-rate performance, while imposing a lower complexity than the optimum multiuser detector.     

Decision feedback multiuser detection: a systematic approach

A systematic approach to decision feedback multiuser detection is introduced for the joint detection of symbols of K simultaneously transmitting users of a synchronous correlated waveform multiple-access (CWMA) channel with Gaussian noise. A new performance criterion called symmetric energy is defined which is a low-noise indicator of the joint error rate that at least one user is detected erroneously. Even the best linear detectors can perform poorly in terms of symmetric energy compared to the maximum-likelihood detector. A general class of decision feedback detectors (DFDs) is defined with O(K) implementational complexity per user. The symmetric energy of arbitrary DFD and bounds on their asymptotic effective energy (AEE) performance are obtained along with an exact bit-error rate and AEE analysis for the decorrelating DFD. The optimum DFD that maximizes symmetric energy is obtained. Each one of the K! optimum, decorrelating, and conventional DFDs, that correspond to the K! orders in which the users can be detected, are shown to outperform the linear optimum, decorrelating, and conventional detectors, respectively, in terms of symmetric energy. Moreover, algorithms are obtained for determining the choice of order of detection for the three DFDs which guarantee that they uniformly (user-wise) outperform their linear counterparts. In addition to optimality in symmetric energy, it is also shown that under certain conditions, the optimum DFD achieves the AEE performance of the exponentially complex maximum-likelihood detector for all users simultaneously. None of the results of this paper make the perfect feedback assumption. The implications of our work on power control for multiuser detection are also discussed     

Adaptive MMSE maximum likelihood CDMA multiuser detection

The well-known code division multiple access maximum likelihood receiver (MF-ML) uses a bank of matched filters as a generator of sufficient statistics for maximum likelihood detection of users transmitted symbols. In this paper, the bank of matched filters is replaced by a bank of adaptive minimum mean squared error (MMSE) filters as the generator of sufficient statistics. This formal replacement of the MF bank by the adaptive MMSE filter bank has significant conceptual consequences and provides improvement by several performance measures. The adaptive MMSE-ML receiver's digital implementation is significantly computationally simplified. The advantages of the proposed adaptive MMSE-ML receiver over the MF-ML receiver are: (1) ability to perform joint synchronization, channel parameter estimation, and signal detection where the signal is sent over an unknown, slowly time-varying, frequency-selective multipath fading channel; (2) increased information capacity in a multicellular environment; and (3) significantly improved bit error rate (BER) performance in a multicellular mobile communications environment. The information capacity and the BER of the proposed MMSE-ML receiver are analyzed. Numerical results showing the BER performance of the MMSE-ML receiver in a multipath channel environment are presented     

Robust multiuser detection for multicarrier CDMA systems

Multiuser detection (MUD) for code-division multiple-access (CDMA) systems usually relies on some a priori channel estimates, which are obtained either blindly or by using training sequences, and the covariance matrix of the received signal, usually replaced by the sample covariance matrix. However, such prior estimates are often affected by errors that are typically ignored in subsequent detection. In this paper, we present robust channel estimation and MUD techniques for multicarrier (MC) CDMA by explicitly taking into account such estimation errors. The proposed techniques are obtained by optimizing the worst case performance over two bounded uncertainty sets pertaining to the two types of estimation errors. We show that although the estimation errors associated with the prior channel estimate and the sample covariance matrix are generally not bounded, it is beneficial to optimize the worst case performance over properly chosen bounded uncertainty sets determined by a parameter called bounding probability. At a slightly higher computational complexity, our proposed robust detectors are shown to yield improved performance over the standard detectors that ignore the prior estimation errors.     

Energy-add multistage detector: a novel multiuser detection methodfor synchronous CDMA systems

In synchronous code division multiple access (CDMA) systems, both multiple access interference (MAI) and intersymbol interference (ISI) arise. MAI is present due to the CDMA format while ISI is present due to channel multipath. One approach to overcome these problems is to detect the entire package of data for all users at once. This implies working with matrices with dimensions proportional to the product of the data package length and the number of active users. In this paper, we present an alternative approach. This alternative consists of a type of multistage detector that overcomes the MAI and ISI problems; in addition, it has complexity proportional to the number of CDMA users, is computationally efficient, and is suitable for pipeline implementation which allows fast data processing. Simulations are compared to a derived single user bound for the average bit error probability and the results prove the validity of the proposed detection method     

Blind multiuser detection over highly dispersive CDMA channels

This paper addresses blind multiuser detection in a direct-sequence code-division multiple-access (DS-CDMA) network in presence of both multiple-access interference and intersymbol interference. In particular, it considers a DS-CDMA system where K out of N users are transmitting; the N admissible spreading codes are known, and so is the code of the user to be demodulated. The number of interferers, the signatures of a certain number, possibly all, of the interferers, and the channel impulse response of each active user are unknown. The spreading codes of the unknown interferers are determined via a procedure that exploits the knowledge of the set of admissible transmitted codes and of the known active codes. The procedure applies to both single and multiple receiving antennas. The performance assessment of a blind decorrelating detector, implemented by resorting to the proposed identification procedure, shows that it outperforms a plain subspace-based blind decorrelator for small sizes of the estimation sample.     

Iterative reduced-state multiuser detection for asynchronous coded CDMA

The conventional maximum a posteriori receiver for coded code-division multiple-access (CDMA) systems has exponential computational complexity in terms of the number of users and the memory of the channel code. In this letter, we propose a low-complexity soft-input soft-output (SISO) multiuser detector based on the reduced-state a posteriori probability algorithm. Per-survivor processing and soft interference cancellation are used to remove the residual past and future interference in the branch metric computation. The complexity of the proposed receiver is related to the reduced memory of the CDMA channel and can be adjusted according to the complexity/performance tradeoff. Simulation results show that for asynchronous convolutionally coded systems, the proposed receiver can achieve the near-single-user performance for moderate to high signal-to-noise ratios.     

Linear space-time multiuser detection for multipath CDMA channels

We consider the problem of detecting synchronous code division multiple access (CDMA) signals in multipath channels that result in multiple access interference (MAI). It is well known that such challenging conditions may create severe near-far situations in which the standard techniques of combined power control and temporal single-user RAKE receivers provide poor performance. To address the shortcomings of the RAKE receiver, multiple antenna receivers combining space-time processing with multiuser detection have been proposed in the literature. Specifically, a space-time detector based on minimizing the mean-squared output between the data stream and the linear combiner output has shown great potential in achieving good near-far performance with much less complexity than the optimum space-time multiuser detector. Moreover, this space-time minimum mean-squared error (ST-MMSE) multiuser detector has the additional advantage of being well suited for adaptive implementation. We propose novel trained and blind adaptive algorithms based on stochastic gradient techniques, which are shown to approximate the ST-MMSE solution without requiring knowledge of the channel. We show that these linear space-time detectors can potentially provide significant capacity enhancements (up to one order of magnitude) over the conventional temporal single-user RAKE receiver