By extending our frequency-domain approach (see Cha'o-Ming Chang and Kwang-Cheng Chen, IEEE Communications Letters, vol.4, no.11, p.331-3, 2000) to practical scenarios such as frequency selective slowly fading channels, we justify the value of our proposed frequency-domain approach to multiuser detection in DS-CDMA communications systems. With this frequency-domain approach, which maintains frequency-domain orthogonality between different users, DS-CDMA communication is MAI-free even in frequency-selective slowly fading asynchronous channels. This frequency-domain approach not only saves the cost of maintaining synchronous channels as in practical communications systems employing time-domain orthogonal codes (e.g. IS-95 and cdma2000), but also enjoys low complexity properties as in conventional point-to-point communications; it therefore holds many desirable properties attractive to practical communications systems.

Different from multiuser detection, synchronization in multiuser communications systems has its unique features. We revisit effective multiuser synchronizers in a systematic way and classify them into two categories: linear multiuser synchronizers and the multiuser synchronizers based on the frequency domain approach. Both categories of estimators have their special advantages according to their characteristics and are applicable to practical DS/CDMA communications systems.

Previous work on multiuser synchronization assumed that either timing recovery or carrier phase recovery schemes were available. Therefore, a generalized joint linear timing and carrier-phase estimation scheme to effectively estimate both the received timings and carrier phases at the same time is of paramount interest. Based on the idea to linearly combine the sufficient statistics of timings and carrier phases, we introduce the generalized joint linear timing and carrier phase estimation scheme with commensurate complexity of the generalized linear timing estimator. To avoid the difficulty of the design by minimizing the mean-square error (MSE), a simple and novel design criterion for this generalized joint linear estimation is proposed. With a discrete timing assumption, we not only mathematically prove that the MSE of the proposed estimator converges to zero as noise vanishes for an arbitrary number of users, but also conduct simulations to verify it. On the other hand, for the general case with a continuous timing assumption, arguments and simulations are provided to confirm the effectiveness of our proposed estimator for an arbitrary number of users. We further show that such an efficient linear-complexity joint estimation scheme is effective in the near-far environment. Consequently, the nonpolynomial (NP) hard multiuser synchronization over additive white Gaussian noise (AWGN) channel is successfully solved.

Previous works on multiuser synchronization assumed that either timing recovery or carrier phase recovery scheme is available. Based on the ideas to linearly combine the sufficient statistics of timings and carrier phases, we introduce the generalized joint linear timing and carrier phase estimation scheme which is of commensurate complexity with the generalized linear timing estimator. To avoid the difficulties of the design by minimizing the mean square error, a simple and novel design criterion for this generalized joint linear timing and carrier phase estimation is proposed. With he discrete timing assumption, we not only mathematically prove that the mean square error of the proposed estimator converges to zero as the noise vanishes for an arbitrary number of users, but also numerically verify it. For the general case with continuous timing assumption, we also confirm the effectiveness of our proposed estimator for an arbitrary number of users. With this effective linear complexity joint timing and carrier phase estimate, the non-polynomial (NP) hard multiuser synchronization over AWGN channel is completely solved.

Timing estimation has been shown an important issue in multiuser communication (Buehrer et al. 1996). Chang and Chen (1997) proposed the optimum timing estimation and confirmed the need of two-stage timing recovery policy: acquisition and tracking. While the complexity of the tracking scheme applying the gradient search algorithm increases linearly to the number of users, the timing acquisition still has non-polynomial (NP) complexity. Timing acquisition with linear complexity, as an M-ary hypothesis testing problem, is therefore needed in practical multiuser communications. This paper not only points out the difference between the design of a linear timing acquisition scheme and the linear detector, but also proposes a novel, simple, and effective criterion for linear timing acquisition design. With a discrete timing assumption, we prove that the estimation error of the linear timing acquisition scheme based on this new criterion converges to zero in L/sup 2/ as the SNR increases to infinity for an arbitrary number of users. In the general case of continuous timing, explanations and simulation results are provided to demonstrate the effectiveness of the linear acquisition scheme by the new criterion. We demonstrate such a linear scheme existing in interference limited operation for an arbitrary number of users.