多用戶偵測在近年來已被視為是分碼多重存取 (CDMA) 系統的下一代進階接收端技術。不同於傳統接收機對用戶之間多重存取干擾的處理方式；多用戶偵測接收機則是將多重存取干擾視為在偵測訊號方面的額外資訊。
在多重用戶偵測技術之中，最大概似 (ML：Maximum likelihood) 偵測的位元錯誤率效能已被證明是最佳的結果；但由於其複雜度正比於以使用者數目為次方的指數函數，使其無法被使用在實際的應用上。因此，多種降低複雜度的次佳多用戶偵測接收機技術陸續的被提出，卻也伴隨著效能的下降。
於此篇論文中，針對K個使用者傳送BPSK信號的同步分碼多重存取系統，在高斯白雜訊 (AWGN) 通道下之接收端多用戶偵測，我們提出一快速、較低複雜度且錯誤率可等效最大概似偵測之效能的方法。我們將多用戶偵測解調視為非線性整數規劃的問題，而利用分支－界限 (Branch and Bound) 演算法來求其最佳解。我們考量演算法的搜尋量與所需記憶空間，討論及比較「最佳優先」(best-first)、「深度優先」(depth-first) 兩種搜尋法的效能，而後提出結合式的搜尋法。除此之外，更進一步的將原始的「界限函數」改良為遞迴式的計算，確實的降低了分支－界限法求解過程中的計算複雜度。

In recent years, multiuser detection has been regarded as an advanced receive technology for the next generation of code-division multiple access (CDMA) systems. Unlike the conventional receiver which treats multiple access interference (MAI) as noise, multiuser detectors treat MAI as additional information to detect transmission signals.
In multiuser detection technologies, it has been proven that the BER performance of maximum likelihood (ML) detection is optimum. But because of the complexity of ML detector for CDMA systems increases exponentially with the number of users, ML detector is not suitable for practical application. Thus, over the past two decades, the research has aimed at low-complexity suboptimum detectors with acceptable performance degradation.
This thesis considers the problem of multiuser detection for synchronous code division multiple access (CDMA) systems in additive white Gaussian noise (AWGN) channel. We propose a fast low-complexity maximum-likelihood multiuser detector. We apply the branch-and-bound principle to solve the nonlinear integer programming problem associated with finding the optimal solution of multiuser detection. A recursive formula for fast metric update is obtained by exploiting the statistical information of matched-filter output. Moreover, considering the search time and memory constraint, we compare the performance of depth-first search and best-first search.

參考文獻
[1] S.Verdu, Multiuser Detection, Cambridge Univ., 1998.
[2] R. Lupas and S. Verdu, “Linear multiuser detectors for synchronous code-division
multiple-access channels”, IEEE Transactions on Information Theory, Vol. 35,
pp.123-136, Jan. 1989.
[3] U. Madhow and M. L. Honig, “MMSE interference suppression for direct sequen-
ce spread spectrum CDMA”, IEEE Trans. Communications, 42:3178-3188, Dec.
1994.
[4] S. Miller, “An adaptive direct-sequence code-division multiple-access receiver for
Multi-user interference rejection”, IEEE Trans. Communications, 43:1746-1755,
Apr. 1995.
[5] P. Rapajic and B. Vucetic, “Adaptive receiver structure for asynchronous CDMA
systems”, IEEE Journal on Selected Areas in Communications, 12:685-697, May
1994.
[6] M. Varanasi and B. Aazhang, ”Multistage detection in asynchronous code division
Multiple access communications”, IEEE Trans. Communications, 38:509-519, Apr. 1990.
[7] Jens Clausen, “Branch and Bound Algorithms – Principles and Examples”, Depar-
tment of Computer Science, University of Copenhagen, March, 1999.
[8] N. J. Nilsson, “Artificial Intelligence: A New Synthesis”, Morgan Kaufmann Publ-
ishers, San Francisco, CA, 1998.
[9] E. W. Felten, “Best-first branch-and-bound on a hypercube”, in The Third Conference on Hypercube Concurrent Computers and Applications, New York,
N.Y., 1988, Association for Computing Machinery.
[10] C. SanKaran and A. Ephremides, “Solving a class of optimum multiuser detectio-
n problems with polynomial complexity,” IEEE Trans. Inform. Theory,
vol. 44, pp. 1958-1961, Sep. 1998.
[11] S. Ulukus and R. Yates, “Optimum multiuser detection is tractable for synchrono-
us CDMA systems using M-sequences,” IEEE Commun. Lett., vol. 2, pp. 89-91,
Feb.1998.
[12] Z. Xie, R. Short, and C. Rushforth, “A family of suboptimum detectors for coher-
ent multiuser communications,” IEEE Trans. Commun., vol. 8, pp.683-690,
May 1990.
[13] M. K. Varanasi and B. Aazhang, “Near-optimum detection in synchronous code-
division multiple-access systems,” IEEE Trans. Commun., vol. 39, pp.725-736,
May 1991.
[14] M. K. Varanasi, “Group detection for synchronous Gaussian code-division multi-
ple access channels,” IEEE Trans. Inform. Theory, vol. 41, pp. 1083-1096, July
1995.
[15] A. Duel-Hallen, “Decorrelating decision-feedback multiuser detector for synchr-
onous code-division multiple-access channel,” IEEE Trans. Commun., vol. 41,
pp.285-290, Feb. 1993.
[16] A. Duel-Hallen, “A family of multiuser decision-feedback detectors for asynchro-
nous code-division multiple-access channels,” IEEE Trans. Commun., vol. 43,
pp. 421-432, Feb.-Apr. 1995.
[17] M. K. Varanasi, “Decision feedback multiuser detection : a systematic approach,”
IEEE Trans. Inform. Theory, vol. 45, pp. 219-240, Jan. 1999.
[18] P.Tan and L. Rasmussen, “The application of semidefinite programming for dete-
ction in CDMA,” IEEE J. Select. Areas Commun., vol. 19, pp. 1442-1449, Aug.
2001.
[19] W. Ma, T. Davison, K. Wong, Z. Luo, and P. Ching, ”Quasi-maximum-likelihood
multiuser detection using semidefinite relaxation with application to synchronous
CDMA,” IEEE Trans. Signal Processing, vol. 50, pp. 912-922, Apr. 2002.
[20] J. Luo, K. Pattipati, P. Willett, and F. Hasegawa, “Near-optimal multiuser detecti-
on in synchronous CDMA using probabilistic data association,” IEEE Commun.
Lett., vol. 5, pp. 361-363, Sep. 2001.
[21] J. Luo, K. Pattipati, and P. Willett, “A sliding window PDA for asynchronous
CDMA, and a proposal for deliberate asynchronicity,” IEEE Trans. Commun.,
vol. 51, pp. 1970-1974, Dec. 2003.
[22] S. Verdu, “Computational complexity of optimum multiuser detection,” Algorith-
mica, vol. 4, pp. 303-312, 1989.
[23] S. Verdu and H. Poor, “Abstract dynamic programming models under commutati-
vely conditions,” SIAM J. Control Optim., vol. 25, pp. 990-1006, July 1987.
[24] B. Paris, “Finite-precision decorrelating receivers for multi-user CDMA commu-
nication systems,” IEEE Trans. Commun., vol. 44, pp. 496-507, Apr. 1996.
[25] C. Schlegel and L. Wei, “A simple way to compute the minimum distance in mu-
ltiuser CDMA systems,” IEEE Trans. Commun., vol. 45, pp. 532-535, May 1997