Y. Sun, A Family of Likelihood Ascent Search Detectors for CDMA Multiuser Detection, submitted to IEEE Trans. on Info. Theory 9/6/99
A Family of Likelihood Ascent Search Detectors for CDMA Multiuser Detection[1]
Yi Sun
Department of Electrical Engineering
The City College of City University of New York
New York, NY 10031
Phone: (212)650-6621
Fax: (212)650-8249
E-mail:
Abstract – Although achieving global maximum likelihood (GML) detection and thus achieving global minimum error probability, the optimum detector is impractical because its computational complexity grows exponentially with the increasing number of users. In this paper, we propose a family of likelihood ascent search (LAS) detectors that achieve some subset maximum likelihood (SML) detection whereas their expected per-bit computational complexity is linear in the number of users. It is shown that when only a subset of hypotheses are allowed to test, the optimum detection is to select the hypothesis that achieves the maximum likelihood in this subset of hypotheses. A generalized search rule is proposed for the family of LAS detectors. The LAS detectors monotonically increase likelihood at every search step, and thus monotonically decrease error probability and converge with probability one to a fixe point in a finite number of steps. It is proved that the thresholds set up in the LAS detectors are necessary and sufficient for monotonic likelihood ascent with probability one. The properties of the fixed points and their observation regions are studied. The fewer are the bits allowed to be flipped at each step, then the less the fixed points are, the smaller the fixed regions are, the slower a LAS detector converges, and the smaller the error probability is. Among the LAS detectors, the wide-sense sequential LAS (WSLAS) detectors are shown to converge to local maximum likelihood (LML) points with probability one, and thus each achieves a local minimum error probability. As side products, some properties of the parallel interference cancellation (PIC) detector are also obtained. Simulations are carried out and verify analytical results.
Index Terms – multiaccess communication, maximum likelihood, fixed point, multipath.
- Introduction
The multiuser detection of CDMA signals has received considerable attention for over a decade. A textbook on multiuser detection was written by Verdú [1]. Tutorial references were presented by Verdú [2], Duel-Hallen et al. [3], and Moshavi [4] with extensive reference lists therein.
Verdú [5] [6] showed that an optimal maximum likelihood multiuser detector can achieve significant performance improvement over the conventional detector. However, its computational complexity grows exponentially with the number of active users. Unless the signal correlations have a special structure as was found for nonpositive correlations by Ulukus and Yates [7], the optimum detector is impractical when the number of active users is large.
To develop low-complexity suboptimal multiuser detectors, suboptimal tree-type maximum-likelihood sequence detectors were proposed for multiuser systems. Xie, Tushforth, and Short [8] considered the sequential detector, and later on considered was breadth-first algorithms [9]. Wei and Schlegel [10] used the M-algorithm tree-search scheme preceded with a decorrelating noise whitening filter. Wei et al. [11] showed that combined with a decorrelating noise whitening matched filter, the M- and T- algorithms can provide near optimum performance at a low level of complexity compared with the optimum detector.
To develop linear suboptimum detector, Lupas and Verdú exploited a linear decorrelating detector [12] [13], which was initially proposed in [14]. The decorrelating detector has computational complexity significantly lower than that of the optimum detector while provides substantial performance gain over the conventional detector. The most significant advantage of the decorrelating detector is that it achieves optimal performance of near-far resistance. However, its performance is far from the optimality due to the noise enhancement of the matrix inverse. Xie, Short and Rushforth [15] applied the minimum mean-square error (MMSE) filter which compromises both multiple access inference suppression and background noise suppression. The structure constraint that the detector is linear is too severe.
Viterbi [16] and Yoon, Kohno, and Imai [17] applied the idea of the successive interference cancellation (SIC). The SIC detector takes a serial approach to canceling interference. Duel-Hallen [18] [19] used the decorrelating decision-feedback detector (DDFD). Klein, Kaleh, and Baier [20] proposed the zero-forcing decision-feedback detector. The DDFD performs linear preprocessing followed by a form of SIC detection. Varanasi [21] developed a systematic approach to the design of decision feedback detector.
The likelihood ascent search (LAS) detectors proposed in this paper are mostly comparable with the parallel interference cancellation (PIC) detector. There has been considerable research on the multistage PIC detector since Varanasi and Aazhang [22] [23] proposed the structure of it. A basic one stage PIC structure was proposed by Kohno, Imai and Hatori [24]. In the PIC detector, the multiple access inference is estimated based on the bit estimate from previous stage and is subtracted from received signal in parallel. This process can be repeated for multiple stages. It was observed [22] that the performance of the PIC detector depends heavily on the initial data estimates. The decorrelating detector was proposed [23] for use as the first stage. It was indicated in [23] that it is the effect of interference doubling from users that are incorrectly detected at the penultimate stage, that ultimately limits the performance of the multistage detector. Verdú demonstrated [1] for a two-user channel that a limit cycle exists in this process of the PIC detector. A number of variations on the PIC detector have been proposed for improved performance. Patel and Holtzman [25] indicated that soft-decision PIC is found to be superior in a well power-controlled channel. Giallorenzi and Wilson [26] proposed the use of the already detected bits at the output of the current stage to improve detection of the remaining bits in the same stage. Moshavi [27] considered the linear combination of the soft-decision outputs of different stages of the PIC detector. Divsalar, Simon, and Raphaeli [28] proposed a partial multiple access interference cancellation at each stage with the amount of cancellation increasing for each successive stage. Other studies on the PIC detector can be found in literature such as Hegarty and Vojcic [29], Gray, Kocic, and Brady [30], Ghazi-Moghadam, Nelson, and Kaveh [31], Shi, Du, and Driessen [32], Buehrer and Woener [33], Zhang and Brady [34], and Beuhrer and Nicoloso [35].
Although there have been many studies on the PIC detector in literature, there were drawbacks in the development of the PIC detector and of the PIC detector itself. These drawbacks can be more easily seen in the framework of the LAS detectors proposed in this paper. The PIC detector is fundamentally a search detector. Given one demodulated vector at one stage, the PIC detector searches out another vector at next stage. The PIC detector was developed mainly based on the intuition motivated by interference cancellation in parallel rather than aiming at guaranteed likelihood ascent stage by stage. There is no indication about whether performance is improved at each stage, probably partly due to the lack of an efficient method for the performance evaluation at every stage when the PIC detectors were developed. Nevertheless, it is the motivation to cancel all interference in parallel simultaneously that yields a greedy and malfunctioned PIC detector. Specifically, the size of search step in the PIC detector is too large, larger than the necessary size to guarantee the likelihood ascent at every step with probability one. Thus, the PIC detector converges to a limit cycle and instability occurs with a nonzero probability. Once a PIC detector converges to a limit cycle, likelihood descent is inevitable. The computation time at stages where likelihood does not increase is wasted. In contrast, the family of the LAS detectors proposed in this paper is developed by aiming at guaranteed likelihood ascent step by step, thus converging to a fixed point in a finite number of search steps with probability one.
Among the large number of existing CDMA multiuser detectors, except the optimum detector that achieves the global maximum likelihood detection and thus achieves global minimum error probability, none of others aims at and is known to achieve a local maximum likelihood (LML) detection so as to achieve a local minimum error probability. In this sense, none of the suboptimal detectors is really suboptimal.
The impracticability of the optimum detection is essentially due to the impracticability of carrying out a test of all hypotheses. To seek suboptimal solution under certain constraint of computational complexity, first we need to know the optimal decision if only a subset of hypotheses are allowed to be tested. Second, we need to know how to design a better subset of hypotheses. In this paper, it is shown that the optimum decision of a subset hypothesis test is to select the hypothesis that achieves the maximum likelihood in the subset of hypotheses. Then presented is a family of likelihood ascent search (LAS) detectors. The LAS detectors achieve the maximum likelihood detection of some subset hypothesis test. Among them, the wide-sense sequential LAS detectors achieve LML detection and thus achieve local minimum error probabilities. All the LAS detectors are shown to have per-bit complexity linear in the number of users. The properties of the LAS detectors are mainly attributed to a low computationally complex method for evaluation of likelihood change at every step.
A partial list of notations and abbreviations used in this paper is given below.
A Diagonal matrix of user energy
Ak Signal amplitude of the kth user
CPIC(r) Set of limit cycle points of the PIC detector with observation r
b Vector of k bits
b(t) Vector of a LAS detector at step t
bf Detector or vector detected by detector f
bf(r) Fixed point or detected vector by detector f with observation r
bf Fixed point of a LAS detector
ej jth coordinate vector
f(r | b) Metric function of b with observation r
g(t) WDb(t)
h(t) Negative gradient of metric at step t
K Number of users
L(t) Index set of bits that are updated at step t
Lf(t) Index set of bits that are updated at step t by a LAS detector f
M Processing gain (number of chips per bit)
n White Gaussian noise vector
Expected total number of additions per demodulated bit
N(b) Neighborhood of b
Pc(bf) Correct detection probability of bf
Pe(bf) Error probability of bf
q Ar
r Sufficient statistics of b
R Crosscorrelation matrix of users’ signature waveforms
Ra A partition region of observation space of index a
S Signature waveform matrix
t Search step
Search step that a LAS detector terminates flip of the kth bit
tf Search step that a LAS detector reaches a fixed point
Search step that a LAS detector f reaches a fixed point
Expected total number of search steps
tk(t) Threshold of the kth bit at step t
Threshold of the kth bit of a LAS detector f at step t
Minimum threshold of the kth bit of a LAS detector f after termination of bit flip
VLML(b) Observation region of LML point b
Vf(b) Observation region of fixed point b of a search detector f
W ARA
z Gaussian noise vector with mean zero and covariance matrix s2R
Za(b) Decision region of b in Ra
Db(t) b(t + 1) - b(t)
Df(t) f[b(t + 1)] - f[b(t)]
f Detector
J Special set of crosscorrelation matrices of signature waveforms
L(r | b) Likelihood function of b with observation r
Va Subset of hypotheses of index a
Áf(r) Limit set of search detector f with observation r
YLML(r) Set of LML points with observation r
Yf(r) Set of fixed points of search detector f with observation r
GLAS Generalized likelihood ascent search
GML Global maximum likelihood – optimum detector
ISML Identical subset maximum likelihood
LAS Likelihood ascent search
LML Local maximum likelihood
PLAS Parallel likelihood ascent search
SLAS Sequential likelihood ascent search
SML Subset maximum likelihood
USML Uniform random subset maximum likelihood
WPLAS Wide-sense parallel likelihood ascent search
WSLAS Wide-sense sequential likelihood ascent search
The rest of the paper is organized as follows. In Section II, the subset hypothesis test is discussed. In Section III, preliminary properties of the search detectors are presented. In Section IV, the generalized LAS detector is presented and its properties are analyzed. In Section V, the wide-sense sequential LAS detectors and the parallel LAS detectors are studied. Section VI addresses the observation regions of fixed points. Simulation results are demonstrated in Section VII. Conclusions are made in Section VIII and some proofs are included in the Appendix.
- Subset hypothesis test
- Received baseband CDMA signal
In contrast to the conventional CDMA system where a bank of matched filters is applied to the received continuous-time signal, in this paper we consider the direct sampling of the received continuous-time signal to obtain sufficient statistics.
Consider a K-user CDMA system. The kth user transmits baseband signal
.
Ak is the amplitude of the kth user’s signal. is referred to as the energy per bit. Throughout this paper, we assume that Ak > 0 for all k and Ak is time-invariant. sk(t) is the signature waveform of duration Tb, which is normalized so as to have unit energy. The chip period of sk(t) is denoted by Tc. Î {-1, 1} is the transmitted bit of period Tb. M º Tb/Tc is the processing gain. xk(t) has bandwidth approximately equal to chip rate 1/Tc.
Consider the following baseband multipath fading channel model for the kth user,
.
In (2), dk is the number of paths. akj(t) is the fading coefficient of the jth path, of which the magnitude is Rayleigh-distributed and the phase is uniformly distributed. tk is the kth user’s reference time. nk(t) is additive white Gaussian noise. Without loss of generality, we assume that tk + tjk ³ 0 and tmax = max (tk + tjk) < Tb/2. Assume further that the fading is slow so that the signal part in y(t) has bandwidth equal to the chip rate 1/Tc. For the up-link transmission, to obtain the sufficient statistics the received signal is sampled at the chip rate at the receiver. Assume that the fading coefficients are time-invariant within one bit period. In the Appendix, the received signal is shown to be rewritten in matrix form as (here t denotes the bit period),