1638

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 19, NO. 8, AUGUST 2001

Turbo Greedy Multiuser Detection

AbstractRecently, a novel scheme for iterative multiuser detection and turbo decoding was proposed by Damnjanovic and Vojcic. In this scheme, multiuser detection and single-user turbo decoding are tightly coupled to maximize the overall gain. The extrinsic probabilities for the coded bits of the interfering users, obtained after each turbo decoding iteration, are used as a priori probabilities in the following multiuser iteration and the extrinsic information for the systematic bits of the desired user is used as a priori information in the next single-user turbo decoding iteration. Turbo decoding of parallel concatenated convolutional codes is carried out in parallel fashion. It has been shown that the proposed detector approaches the multiuser capacity limit within 1 dB in the low signal-to-noise ratio region. However, the main drawback of the scheme is its exponential complexity in the number of users, which is due to the complexity of the maximum a posteriori probability (MAP) multiuser detector. In this paper, we show that the complexity of the scheme can be significantly reduced by replacing the MAP multiuser detector with an iterative detector derived from the greedy multiuser detector proposed by AlRustamani and Vojcic. In this paper, we demonstrate that, for both the additive white Gaussian noise and the frequency-nonselective Rayleigh fading, the substantial reduction in complexity of the iterative scheme proposed by Damnjanovic and Vojcic when the greedy detector is utilized introduces a slight degradation in performance; the loss in performance is 0 5 dB compared to MAP detector for systems with number of users double the spreading gain. Index TermsCode division multiaccess, concatenated coding, iterative methods, multiuser channels.

I. INTRODUCTION ECENTLY, researchers have focused their attention on iterative decoding [6][12] and their application to the coded multiuser systems [1], [2], [13][20]. Iterative multiuser detection/decoding offers a way of combining the process of multiuser detection and decoding. In such schemes, the problem of multiuser detection and channel decoding are partitioned into two parts. However, the multiuser detector and the decoder utilize soft-input, soft-output (SISO) algorithms and operate in an iterative feedback mode as in turbo decoding [6], [7], [18]. The

Manuscript received December 15, 2000; revised May 24, 2001. This paper was presented in part at the 2000 International Conference on Telecommunications, Mexico, May 2000, and at the IEEE International Conference on Communications (ICC), 2001. A. A. AlRustamani is with Dubai Internet City, Dubai, UAE (e-mail: amina.alrustamani@dubaiinternetcity.co.ae). A. D. Damnjanovic was with the Department of Electrical and Computer Engineering, The George Washington University, Washington, DC 20052 USA. He is now with Ericsson Wireless Communications, San Diego, CA 92121 USA (e-mail: a.damnjanovic@ericsson.com). B. R. Vojcic is with the Department of Electrical and Computer Engineering, The George Washington University, Washington, DC 20052 USA (e-mail: vojcic@seas.gwu.edu). Publisher Item Identifier S 0733-8716(01)07230-4.

soft-output of a bank of single-user decoders is fed back to the multiuser detector and used as a priori information for the next multiuser detection iteration. The optimal iterative multiuser detector for convolutionally coded synchronous multiuser systems, based on the iterative techniques for cross-entropy minimization, is derived [13]. A suboptimum implementation with exponential complexity in the number of users is also presented. The scheme was examined for systems characterized with equal and high crosscorrelation between users. The results show that performance asymptotically approaching the single-user bound is achievable in the high signal-to-noise ratio (SNR) region [13]. The main drawback of that scheme is a relatively poor single-user performance of a convolutional code at low SNR. It is reasonable to believe that this limitation can be mitigated with more powerful turbo codes. In [13], the authors investigated the use of log-MAP [10], [21] algorithm in their iterative scheme for both multiuser detection and decoding for a convolutionally coded asynchronous multiuser system over the additive white Gaussian channel (AWGN) and the flat Rayleigh-fading channel. The results for both channels show that the performance is close to the single-user bound [19]. However, the main disadvantage of the iterative schemes in [13], [19] is that the complexity is exponential in the number of users and, thus, not practical for real systems. Therefore, researchers have focused on developing iterative schemes with substantially lower complexity. In [14], an iterative scheme is developed for turbo coded synchronous multiuser system. Parallel concatenated convolutional codes (PCCCs) are used. After several iterations, the single-user turbo decoding is stopped, and a posteriori probabilities are used as a priori ones in the next multiuser iteration. The procedure is repeated iteratively. The MAP multiuser detector is examined and the -algorithm [11] is introduced as a complexity reduction technique for multiuser detection. The simulation results suggest that iterations improve performance, but the reported results are still far from the multiuser capacity limit. algorithm is employed The loss in performance when the is about 1 dB compared to the MAP detector for systems with and and random spreading sequences, where is the number of users and is the spreading gain. An iterative scheme for the asynchronous channel is studied in [16], where the CDMA channel is viewed as a time-varying convolutional code. Thus, at the receiver, the single-user encoder and the multiuser channel are considered as a concatenation of two convolutional codes and are decoded in a serial turbo code fashion. algorithm is also investigated to reduce the complexity The of the iterative scheme [16] and the loss in performance, compared to the full complexity scheme, is about 1 dB for systems and . In [15] a low complexity SISO with

07338716/01$10.00 2001 IEEE

ALRUSTAMANI et al.: TURBO GREEDY MULTIUSER DETECTION

1639

multiuser detection for asynchronous multipath channel is developed based on soft interference cancellation and minimum mean square error (MMSE) filtering. The scheme was examined for systems with equal and high cross-correlation. The loss in performance due to the complexity reduction is negligible; however, the performance is far from the single-user bound at low SNR. An iterative scheme for multiuser detection/decoding based on the MMSE criterion and convolutional coding was developed in [17]. The performance of the scheme is 1 dB away and from the single-user bound for a system with random spreading sequences. A novel iterative multiuser detector/decoder has been proposed in [1], [2]. In this scheme, multiuser detection and single-user turbo decoding are tightly coupled to maximize the overall gain. Unlike in [14], multiuser iterations are embedded into single user turbo decoding iterations. The extrinsic probabilities for the coded bits of the interfering users, obtained after each turbo decoding iteration, are used as a priori probabilities in the following multiuser iteration and the extrinsic information for the systematic bits of the desired user is used as a priori information in the next single-user turbo decoding iteration. Turbo decoding of PCCC is done in parallel fashion [12]. The simulation results indicate that, at low SNR, the iterative receiver with binary signaling can operate close to the multiuser capacity limit [1], [2]. However, since the scheme employs MAP multiuser detection, the complexity is exponential in the number of users. In this paper, we introduce a complexity reduction technique for the scheme presented in [1] and [2] that substantially reduces the computational load, yet insignificantly degrades performance. In this technique, the MAP detector is replaced with an iterative detector that is based on the greedy principle proposed in [3] and [4]. The complexity of the greedy algorithm is operations per bit interval, where is approximately the number of users, and it has been shown that its performance is close to that of an isolated single user, in low SNR region. The results in [3], [4] show that in the presence of moderate-to-high noise, nearfar effect, fading, and asynchronous transmission, near-optimum performance is achieved by the greedy detection for a number of users that is close to double the processing gain. Furthermore, it has been shown in [3] and [4] that the greedy multiuser detector considerably outperforms the most popular alternatives studied in the literature, such as: conventional, successive interference cancellation, decorrelator, sequential and multistage detectors, especially for moderate and high loads in low and moderate SNR; exactly where practical coded systems would operate. The performance of the proposed scheme over the AWGN was investigated in [20]; in this paper, we extend the results to the frequency-nonselective Rayleigh-fading channel. dB for The results show that the loss in performance is a system with the number of users double the spreading gain . The paper is organized as follows. In Section II, the system model is presented. Section III provides a brief description of the iterative multiuser detector proposed in [1], [2]. A description of the greedy multiuser detector and its utilization in the proposed complexity reduction technique is given in Section IV. In Section V, we present the numerical results while our concluding remarks are given in Section VI.

II. SYSTEM MODEL Consider a PCCC coded synchronous baseband multiuser users, employing unit energy time limited system with , .A spreading waveforms block of message bits, , is encoded by a constituent encoder to create a parity sequence, , and interleaved and to create the second parity encoded by a constituent encoder . The systematic bits, , and the parity bits, sequence, and , are then multiplexed to create a coded output , resulting in the rate 1/3 code. sequence The coded bits at the output of the PCCC encoder are moduand then transmitted lated by the spreading waveform over a multiuser channel. For a frequency-nonselective fading , is significantly smaller channel, the signal bandwidth, , and the than the coherence bandwidth of the channel, multipath components are not resolvable [23]. In this case, the received signal is the transmitted signal multiplied by a complex-valued random process representing the time-variant characteristics of the channel. Furthermore, we assume that the symbol duration is smaller than the coherence time of the channel such that attenuation and phase shift are essentially constant for the duration of at least one symbol interval [23]. Therefore, the received signal can be written as (1) is a zero-mean complex-valued Gaussian where , and variable, such that, is the spacetime correlation function of the channel associated with th user. denotes is the expected value of the -th complex conjugate and is the value of the th users th coded user. is the symbol duration, is a complex zero-mean bit, is the coded packet length. Gaussian random process and The AWGN channel can be viewed as a special case for which for and and is real Gaussian random process. We assume that at the receiver , and , are the values known, i.e., perfect knowledge of channel state information. The sufficient statistic for demodulation of coded bits in the -th interval is given by the vector , whose th component is the output of a filter matched to (2) The vector of sufficient statistic can be written as (3) where normalized cross-correlation matrix of spreading waveforms; ; ; ; , where

1640

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 19, NO. 8, AUGUST 2001

Fig. 1.

Principal block diagram of the proposed iterative multiuser receiver, two-user case.

III. ITERATIVE RECEIVER In the first iteration, multiuser detection is activated disjointly of single-user turbo decoding. The purpose of multiuser detection is to provide the single-user turbo decoders with the soft input metrics. In the th interval, at the beginning of the iterative process, the MUD computes the likelihood vector , which is a multivariate conditional Gaussian is computed only once, and it is used distribution. in subsequent multiuser iterations. is given by The marginal likelihood

exploited. The extrinsic probabilities for coded bits of the interfering users can be factored out from a posteriori probabilities, which are generated by the single-user turbo decoders. For user , after the -th iteration, the extrinsic distribution is de, and can be fed back as a priori distribution noted as th multiuser iterafor next multiuser iteration. After the tion, updated marginal a posteriori distribution of the coded bits is equal to

(6)

(4) where we assume statistical independence among the coded bits , . The soft input metric for the single-user turbo decoder of user is a posteriori distribution (5) refers to the first itwhere the first subscript 1 in eration and is a constant that normalizes the probability mass. In the first iteration, a priori probabilities for coded bits are all . equal, i.e., The decoders of the constituent codes are activated simultaneously. The goal is to ensure that the output of the turbo decoder equally weights the contribution from both constituent decoders and to minimize the decoding delay through parallel processing. The single-user MAP decoder is modified to produce a posteriori probabilities of coded bits. After one parallel iteration, a posteriori probabilities of all coded bits are obtained, and the extrinsic information of the systematic bits becomes a priori information for the next single-user parallel turbo decoding iteration. The extrinsic probabilities of the systematic bits at the output of decoder 1 are fed as a priori ones to decoder 2, and the extrinsic probabilities of the systematic bits at the output of decoder 2 are fed as a priori ones to decoder 1. Notice, however, that there is some additional extrinsic information that may be and it is fed as the soft input metric into the single-user turbo decoder of user . The procedure is iteratively repeated until some predetermined stopping condition is met. The final bit decisions are obtained based on a posteriori probabilities of the systematic bits at the output of single-user MAP decoders. The principal block diagram of the proposed iterative receiver, for a two-user example, is presented in Fig. 1. Note that the probais calculated only once in the first iteration, and bilities they are used in subsequent MUD iterations which are presented as inputs to the MUD blocks in Fig. 1. IV. REDUCTION IN COMPLEXITY The complexity of the original scheme [1], [2] discussed per bit per user per iteration, since above is computations are needed to compute (6), and for the constituent convolutional codes of constraint length , the . Therefore, the main comdecoding complexity is putational burden is imposed by the MAP multiuser detector. The complexity of the scheme can be profoundly reduced if we utilize a suboptimum multiuser detector that examines a subset corresponding to large values of of the possible vectors in (4). Instead of the MAP detector, likelihoods we propose the use of the greedy algorithm for multiuser detection presented in [3] and [4].

ALRUSTAMANI et al.: TURBO GREEDY MULTIUSER DETECTION

1641

To employ the greedy algorithm in iterative decoding, the metric used in the algorithm is modified to incorporate the updated a priori distribution from the single-user turbo decoders (7) It can be easily shown that after eliminating all the terms that , we can write the above metric are equal for all the vectors as

four possible vectors obtained by substituting and in . ; ; ; . The vector that results in the largest metric value is chosen as in the th stage the new estimate of the vector if and only if

(8) where and is real part of and is the variance of the noise . Based on the greedy principle, the greedy multiuser detector views the absolute values of the coefficients and as weights that indicate the order in which bits can be estimated. The dominating coefficients, the large values, will have more effect on deciding the bit value than smaller values, i.e., we take into consideration the order of the coefficients contribution to the metric value, . Initially the absolute values of the coefficients are sorted in a descending order. The subscripts of these coefficients indicate in which order the bits might be estimated. Therefore, the algorithm consists of stages, which is the total number of the and . The th stage corresponds to the th coefficients coefficient after sorting. In some cases, the number of stages for reasons that will be evident may be less than later. be the estimate of the vector Let in the th stage and . In the th stage, if the , then the th bit in is corresponding coefficient is examined and updated. This is done by calculating the metric in (8) twice for the two possible vectors obtained by substituting in the values of and

and Therefore, at the th stage, one or two bits in , depending on the coefficient corresponding to the th stage, are examined and updated based on the estimates of the bits made in the previous stages, corresponding to the largest increment to the likelihood metric. As mentioned earlier, the number of stages might be less than in some cases. The cases in which the number of stages can be reduced are summarized in Lemma 1. Lemma 1: In the greedy algorithm, if two consecutive stages or , or if three consecutive stages examine or all the other five possible permutaexamine , then deleting the stages corresponding tions of , and (and ) will not affect the result. to Proof: The vectors examined in the consecutive stages or , or all other possible permutations, have the same elements in all other positions besides and , i.e., same symbol estimates for all other users except users and . Moreover, the examined vectors in the stages (and ) are subsets of the examined vectors in the stage . Therefore, deleting stages (and ) will not have an effect on the results. One possibility to improve the performance of the greedy largest metric values and the algorithm is to forward the corresponding bit vectors from one stage to the next one. will be the largest metric Therefore, the input to a stage and the corresponding values . In stage , for estimates of , the metric values are calculated every or vectors obtained by examining the bits for the indicated by the th coefficient and the largest values and the corresponding bit vectors are chosen as the output of the stage. The improvement in performance by increasing the value of is at the expense of a slight increase in the computational complexity. A detailed description of the algorithm is given in[3][5]. , estimates of all bits might be available Since or at most until stage , at least until stage is the smallest integer greater than or equal to . Once where

. The vector that results in the largest metric value is chosen as in the th stage the new estimate of the vector if and only if and On the other hand, if the coefficient is of the form , then are examined and updated. This the th and th bits in is done by calculating the metric in (8) four times for all the

1642

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 19, NO. 8, AUGUST 2001

Fig. 2.

Principal block diagram of the proposed reduced complexity iterative multiuser receiver, two-user case.

estimates of all bits are available, the greedy detector saves the new bit vectors that are examined in every stage and the corresponding metric value, . Therefore, instead of calculating metric values, the number of the values the greedy deall tector computes, which is a random variable that depends on the order of detection and the speed of convergence of the aland less gorithm to a maximum, is greater than . The detector assumes that than the rest of the values are negligibly small and can be set to zero. These values are then used to update the marginal a posteriori distribution of the coded bits, as given in (6). The principal block diagram of the proposed iterative receiver, for a two-user example, is presented in Fig. 2. Note that, unlike the proposed scheme with the MAP detector, shown in Fig. 1, the greedy detector is activated in every iteration to calculate the probabilities. Since the metric is a function of the updated a priori distribution obtained from the single-user turbo decoders, in every iteration the greedy detector is forced and to explore a different subset of the bit combinations the associated metric values. The complexity of the greedy multiuser detector is [4]. Therefore, the complexity of the proposed scheme is significantly reduced to per bit per user per iteration. V. NUMERICAL RESULTS AND DISCUSSION In all the simulation results in this section, all users employ the same PCCC encoders of rate 1/3, obtained by using systematic, recursive, four-state convolutional encoders of rate 1/2 as constituent codes. Difwith generator matrix ferent users employ different pseudorandom interleavers that are changed for every new packet transmission. Although the gain in complexity reduction by utilizing the greedy multiuser detector is more evident for large values of number of users, , as demonstrated in [3], [4], the simulation results are obtained for small values of for the sake of the computational speed. Nevertheless, the scheme is examined for moderately to heavily loaded systems.

To illustrate the potential of the proposed scheme, we first consider a synchronous eight-user symmetric AWGN channel that is characterized by the following cross-correlation matrix, and for ; . All users have the same power. In Fig. 3, we show the results for and different numbers of iterthe greedy algorithm with ations and compare it with the original scheme with the MAP detector [1], [2] as well as scheme suggested in [14]. Also, the multiuser capacity limit for Gaussian signaling and equal am, plitudes is computed from [24] as where is the identity matrix and snr is the SNR per coded bit. In this case, the limit is at 0.86 dB, which means that for the interleaver size of 2,000 bits, it is possible to operate only 1.1 dB away from the limit at the packet error rate of 1%. The gap should be somewhat smaller if these results are compared to the multiuser capacity for binary signaling. For eight users, the greedy multiuser detector examines in every iteration between and 33.6% of the pos6.25% sible bit vectors. The results show that for a profound reduction in complexity the loss in performance for the 32 iterations is less than 0.2 dB. Moreover, the results of the proposed iterative scheme with the greedy detector for different numbers of iterations indicate that the number of iterations is crucial in determining the performance of the scheme; the difference between 32 iterations and 16, 8, and 4 iterations are 0.25, 0.8, and 2 dB, respectively. It appears that the performance can further be improved by increasing the number of iterations beyond 32, although the incremental gain diminishes. In Fig. 3, the performance of the scheme suggested in [14] (Reed 8/32) is obtained for 32 turbo-decoding iterations and eight MAP multiuser iterations. The issue of optimum number of multiuser iterations is discussed in [14]. For the considered example, simulation results that we obtained indicate that eight-MAP multiuser iterations is the optimum number of iterations. Compared to the scheme proposed in this paper with the same number of multiuser/decoding iterations (Greedy 8/32), Reeds scheme outperforms the proposed greedy scheme by about 0.2 dB. Nevertheless, the complexity of Reeds scheme is exponential in the number of users while it is polynomial for the greedy approach.

ALRUSTAMANI et al.: TURBO GREEDY MULTIUSER DETECTION

1643

Fig. 3.

Packet error probability with the greedy multiuser detection, for eight-user case,  = 0:575, interleaver size is 2000 bits, over AWGN channel.

Fig. 4. Packet error probability with the greedy multiuser detection, for eight-user case, random spreading sequences with spreading factor of 15, interleaver size is 2000 bits, over frequency-nonselective fading channel.

Once the complexity of the greedy approach is increased to be comparable to that of Reeds scheme, its performance becomes better. The simulation results indicate that at low SNR the proposed iterative detection/decoding algorithm can operate close to the multiuser capacity limit, even with the proposed complexity reduction technique. This is in contrast to the iterative receivers suggested in [13] and [17] that need high SNR to overcome the detrimental effects of multiuser interference, since at low SNR, it is limited by a relatively poor performance of the employed convolutional code.

In Fig. 4, the performance of the proposed scheme with the greedy algorithm and the MAP detector in the frequency-nonselective fading channel is presented, for eight-user case with 32 iterations, and interleaver size of 2000 bits. As explained in Section II, the fading amplitudes of each user are modeled as Rayleigh fading, assuming independent fading from user to user. The fading amplitudes are assumed to be constant for the whole symbol duration and independent from symbol to symbol. Also, perfect knowledge of the value of these amplitudes is assumed at the receiver. Random signature waveforms with a spreading and code rate 1/3 are used (total bandwidth exgain

1644

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 19, NO. 8, AUGUST 2001

Fig. 5. Packet error probability with the greedy multiuser detection, for ten-user case, spreading factor of 5, interleaver size is 1000 bits, over frequency-nonselective fading channel.

pansion is 15). The multiuser capacity limit for Gaussian signaling is simulated using the capacity formula from [24], , where is the diagonal amplitude matrix with unit power Rayleigh faded amplitudes. In this case, for rate 1/3 code, the limit is at 1.3 dB. For the optimum rate, (no spreading), the multiuser capacity is at 0.3 dB. At and , the performance of packet error probabilities of the original scheme [1], [2] is only 0.5 and 1.1 dB away from the multiuser capacity, respectively. Compared to the scheme with the MAP detector, the loss in performance when the greedy deis employed is less than 0.3 dB and is neglitector with . For this example, the greedy multiuser detector gible for examines in every iteration between 6.25% and 33.6% for and between 6.25% and 67.2% for of the possible bit vectors. The performance of the scheme for a system with 10 users, with 32 iterations and interleaver size of 1000 bits is shown in Fig. 5. In this case, the multiuser capacity limit for rate 1/3 code is at 1.8 dB. For the optimum code rate (no spreading), the multiuser capacity is at 0.7 dB. The signature waveforms of the users, with binary components and , are chosen such that the sum of spreading gain of is minimized, the square of the cross-correlation values in . This criterion is chosen to mini.e., imize interference and to construct spreading sequences with the total squared cross-correlation close to the Welchs bound [25]. In this scenario, the greedy method examines at least 2% of all the possible vectors and at most 13.4%, 26.8%, 40.1%, 53.5%, and 66.9% of all the possible bit vectors for , 2, 3, 4, and 5, respectively. Compared to the results , the loss in performance at is only obtained for , 2, 3, and 4, respectively. 0.7, 0.3, 0.2, and 0.1 dB for is observed The same loss in performance reported at

for lower packet error probabilities for . However, we observe that at high SNR, approximately at 3.5 dB, the reaches an error floor, which is greedy scheme with also observed in [3] and [4]. This is because error-free demodulation in the absence of noise is not achievable by the since the algorithm considers algorithm for low values of a subset of the possible bit combinations and might not converge to the global maximum. However, the error floor is . For this example the perforreduced or vanishes for mance of the algorithm is 1.0 dB away from the multiuser capacity. VI. CONCLUSION A novel iterative approach for multiuser detection and single-user turbo decoding was proposed and described in [1] and [2]. Soft output MAP multiuser detection and turbo decoding are executed disjointly, but are coupled in each iteration by exchanging the extrinsic and a posteriori information. It has been shown that for binary signaling and low SNR the proposed detector/decoder can approach the multiuser capacity limit within approximately 1 dB. However, the proposed scheme suffers from an exponential complexity in the number of users. In this paper, we proposed a new complexity reduction technique that replaces the MAP detector with the greedy detector proposed in [3] and [4], whose complexity . The results for both AWGN is proportional to and frequency-nonselective Rayleigh fading channels show that by replacing the MAP detector by the greedy detector, a substantial reduction in complexity is obtained at the expense dB compared of a slight degradation in performance, to MAP detector, for moderately to heavily loaded systems. The complexity gain of greedy approach, relative to the MAP scheme, rapidly increases with the number of users.

ALRUSTAMANI et al.: TURBO GREEDY MULTIUSER DETECTION

1645

REFERENCES
[1] A. D. Damnjanovic and B. R. Vojcic, Iterative multiuser detection/decoding for turbo coded CDMA systems, IEEE Commun. Lett., vol. 5, pp. 104106, Mar. 2001. [2] A. D. Damnjanovic and B. R. Vojcic, Iterative multiuser detection/decoding for turbo coded CDMA systems, in Proc. IEEE Int. Symp. Spread Spectrum Techniques and Applications, NJ, Sept. 2000, pp. 603607. [3] A. AlRustamani and B. R. Vojcic, Greedy-based multiuser detection for CDMA systems, in Proc. Conf. Information Sciences and Systems, vol. II, Princeton, NJ, Mar. 2000, pp. FA8-11FA8-14. [4] A. AlRustamani and B. Vojcic, Greedy multiuser detection over single-path fading channel, in Proc. IEEE Int. Symp, Spread Spectrum Techniques and Applications, NJ, Sept. 2000, pp. 708712. , Greedy multiuser detection, IEEE Trans. Commun., Dec. 2000. [5] [6] C. Berrou, A. Glavieux, and P. Thitimajshima, Near shannon limit error-correcting coding: Turbo codes, in Proceedings IEEE ICC, Geneva, Switzerland, May 1980, pp. 10641070. [7] C. Berrou and A. Glavieux, Near optimum error-correcting coding and decoding: Turbo codes, IEEE Trans. Commun., vol. 44, pp. 12611271, Oct. 1996. [8] S. Benedetto, G. Montorsi, D. Divsalar, and F. Pollara, A soft-input soft-output maximum a posteriori (MAP) module to decode parallel and serial concatenated codes, TDA Progress Rep., vol. 42, pp. 120, Nov. 1996. [9] J. Hagenauer, E. Offer, and L. Papke, Iterative decoding of binary block and convolutional codes, IEEE Trans. Inform. Theory, vol. 42, pp. 429445, Mar. 1996. [10] P. Robertson, E. Villebrun, and P. Hoeher, A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain, in Proc. IEEE ICC , 1995, pp. 10091013. [11] C. Schlegel, Trellis Coding. Piscataway, NJ: IEEE Press, 1997. [12] C. Heegard and S. B. Wicker, Turbo Coding. Norwell, MA: Kluwer, 1998. [13] M. Moher, An iterative multiuser decoder for near-capacity communications, IEEE Trans. Commun., vol. 46, pp. 870880, July 1998. [14] M. C. Reed et al., Iterative multiuser detection for CDMA with FEC: Nearsingleuser performance, IEEE Trans. Commun., vol. 46, pp. 16931699, Dec. 1998. [15] X. Wang and H. V. Poor, Iterative (Turbo) soft interference cancellation and decoding for coded CDMA, IEEE Trans. Commun., vol. 47, pp. 104661, July 1999. [16] P. D. Alexander, M. C. Reed, J. A. Asenstorfer, and C. B. Schlegel, Iterative multiuser interference reduction: Turbo CDMA, IEEE Trans. Commun., vol. 47, pp. 10081014, July 1999. [17] H. E. Gamal and E. Geraniotis, Iterative multiuser detection for coded CDMA signals in AWGN and fading channels, IEEE J. Select. Areas Commun., vol. 18, pp. 3041, Jan. 2000. [18] J. Hagenauer, Forward error correcting for CDMA systems, in Proc. IEEE 4th Int. Symp. Spread Spectrum Techniques and Application, Mainz, Germany, Sept. 1996, pp. 566569. [19] M. C. Valenti and B. Woerner, Iterative multiuser detection for convolutionally coded asynchronous DS-CDMA, in IEEE Int. Symp. Personal, Indoor and Mobile Radio Communications, Boston, MA, 1998, pp. 213217. [20] B. Vojcic, A. AlRustamani, and A. Damnjanovic, Greedy iterative multiuser detection for turbo coded multiuser communications, in Proc. Int. Conf. Telecommunications, vol. II, Mexico, May 2000, pp. 769774.

[21] A. J. Viterbi, An intutive justification and a simplified implementation of the MAP decoder for convolutional codes, IEEE J. Select. Areas Commun., vol. 16, pp. 260264, Feb. 1998. [22] L. R. Bahl et al., Optimal decoding of linear codes for minimizing symbol error rate, IEEE Trans. Inform. Theory, vol. IT-20, pp. 284287, Mar. 1974. [23] J. G. Proakis, Digital Communications, 3rd ed. New York: McGrawHill, 1995. [24] S. Verdu, Capacity region for gaussian CDMA channels: The symbolsynchronous case, in Proc. Allerton Conf. Communications, Control and Computing, Oct. 1986, pp. 10251039. [25] L. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inform. Theory, vol. IT-20, pp. 397399, May 1974.

Amina A. AlRustamani (M01) received the B.S., M.S., and D.Sc. degrees in electrical engineering from the George Washington University, Washington, DC, in 1993, 1996, and 2001, respectively. She is currently working for Dubai Internet City, Dubai, UAE. Her areas of interest are spread spectrum, multiuser detection, wireless/mobile networks, and satellite communications.

Aleksandar D. Damnjanovic (S96M00) received the Dipl. degree in electrical engineering from University of Nis, Yugoslavia, in 1994, and the D.Sc. degree in electrical engineering from the George Washington University, Washington, DC, in 2000. In July 2000, he joined Ericsson Wireless Communications Inc., San Diego, CA, where he is currently a Senior Engineer working on the wireless CDMA systems. His areas of interests are algorithms and architectures for wireless communications, with emphasis on evolution of third-generation wireless networks.

Branimir R. Vojcic (M86SM96) received the Dipl., M.S., and D.Sc. degrees in electrical engineering from the Faculty of Electrical Engineering, University of Belgrade, Yugoslavia, in 1980, 1986, and 1989, respectively. Since 1991, he has been a Professor with the Department of Electrical and Computer Engineering, George Washington University, where he is also the Department Chairman. His current research interests are in the areas of communication theory, performance evaluation and modeling of terrestrial cellular and satellite mobile communications, code division multiple access, multiuser detection, adaptive antenna arrays and spacetime coding, and ad hoc networks. He has also been an industry consultant in these areas, and has published and lectured extensively in these areas. Dr. Vojcic was an Associate Editor for IEEE COMMUNICATIONS LETTERS. He was also a recipient of 1995 National Science Foundation CAREER Award.