Lattice-Reduction Aided Linear Equalization For Wireless Communications Over Fading Channels Except where reference is made to the work of others, the work described in this thesis is my own or was done in collaboration with my advisory committee. This thesis does not include proprietary or classifled information. Wei Zhang Certiflcate of Approval: Jitendra Tugnait James B. Davis and Alumni Professor Department of Electrical and Computer Engineering Xiaoli Ma, Chair Assistant Professor Department of Electrical and Computer Engineering Min-Te Sun Assistant Professor Department of Computer Science and Software Engineering Stephen L. McFarland Acting Dean Graduate School Lattice-Reduction Aided Linear Equalization For Wireless Communications Over Fading Channels Wei Zhang A Thesis Submitted to the Graduate Faculty of Auburn University in Partial Fulflllment of the Requirements for the Degree of Master of Science Auburn, Alabama May 11, 2006 Lattice-Reduction Aided Linear Equalization For Wireless Communications Over Fading Channels Wei Zhang Permission is granted to Auburn University to make copies of this thesis at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Vita Wei Zhang was born on May 14, 1982 in Qingdao, a beautiful seaside city in China. He graduated from Qingdao No. 2 Middle School in 2000. Then, he attended Zhejiang University in Hangzhou, China. He got his Bachelor of Engineering degree with honors from the Department of Information Science and Electronic Engineering in Chu Kechen Honors College, Zhejiang University in 2004. After that, he joined Auburn University to continue his graduate study in Department of Electrical and Computer Engineering. iv Thesis Abstract Lattice-Reduction Aided Linear Equalization For Wireless Communications Over Fading Channels Wei Zhang Master of Science, May 11, 2006 (B.S., Zhejiang University, 2004) 73 Typed Pages Directed by Xiaoli Ma Modern wireless communications ask for high data rate, high transmission perfor- mance and low complexity. High data rate induces frequency-selective channels because of the relatively shorter symbol duration than the delay spread. Wireless links intro- duce fading which degrades performance and requires diversity techniques to combat. Orthogonal Frequency Division Multiplexing (OFDM) is an efiective method to deal with frequency-selective channels since it facilitates low complexity equalization and decoding. To eliminate the efiects of the channel nulls and fading, linear precoded OFDM is introduced to enable multipath diversity and the maximum likelihood decoder is used to collect the diversity. But, the low complexity provided by OFDM is sacri- flced. Multi-antenna techniques are shown to be able to boost the data rate and also collect space diversity to combat fading. The V-BLAST (Vertical Bell Labs Layered Space-Time) scheme enables higher data rate than single-antenna setup does, but it also requires higher decoding complexity. As a combination, multi-input multi-output (MIMO-) OFDM has been widely studied to boost the transmit-rate and performance v in terms of diversity. For MIMO-OFDM systems, many designs successfully exploit the joint space-multipath diversity when maximum likelihood (ML) detector is adopted at the receiver, which is well known for high complexity. To reduce the decoding complexity, linear equalizers are favored in practical systems, but they usually induce performance degradation. In this thesis, we flrst quantify the diversity of conventional linear equaliz- ers for linear precoded OFDM, V-BLAST and MIMO-OFDM designs. Then, we propose lattice reduction (LR-) aided equalizers to improve the performance, and show that LR- aided linear equalizers achieve the same diversity order as that collected by ML detectors for (MIMO-) OFDM systems and V-BLAST systems. Simulation results corroborate the theoretical flndings. vi Acknowledgments A journey is easier when you travel together. This thesis is the result of two years of work during which I have been accompanied and supported by many people. It is a pleasure that I now have the opportunity to express my gratitude for them. First, I would like to express my sincere appreciation to my advisor Dr. Xiaoli Ma for her guidance and support throughout this work. With her enthusiasm and inspiration, this work has been carried out smoothly. During these two years? study, she provided excellent mentoring, but what I beneflt most from her is her specially designed training procedure which helped me to transmit from an undergraduate to graduate student successfully. Her persistent encouragement and insightful advice make me believe in my choice which results in this thesis. I owe her lots of gratitude for leading me to the exciting world of wireless communications and showing me the way of performing research. She could not even realize how much I have learned from her. Besides of being an excellent supervisor, Dr. Ma is as close as a good friend to me. I am really glad that I have known Dr. Ma in my life. I am also grateful for the contributions of Dr. Jitendra Tugnait both as member of my thesis committee and as a great teacher, and for his assistance throughout my graduate studies. My appreciation also goes to Dr. Min-Te Sun from whom I broaden knowledge to computer science from the weekly study group. Also, I thank my colleagues Liying Song and Zhenqi Chen for their helpful discussions and support through this work. It is not easy to start a new life in a difierent country. So I will give my appreciation to my friends Wei Feng, Shuangchi He, Jin Li, Tao Li, Weidong Tang and Yuan Yao, with whom my life becomes easier and happier. vii I would like to give my special thanks to my dear wife Xiaoming Li for her love and support, and to my parents for their understanding, endless patience and encouragement. As the only child of the family, I owe them a lot for studying abroad. I would like to acknowledge the flnancial support provided by the U.S. Army Re- search Laboratory and the U.S. Army Research O?ce under grant number W911NF-04- 1-0338 and through collaborative participation in the Collaborative Technology Alliance for Communications & Networks sponsored by the U.S. Army Research Laboratory un- der Cooperative Agreement DAAD19-01-2-0011. viii Style manual or journal used Journal of Approximation Theory (together with the style known as ?aums?). Bibliograpy follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speciflcally LATEX) together with the departmental style-flle aums.sty. ix Table of Contents List of Figures xii 1 INTRODUCTION 1 2 PERFORMANCE ANALYSIS OF LLP-OFDM SYSTEMS 5 2.1 System Model of LLP-OFDM . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Linear Equalization For LLP-OFDM . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 ZF Equalizer for LLP-OFDM . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 MMSE Equalizer for LLP-OFDM . . . . . . . . . . . . . . . . . . . 12 2.2.3 DFE Equalizer for LLP-OFDM . . . . . . . . . . . . . . . . . . . . 14 2.3 LR-aided Linear Equalization For LLP-OFDM . . . . . . . . . . . . . . . 15 2.3.1 LR-aided Linear Equalization . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 Performance Analysis on LR-aided Linear Equalizers . . . . . . . . 18 2.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 LINEAR EQUALIZATION FOR V-BLAST SYSTEMS 29 3.1 System Model of V-BLAST Systems . . . . . . . . . . . . . . . . . . . . . 29 3.2 Linear Equalizers and Performance Analysis . . . . . . . . . . . . . . . . . 30 3.2.1 ZF Equalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.2 MMSE Equalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 LR-Aided Linear Equalizers . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4 EXTENSION TO MIMO-OFDM SYSTEMS 40 4.1 FDFR-OFDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 STF-OFDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5 CONCLUDING REMARKS AND FUTURE RESEARCH DIRECTIONS 49 Bibliography 51 Appendices 54 Appendix A 55 Appendix B 57 Appendix C 58 x Appendix D 60 xi List of Figures 2.1 Comparisons among difierent linear equalizers . . . . . . . . . . . . . . . . 24 2.2 Comparisons among difierent equalizers for LLP-OFDM . . . . . . . . . . 25 2.3 Comparisons among difierent group sizes using ML detector and complex LR-aided equalizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Complexity comparison of difierent decoding methods . . . . . . . . . . . 27 3.1 BER of systems with Nt = 2 and Nr = 2,3,4 separately and BPSK modulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2 SER of a system with (Nt,Nr) = (3,4) and QPSK modulation . . . . . . 37 3.3 Complexity comparison between complex LLL and real LLL algorithms . 38 3.4 Performance comparison between the complex and real LLL algorithms with (Nt,Nr) = (4,4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Block Diagram of MIMO-OFDM . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Comparison among difierent equalizers for FDFR design . . . . . . . . . . 47 4.3 Comparison among difierent equalizers for STF design . . . . . . . . . . . 48 xii Chapter 1 INTRODUCTION Modern development of wireless communications requires reliable high-data-rate services. To increase data rate, we can decrease the symbol period, but this will intro- duce frequency-selectivity (and hence time-dispersive) channels. Orthogonal frequency division multiplexing (OFDM) is known as an efiective method to deal with frequency- selective channels since it facilitates low-comlexity equalization and decoding [22]. How- ever, the original uncoded OFDM design neither guarantees symbol recovery, nor collects the multipath diversity to combat fading. Several techniques were proposed to collect the multipath diversity provided by the channel. One way to recover the symbol detectabil- ity for single antenna OFDM systems, is linear complex-fleld coded (LCFC-) OFDM (a.k.a. linear precoded OFDM) presented in [11, 22] to collect the multipath diversity but at the cost of increased decoding complexity. Another way to achieve high-data-rate is to adopt multi-antenna at the transmitter and receiver. Space-time multiplexing of multi-antenna transmissions over multi-input multi-output (MIMO) channels has well documented merits in combating fading, and further enhancing data rates. The V-BLAST (Vertical Bell Labs Layered Space-Time) architecture presented in [4, 25] is a well-known method for achieving high spectral e?ciencies over a rich-scattered environment. Since high data rate is achieved through multiple transmit- and receive-antennas, and high order signal constellation is usually used, the high decoding complexity at the receiver for collecting the diversity provided by the channels becomes the bottle-neck of the development of multi-antenna systems. 1 Frequency-selective MIMO fading channels provide space-multipath diversity to combat fading. Thus, MIMO-OFDM becomes a strong candidate for next generation wireless multi-antenna communications. Numerous space-time (ST) coding schemes have been developed for MIMO-OFDM systems to collect space-multipath diversity (e.g., [11] and [13]). Since all of them used maximum likelihood (ML) detection or near-ML schemes such as sphere-decoding (SD) method, the decoding complexity is high especially when a large number of transmit-antennas and/or high signal constellations are employed. Thus, it is obvious that, no matter in single antenna LCFC-OFDM systems, V-BLAST systems or in MIMO-OFDM systems, how to reduce the decoding complexity while exploiting the diversity order is the problem we would like to study. The flrst straightforward thought to solve this problem is to use linear equalizers such as zero-forcing (ZF) and minimum mean square error (MMSE) equalizers. It is well-known that linear detection methods have much lower complexity than ML and SD methods but introducing an inferior performance. Interestingly, it has been shown that even linear equalizers guarantee maximum multipath diversity for certain precoded OFDM systems [21] (e.g., the system in [22]). However, the decoding complexity of linear equalizers in [21] depends on the number of subcarriers which usually is large. Grouped LCFC-OFDM design has been proposed in [11] to reduce the decoding complexity by performing smaller size of ML. The major difierence for the LCF coder design of [22, 21] and the one in [11] is that LCF coder in [11] depends on the lattice structure of the transmitted symbols. Therefore, to difierentiate these two, we call the grouped LCFC-OFDM scheme as linear lattice-based precoded (LLP)-OFDM. In general, the performance of linear equalization has not been studied for LLP-OFDM, V-BLAST and MIMO-OFDM systems in the literature. In this thesis, we analyze the performance 2 of the linear equalizers for LLP-OFDM systems and extend the results to V-BLAST systems and MIMO-OFDM systems. Recently LR technique has been used to improve the performance of linear equaliz- ers over MIMO systems (e.g., [8] and [24]). A class of real LR-aided linear equalizers was presented in [26, 27], to transform the system model into an equivalent one with better conditioned channel matrix while maintaining the low complexity. It is shown that LR technique can help to collect the maximum diversity order while does not increase the complexity much. Therefore, in this thesis, we develop complex LR-aided linear equal- izers to decode LLP-OFDM systems and analyze the performance in terms of diversity. The results can also be extended to V-BLAST and MIMO-OFDM designs to show the diversity order explicitly. This thesis is organized as follows. In Chapter 2, we study the performance of LLP-OFDM systems: flrst, the system model of LLP-OFDM is presented; then the performance of LLP-OFDM systems with three kinds of low-complexity equalizers (ZF, MMSE and decision-feedback equalizer (DFE)) is analyzed separately; LR-aided linear detection methods for LLP-OFDM systems are developed and analyzed. We show that LR-aided linear equalizers exploit multipath diversity. The simulation results will cor- roborate our theoretical claims. Chapter 3 and Chapter 4 will follow similar structure while Chapter 3 studies the V-BLAST systems and Chapter 4 copes with MIMO-OFDM systems, where two kinds of multi-antenna OFDM designs are analyzed as examples. The last chapter presents concluding remarks and future research directions. Notation: Upper (lower) bold face letters will be used for matrices (column vectors). Superscript H denotes Hermitian, ? conjugate, and T transpose. We will reserve ? for the Kronecker product, d?e for integer ceiling, and E[?] for expectation; diag[x] will stand 3 for a diagonal matrix with x on its main diagonal. IN will denote the N ?N identity matrix. Z is the integer set and C stands for the complex fleld. Z[p?1] denotes the Gaussian integer ring whose elements have the form Z+p?1Z. 4 Chapter 2 PERFORMANCE ANALYSIS OF LLP-OFDM SYSTEMS In this chapter, we consider single-antenna LLP-OFDM systems. First, the system model of grouped LLP-OFDM is introduced. With this model, the performance of linear equalizers is studied. Then, we develop the complex LR-aided linear equalizers for LLP-OFDM systems and analyze the performance to show it can collect the multi-path diversity. 2.1 System Model of LLP-OFDM For high-rate transmissions, when the maximum delay spread (?d) of the channel exceeds the symbol period (Ts), inter-symbol interference (ISI) cannot be ignored and the channel exhibits frequency-selectivity. Suppose the channel is random, with flnite impulse response, consisting of L+1 taps, where L is deflned as b?d/Tsc. Channel taps are denoted as a vector h = [h0,h1,...,hL]T and modelled as complex Gaussian random variables. Here, the conventional uncoded OFDM system we consider includes cyclic preflx (CP) insertion and inverse FFT (IFFT) operations at the transmitter, and CP removal and FFT operations at the receiver. It has been shown that plain OFDM enables symbol-by-symbol low complexity decoding. However, as stated in [3] and [22], the performance of uncoded OFDM sufiers from loss of diversity. LLP-OFDM [11, 12, 22] has been proposed to combat frequency-selective fading by collecting the multipath diversity provided by the channel. 5 In order to exploit the multipath diversity in OFDM, the LCFC-OFDM designs flrst linearly encode the ith information block s(i) = [s(iN),...,s(iN + N ? 1)]T 2 Z[p?1]N?1 (N is much greater than L, but less than the normalized channel coherence time) by a time-invariant matrix ? 2 CN?N; and then multiplexes the coded symbols u(i) = ?s(i) 2 CN?1 using conventional OFDM. Collecting the ith received OFDM block after CP removal and FFT operations as: y(i) = [y(iN),...,y(iN +N ?1)]T, the input-output (I/O) relationship of the overall system model can be expressed as: y(i) = DHu(i) +w(i) = DH?s(i) +w(i), (2.1) where DH = diag[H(0),H(1),...,H(N ?1)], with H(n) = PLl=0 hle?j2?ln/N. w(i) is the ith white complex Gaussian noise vector observed at the receiver with zero mean and covariance matrix 2wIN. Since we consider block-by-block decoding, for notational simplicity, we will drop our OFDM block index i from now on. There are several ways to design ? to achieve maximum diversity without any chan- nel knowledge at the transmitter. One way is to design ? as a tall Vandermonde matrix with properly chosen generators [22]. For this case, though the bandwidth e?ciency is sacriflced, it has been proved that even linear equalizers (ZF and MMSE) can also achieve the full diversity [21]. But since the complexity of linear equalizers in [21, 22] depends on the block size N with a order of O(N3), when N is large, even linear equalizers require high decoding complexity. Another way to design the LCF encoder uses algebraic number theory and grouping method [11]. Suppose the N subcarriers are split into Ng groups and each group has size K. To achieve the maximum coding gain, we select the gth group as [11] and [12]: 6 sg = [s(g),s(g + Ng),...,s(g + (K ?1)Ng)]T, with s(n) denoting the nth symbol in s. The K equi-spaced symbols are precoded (or linear block coded) by a K ? K unitary matrix ?, and the precoded symbol ug = ?sg is mapped into K equi-spaced carriers. It is readily seen that analogous to (2.1), the I/O relationship for the gth group becomes: yg = DH,g?sg +wg = Hequsg +wg, (2.2) where Hequ := DH,g? is the equivalent channel matrix with DH,g = diag[H(g),H(g + Ng),...,H(g + (K ? 1)Ng)], and wg is the corresponding noise of the gth group. We observe that the I/O relationship of the gth group in (2.2) has the same form as (2.1). Thus, ML or SD method can be used to collect full multipath diversity. As proposed in [12, 11], the maximum achievable multipath diversity order is Gd = min(K,Rh), where Rh denotes the rank of the channel coe?cients correlation matrix E(hhH). Compared with the ungrouped version in [22], grouped LLP-OFDM has lower com- plexity since each group only has K < N symbols. However, ML or near-ML decoder is required to collect multipath diversity. One natural question now is what if one wants to further reduce the complexity and just uses linear equalizer to (2.2) and what the diversity is in this case. In the next section, we analyze the performance of the linear equalizers for LLP-OFDM systems and answer this question. For brevity, we will drop the group index g in (2.2). 2.2 Linear Equalization For LLP-OFDM Linear equalizers are favored in practical systems because they have the lowest complexity among all kinds of detection methods. However, at the same time, linear 7 equalizers are ?blamed? because they usually have inferior and unpredicted performance (e.g., unknown diversity order). In the literature, the performance in terms of diversity with optimal decoders (e.g., ML) has been well-documented (see e.g., [18, 12]). However, the performance of linear equalizers is not well studied. Recently, it has been shown that even linear equalizers can collect the multipath diversity for LLP-OFDM with tall Vandermonde LCF encoders [21], while it is unclear on the performance of LLP-OFDM with linear equalizers. In this section, we study the performance of LLP-OFDM systems with ZF equalizer, MMSE equalizer and decision-feedback equalizer (DFE). We will keep our proofs general so that they can be applied to other linear systems. 2.2.1 ZF Equalizer for LLP-OFDM Suppose that the receiver has perfect channel knowledge. Based on the model in (2.2), the output of ZF equalizer is given as: x = (Hequ)?1y = s+(Hequ)?1w = s+n, (2.3) where n := H?1equw is the noise after equalization. The channel matrix Hequ = DH? has full rank with probability one (wp1) because ? is a unitary matrix and the diagonal matrix DH has full rank wp1. Note that the noise vector n is no longer white and its covariance matrix depends on the equalization matrix H?1equ. The next step is to map the output to signal constellation: ?si = Q(xi) = arg s2S minjxi ?sj, (2.4) where xi denotes the ith element of x and Q(?) means the quantization of the symbol. 8 Starting from (2.3), we now analyze the diversity collected by ZF equalizer. Suppose that the ith transmitted symbol is si, and at the receiver it is erroneously decoded as ?si 6= si. The error probability is given as: P(si ! ?sijHequ) = P(jxi ? ?sij2 < jxi ?sij2 j Hequ), where ni is the ith element of n. If we deflne ei = si ??si, then the error probability can be further simplifled as: P(si ! ?si j Hequ) = P(jei +nij2 < jnij2 j Hequ) = P ?e in?i ?e?ini 2 > jeij2 2 flfl flflHequ ? . (2.5) Though as we stated, the ZF equalized noise vector n is no longer white, it is not di?cult to verify that for each channel realization, n is still complex Gaussian distributed with zero mean and covariance matrix E[nnH] = 2w(HHequHequ)?1 = 2wC, (2.6) where C := (HHequHequ)?1. Deflne a random variable vi = (?ein?i ?e?ini)/2. Given the error symbolei, vi is real Gaussian distributed with zero mean and variancejeij2E[jnij2]/2 = jeij2 2wCii/2, where Cii is the (i,i)th element of C in (2.6). Thus, the error probability in (2.5) can be re-written as: P(si ! ?si j Hequ) = Q ?s jeij2 2 2wCii ! . (2.7) 9 Based on (2.7), the diversity order collected by the ZF equalizer is established in the following: Proposition 1 Given the model in (2.2), if the channel taps are complex Gaussian distributed with zero mean, then the ZF equalizer in (2.3) exists wp1 and collects diversity order 1 over LLP-OFDM systems with frequency-selective channels. Proof: According to the design in [11] or [12], there exists at least one unitary matrix ? that enables maximum diversity for any block size K and constellations that belong to Gaussian integer ring. The diagonal matrix DH has full rank wp1. Thus, both of them are invertible wp1. This shows the ZF equalizer exists wp1. Because ? is unitary and recalling the Vandermonde structure of ?, we notice that the elements of ? have amplitude 1/pK. Thus, matrix C in (2.6) can be written as C = (HHequHequ)?1 = (?HDHHDH?)?1 = ?HD?1H (DHH)?1?, and the (i,i)th entry of C, Cii becomes Cii = Hi D?1H (DHH)?1 i = 1K K?1X k=0 1 jH(k)j2 (2.8) where i is the ith column of the LCF encoder ?. Based on (2.8), we can bound Cii as : 1 KjH(c)j2 ? Cii ? 1 min 0?k?K?1 jH(k)j2 (2.9) where c is any integer, c 2 [0,K ? 1]. The left inequality holds because Cii is the summation of K nonnegative numbers and is surely larger than or equal to any one of 10 them. The right inequality holds because 1jH(k)j2 ? 1min 0?i?K?1 jH(i)j2 for any 0 ? k ? K ?1. According to (2.7), the post-processing signal-to-noise ratio (SNR) of ZF equalizer is = jeij22 2 wCii . Plugging the inequality (2.9) into (2.7), we will have: Kjeij2jH(c)j2 2 2w ? = jeij2 2 2wCii ? jeij2 min 0?k?K?1 jH(k)j2 2 2w . (2.10) Thus, the outage probability [23] can be bounded as: P jH(c)j2 ? 2 2w th Kjeij2 ? ? P( < th) ? P min 0?k?K?1 jH(k)j2 ? 2 2w th jeij2 ? . (2.11) Next, to show the diversity order collected by ZF equalizer, we need the following lemma: Lemma 1 Given N random variables X1,X2,...,XN (either dependent or indepen- dent), they are all central Chi-square distributed with degrees of freedom 2M. Let Xmin denote the minimum of them, and then we have P(xmin < ?) ? cu?M, where cu is a constant depending on N and M. The proof is given in Appendix A. Since jH(k)j2 is exponentially distributed (or Chi- square distributed with degrees of freedom 2), according to Lemma 1, we can obtain: P min 0?k?K?1 jH(k)j2 ? 2 2w th jeij2 ? ? cu th je ij2 2 2w ??1 So the performance upper-bound in (2.11) shows diversity one. Since H(c) is complex Gaussian distributed, jH(c)j2 is Chi-square distributed with degrees of freedom 2. Then, 11 we can obtain that: P jH(c)j2 ? 2 2w th Kjeij2 ? = exp ? 2w th Kjeij2 ? , which shows that the performance lower-bound also has diversity one (see also [23] for similar argument). So the diversity order of the outage probability is just 1. According to [23], the diversity of outage probability is the same as that of average error probability. Thus, the diversity collected by the ZF equalizer for LLP-OFDM system is just 1. ? Interestingly, difierent from the claim in [21], Proposition 1 shows that if we use ZF linear equalizer for LLP-OFDM systems, the diversity order for the performance is only 1. This is because of the difierent structures of the precoders in [11, 22]. For LLP- OFDM, although the ZF equalizer has low complexity, it cannot collect any multipath diversity. 2.2.2 MMSE Equalizer for LLP-OFDM Another often used linear equalizer is minimum mean square error (MMSE) equal- izer. Based on the model in (2.2), the linear MMSE equalizer for LLP-OFDM systems is given as: x = (HHequHequ + 2wIK)?1HHequy. (2.12) 12 It is easy to verify that the MSE of the symbols after MMSE equalization is E[ks? ?sk2] = 2w ?HHequHequ + 2wIK??1 . (2.13) Deflning C = ?HHequHequ + 2wIK??1 and plugging in the fact that Hequ = DH? into C, we have the (i,i)th entry of C Cii = Hi (DHHDH + 2wIK)?1 i = 1K KX k=1 1 jH(k)j2 + 2w. (2.14) The approximate BER after MMSE equalization is [16]: Pe ? X m fimQ ? flm s 1 2wCii ?1 ! , (2.15) where fim and flm depend on the symbol constellation. Based on (2.14), we flnd that the SNR for the error probability is bounded by: min 0?k?K?1 jH(k)j2 2w ? 1 2wCii ?1 ? K 2w(jH(c)j 2 + 2 w). (2.16) Similar to the ZF equalizer case, based on (2.16), the diversity order collected by the MMSE equalizer is established in the following: Proposition 2 Given the model in (2.2), if the channel taps are complex Gaussian dis- tributed with zero mean, then the MMSE equalizer in (2.12) for the LLP-OFDM system collects diversity order 1. 13 2.2.3 DFE Equalizer for LLP-OFDM Generalized decision feedback equalizer (GDFE) is proposed and compared with the Nulling-Cancelling (NC) equalization ([6]) in [5]. It is shown that the operation of GDFE is equivalent to the NC processing. There are two types of GDFE: ZF-GDFE and MMSE- GDFE. Here, we consider the performance of ZF-GDFE while it is straightforward to see the performance of MMSE-GDFE following the similar analysis. For ZF-GDFE (or ZF-NC), the output of the forward equalizer is: x = QHy, (2.17) whereQR is the QR-decomposition of Hequ with unitary matrixQ and upper triangular matrix R. Then the decision process becomes for n = 0 : K ?1 ?sK?n = Q((xK?n ?Ppi=1 RK?n,K?n+i?sK?n+i)/RK?n,K?n) end where Rp,q is the (p,q)th entry of R and xi is the ith entry of x. According to [5], the diversity of LLP-OFDM systems with ZF-GDFE equalizer is determined by the lowest degrees of freedom of jRk,kj2,k 2 [1,K], where R is the QR decomposition of DH? and Rk,k is the (k,k)th entry of R. Considering the QR decomposition process, RK,K ofiers the lowest degrees of freedom. Because C = (HHequHequ)?1 = (RHR)?1, it can be verifled that jRK,Kj2 = C?1KK satisfles: min 0?k?K?1 jH(k)j2 ? jRKKj2 ? KjH(c)j2. (2.18) 14 Thus, following the analysis for ZF equalizer, we can see that the maximum diversity order that ZF-GDFE can collect is just 1. Similarly, the diversity of the LLP-OFDM systems with MMSE-GDFE is also 1. Proof is omitted here. Remark 1 From our analysis, we notice that for LLP-OFDM systems, the linear equal- izers cannot exploit any multipath diversity, though they have much lower decoding complexity compared with ML or SD methods. Furthermore, the performance of ZF equalizer is the worst among these three linear equalizers while MMSE-GDFE equalizer has the best performance of them. 2.3 LR-aided Linear Equalization For LLP-OFDM As we know, for linear systems, if Hequ in (2.2) is diagonal, ZF equalizer has the same performance as ML decoder (e.g., for plan OFDM case). However, in general Hequ is not diagonal, and thus ZF equalizer has inferior performance (e.g., in Section III we have shown that ZF equalizer cannot collect multipath diversity). This motivates us to flnd a way to make Hequ close to a diagonal matrix. If the symbols s are drawn from Gaussian integer ring (QAM, PAM constellations), then Hequs belongs to a lattice generated by the columns of Hequ. Thus, to estimate the information symbols is equivalent to searching for the closet point in the lattice [1]. The motivation to use lattice reduction (LR) technique in equalization is to make the decision region of the linear equalizers more like that of ML detector by flnding a more orthogonal basis for the lattice, thus increase the performance. Recently, Lenstra-Lenstra-Lov?asz (LLL) algorithm has been adopted for LR-aided linear equalizers to flnd more orthogonal basis for communication MIMO channels, because it guarantees polynomial complexity 15 to flnd a set of bases within a factor of the shortest vectors (see e.g., [8, 24, 27]). The LLL reduction was flrst posted in [10]. The LR-aided linear equalizers were flrst applied to MIMO systems (see e.g., [8, 24, 27]). However, the methods in [24, 26, 27] are based on real lattice reduction methods, which increase the decoding complexity by splitting the complex channels into real and imaginary parts. [8] uses complex lattice reduction method, but only for two-transmit-antenna case. In [14], it is mentioned that complex LLL algorithm can be extended to any number of transmit-antennas. Unfortunately, detailed complex LLL algorithm is not provided in [14]. In general, these existing re- sults show that LR performed on the channel matrix can improve the linear detectors? performance while does not increase the complexity much. 2.3.1 LR-aided Linear Equalization We flrst extend the LLL algorithm to complex fleld for any number of transmit- antenna. Our proposed complex LLL algorithm can be found in Appendix B, where we use the conventional Matlab notation (e.g., R(k,k) denotes the (k,k)th element of matrix R). Compared with the real LLL algorithm in [27], the major difierence of the complex LLL algorithm exists at Steps (8) and (16) in Table 1. Later by simulations, we show that the complex LLL algorithm enables lower computational complexity than the real LLL algorithm without sacriflcing any performance. Given the system model in (2.2), we adopt CLLL algorithm to reduce the lattice basis of Hequ and obtain ?H = HequT, where T is a unimodular matrix which means all the entries of T and T?1 are Gaussian integers and the determinant of T is ?1 or ?j. Then, we apply the LR-aided ZF equalizer ?H?1 instead of H?1equ, and the output can be 16 S1: Map the information bits to symbols s whose constellation belongs to Gaussian integer ring; S2: Obtain (2.2) after LLP-OFDM transceiver operations; S3: Perform the Complex LLL algorithm to reduce the lattice basis of the equivalent channel matrix: [ ?H,T] = CLLL(Hequ); S4: Rewrite the system as y = HequT(T?1s)+w = ?Hz +w; S5: Apply the ZF equalization based on the new system to obtain ?z = Q( ?H?1y); S6: Use ?z and T to recover the original information: ?s = Q(T?z). Table 2.1: Lattice-Reduction Aided ZF Equalization written as [c.f. (2.2)]: x = T?1s+ ?H?1w = z +n. (2.19) Since all the entries of T?1 and the signal constellation belong to Gaussian integer ring, the entries of z are also Gaussian integers. One can estimate z from x by quantization. After obtaining z, one can recover s by using T and mapping to the appropriate constel- lation. We summarize the main steps of LR-aided ZF equalizer for LLP-OFDM systems in Table . Note that the equivalent channel matrix Hequ can be other communication channels (e.g. MIMO channel matrix later in Chapter 3, MIMO-OFDM matrices in Chapter 4). To perform the LR-aided MMSE equalizer, we cannot just apply the conventional MMSE equalizer to the new system in Step S4, because the average power of z is not easy to determine. In [27], it shows that LR-aided MMSE equalizer agrees to the LR-aided ZF equalizer with respect to an extended system. Compared with the conventional linear equalizers, LR-aided linear equalizers increase the complexity only in the CLLL reduction step, we will compare the complexity over difierent systems by simulations. 17 Remark 2 Here, we notice that in Step S5, the quantization of ?H?1y is simply round- ing to the nearest integer in order to reduce the complexity. Thus, we must make sure the constellation of symbols s belongs to Gaussian integer ring, and both the real and the imaginary parts are drawn from an integer set whose elements are consecutive integers, or can be transferred to consecutive integers by shifting and scaling. Otherwise, for each realization of channel Hequ, one needs to calculate T and then flnd the set of possible ?z. Typically, M-QAM constellations satisfy this prerequisite, e.g., 4-QAM symbols s whose constellation is f?1?jg, can be transferred to f1(0)+1(0)jg by performing 12(s+1+j). Difierent from the simple rounding in Step S5, the quantization in Step S6 is to map the product of T and ?z to the original information constellation. 2.3.2 Performance Analysis on LR-aided Linear Equalizers In this section, we prove the diversity order collected by LR-aided linear equalizers. To make our proof compact, we introduce some important deflnition and lemmas flrst. Deflnition 1 An orthogonality deflciency (od) of an M?N matrix B = [b1,b2,...,bN] as: od(B) = 1? det(B HB) QN n=1 jbnj2 (2.20) where jbnj,1 ? n ? N is the norm of the nth column of B. Note that 0 ? od(B) ? 1, 8B and if B is singular, od(B) = 1; and if the columns of B are orthogonal, od(B) = 0. It has been shown that LLL algorithm tries to reduce the 18 od of the studied matrix [10]. The quantitative result on od reduction is given in the following lemma: Lemma 2 Given a matrix H 2 CM?N with rank N, ?H is obtained after applying complex LLL (CLLL) algorithm with parameter ? on H [30]. Then, the orthogonality deflciency of ?H satisfles: q 1?od( ?H) ? 4 4? ?1 ??N(N?1)/4 := c?, (2.21) where c? is determined by ? and N, and ? can be any flxed real number in (1/4,1). For real H, Lemma 2 is consistent with the result in [10, Proposition 1.8]. Here, we extend it to complex fleld according to the CLLL algorithm in [30]. Given ? and any integer N ? 1, c? is always less than 1. Therefore, the od(H) is bounded by 1 ?c2?. If H is singular, i.e., rank(H) < N, then Lemma 2 does not hold true. In this case, we need to reduce the size of H and then apply CLLL algorithm. Since information symbols s belong to Gaussian integer ring, then Hs generates a lattice L 2 CM?1 with a set of basis vectors H = [h1,h2,...,hN]. The following lemma shows an important statistical property of the minimum distance of the lattice L, which will be useful for our proof on diversity order. Lemma 3 Let H = [h1,h2,...,hN] be a set of bases for a lattice L in CM?1. Deflne hmin as the vector in L which has the minimum non-zero norm among all the vectors. If all entries of H are complex Gaussian distributed with zero mean, the following inequality 19 holds: Pfjhminj2 ? ?g ? ch?D, (2.22) where ch is a constant determined by N and M, and D = min 8p6=0 rank(E(pp H)), (2.23) where p 2 L and p 6= 0. The proof can be found in Appendix C. From Lemma 3 we notice that the degrees of freedom D ofhmin is determined by the minimum rank of all possible covariance matrices generated by the vectors L. Apparently, it depends on the covariance matrices of each column hn and the cross-correlation among the columns. To facilitate the use of Lemma 3, we give a corollary as follows: Corollary 1 Let H = [h1,h2,...,hN] be a set of bases for a lattice L in CM?1. If 1) all the entries of H are complex Gaussian distributed with zero mean; 2) rank(E[hnhHn ]) = D, 8n 2 [1,N]; and 3) all the columns are linear independent with each other on the Gaussian integer ring, then we have Pfjhminj2 ? ?g ? ch?D. Now we are ready to analyze the diversity order collected by the LR-aided ZF equalizer for the LLP-OFDM systems which is quantifled in the following proposition: Proposition 3 Considering an LLP-OFDM system with group size of K and frequency- selective channel order of L, given the model in (2.2), the diversity order collected by an 20 LR-aided ZF equalizer is min(K,Rh) which is the same as that obtained by ML detector, where Rh = E[hhH] and h = [h(0),...,h(L)]T. Proof: The output of the LR-aided ZF equalizer is stated in (2.19). Because the entries of z are integers, if the real and imaginary parts of each entry of n = ?H?1w are in the interval (?12, 12), one is able to decode z correctly and thus obtain s correctly. Let us denote ?H?1 as [a0,a1,...,aK?1]T, where aTi ,i 2 [0,K ? 1] is the ith row of ?H?1. Hence, if jaTi wj is less than 12, we will deflnitely decode the ith symbol correctly. Thus, PejHequ, the error probability for a given Hequ is upper-bounded by PejHequ ? P jaTi wj ? 12 flfl flflHequ ? . From [19, Lemma 1], we obtain the following inequality: jaTi j ? 1q 1?od( ?H)j?hij (2.24) where ?hi,i 2 [0,K ?1] represents the ith column of ?H. Because jaTi wj ? jaTi jjwj ? jwjq 1?od( ?H)j?hij , if jwj is less than 12 q 1?od( ?H)j?hij, we will have jaTi wj ? 12. Furthermore, since ?H is reduced from Hequ using CLLL algorithm, q 1?od( ?H) ? ( 44??1)?K(K?1)/4 according to Lemma 2 wp1. Deflne Hequ := [h0,h1,...,hK?1], where hi,i 2 [0,K ?1] is the ith column of Hequ. Let hmin represent the vector with minimum non-zero norm of all the vectors in the lattice generated by Hequ. Since T is unimodular, ?H spans the same 21 lattice as Hequ. It is easy to verify that jhminj is less than or equal to min 1?i?K j?hij. Thus, we can see that if jwj is less than 12c?jhminj, then jwj is less than 12 q 1?od( ?H)j?hij for any i 2 [1,K]. Here we notice that though c? is independent on Hequ, hmin depends on Hequ. In summary, we have: PejHequ ? P jaTi wj ? 12 flfl flflHequ ? ? P jwj ? 12c?jhminj flfl flflHequ ? . (2.25) Since w is complex Gaussian white noise, jwj2 is a central Chi-square random vari- able with degrees of freedom 2K and mean K 2w. Thus, by averaging (2.25) with respect to the random matrix Hequ (or hmin, the error probability can be further simplifled as: Pe ? EH ? P jwj ? 12c?jhminj flfl flflHequ ?? ? P '(c?jhminj)2 ? 4K 2w?P 'jwj2 ? K 2w? +P '4K 2w ? (c?jhminj)2 ? 4t2K 2w?P 'jwj2 ? t2K 2w? +P '4t2K 2w ? (c?jhminj)2 ? 4t3K 2w?P 'jwj2 ? t3K 2w?+... (2.26) where t is a positive constant that satisfles t > 1. Here, we notice that all the entries of Hequ are complex Gaussian distributed with zero mean and all the columns are linear independent with each other with probability one. Furthermore, the rank of the covariance matrices of hi,i 2 [0,K ?1] is min(K,Rh) [11]. With these three conditions satisfled, according to Corollary 1, we have Pfjhminj2 ? ?g ? ch?min(K,Rh). Thus, we can get the probability that: P '(c?jhminj)2 ? aK 2w? ? ch ? aK 2 w c2? ?min(K,Rh) . 22 Because jwj2 is Chi-square distributed, we obtain that [9, p. 25] P 'jwj2 ? aK 2w? = e?aK K?1X k=0 (2aK)k k! ? cKe ?aKaK, where cK = PK?1k=0 (2K)kk! is a constant that only depends on K. By using Gd to represent min(K,Rh), Eq. (2.26) is simplifled as : Pe ? chcK 4K c2? ?Gd 1 2w ??Gd " 1X n=0 tn(K+Gd)e?Ktn # . (2.27) It is not di?cult to show that the summation (2.27) converges to a constant which only depends on K,t, and Gd when t > 1. Therefore, the diversity order of the LR-aided ZF equalizer is greater than or equal to Gd = min(K,Rh). However, as we know, the maxi- mum diversity order for each group is min(K,Rh). Thus for LLP-OFDM, the LR-aided ZF equalizer collects diversity order min(K,Rh). ? As we have shown, linear equalizers cannot exploit the multipath diversity for LLP- OFDM systems, however, after introducing the LR technique into the linear equalization process, multipath diversity is collected. Similar to the proof for Proposition 3, one can show that LR-aided MMSE estimator also collects multipath diversity. Note that LR-aided linear equalizers have some unique properties: i) the decoding complexity is much lower than ML and quite close to linear ones; ii) unlike SD, the complexity does not depend on SNR; iii) the complexity of CLLL part does not change along with constellation size. 23 0 5 10 15 20 25 3010?5 10?4 10?3 10?2 10?1 100 SNR in dB BER LLP?OFDM w/ ZFLLP?OFDM w/ MMSE LLP?OFDM w/ ZF?GDFELLP?OFDM w/ MMSE?GDFE Plain OFDM w/ ML Figure 2.1: Comparisons among difierent linear equalizers 2.4 Simulation Results In this section, we use computer simulations to verify our theoretical claims on the diversity order of linear equalizers and the performance of LR-aided linear equalizers. Example 1 (Performance comparison of difierent equalizers): We flrst compare the performance of the LLP-OFDM with difierent equalizers with the conventional (plain) OFDM. We select L = 3, and the total subcarriers N = 8. The channel taps are i.i.d complex Gaussian random variables with zero mean and variance 2 = 1/(L + 1). To enable the multipath diversity Gd = L + 1 = 4, we adopt the LLP-OFDM. The subcarriers are split into Ng = 2 groups with group size K = 4. QPSK modulation is used. The bit-error-rate (BER) versus SNR for linear equalizers is shown in Figure 2.1. 24 0 5 10 15 20 25 3010?7 10?6 10?5 10?4 10?3 10?2 10?1 100 SNR in dB BER LLP?OFDM w/ LR?aided ZFLLP?OFDM w/ LR?aided ZF?GDFE LLP?OFDM w/ LR?aided MMSELLP?OFDM w/ ML Figure 2.2: Comparisons among difierent equalizers for LLP-OFDM For plain OFDM, we only consider symbol-by-symbol ML detection. For LLP-OFDM, we consider ZF, ZF-GDFE, MMSE, MMSE-GDFE. From Figure 2.1, we notice that: i) plain OFDM only achieves diversity one, and so do ZF, ZF-GDFE, MMSE and MMSE- GDFE detectors for LLP-OFDM; ii) for LLP-OFDM, the performance of ZF equalizer has the worst performance, while MMSE(-GDFE) has better performance than others. Figure 2.2 shows the BER curves of LR-aided ZF, LR-aided MMSE, LR-aided ZF-GDFE and ML detectors for LLP-OFDM. From this flgure, we observe LR-aided ZF, MMSE or ZF-GDFE detectors of LLP-OFDM collect diversity order L+1 and so does ML detector. The performance of LR-aided MMSE equalizer is better than that of LR-aided ZF and ZF-GDFE, but there still exists a gap between the performance of LR-aided equalizers and ML detector. This is one of our future topics. 25 0 5 10 15 20 25 3010?7 10?6 10?5 10?4 10?3 10?2 10?1 100 SNR in dB BER LR?aided ZF with K=2LR?aided ZF with K=3 LR?aided ZF with K=4SD with K=2 SD with K=3SD with K=4 Figure 2.3: Comparisons among difierent group sizes using ML detector and complex LR-aided equalizer Example 2 (Performance comparison of difierent group sizes):In this example, we flx the total number of subcarriers N = 12, channel order L = 2 and the number of total channel taps is L + 1 = 3. We use difierent group sizes to simulate the LLP- OFDM, and then compare the performance of them. The group size is chosen to be K = 2,3,4 respectively, and precoder ? is designed according to [29]. At the receiver, both SD decoder and complex LR-aided ZF equalizer are employed and compared. Fig- ure 2.3 shows the performance for difierent cases. Theoretically, the diversity order is Gd = min(K,L+1) [12]. Based on the simulation results, we observe that the diversity order collected by both SD and complex LR-aided ZF equalizer is 2,3 respectively cor- responding to group size K = 2,3. When K = 4, the channel taps in each group are 26 2 2.5 3 3.5 4 4.5 5 5.5 60 0.5 1 1.5 2 2.5 3x 104 Group Size K Number of Arithmetic Operations ZF DetectionGeneral ZF LR?aided ZFSD method Figure 2.4: Complexity comparison of difierent decoding methods correlated. We notice that our LR-aided linear equalizer still collects full diversity. Example 3 (Complexity comparison of decoding schemes):After comparing the performance of difierent decoding methods with difierent group size, we verify here the difierence of the complexity. Here, we choose the number of total sub-carriers of OFDM as N = 12 and the order of channel L = 5, then the multipath diversity order is 6. To compare the complexity of difierent decoding methods, we flx SNR = 30dB and count the number of arithmetic operations (real additions and real multiplications). In Figure 2.4, we plot four curves to represent: SD method [7], complex LR-aided ZF equalizer, general ZF equalizer and ZF detection for LLP-OFDM. Here, general ZF detection means using pseudo-inverse equalizer ((DH?)?1) and the simple ZF detection 27 is ?HD?1H . From Figure 2.4, we notice that, the curve of LR-aided ZF equalizer is much colser to general ZF detection than to SD method. This means that the decoding complexity of LR-aided ZF is near that of general linear equalizers, and much lower than SD method. Furthermore, the ratio of the gap between LR-aided ZF and SD to the gap between LR-aided ZF and general ZF increases as group size K increases. Thus, LR-aided ZF equalizer becomes computational preferable as K increases. All of these four curves increase as K increases, which means the complexity increases as the group size increases while the performance is getting better. From Figure 2.4, we can see that the simplifled ZF equalizer for LLP-OFDM is quite low but it can only collect diversity 1. However, with a complexity that is a little bit higher than ZF equalizer, LR-aided ZF equalizer can gurantee the same diversity as ML detector. 28 Chapter 3 LINEAR EQUALIZATION FOR V-BLAST SYSTEMS In this chapter, we study the performance of V-BLAST multi-antenna architecture which is presented in [4] and [25]. Similar to the LLP-OFDM systems, through the analysis, we show that LR-aided linear equalizers can exploit the same diversity as ML detection while linear equalizers lose diversity which means performance degradation. 3.1 System Model of V-BLAST Systems Consider a multi-antenna system withNt transmit-antennas andNr receive-antennas, where Nr ? Nt. In V-BLAST model ([4, 25]), the data stream is divided into Nt sub-streams and transmitted through Nt antennas. These sub-streams consist of M- QAM symbols (or in general, symbols on Gaussian integer ring). For notation sim- plicity, we assume that the power of each transmit-antenna is normalized to one. Let s = [s1,s2,...,sNt]T represents the Nt ? 1 transmitted data vector at one time slot, while w = [w1,w2,...,wNr]T denotes the white Gaussian noise vector observed at the Nr receive-antennas with zero mean and variance 2w. Without any coding, we consider that E'ssH? = INt and E'wwH? = 2wINr. The received signal at one time slot is denoted as: y = [y1,y2,...,yNr]T which is represented by: y = Hs+w, (3.1) 29 where H is the channel matrix, which consists of Nr ?Nt uncorrelated complex Gaus- sian channel coe?cients with zero mean and unit variance. We assume a at-fading environment that the channel coe?cients are constant during a frame and change inde- pendently from frame to frame. Also we assume that the channel matrix H is known at the receiver. Theoretically, at the receiver, we can perform maximum-likelihood (ML) detection to obtain the optimal performance of the system. Recall that the ML estimate is given as: ?sML = arg s2SNt min k y?Hs k2, (3.2) where k ? k denotes the 2-norm. The diversity order collected by an ML decoder for the system in (3.1) is Nr, the number of receive-antennas (see e.g., [28]). However, the cardinality of the searching space is jSNtj = MNt, thus the exponential complexity pro- hibits the use of ML detection in practical systems (especially for systems that have large constellations and numbers of antennas). In the next section, we will introduce the linear detectors, whose decoding complexity is much lower than ML and thus computationally preferable in certain situation. 3.2 Linear Equalizers and Performance Analysis In this section, we brie y describe the linear equalizers for V-BLAST systems and then focus on analyzing their performance. 30 3.2.1 ZF Equalizers The zero-forcing (ZF) detector for the input-output relationship in (3.1) is given as: xZF = Hyy = s+Hyw = s+n, (3.3) where Hy denotes the Moore-Penrose Pseudo-inverse of the channel matrix H and n := Hyw is the noise after equalization. The pseudo-inverse matrix can be written as : Hy = (HHH)?1HH (3.4) where the channel matrix H has full column rank with probability one. Note that the noise vector n is no longer white and its covariance matrix depends on the equalizer matrix Hy. The quantization step is then used to map each entry of x into the symbol alphabet S : ?sZFn = Q(xn) = arg s2S minjxn ?snj, (3.5) where xn denotes the nth element of xZF and Q(?) means the quantizer of the symbol. Starting from (3.3), we flrst study the performance of the ZF equalizer. Following the proof for Proposition 1 with Hequ = H, we can get the error probability given H as: P(si ! ?si j H) = Q ?s j ei j2 2 2wCii ! , (3.6) 31 where Cii is the (i,i)th element of C and C can be expressed as: C = Hy(Hy)H = (HHH)?1. (3.7) Based on (3.6), the diversity order collected by ZF equalizer is established in the following: Proposition 4 Given the model in (3.1), if the channels are i.i.d. complex Gaussian distributed, then the ZF equalizer in (3.3) exists with probability one and the diversity order for the system is Nr ?Nt + 1. Proof: See Appendix D. This proposition shows that not surprisingly, the ZF linear equalizer enables the same diversity as nulling-cancelling (NC) method for V-BLAST system [28], since NC method agrees with ZF equalizer when detecting the flrst symbol ( the Ntth symbol of s). However, the diversity order is lower than the ML equalizer. 3.2.2 MMSE Equalizers Another type of linear equalizer is minimum mean square error (MMSE) detector which takes into account the noise variance. It minimizes the mean-square error between the actually transmitted symbols and the output of the linear detector and thus improves the performance. Given the model in (3.1), the MMSE equalizer is : xMMSE = ?HHH + 2wINt??1HHy. (3.8) 32 Again, the quantization step is the same as the one in (3.5). As shown in [26], with the deflnition of an extended system, the MMSE detector agrees with the ZF detector. For the MMSE equalizer, we start from (3.8) and rewrite the system model as: xMMSE = s+?HHH + 2wINt??1 (HHw? 2ws). (3.9) Deflne the equivalent noise vector n = (HHH+ 2w INt)?1(HHw? 2ws). Given a signal vector s, the noise vector n has mean and covariance matrix, respectively as: ?n = ? 2w(HHH + 2wINt)?1s ? = 2w(HHH + 2wINt)?1 ? 4w(HHH + 2wINt)?2. (3.10) Similar to the analysis for the ZF equalizer, we can verify that error probability is given as: P(si ! ?si j H) = Q ?s (j ei j2 +e?i ?ni +ei?n?i)2 2jeij2?ii ! , (3.11) where ?ni is the ith element of noise mean ?n and ?ii is the (i,i)th element of noise covariance matrix ? in (3.10). At high signa-to-noise ratio (SNR), i.e., when 2w is much smaller than 1, Eq. (3.11) can be approximated as: P(si ! ?si j H) ? Q ?s j ei j2 2 2w ?Cii ! , (3.12) 33 where ?Cii is the (i,i)th element of (HHH + 2wINt)?1. It is ready to verify that ?Cii has the same degrees of freedom as Cii in (3.6). This shows that MMSE detector can achieve the same diversity as ZF detector: Proposition 5 Given the model in (3.1), if the channels are i.i.d. complex Gaussian distributed, then MMSE equalizer in (3.8) exists with probability one and the diversity order for the system is Nr ?Nt + 1. In general, the MMSE equalizer outperforms the ZF equalizer with larger coding ad- vantage because ?Cii is always less than Cii. Furthermore, if we spell out ?Cii and Cii, for the same SNR, as the number of receive-antennas (Nr) increases, the performance gap between MMSE and ZF detectors decreases. In [21], it has been shown that certain linear precoded OFDM systems can also achieve maximum diversity by linear equaliz- ers. However, here we have shown that linear equalizers for V-BLAST systems can only achieve diversity order Nr?Nt+1, which is less than the maximum diversity Nr. In the following, we show that using lattice reduction methods, we can restore the maximum diversity order Nr. 3.3 LR-Aided Linear Equalizers The performance of LR-aided linear detectors for V-BLAST system is established in the following proposition: Proposition 6 The diversity order collected by a Lattice-Reduction aided linear detector (LR-aided ZF or LR-aided MMSE) for an MIMO V-BLAST system with Nt transmit- antennas and Nr receive-antennas is Nr, which is the same as that obtained by maximum- likelihood detector. 34 The proof is similar to that of Proposition 3. What we need to prove is Pfjhminj ? ?g ? ch?2Nr, where hmin is the vector with the minimum norm of all the vectors in the lattice spanned by H. Since all the entries of H are i.i.d. complex Gaussian random variables with zero-mean, the rank of E[hnhHn ] is Nr for n 2 [1,Nt]. Furthermore, the Nt columns are linear independent with each other on the Gaussian integer ring with probability one. Thus, according to Corollary 1, we can obtain that Pfjhminj ? ?g ? ch?2Nr. Then following the proof of Proposition 3, we can see, for V-BLAST systems LR-aided ZF equalizer can collect diversity Nr, which is the same as that exploited by ML detection. 3.4 Simulation Results In this section, we use computer simulations to verify our theoretical claims on the diversity order of linear equalizers and the performance of LR-aided linear equalizers for V-BLAST systems. The channels are generated as i.i.d. complex Gaussian variables with zero mean and unit variance. The SNR is deflned as symbol energy per transmit- antenna versus noise power. Example 1 (Diversity collected by linear equalizers): The ZF and MMSE equal- izers in (3.3) and (3.8) are considered for V-BLAST systems in this example. We consider Nt = 2 transmit-antennas, and difierent numbers of receive-antennas Nr = 2,3,4. BPSK is used as the modulation scheme. The bit-error rate (BER) versus SNR is depicted in Figure 3.1. Reading the slopes of the curves in Figure 3.1, we observe that the diversity orders enabled by either ZF or MMSE equalizer are indeed Nr ? Nt + 1, which in this 35 0 5 10 15 20 25 3010?5 10?4 10?3 10?2 10?1 100 SNR in dB SER ZF equalizer(Nr=2)ZF equalizer(Nr=3) ZF equalizer(Nr=4)MMSE equalizer(Nr=2) MMSE equalizer(Nr=3)MMSE equalizer(Nr=4) Figure 3.1: BER of systems with Nt = 2 and Nr = 2,3,4 separately and BPSK modu- lation example are 1,2, and 3. Furthermore, we observe that the performance of MMSE detec- tion is better than ZF detection and the gap between them decreases as Nr increases. Example 2 (LR-aided linear equalizers): In this example, we flx the number of transmit- and receive-antennas as Nt = 3,Nr = 4, and use QPSK as the modulation scheme. Five detection methods are applied to the system: ZF detection, MMSE de- tection, complex LR-aided ZF detection, complex LR-aided MMSE detection and ML detection. Observing Figure 3.2, we notice that the linear detectors can only achieve the diversity order Nr ? Nt + 1 which is 2 in this case. The ML detector enables diversity order Nr = 4. As expected, the LR-aided linear detectors achieve the same diversity order as the ML does. The performance gap between LR-aided linear detectors and ML 36 0 5 10 15 20 25 3010?5 10?4 10?3 10?2 10?1 100 SNR in dB SER ZF DetectionLR?aided ZF Detection MMSE DetectionLR?aided MMSE Detection ML Detection Figure 3.2: SER of a system with (Nt,Nr) = (3,4) and QPSK modulation detector is because the LLL algorithm cannot perfectly diagonalize the channel matrix. Example 3 (Complex LLL algorithm): As shown in Chapter 2, we have extended the LLL algorithm to complex fleld for any number of transmit-antenna. The detailed CLLL algorithm can be found in Appendix B. In this example, we compare the complex LLL algorithm with the real LLL algorithm in terms of complexity and performance. The arithmetic operations we count are the number of real additions and real multiplications. In Figure 3.3, we count the average number of arithmetic operations needed by the complex and real LLL algorithm separately as Nr = Nt = n increases. We can see that the complexity of the real LLL algorithm is about O(n4) which is consistent with the result in [10]. The number of arithmetic operations that the real LLL algorithm 37 2 3 4 5 6 7 8 9 100 5000 10000 15000 Nr=Nt Number of Arithmetic Operations Complex?LR?aided ZFReal?LR?aided ZF Figure 3.3: Complexity comparison between complex LLL and real LLL algorithms needs is about 1.5 times of that of the complex LLL algorithm. Therefore, the complex LLL algorithm is more e?cient. In Figure 3.4, we also compare the performance of complex LR-aided and real LR-aided schemes. It can be seen that complex LR-aided linear equalizers have the same performance as the real ones. So we can see, with lower complexity and the same performance, complex LLL algorithm is computational preferable to real LLL algorithm. 38 0 5 10 15 20 25 3010?5 10?4 10?3 10?2 10?1 100 SNR in dB SER ZFComplex?LR?aided ZF Real?LR?aided ZFML Figure 3.4: Performance comparison between the complex and real LLL algorithms with (Nt,Nr) = (4,4) 39 Chapter 4 EXTENSION TO MIMO-OFDM SYSTEMS As we have shown, linear equalizers can not exploit the multipath diversity for LLP- OFDM systems, however, after introducing the LR technique into the linear equalization process, multipath diversity is collected. In this chapter, we see similar situation happens to the MIMO-OFDM designs. The block diagram of MIMO-OFDM is depicted in Fig.4.1. There are Nr receive-antennas and Nt transmit-antennas, and the frequency-selective wireless links between transmit- and receive-antennas have the same channel order L. The channel taps of the link between the ?th transmit-antenna and the ?th receive- antenna are denoted as h(?,?)l for l 2 [0,L] and ? 2 [1,Nr],? 2 [1,Nt]. x?n(p) represents the symbol transmitted on the pth subcarrier from the ?th transmit-antenna in the nth OFDM time slot while y?n(p) is received at the ?th receive-antenna on the pth subcarrier in the nth OFDM slot. There are many coding schemes designed for MIMO-OFDM and difierent designs will present difierent performance even with the same equalizers. In this section, we will use two coding schemes: full-diversity-full-rate (FDFR) design in [13] and space-time- frequency (STF) design in [11] as examples to show the diversity that linear equalizers and LR-aided linear detection methods can collect. 4.1 FDFR-OFDM Multi-antenna systems not only provide space diversity, but also boost transmission rate. FDFR design has been introduced to enjoy both advantages [13]. When channels 40 Figure 4.1: Block Diagram of MIMO-OFDM are frequency-selective, FDFR design can be combined with OFDM to reduce the equal- ization complexity and collect diversity to combat fading. However, the main price paid here is decoding complexity (see [13] for details). In the following, we brie y introduce the FDFR-OFDM design and then give the performance analysis when linear equalizers or LR-aided equalizers are employed. Let y(p) 2 CNr?1 represent the symbol vector received through Nr receive-antennas on the pth subcarrier. By stacking y(p),p 2 [0,Nc ?1] (Nc is the number of total sub- carriers which we assume to be Nt(L+1) for simplicity) into one symbol vector, the I/O relationship of FDFR design is represented as: 2 66 66 64 y(0) ... y(Nc ?1) 3 77 77 75 = 2 66 66 64 H(0)(P1Dfl)? T1 ... H(Nc ?1)(PNtDfl)? TNc 3 77 77 75s+ 2 66 66 64 w(0) ... w(Nc ?1) 3 77 77 75 = HFDFRs+w,(4.1) where the permutation matrix Pn and the diagonal matrix Dfl are deflned as: Pn := 2 64 0 In?1 INt?n+1 0 3 75, D fl := diag[1,fl,...,flNt?1], (4.2) 41 and scalar fl can be found in [13], H(p),p 2 [0,Nc ?1] is the MIMO channel matrix on the (p+1)st sub-carrier with the (?,?)th entry H(?,?)(p) = PLl=0 h(?,?)l e?j2?plNc , Tn is the nth row of Nc?Nc LCF encoding matrix ? and s comprises N2t (L+1) symbols. Based on this system model, we flrst summarize the results for FDFR design as follows: Proposition 7 Considering an FDFR-OFDM system with Nt transmit-antennas and Nr receive-antennas, and the frequency-selective channel order of L, given the model in (4.1), if the channel taps are independently complex Gaussian distributed with zero mean, then the ZF equalizer exists wp1 and collects diversity order Nr ?Nt + 1. An LR-aided ZF equalizer exists wp1 and collects full diversity NrNt(L+1) which is the same as that exploited by ML detector. According to the design of fl and ? in [13] and the structure of HFDFR, it is not di?cult to verify that HFDFR has full rank wp1, which means ZF equalizer exists wp1 for the model given in (4.1). Following the general proof of Proposition 1, we can express the error probability of the FDFR design using ZF equalizer as: P(si ! ?si j HFDFR) = Q ?s jeij2 2 2wCii ! . (4.3) where Cii is the (i,i)th entry of the matrix C = (HHFDFRHFDFR)?1. Given HFDFR as in (4.1) we can get the speciflc form of Cii as: Cii = 1N c Nc?1X p=0 Ckk(p) = 1N c Nc?1X p=0 1 C?1kk (p), k = (m+p)? ?m+p Nt ? ?1 ? Nt (4.4) 42 where m = l i Nc m and Ckk(p) is the (k,k)th entry of the matrix C(p) = (HH(p)H(p))?1. Thus, we can bound Cii as: 1 NcC?1kckc(c) ? Cii ? 1 min 0?p?Nc?1 C?1kk (p) (4.5) Here c is a constant number, c 2 [0,Nc ?1] and kc is determined by c and i. As stated in Appendix. D, C?1kk (p) is a Chi-square random variable with degrees of freedom of 2(Nr ? Nt + 1). With the error probability expressed in (4.3), by using Lemma 1, the outage probability can be bounded as: (Nr ?Nt + 1)Nr?Nt ?(Nr ?Nt +1) 2 2 w th Ncjeij2 ?Nr?Nt+1 ? P( < th) ? cu 2 2 w th jeij2 ?Nr?Nt+1 . (4.6) So we can obtain that the diversity order of ZF equalizer for FDFR design is Nr?Nt+1. Regarding the performance of LR-aided ZF equalizer for FDFR designs, the proof is similar to that for Proposition 3. We only need to prove Pfjhminj2 ? ?g ? ch?NrNt(L+1), where hmin is the vector with minimum non-zero norm of all the vectors in the lattice spanned by HFDFR. Given the system in (4.1), we can write the speciflc form of the ith column of HFDFR as : hi = 2 66 66 66 66 66 66 4 H(0)mfl(m?1)?1, i?(m?1)Nc ... H(p)(p+m)?(n?1)Ntfl(m?1)?p+1, i?(m?1)Nc ... H(Nc ?1)(Nc+m)?(n?1)Ntfl(m?1)?Nc, i?(m?1)Nc 3 77 77 77 77 77 77 5 , (4.7) 43 where m = d iNce and n = dm+pNt e. H(p)(p+m)?(n?1)Nt is the ((p+m)?(n?1)Nt)th column of the matrix H(p), and ?p+1, i?(m?1)Nc is the (p + 1, i?(m?1)Nc)th entry of the LCF encoder ?. Since fl(m?1)?p+1, i?(m?1)Nc is deterministic given i and p, the statistical property of the ith column is determined byH(p)(p+m)?(n?1)Nt,p 2 [0,Nc?1], which is the frequency response of the pth subcarrier of the frequency-selective channels between the ((p + m) ? (n ? 1)Nt)th transmit-antenna and Nr receive-antennas. Intu- itively, the NrNt(L + 1) ? 1 vector hi selects L + 1 subcarriers from each of the total NrNt frequency-selective channels. So the rank of the covariance matrix of each column is NrNt(L + 1). The N2t (L + 1) columns are linear independent with each other which is guaranteed by the LCF encoder ? and the choice of fl in [13]. Thus, similar to LLP- OFDM, following the proof of Proposition 3, we can get that the diversity order of the LR-aided linear equalizer for FDFR design is NrNt(L + 1) which is also the maximum diversity order that the system can achieve. 4.2 STF-OFDM STF design is also composed of two stages: LCF encoding across subcarriers and ST multiplexing using ST orthogonal code [20]. For example, when Nt = 2, the 2NgK ?1 symbol vector s is split into 2Ng groups, sn 2 CK?1,n 2 [1,2Ng]. Then, we transmit every two groups through two transmit-antennas using Alamouti scheme [2] after encod- ing the symbol blocks sn with the K?K LCF encoding matrix ?. The I/O relationship 44 for each group is: 2 66 66 64 yn(0) ... yn(K ?1) 3 77 77 75 = 2 66 66 64 jH(0)j ... jH(K ?1)j 3 77 77 75?sn + ?w = HSTFsn + ?w. (4.8) where ?w is the equivalent white Gaussian noise vector, and jH(p)j2 = NrX ?=1 NtX ?=1 jH(?,?)(p)j2 = NrX ?=1 NtX ?=1 flfl flfl fl LX l=0 h(?,?)l e?j2? p lK flfl flfl fl 2 . (4.9) Based on this system model in (4.8), we apply the ML detection or SD method to get the estimation of information symbols ?sn. According to [11], when the group length K is greater than or equal to L + 1, these optimal and near optimal detectors exploit the full diversity NrNt(L+1). Given the model in (4.8), we can see that the ZF equalizer for the STF design exits with probability one. Since (4.8) has the same form as (2.2), we can get the error probability as in (2.7), where Cii now is the (i,i)th entry of the matrix C = (HHSTFHSTF)?1. Similarly, we can bound Cii as: 1 K 1 jH(c)j2 ? Cii = 1 K K?1X k=0 1 jH(k)j2 ? 1 min 0?k?K?1 jH(k)j2, (4.10) where c is a constant in [0,K?1]. Since jH(p)j2 is the summation of NrNt independent Chi-square random variable with degrees of freedom 2 as shown in (4.9), according to [15], jH(p)j2 still performs like a Chi-square random variable with degrees of freedom 45 2NrNt. Following the proof of Proposition 3, we can bound the outage probability as: (NrNt)NrNt?1 ?(NrNt) 2 2 w th Kjeij2 ?NrNt ? P( < th) ? cu 2 2 w th jeij2 ?NrNt (4.11) So, the diversity order that the ZF equalizer can exploit for STF design is NrNt. To show that the diversity order collected by LR-aided ZF equalizer for STF design is NrNt(L + 1), we need to show for the lattice spanned by HSTF, Pfjhminj2 ? ?g ? ch?NrNt(L+1), where hmin is the vector with minimum non-zero norm of all the vectors in the lattice. In other words we need to make sure the three conditions in Corollary 1 are satisfled. Obviously, all the entries in HSTF are complex Gaussian distributed with zero mean. From (4.8), we can see that the kth column of the equivalent channel matrixHSTF of the system is hk = diag[jH(0)j,...,jH(K ?1)j] k,k 2 [1,K], the square norm of which is a Chi-square random variable with degrees of freedom 2NrNt(L+1), where k is the kth column of ?. Further, because of the linear independence of LCF encoding matrix ?, all the columns of the equivalent channel matrix HSTF are linear independent with each other. So according to Corollary 1, we have Pfjhminj ? ?g ? ch?2NrNt(L+1). Thus, following the proof of Proposition 3, we can get that the diversity order of LR-aided ZF equalizer for STF design is NrNt(L+1). The results for STF design are summarized in the following proposition: Proposition 8 Consider an STF-OFDM system with Nt transmit-antennas and Nr receive-antennas, and the frequency-selective channel order of L. Given the model in (4.8), if the channel taps are independently complex Gaussian distributed with zero mean, then ZF equalizer in (2.3) exists wp1 and exploits diversity order NrNt. For STF design, 46 0 5 10 15 20 25 3010?7 10?6 10?5 10?4 10?3 10?2 10?1 100 SNR in dB BER ZF equalizerLR?aided ZF MMSE equalizerLR?aided MMSE SD method Figure 4.2: Comparison among difierent equalizers for FDFR design an LR-aided ZF equalizer collects diversity order NrNt(L+1) which is the same as that obtained by ML detector. 4.3 Simulation Results Example 1 (Performance comparison of difierent equalizers for FDFR):Con- sider a multiantenna system with Nt = Nr = 2 and frequency-selective channel order L = 1. Five detectors are employed respectively on model (4.1): ZF, MMSE, LR-aided ZF, LR-aided MMSE detectors and sphere decoder (SD). QPSK modulation is used for modulation. The BER versus SNR performance is depicted in Figure 4.2. It shows that the linear detectors (ZF, MMSE) can only achieve diversity Nr ? Nt + 1 = 1. How- ever, the LR-aided linear detectors achieve maximum diversity NrNt(L + 1) = 8 with 47 0 5 10 15 20 2510?8 10?6 10?4 10?2 100 SNR in dB BER ZF equalizerLR?aided ZF SD method Figure 4.3: Comparison among difierent equalizers for STF design much lower complexity than the SD detector though there exists a gap between SD and LR-aided linear detectors. Example 2 (Performance comparison of difierent equalizers for STF):STF de- sign is simulated and 16-QAM is chosen as symbol modulation scheme. We use the chan- nel conflguration in previous example. ZF, LR-aided ZF and SD equalizers are applied to the system model in (4.8). Performance of difierent equalizers is plotted in Figure 4.3. Reading the slopes of the curves in Figure 4.3, we observe that the diversity orders for ZF equalizer is indeed NrNt = 4 while LR-aided ZF equalizer can achieve maximum diversity NrNt(L+ 1) = 8, the same as SD. Note that Figure 4.3 also shows that if the spatial diversity order (NtNr) is high, linear equalizers achieve similar performance as SD for a large SNR range. 48 Chapter 5 CONCLUDING REMARKS AND FUTURE RESEARCH DIRECTIONS In this thesis, we have discussed the performance in terms of diversity of linear detectors for LLP-OFDM systems, V-BLAST systems and two MIMO-OFDM designs. It shows that conventional linear equalizers can only collect diversity 1 for LLP-OFDM systems and Nr ?Nt+1 for V-BLAST systems though they have the lowest complexity. For MIMO-OFDM designs, it depends on the ST coding schemes. However, with slightly increased complexity, LR-aided linear equalizers achieve maximum diversity for LLP- OFDM, V-BLAST and MIMO-OFDM designs, which is the same as that collected by ML detector. The complexity of LR-aided linear equalizers is much lower than those of ML and near-ML detectors. Based on this thesis, future research directions are listed but not limited as follows: First, the performance analysis in terms of coding gain will be studied. Based on our simulation results, it has been shown that although LR-aided equalizers achieve the same diversity as ML does, there still exists a performance gap which is mainly due to coding gain loss. In this research thrust, we will flrst quantify the coding gain of LR- aided linear equalizers and then try to modify the equalizers to reduce the performance gap with ML. Furthermore, we will study the performance of coded linear systems with LR-aided decoding and compare the performance and complexity with other alternatives in the literature. Another future research direction is the study of the orthogonality deflciency of the equivalent channel matrix for wireless communications. As we know, for linear systems, 49 when the equivalent channel matrix is diagonal, the performance of ZF equalizer is the same as that of ML detector. However, in general the channel matrix Hequ is not diagonal, and thus linear equalizers have inferior performance. Orthogonality deflciency describes how ?diagonal? a matrix is. So the study of orthogonality deflciency provides a useful tool to quantify the diversity and coding gains of linear equalizers. Furthermore, how it will afiect the performance of linear equalizations may guide us to construct the coding schemes to reach full diversity and high coding gain when linear equalizers are adopted at the receiver. Hybrid equalizers will also be designed to trade-ofi the performance with complexity. 50 Bibliography [1] E. Agrell, T. Eriksson, A. Vardy and K. Zeger, ?Closest point search in lattices,? IEEE Trans. on Information Theory, vol. 48, no. 8, pp. 2201?2214, Aug. 2002. [2] S. M. Alamouti, ?A simple transmit diversity technique for wireless communica- tions,? IEEE Journal on Selected Areas in Communications, vol. 16, no. 8, pp. 1451?1458, Oct. 1998. [3] J. A. C. Bingham, ?Multicarrier modulation for data transmission: an idea whose time has come,? IEEE Communications Magazine, vol. 28, no. 5, pp. 5?14, May. 1990. [4] G. J. Foschini, ?Layered space-time architecture for wireless communication in a fading environment when using multiple antennas,? Bell Labs Technical Journal, vol. 1, no. 2, pp 41-59, Autumn 1996. [5] G. Ginis and J. M. Cio?, ?On the relationship between V-BLAST and the GDFE,? IEEE Communications Letters, vol. 5, pp. 364?366, Sept. 2001. [6] G. D. Golden, C. J. Foschini, R. A. Valenzuela and P. W. Wolniansky, ?Detection algorithm and initial laboratory results using V-BLAST space-time communication architecture,? Electronics Letters, vol. 35, no. 1, pp. 14?16, Jan. 1999. [7] B. Hassibi and H. Vikalo, ?On the sphere-decoding algorithm I. Expected complex- ity,? IEEE Trans. on Signal Processing, vol. 53, no. 8, pp. 2806?2818, Aug. 2005. [8] Y. Huan and G. W. Wornell, ?Lattice-reduction-aided detectors for MIMO com- munication systems,? Proc. of IEEE Global Telecommunications Conf., vol. 1, pp. 424?428, Nov. 17-21, 2002. [9] S. Kay, Fundamentals of statistical signal processing: Detection Theory, Vol. II, Prentice Hall, 1998. [10] A. K. Lenstra, H. W. Lenstra and L. Lov?asz, ?Factoring polynomials with rational coe?cients,? Math. Ann, vol. 261, pp. 515?534, 1982. [11] Z. Liu, Y. Xin and G. B. Giannakis, ?Space-time-frequency coded OFDM over frequency-selective fading channels,? IEEE Trans. on Signal Processing, vol. 50, no. 10, pp. 2465?2476, Oct. 2002. [12] X. Ma and G. B. Giannakis, ?Complex fleld coded MIMO systems: performance, rate, and tradeofis,? Wireless Communications and Mobile Computing, pp. 693-717, Nov. 2002. 51 [13] X. Ma and G. B. Giannakis, ?Full-diversity full-rate complex-fleld space-time cod- ing,? IEEE Trans. on Signal Processing, vol. 51, no. 11, pp. 2917-2930, Nov. 2003. [14] W. H. Mow, ?Universal lattice decoding: a review and some recent results,? Proc. of IEEE International Conf. on Communications, vol. 5, pp. 2842 - 2846, Jun. 20-24, 2004. [15] A. Papoulis and U. S. Pillai, Probability, random variables and stochastic processes, McGraw-Hill Science/Engineering/Math, 4th edition, 2001. [16] H. V. Poor and S. Verd u, ?Probability of error in MMSE multiuser detection,? IEEE Trans. on Information Theory, vol. 43, no. 3, pp. 858-871, May. 1997. [17] J. G. Proakis, ?Digital Communications,? McGraw-Hill, 4th edition, 2000. [18] V. Tarokh, N. Seshadri and A. R. Calderbank, ?Space-time codes for high data rate wireless communication: performance criterion and code construction,? IEEE Trans. on Information Theory, vol. 44, no. 2, pp. 744?765, Mar. 1998. [19] M. Taherzadeh, A. Mobasher and A. K. Khandani, ?Lattice-basis reduction achieves the precoding diversity in MIMO broadcast systems,? Proc. of the 39th Conf. on Information Sciences and Systems, Johns Hopkins Univ., MD, Mar. 15-18, 2005. [20] V. Tarokh, H. Jafarkhani and A. R. Calderbank, ?Space-time block coding for wireless communications: performance results,? IEEE Journal of Selected Areas, vol. 17, no. 3, pp. 451?460, Mar. 1999. [21] C. Tepedelenlioglu, ?Maximum multipath diversity with linear equalization in pre- coded OFDM systems,? IEEE Trans. on Information Theory, vol. 50, no. 1, pp. 232?235, Jan. 2004. [22] Z. Wang and G. B. Giannakis, ?Complex-fleld coding for OFDM over fading wireless channels,? IEEE Trans. on Information Theory, vol. 49, no. 3, pp. 707?720, Mar. 2003. [23] Z. Wang and G. B. Giannakis, ?A simple and general parameterization quantifying performance in fading channels,? IEEE Trans. on Communications, vol. 51, no. 8, pp. 1389-1398, Aug. 2003. [24] C. Windpassinger and R. F. H. Fischer, ?Low-complexity near-maximum-likelihood detection and precoding for MIMO systems using lattice reduction,? Proc. of Infor- mation Theory Workshop, pp. 345?348, Mar. 31-Apr. 4, 2003. [25] P. W. Wolniansky, G. J. Foschini, G. D. Golden and R. A. Valenzuela, ?V-BLAST: an architecture for realizing very high data rates over the rich-scattering wireless channel,? Proc. of International Symposium on Signals, Systems, and Electronics, pp. 295?300, Sept. 29-Oct. 2, 1998. 52 [26] D. Wubben, R. Bohnke, V. Kuhn and K.-D. Kammeyer, ?MMSE extension of V- BLAST based on sorted QR decomposition,? Proc. of IEEE 58th Vehicular Tech- nology Conference, vol. 1, pp. 508?512, Oct. 6-9, 2003. [27] D. Wubben, R. Bohnke, V. Kuhn and K.-D. Kammeyer, ?Near-maximum-likelihood detection of MIMO systems using MMSE-based lattice reduction,? Proc. of IEEE International Conf. on Communications, vol. 2, pp. 798?802, Jun. 20-24, 2004. [28] Y. Xin, Z. Liu, and G. B. Giannakis, ?High-rate layered space-time coding based on constellation precoding,? Proc. of Wireless Communications and Networking Conf., vol. 1, pp. 471-476, Orlando, FL, Mar. 17-21, 2002. [29] Y. Xin, Z. Wang and G. B. Giannakis, ?Space-time diversity systems based on linear constellation precoding,? IEEE Trans. on Wireless Communications, vol. 2, no. 2, pp. 294-309, Mar. 2003. [30] W. Zhang and X. Ma, ?Performance analysis for V-BLAST systems with linear equalization,? Proc. of 39th Conf. on Information Sciences and Systems, Johns Hopkins Univ., MD, Mar. 15-18, 2005. 53 APPENDICES 54 APPENDIX A: Proof of Lemma 1 Suppose the joint probability density function (pdf) of Xn?s is f(x1,x2,...,xN). The cumulative density function (cdf) of Xmin is: F(v) = P(xmin < v) = 1?P(xmin ? v) = 1? Z 1 v dx1 Z 1 v dx2 ??? Z 1 v f(x1,x2,...,xN)dxN. (1) Then, we can obtain the pdf of Xmin by taking the derivative of the cdf: f(v) = ddvF(v) = ? Z 1 v dx1 ddv Z 1 v dx2 ??? Z 1 v f(x1,x2,...,xN)dxN ? + Z 1 v dx2 ??? Z 1 v f(v,x2,...,xN)dxN = NX n=1 Z 1 v dx1 ??? Z 1 v dxn?1 Z 1 v dxn+1 ??? Z 1 v f(x1,??? ,xn?1,v,xn+1 ...,xN)dxN ? NX n=1 fXn(v), (2) where fXn(x) is the pdf of Xn. According to [9, p. 25], we know that for a central Chi-square random variable Xn with degrees of freedom 2M, we have P(xn < ?) = 1?e??/2 M?1X k=0 ?? 2 ?k k! = e ??/2 1X k=M ?? 2 ?k k! ? ?? 2 ?M = cM?M, 55 where cM := 2?M is a constant only dependent on M. With this inequality, we can obtain: P(xmin < ?) = Z ? 0 f(v)dv ? Z ? 0 NX n=1 fXn(v)dv ? NX n=1 cM?M = cu?M, (3) where cu := NcM. Thus, Lemma 1 is proved. We notice that, Lemma 1 can be general- ized to Xn?s with other pdfs. ? 56 APPENDIX B: Complex LLL algorithm Here, we give the details of complex LLL algorithm in conventional Matlab nota- tion in the following table. INPUT: H OUTPUT: Q, R, T (1) [Q,R] = QR Decomposition(H); (2) ? = 0.75; (3) m = size(H,2); (4) T = Im; (5) k = 2; (6) while k ? m (7) for n = k ?1 : ?1 : 1 (8) u = round((R(n,k)/R(n,n))); (9) if u ?= 0 (10) R(1 : n,k) = R(1 : n,k)?uR(1 : n,n); (11) T(:,k) = T(:,k)?uT(:,n); (12) end (13) end (14) if ?(R(k ?1,k ?1)2) > kR(k ?1,k)?Q(:,k ?1) +R(k,k)?Q(:,k)k2 (15) Swap the (k-1) th and k th columns in R and T (16) ? = ?fi? fl ?fl fi ? where fi = R(k?1,k?1)kR(k?1:k,k?1)k; fl = R(k,k?1)kR(k?1:k,k?1)k; (17) R(k ?1 : k,k ?1 : m) = ?R(k ?1 : k,k ?1 : m); (18) Q(:,k ?1 : k) = Q(:,k ?1 : k)?H; (19) k = max(k ?1,2); (20) else (21) k = k +2; (22) end (23) end Table 1: The complex LLL algorithm 57 APPENDIX C: Proof of Lemma 3 Let x be a vector in the lattice L. Since L is spanned by the columns of H, then x can be expressed as Ha, where a is an N ?1 column vector with all entries belonging to Gaussian integer ring. So based on the deflnition of hmin, we can obtain: hmin = arg minx 2L, x6=0jxj 2 = HaH, (4) where aH 2 Z[p?1]N?1. By deflning an MN ?1 vector h = [hT1 ,...,hTN]T, we have: jhminj2 = jHaHj2 = hH(IM ??(aTH)HaTH?)h = hHAHh, (5) where AH = IM ? ?(aTH)HaTH?. Suppose that the correlation matrix of the channel vector is E[hhH] = Rh. The singular-value decomposition (SVD) of Rh is Uh?hUHh where Uh is a unitary matrix and ?h is a diagonal matrix with all singular values. Suppose rank(Rh) = Rh and deflne an Rh ?1 vector ?h with i.i.d. entries. Then h and Uh? 1 2 h?h have identical distribution and thus the same statistical properties. Similar to pairwise error probability (PEP) analysis in [18] and [22], we can get an upper bound for the probability that jhminj is less than ? by averaging (5) with respect to the random basis H: P(jhminj2 ? ?) = P(?hH? 1 2 hU H h AHUh? 1 2 h?h ? ?) ? ch? D, (6) 58 where D = min 8aH rank(RhAH). Since H are complex Gaussian distributed, the set of possible aH can be the whole Gaussian integer ring. Thus, we can represent D as D = min 8p6=0 rank(E(pp H)). (7) ? 59 APPENDIX D: Proof of Proposition 4 In (3.7), we have deflned that C = (HHH)?1. By properly permutating H to [hi,Hi], where hi is the ith column of H and Hi denotes the rest columns, we obtain that C = (HHH)?1 = P 2 64 hHi hi hHi Hi HHi hi HHi Hi 3 75 ?1 PT, where P is a permutation matrix such that HP = [hi Hi]. Based on the matrix inversion lemma, we know that the (i,i)th element of C is Cii = ? hHi hi ?hHi Hi?HHi Hi??1HHi hi ??1 . (8) Suppose the singular value decomposition (SVD) of Hi is Hi = VDUH, where V is an Nr?(Nt?1) unitary matrix, D is an (Nt?1)?(Nt?1) diagonal matrix and U is an (Nt ?1)?(Nt ?1) unitary matrix. Plugging this SVD result into (8), we are ready to verify that: Hi(HHi Hi)?1HHi = VV H. It is straightforward to see that the rank of VV H is Nt ?1. More speciflcally, VV H is an Nr ?Nr matrix whose eigenvalue decomposition can be written as: VV H = ?V 2 64 INt?1 0Nt?1,Nr?Nt+1 0Nr?Nt+1,Nt?1 0Nr?Nt+1,Nr?Nt+1 3 75 ?V H, 60 where ?V is an Nr ?Nr unitary matrix with the flrst Nt ? 1 columns same as V . This is because the matrix VV H has the same non-zero eigenvalues as V HV . Therefore, we can verify C?1ii = hHi (INr ?VV H)hi = hHi ?V 2 64 0Nt?1 0Nt?1,Nr?Nt+1 0Nr?Nt+1,Nt?1 INr?Nt+1,Nr?Nt+1 3 75 ?V Hh i. It can be seen that the number of degrees of freedom in C?1ii is 2(Nr ? Nt + 1). Fur- thermore, C?1ii is a chi-squared random variable with 2(Nr ?Nt +1) degrees of freedom, because the channel coe?cients are complex Gaussian distributed. As shown in [22], if we integrate the right side of (2.7) with respect to this random variable, we obtain that the diversity order is equal to Nr ? Nt + 1. This means the diversity order of the ZF detection is Nr ?Nt + 1. ? 61