Ecole d'ingénieur et centre de recherche en télécommunications

Iterative techniques for CDMA and algorithms for MIMO detection

Khan, Ejaz


The explosive growth of mobile internet is a major driver of wireless telecommunications market today. In future years, the number of online wireless users will exhibit strong progression in every geographic region and devices will tend to support multimedia applications which need big transmission data rates and high quality. Third generation telecommunication systems, like UMTS in Europe, aim at rates approaching lems, where algorithms such as the Newton-Raphson method may turn out to be more complicated. On each iteration of the EM algorithm, there are two steps- called expectation step or E-step and maximization step or M-step. The basic idea of the EM algorithm is to associate with the given incomplete-data problem, a complete-data problem for which ML estimation is computationally more tractable. In the first part of the thesis, we use EM algorithm to estimate the channel amplitudes blindly and compare the results with the Cramer-Rao bound (CRB). Furthermore, we find low complexity relaxed ML detection for the CDMA, and show its superior performance to the MMSE receiver. The second part of the thesis concerns the detection problem in MIMO systems. As mentioned earlier, the ML method by enumeration for detection is computational complex. In the language of optimization theory, the ML problem is NP-hard. Recently, low complexity exact ML has been obtained by sophisticated method called sphere decoding. The sphere decoding searches the closest point in a lattice to a given received signal. Its computational complexity is polynomial (if the radius of the sphere is optimally chosen) for high SNR and at low SNR its complexity explodes. We are able to device an algorithm for exact ML detection using a discrete geometric approach. The advantage of this algorithm is that its performance is polynomial irrespective of the SNR and no heuristic is employed in our algorithm. An alternative way to ML problem is to devise low complexity algorithms whose performance is close to the exact ML. This can be done using semidefinite programming (SDP) approach. The computational complexity of the SDP approach is comparable to the average complexity of the sphere decoder but still it is quite complicated for large systems. We obtained low complexity (by reducing the number of the variables) approximate ML by second order cone programming (SOCP) approach. In the above discussion the channel state information is assumed to be known at the receiver. We further looked into the problem of detection with no channel knowledge at the receiver. The result was the joint channel-symbol estimation. We obtained the results of joint channel-symbol estimation using EM algorithm and in order to reduce the complexity of the resulting EM algorithm, we used mean field theory (MFT) approach (a method vastly used in statistical physics). The MFT approach is used to approximate the posteriori MAI probabilities for MIMO system and the results are compared with exact ML for a known channel.

Document Bibtex

Titre:Iterative techniques for CDMA and algorithms for MIMO detection
Département:Systèmes de Communication
Eurecom ref:1207
Copyright: © ENST Paris. Personal use of this material is permitted. The definitive version of this paper was published in Thesis and is available at :
Bibtex: @phdthesis{EURECOM+1207, year = {2003}, title = {{I}terative techniques for {CDMA} and algorithms for {MIMO} detection}, author = {{K}han, {E}jaz}, school = {{T}hesis}, month = {07}, url = {} }
Voir aussi: