Sphere Decoding Algorithm for Space-TimeBlock CodesMohammad Arslan [email protected] 16, 20091 MotivationThe key challenge faced by future wireless communication systems is to providehigh-data rate wireless access at high quality of service. Combined with the factthat the spec trum is a scarce resource and the propagation conditions are hostiledue to fading and due to interfere nce from users, this r e quirement calls for ameans to radically increase spectral efficiency and to improve the link reliability.Multiple-input multiple output wireless technology seems to meet these demandsby offering increased spectral efficiency through spatial multiplexing g ain, andimproved link reliability due to antenna diversity gain. That is why, MIMOtechnolo gy has been proposed for next generation wireless systems (WiMax,LTE, 802.11n). But, the gains achievable in MIMO systems co me at the cost ofincreased complexity. D. Perels et al. [1] show that their ASIC implementationof MIMO-OFDM WLAN physical layer based on the IEEE 802.11a standardincreases in area by a factor of 6.5 in go ing from a SISO to a 4 x 4 MIMO sys-tem. Due to the increased complexity, a significant focus in research on MIMOsystems has been directed at sub-optimal deco ding strateg ie s [2, 3]. Examplesof les s co mplex decoding techniques include zero-fo rcing and V-BLAST. But,they come at the price of reduced performance at the r e c eiver. The optimalMaximum likelihood strategy which gives the best performance is ba sed on ex-haustive search and becomes too complex as the number of antennas and datarates increase.2 ObjectiveFor the class project, I would like to implement the sphere decoding algorithmproposed by [4]. It has been shown that the sphere decoding algorithm hasalmost the same performance as the maximum likelihood decoder but requirescomputational effort implementable in practice [5]. I would like to do the im-plementation in MATLAB and explore different opportunities for optimization.13 Game PlanThe approach I will adopt for this project is:• First, I will develop a complete understanding of the algorithm by studyingthe relevant literature [4, 5]. A brief description of the algorithm is givenin Section 4.• Implement the basic algorithm in floating-point using MATLAB.• Optimize the algorithm using techniques lear nt in class (unfolding, re-timing, algorithmic transfor mation etc.) as well as those proposed inresearch [6–8]. Specifically, I will e xamine the constraints and trade-offsof these methods in detail.• If time permits, convert the algorithm to fixed-point implementation using16 and 32 bit storage variables and study the performance degradation interms of SNR on the probability of error. Currently, most of the ha rdwareused in mobile handsets is ba sed on fixed-point arithmetic due to its low-power consumption. So, it would be beneficia l to study the impact onperformance in converting the algorithm to fixed-po int.4 Sphere Decoding Algorithm4.1 Basic SetupIn this section, I’ll present a brief overview of the Sphere decoding algorithm.More details including derivation will be included in the final report. The mate-rial presented in this section is mostly referenced from [5 ]. For a MIMO system,the rece ived signal vector x is modeled asx = Hs + vwhere x is the n×1 received signal vector, H is the known n×m channel matrix,s is the m × 1transmitted signal vector and v represents a n × 1 i.i.d Gaussiannoise vector with N (0, σ2) distributed entries.Now, the optimal Maximum Likelihood detector that minimizes the averageprobability of error P r(ˆs 6= s) is given asˆs = arg mins∈DmL||x − Hs||2(1)where DLis the set of alphabets for a L-QAM cons tellation e.g., for 16-QAM,we may have DL= {−3, −1, 1, 3}.The non-linear optimization problem given by (1) is an exponentially com-plex problem in m. Finding its exact solution is, in general, NP hard. Thereare two possible approaches one can take:1. Brute force, which involves sear ching over the entire lattice space DmL.22. Exploit the structure of the lattice and search only those s ∈ DmLthat liein sphere of radius d around x. This is where the sphere decoding strategycomes in.It is intuitively obvious that the second approach will be less computationallyintensive. But, there are two questions that immediately come to mind if thesecond approach is considered:1. How to choose the radius of the sphere d:Note that in (1), (1/σ2)||v||2= (1/σ2)||x − Hs||2is distributed as X2random varia ble with n degrees of freedom. Now, if we define d2= αnσ2,then solving P r(||x − Hs||2< d2) = 1 − ǫ for α for a small ǫ will ensurethat with high probability, the sphere of radius d, contains a lattice point.2. Once d is chosen, how do we tell which points lie inside the sphere:The Sphere decoding alg orithm proposed by [4] deals with this issue. T hebasic premise of the algo rithm is that in one-dimension, a sphere reducesto an interval. Hence, if we consider the multi-dimensional problem onedimension at a time, then we only need to deal with intervals, whichmakes the problem easier. Of course, this is just a crude explanation. Thederivation of the exact a lgorithm is provided below.4.2 DerivationAssume n ≥ m i.e., there are at least as many equations as unknowns. Also,the lattice point Hs lies inside the sphere of radius d centered at x if and onlyifd2≥ ||x − Hs||2(2)Taking the QR factorization of the channel matrix H, we getH = QR0(n−m)×mwhere R is an upper triangular m × m matrix and Q = [Q1Q2] is an n × northogonal matrix. Eq. (2) can now be written asd2≥x − [Q1Q2]R0s2= ||Q∗1x − Rs||2+ ||Q∗2x||2where (.)∗denotes Hermitian matrix transposition. In other words,d′2− ||Q∗2x||2≥ ||Q∗1x − Rs||2Defining y = Q∗1x and d′2= d2− ||Q∗2x||2, we can r e w rite the above e quationasd′2≥mXi=1yi−mXj=iri,jsj23where ri,jdenotes the (i, j) entry of R. Notice, that the indices of the inner sumgo from i to m and not from 1 to m. This is becaus e of the upper triangularproperty of R. This enables us to expand the RHS of the above equation asd′2≥ (ym− rm,msm)2+ (ym−1− rm−1,msm− rm−1,m−1sm−1)2+ · · · (3)where the first ter m depends only on sm, the second term on {sm, sm−1} andso on. Therefore, a nec e ssary condition for Hs to lie inside the sphere is thatd′2≥ (ym− rm,msm)2. This leads to−d′+
View Full Document
Unlocking...