這本篇論文中，我們提出了一個新的適用於分碼多工(CDMA)及多載波分碼多工(multi-carrier CDMA, MC-CDMA)系統之低雜度多用戶偵測(multiuser detection)的削樹演算法。我們提出的演算法是由最大概似偵側所衍生，並且是以一個通用的訊號模型為基礎。另外，我們亦提出了一個低複雜度之使用者排序演算法以進一步提升削樹演算法之效能。接著，我們延伸削樹演算法之概念，將雜訊之效應加以同時考慮。此一延伸之削樹演算法有非常優異的效能表現。我們並討論了關於干擾消除以及訊號維度的議題，並且得知在高負載的系統中，使用4PAM的訊號比QPSK更有效率。
所有我們討論的議題與演算法均適用於DS-CDMA與MC-CDMA兩種系統。而模擬主要是在於MC-CDMA的系統上進行。模擬的結果顯示，我們所提出的演算法比前人所提出者為佳，並且可以非常低的複雜度達到幾乎最佳(near-optimal)的效能。

In this thesis, we first propose a novel low-complexity tree-pruning algorithm for multiuser detection (MUD) in code-division multiple access (CDMA) systems. The proposed algorithm is derived from the maximum-likelihood (ML) detector for a unified signal model. A low-complexity sorting algorithm is also proposed to further improve the performance. An extension of the tree-pruning algorithm, which takes noise into account, is also proposed and is shown to have excellent performance. Applications to interference cancellation and signal dimensionality issues are also investigated. It is also shown that 4-level pulse amplitude modulation (4PAM) can achieve better performance than quadrature phase shift keying (QPSK) for heavily loaded systems.
All proposed algorithms apply to both direct-sequence CDMA (DS-CDMA) and multi-carrier CDMA (MC-CDMA) systems. Simulation results for MC-CDMA show that the proposed algorithms outperform most previously proposed multiuser detection schemes, and can achieve near-optimal performance with very low complexity.

Acknowledgement
Abstract
1 Introduction
2 Signal Models of CDMA Systems
2.1 General Signal Model for Linearly Modulated CDMA
2.2 Signal Models of DS-CDMA
2.2.1 Downlink Synchronous DS-CDMA in a Flat Channel
2.2.2 Uplink Asynch ronous DS-CDMA
2.3 MC-CDMA Systems
2.3.1 Signal Model of OFDMSystem
2.3.2 Block DiagramofMC-CDMA
2.3.3 Downlink Synchronous and Uplink Quasi-Synchronous MC-CDMA
3 Multiuser Detection
3.1 Detection in CDMA Systems
3.2 Conventional Single-User Matched Filter Receiver
3.3 Some Performance Measures for Multiuser Detectors
3.4 Individually Optimal and Jointly Optimal Multiuser Detectors
3.4.1 Decision Rules
3.4.2 Complexity of the Minimum-Distance Detector
3.5 Some Typical Suboptimal MUDs
3.5.1 Linear Detectors
3.5.2 Nonlinear Detectors
4 Proposed Receivers and Algorithms
4.1 An Efficient Near-Optimal PW-TP MUD Algorithm
4.1.1 Motivations
4.1.2 PW-TP Algorithm Description
4.1.3 Complexity Analysis
4.1.4 Statistical Analysis of R and L
4.1.5 The Statistics of R
4.1.6 The Statistics of L
4.1.7 Sensitivity to Channel Estimation Error
4.2 Sorting Algorithms for Determining Detection Order
4.2.1 Conventional Power Sorting
4.2.2 Sorting Algorithms for ZF-DF Detector
4.2.3 Sorting Algorithms for PW-TP Algorithm
4.3 Some Variations of PW-TP
4.3.1 MMSE-based Tree-Pruning Algorithm (MMSE-TP)
4.3.2 Interference Cancellation
4.4 Issues in Signal Space and Signal Constellation Dimensionality
5 Simulation Results
5.1 Simulation Parameters
5.1.1 Default System Model
5.1.2 Power Variation
5.1.3 Other-cell interference
5.1.4 Parameters of Tree-Pruning Algorithm
5.2 Simulation Results
5.2.1 Statistics of lkk
5.2.2 Statistics of lM,kk
5.2.3 Performance of PW-TP With out Sorting
5.2.4 Performance of PW-TP with Channel Estimation Error
5.2.5 Performance of PW-TP with Sorting Algorithms
5.2.6 Performance of MMSE-TP Algorithms
5.2.7 Cancellation of Unknown Interference
5.2.8 Effects of Signal Space and Constellation Dimensions
6 Conclusions and Future Works
6.1 Conclusions
6.2 Future Works

[1] A. J. Viterbi, “When not to spread spectrum-a sequel,” IEEE Communications Magazine, vol. 23, pp. 12—17, Apr. 1985.
[2] K. S. Gilhousen, I. M. Jacobs, R. Padovani, and L. A. Weaver, “Increased capacity using CDMA for mobile satellite communication,” IEEE Journal on Selected Areas in Communications, vol. 8, pp. 503—514, May 1990.
[3] A. J. Viterbi, CDMA: Principles of Spread Spectrum Communications. Addison-Wesley, 1995.
[4] J. G. Proakis, Digital Communications. McGRAW-HILL, 4th ed., 2001.
[5] E. A. Lee and D. G. Messersch mitt, Digital Communicaiton. Kluwer Academic publishers, 2nd ed., 1994.
[6] S. Verdu, Multiuser Detection. Cambridge university press, 1998.
[7] A. Duel-Hallen, J. Holtzman, and Z. Zvonar, “Multiuser detection for CDMA systems,” IEEE Personal Communications, April 1995.
[8] S. Moshavi, “Multi-user detection for DS-CDMA communications,” IEEE Communications Magazine, Oct. 1996.
[9] R. M. Buehrer, N. S. Correal-Mendoza, and B. D. Woerner, “A simulation comparison of multiuser receivers for cellular CDMA,” IEEE Transations on Vehicular Technology, vol. 49, pp. 1065 —1085, July 2000.
[10] T. S. Rappaport, Wireless Communications: Principles and Practice. Prentice-Hall, 1996.
[11] S. R. Saunders, Antennas and Propagation for Wireless Communication Systems. John Wiley, 1999.
[12] L. B. Milstein, “Wideband code division multiple access,” IEEE Journal on Selected Areas in Communications, vol. 18, pp. 1344—1354, Aug. 2000.
[13] R. van Nee and R. Prasad, OFDM for Wireless Multimedia Communications. Artech House, 2000.
[14] S. Hara and R. Prasad, “Overview of multicarrier CDMA,” IEEE Communications Magazine, pp. 126—133, Dec. 1997.
[15] A. V. Oppenheim, R. W. Schafer, and J. R. Buck, Discrete-Time Signal Processing. Prentice Hall, 2nd ed., 1998.
[16] L. Wei, L. K. Rasmussen, and R. Wyrwas, “Near optimum tree-search detection schemes for bit-synchronous multiuser CDMA systems over Gaussian and two-path Rayleigh-fading channels,” IEEE Transactions on Communications, vol. 45, pp. 691—700, June 1997.
[17] W. V. Etten, “Maximum likelihood receiver for multiple channel transmission systems,” IEEE Transactions on Communications, vol. 24, pp. 276—283, Feb. 1976.
[18] K. S. Schneider, “Optimum detection of code division multiplexed signals,” IEEE Transactions on Aerosp. Electron. Syst., vol. 15, pp. 181—185, Jan. 1979.
[19] H. L. V. Trees, Detection, Estimation and Modulation Theory, vol. I. John Wiley, 1968.
[20] H. V. Poor, An Introduction to Signal Detection and Estimation. Springer, 2nd ed., 1994.
[21] J. M. Wozencraft and I. M. Jacobs, Principles of Communication Engineering. John Wiley, 1965.
[22] S. Haykin, Adaptive Filter Theory. Prentice Hall, 3rd ed., 1996.
[23] A. J. Viterbi, “Very low rate convolutional codes for maximum theoretical performance of spread spectrum multiple access channels,” IEEE Journal on Selected Areas in Communications, vol. 8, pp. 641—649, May 1990.
[24] S. Benedetto and E. Biglieri, Principles of Digital Transmission with Wireless Applicatoins. Kluwer Academic/Plenum Publishers, 1999.
[25] G. Ungerboeck, “Channel coding with multilevel/phase signals,” IEEE Transactions on Information Theory, vol. 28, pp. 55—67, Jan. 1982.