Introduction

In this paper we consider the K user direct sequence CDMA communications problem where a single-antenna receives the superposition of the users' signals through fast time-varying ISI channels and additive white Gaussian noise. Whereas MLSE is widely used in digital communication systems to estimate a transmitted data sequence for the single user, known channel case, it is not presently considered practical for the multiuser case considered here. For the known multiuser ISI channel case, the MLSE receiver is well known to be a straightforward extension of the MLSE algorithm described by Verdu [1] for the asynchronous (no ISI) case. Though the Verdu algorithm employs the computationally efficient Viterbi algorithm, the number of trellis states ( 2^K-1 for binary symbols) has been considered prohibitively large for many multiuser applications. The presence of unknown, fast time-varying, ISI channels represents a significant complication.

Several recent developments in digital communications have potential utility for a MLSE based solution to the problem addressed here. First, for single user applications, several exhaustive search algorithms have been proposed for unknown, time-varying, ISI channels. These include joint channel/sequence estimators where for each possible symbol sequence the channel is estimated using a LMS or RLS algorithm (Seshadri [2], Kobo and Fujino [3]) or a Kalman filter (Gustafsson and Wahlberg [4]). Alternatively, Chen, et al. [5] developed an optimum sequence estimator by assigning a time-varying stochastic model for the channel and marginalizing over the channel model parameters to obtain a ML cost for the symbol sequence.

Although these exhaustive search algorithms are computationally unrealistic for long symbol sequences, a second development - Per Survivor Processing (PSP) (Raheli, et al. [6]) - provides an effective, suboptimal means of pruning the number of sequences for which channel estimates and/or sequence costs have to be computed. Efficient, effective, suboptimum PSP algorithms were suggested in [2,3,4] and [5]. These PSP algorithms are formulated using a trellis representation of hypothesized symbol sequences, and a list Viterbi approach to pruning, where only the L best paths into each trellis state are kept for further consideration. For multiuser CDMA, Fonollosa, et al. [7] formulated the MLSE problem, and proposed a PSP-like algorithm which employs LMS based time-varying channel estimation. However, even with PSP, the memory and computational requirements are prohibitive for even moderate numbers of users. In terms of a trellis formulation of the problem, the number of trellis states, and therefore trellis branches, grows exponentially with the number of users K and the ISI channel memory depth M-1.

A third development which addresses this exponential growth of memory and computation is Reduced State Sequence Estimation (RSSE). Duel-Hallen and Heegard [8] proposed a decision-feedback RSSE approach in which tentative past symbol decisions are used to reduce the number of unknown symbols represented by the trellis states (i.e. by reducing the number of assumed unknown symbols in the channel memory). Eyuboglu and Qureshi [9] also proposed trellis state reduction, coined the term RSSE, and considered trellis state reduction approaches based in symbol clustering (applicable for modulation schemes with many symbols) and decision-feedback. More recently, Skelton and Taylor [10] developed a multiuser CDMA reduced-complexity approach based on trellis substages and state clustering RSSE.

Finally, with digital communications hardware advancements following Moore's law, practical multiuser MLSE is coming closer to reality.

In this paper we describe the unknown, fast time-varying, frequency-selective multiuser CDMA problem. We will develop the MLSE solution by marginalizing over the parameters of a Gauss-Markov time-varying model of the multiuser channels. We then investigate PSP and RSSE based reduced complexity algorithms.