Reduced Complexity Processing

The multiuser MLSE algorithm derived above requires an exhaustive search of all hypothesized multiuser sequences. The number of hypothesized sequences grows exponentially with time (i.e. as 2^Kn). Concerning this problem, one point of view is that, for the unknown channel problem, the Viterbi algorithm can not be used to optimally prune the hypothesized multiuser sequences. This is because received data at time i provides channel estimation information and thus effects the the cost of all hypothesized multiuser sequences up to time i (unless the channel coefficients are statistically independent across time).

Per-Survivor Processing

Per-survivor processing (PSP), [6], has been established as a general, effective, suboptimal approach to the unknown channel problem for pruning the number of sequences considered at any symbol time. Conceptually, for each survivor (unpruned) sequence, the received data is used to estimate the channel (typically data adaptively) under the assumption that that sequence is the correct (desired) signal. In [5], for the single user Gauss-Markov channel MLSE problem, we use a trellis representation on the hypothesized sequences and the list Viterbi algorithm [2] to select the survivors. For each survivor the single-user version of the channel-marginalized MLSE cost derived above is computed. Here we propose the same approach to pruning for the multiuser MLSE estimator, and below we present simulation results using this PSP technique.

Using PSP as described above, the number of multiuser binary sequences kept at Viterbi stage k is $L \cdot 2^{K(M-1)}$, where L is the number of paths kept per trellis state, and 2^K(M-1) is the number of trellis states. Even with PSP, because of the large number of states, for large K both memory and computational requirements are prohibitive.

Reduced State Sequence Estimation

Reduced State Sequence Estimation (RSSE) (e.g. [8],[9],[10]), is an effective, suboptimal general approach to reducing the number of trellis states to an acceptable number. In the decision-feedback approach to RSSE, tentative symbol decisions are used to reduce the number of unknown symbols represented by the trellis states, thereby reducing the number of trellis states. In the set partitioning approach to RSSE, trellis states are clustered, with each cluster becoming a state in a reduced-state trellis. For the problem considered here, we employ an iterative decision-feedback algorithm to substantially reduce the number of trellis states.

For the multiuser, multipath MLSE problem, at stage i of the full trellis, the 2^K(M-1) states represent the K(M-1) multiuser bits $\{ a_k (i-m); ~ k=1,2, \cdots , K; ~ m=1,2, , \cdots , M-1 \}$. For the proposed iterative RSSE approach, K reduced state trellises are set up - one for each user. Each trellis has 2^M-1 states which for the k^th user and the i^th stage represent the bits $\{ a_k (i-m); ~ m=1,2, \cdots , M-1 \}$. At stage i, a sequential update of all K of these users' trellises constitutes an iteration. There are P iterations per each stage of trellises.

Consider the update of the l^th user's trellis at stage i and iteration p. For branch costs, soft estimates of the other users' bits, derived from the other trellises, are employed. Denote these soft estimates ${\hat a}_k (i-m); ~ m=1,2, \cdots , M-1; ~ k=1,2, \cdots , K, k \neq l \}$. For the k^th user ($k \neq l$), these soft estimates are averages of the bits associated with the L unpruned (list Viterbi) paths from the i^th stage of the k^th user's reduced trellis, probabilistically weighted by the path likelihoods. For the first iteration and k>l, we set ${\hat a}_k (i) = 0$. Because of this, if user power information is available, users should be listed in order of decreasing power.