CHANNEL ESTIMATION AND EQUALIZATION FOR DOUBLY-SELECTIVE CHANNELS USING BASIS EXPANSION MODELS Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classified information. Liying Song Certificate of Approval: Stanley J. Reeves Professor Electrical and Computer Engineering Jitendra K. Tugnait, Chair James B. Davis Professor Electrical and Computer Engineering Shiwen Mao Assistant Professor Electrical and Computer Engineering Joe F. Pittman Interim Dean Graduate School CHANNEL ESTIMATION AND EQUALIZATION FOR DOUBLY-SELECTIVE CHANNELS USING BASIS EXPANSION MODELS Liying Song A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 10, 2008 CHANNEL ESTIMATION AND EQUALIZATION FOR DOUBLY-SELECTIVE CHANNELS USING BASIS EXPANSION MODELS Liying Song Permission is granted to Auburn University to make copies of this dissertation 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 Liying Song, daughter of Zhoutian Song and Shuqin Qian, was born in Daqing, Heilongjiang Province, China, on May 25, 1980. She received her B. E. and M. S. degree in Electrical Engineer- ing from University of Electronics Science and Technology of China in 2001 and 2004, respectively. Since August 2004 she has been a Ph. D student in Electrical and Computer Engineering Depart- ment of Auburn University. Her research interests are in wireless communications and signal processing, including channel estimation and equalization for time- and frequency-selective channels, OFDM for wireless com- munications, and MIMO technique. iv DISSERTATION ABSTRACT CHANNEL ESTIMATION AND EQUALIZATION FOR DOUBLY-SELECTIVE CHANNELS USING BASIS EXPANSION MODELS Liying Song Doctor of Philosophy, May 10, 2008 (M. S., Univ. of Electronics Sci. and Tech. of China, 2001) (B. E., Univ. of Electronics Sci. and Tech. of China, 2004) 166 Typed Pages Directed by Jitendra K. Tugnait The nature of the wireless channels places fundamental limitations on the performance of wire- less communication systems. In addition to the frequency-selectivity characteristics caused by mul- tipath propagation, the high-rate wireless and mobile links often exhibit time-selectivity charac- teristics caused by the user?s mobility, so-called doubly-selective wireless channels. The quality of channel acquisition has a major impact on the overall system performance. Therefore, reliable estimation of doubly-selective channels is well motivated. Equalization is used at the receiver to compensate for intersymbol interference created by multipath propagation and improve received signal quality. Equalizers should be adaptive since the channel is time-varying. In this dissertation, channel estimation and equalization for doubly-selective channels are con- sidered in Chapter 2 (under single input single output models) and Chapter 3 (under multiple input multiple output models), where the time-varying channel is assumed to be well described by basis expansion models (BEM). Our focus is on time-multiplexed training for channel estimation where the training symbols are periodically inserted and use all transmitted power during their transmis- sion. v The linear equalization and decision feedback equalization (DFE) of doubly-selective channels modeled via BEMs are introduced in Chapter 4. There has been much interest in designing time- variant serial finite impulse response (FIR) linear and DFE equalizers using complex exponential (CE-) BEMs for equalizers in addition to using CE-BEM for modeling the channel itself. In this dissertation we show that the Kalman filter formulation of the linear equalizer and an alternative formulation of the FIR DFE based on a CE-BEM channel model yields the same or an improved BER at a lower computational cost, without incurring the approximation error inherent in CE-BEM modeling of equalizers. In Chapter 5, an adaptive channel estimation scheme, exploiting the oversampled complex exponential basis expansion model (CE-BEM), is presented for doubly-selective channels where we track the BEM coefficients via a multiple model approach in this dissertation. We propose to use a multiple model framework where several candidate Doppler spread values are used to cover the range from zero to an upper bound, which leads to multiple CE-BEM channel models, each corresponding to an assumed value of the Doppler spread. Subsequently, the well known interacting multiple model (IMM) algorithm is used for symbol detection based on multiple state-space models corresponding to the multiple estimated channels. Orthogonal Frequency-Division Multiplexing (OFDM), a digital multi-carrier modulation scheme, has developed into a popular scheme for wideband wireless communication due to its high spec- tral efficiency and simple equalization. We extend the optimum time-multiplexed training based channel estimation introduced in Chapter 2 to OFDM systems under doubly-selective channels in Chapter 6. Compared to the traditional frequency-domain training design, the main advantages of time-domain training for OFDM system is that the information symbols are not contaminated by the training symbols as in the frequency-domain training case. vi ACKNOWLEDGMENTS It has been a great pleasure working with the faculty, staff, and students at the Electrical and Computer Engineering Department, Auburn University, during my tenure as a doctoral student. Completing this work is definitely a high point in my academic career. I could not have come this far without the assistance of many individuals and I want to express my deepest appreciation to them. My first and most earnest thanks go to my advisor, Dr. Jitendra K. Tugnait for his support, guidance, and kindness. In every sense, none of this work would have been possible without him. I would like to sincerely thank my committee members Dr. Stanley J. Reeves and Dr. Shiwen Mao who have given their time to read this manuscript and offered valuable advice during my graduate studies. Many thanks to Dr. Douglas A. Leonard who served as my outside reader for providing valuable comments that improved the contents of this dissertation. I gratefully acknowledge Dr. Xiaoli Ma who gave me the chance to start my PhD journey at Auburn University. I also wish to thank my colleagues and friends whose encouragement over the years has been invaluable. My final, and most heartfelt, acknowledgment must go to my parents. They have raised me and have been giving their love and support all the time. I would end this list of acknowledgments not with a ?thank you? but with a warm memory. vii Style manual or journal used Journal of Approximation Theory (together with the style known as ?aums?). Bibliography follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (specifically LATEX) together with the departmental style-file aums.sty. viii TABLE OF CONTENTS LIST OF FIGURES xii LIST OF TABLES xv 1 INTRODUCTION 1 1.1 Characteristics and Representations of Wireless Communication Channels . . . . . 1 1.1.1 Jakes? Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Complex Exponential Basis Expansion Model (CE-BEM) . . . . . . . . . 5 1.1.3 Discrete Prolate Spheroidal Basis Expansion Model (DPS-BEM) . . . . . . 7 1.1.4 Modeling Error Comparison between CE-BEM and DPS-BEM . . . . . . 9 1.2 Channel Estimation and Equalization Approaches . . . . . . . . . . . . . . . . . . 11 1.2.1 Channel Estimation Approaches . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Equalization Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Optimal Maximum Likelihood Detector (Viterbi Decoder) . . . . . . . . . . . . . 14 1.4 Orthogonal Frequency Division Multiplexing (OFDM) . . . . . . . . . . . . . . . 17 1.5 Outline and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 SISO DOUBLY-SELECTIVE CHANNEL ESTIMATION USING DISCRETE PROLATE SPHEROIDAL BASIS EXPANSION MODELS AND TIME-MULTIPLEXED TRAINING 22 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Channel Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.1 Least-squares Channel Estimation . . . . . . . . . . . . . . . . . . . . . . 29 2.3.2 Linear Minimum Mean-Square-Error Channel Estimation . . . . . . . . . 30 2.3.3 Channel Estimation Error . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4 Optimum Training Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5 Training Power Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.6 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.6.1 Example 1: Approximation Errors . . . . . . . . . . . . . . . . . . . . . 41 2.6.2 Example 2: DPS-BEM Channel Estimation Performance . . . . . . . . . . 44 2.6.3 Example 3: CE-BEM versus DPS-BEM . . . . . . . . . . . . . . . . . . . 46 2.6.4 Example 4. Training Power Allocation . . . . . . . . . . . . . . . . . . . 47 2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 ix 3 MIMO DOUBLY-SELECTIVE CHANNEL ESTIMATION USING DISCRETE PROLATE SPHEROIDAL BASIS EXPANSION MODELS AND TIME-MULTIPLEXED TRAINING 50 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2 Multiuser MIMO Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Channel Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3.1 Linear Least-Squares Channel Estimator . . . . . . . . . . . . . . . . . . . 55 3.3.2 Linear MMSE Channel Estimator . . . . . . . . . . . . . . . . . . . . . . 56 3.3.3 Channel Estimation Error . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 Optimum Training Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Training Power Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.6 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.6.1 Example 1: Approximation Errors . . . . . . . . . . . . . . . . . . . . . . 70 3.6.2 Example 2: Channel Estimation Performance . . . . . . . . . . . . . . . . 71 3.6.3 Example 3: CE-BEM versus DPS-BEM . . . . . . . . . . . . . . . . . . . 74 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4 TIME-VARYING EQUALIZATION FOR DOUBLY-SELECTIVE CHANNELS 76 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 Linear Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.2 Existing Linear Time-Varying MMSE Equalizers . . . . . . . . . . . . . . 80 4.2.3 Kalman Filter with Equalization Delay d . . . . . . . . . . . . . . . . . . 83 4.2.4 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3 Decision Feedback Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.3.2 Time-Varying FIR MMSE DFEs . . . . . . . . . . . . . . . . . . . . . . . 94 4.3.3 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5 A MULTIPLE MODEL APPROACH TO DOUBLY-SELECTIVE CHANNEL ESTIMATION US- ING EXPONENTIAL BASIS MODELS 104 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.2 System Model and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.2.2 Block-Adaptive Channel Estimation [48] . . . . . . . . . . . . . . . . . . 107 5.2.3 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.3 Multiple Model Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.3.1 Multiple Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.3.2 Interacting Multiple Model Data Detection . . . . . . . . . . . . . . . . . 110 5.4 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.4.1 Example 1: IMM with Three Models . . . . . . . . . . . . . . . . . . . . 113 5.4.2 Example 2: IMM with Two Models . . . . . . . . . . . . . . . . . . . . . 115 x 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6 DOUBLY-SELECTIVE CHANNEL ESTIMATION FOR OFDM SYSTEMS USING DPS-BEM AND TIME-MULTIPLEXED TRAINING 123 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.3 Doubly-Selective Channel Estimation for OFDM Systems Using Frequency- Domain Training [62] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.4 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.4.1 Example 1: Channel Estimation Performance . . . . . . . . . . . . . . . . 129 6.4.2 Example 2: CE-BEM versus DPS-BEM . . . . . . . . . . . . . . . . . . . 130 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7 SUMMARY AND FUTURE WORK 133 7.1 Summary of Original Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.2 Possible Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 BIBLIOGRAPHY 138 A ASYMPTOTIC DPS-BEM/ SLEPIAN SEQUENCES 145 B MATHEMATICAL NOTATIONS 147 C ABBREVIATIONS 149 xi LIST OF FIGURES 1.1 Basis expansion modeling error comparison between CE-BEM and DPS-BEM models 9 1.2 Subchannels are 312 kHz wide in 802.11a and HyperLAN II . . . . . . . . . . . . 18 1.3 An OFDM transceiver diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1 Channel estimation errors (with and without modeling errors):Numerical results de- rived from QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1, SNR=20dB . . . . 41 2.2 MSE lower bound comparison between LS (2:44) and MMSE (2:45) estimators . . 42 2.3 Comparison between the LS channel estimation MSE lower bound in (2:44) and simulation results in (2:65), QS = d2?DmaxNe+1 . . . . . . . . . . . . . . . . . 42 2.4 Comparison between the MMSE channel estimation MSE lower bound in (2:45) and simulation results in (2:65), QS = d2?DmaxNe+1 . . . . . . . . . . . . . . . 43 2.5 LS channel estimation MSE with varying maximum normalized Doppler band- width, QS = d2?DmaxNe+1,QF = 2d?DmaxNe+1 . . . . . . . . . . . . . . . . 44 2.6 BER with varying maximum normalized Doppler bandwidth using BPSK modula- tion, QS = d2?DmaxNe+1,QF = 2d?DmaxNe+1 . . . . . . . . . . . . . . . . 45 2.7 BER with varying maximum normalized Doppler bandwidth using QPSK modula- tion, QS = d2?DmaxNe+1,QF = 2d?DmaxNe+1 . . . . . . . . . . . . . . . . 46 2.8 Simulations-based BER versus fl for SNR=15dB . . . . . . . . . . . . . . . . . . 47 2.9 Theoretical flopt (2:64) versus received signal SNR . . . . . . . . . . . . . . . . . 48 3.1 Channel estimation errors (with and without modeling errors): numerical results derived from QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1, SNR=25dB . . 67 3.2 MSE lower bound comparison between LS (3.37) and MMSE (3.38) estimators . . 68 3.3 Comparison between channel estimation MSEs lower bound in (3.37) and simula- tion results (3.58) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 xii 3.4 Comparison between channel estimation MSEs lower bound in (3.38) and simula- tion results (3.58) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.5 Channel estimation MSE with varying maximum normalized Doppler bandwidth, QF = 2d?DmaxNe and QS = d2?DmaxNe . . . . . . . . . . . . . . . . . . . . . 70 3.6 Channel estimation MSE with varying maximum normalized Doppler bandwidth, QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 . . . . . . . . . . . . . . . . . 71 3.7 BER with varying maximum normalized Doppler bandwidth for BPSK modulation, QF = 2d?DmaxNe and QS = d2?DmaxNe . . . . . . . . . . . . . . . . . . . . . 72 3.8 BER with varying maximum normalized Doppler bandwidth for QPSK modulation, QF = 2d?DmaxNe and QS = d2?DmaxNe . . . . . . . . . . . . . . . . . . . . . 73 3.9 BER with varying maximum normalized Doppler bandwidth for BPSK modulation, QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 . . . . . . . . . . . . . . . . . 73 3.10 BER with varying maximum normalized Doppler bandwidth for QPSK modulation, QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 . . . . . . . . . . . . . . . . . 74 4.1 BER performance versus SNR using BPSK modulation, averaged over 10,000 runs. BLM denotes the method of [5]; FRESH-OPT and FRESH-SUBOPT are methods of [68]. N = 50, P = 100, Q = 4, L = 3, d = 5, Q0 = 18, L0 = 6 . . . . . . . . . 88 4.2 BER performance versus SNR using QPSK modulation, averaged over 10,000 runs 89 4.3 BER performance versus SNR using BPSK modulation, averaged over 1,000 runs. BLM denotes the method of [5]; FRESH-OPT and FRESH-SUBOPT are methods of [68]. Kalman filter is based on P = 800 when Q = 4 and on P = 1600 when Q = 8. P = N corresponds to critically sampled CE-BEM and P = 2N corresponds to oversampled CE-BEM. N = 800, P = 800 or 1600, Q = 4 or Q = 8, L = 3, d = 10, Q0 = 12, L0 = 12 . . . . . . . . . . . . . . . . . . . . . . 90 4.4 BER performance versus SNR using QPSK modulation, averaged over 1,000 runs . 91 4.5 BER performance versus SNR For DPS-BEM and CE-BEM channel modeling us- ing Kalman filtering, BPSK modulation . . . . . . . . . . . . . . . . . . . . . . . 91 4.6 BER performance versus SNR For DPS-BEM and CE-BEM channel modeling us- ing Kalman filtering, QPSK modulation . . . . . . . . . . . . . . . . . . . . . . . 92 xiii 4.7 BER performance versus SNR, averaged over 1,000 runs, BPSK signal. N = 800, P = 1600, Q = 8, L = 3, d=5, Q0=12, lf=12, Q00 = 4, lb = 3. R denotes the number of receive antennas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.8 BER performance versus SNR, averaged over 1,000 runs, BPSK signal. N = 800, P = 1600, Q = 8, L = 3, d=5, Q0=12, lf=12, Q00 = 4, lb = 3. R denotes the number of receive antennas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.1 IMM with three models, BER vs SNR with BPSK information symbols. . . . . . . 113 5.2 IMM with three models, BER vs SNR with QPSK information symbols. . . . . . . 114 5.3 IMM with two models. BER vs SNR with BPSK information symbols. Step shape time-varying Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.4 IMM with two models. BER vs SNR with QPSK information symbols. Step shape time-varying Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.5 Average mode probability of IMM. Step shape time-varying channel. SNR=20dB . 119 5.6 IMM with two models. BER vs SNR with BPSK information symbols. Linear Shape Time-Varying Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.7 IMM with two models. BER vs SNR with QPSK information symbols. Linear Shape Time-Varying Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.8 Average mode probability of IMM. Linear shape time-varying channel. SNR=20dB 120 5.9 Average mode probability of IMM. Time-invariant channel. With training insertion. SNR=20dB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.10 Average mode probability of IMM. Time-invariant channel. Without training inser- tion. SNR=20dB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.1 OFDM transceiver block diagram in [62] . . . . . . . . . . . . . . . . . . . . . . . 123 6.2 Proposed OFDM transceiver block diagram . . . . . . . . . . . . . . . . . . . . . 124 6.3 LS Channel estimation MSE comparison between TDE and FDE with varying ?Dmax129 6.4 LS Channel estimation MSE comparison between DPS-BEM and CE-BEM with varying ?Dmax, TDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.5 BER comparison between DPS-BEM and CE-BEM with varying ?Dmax, TDE . . 131 xiv LIST OF TABLES 4.1 Operation summary for Kalman filter . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.2 Computation complexity; N = 50, P = 2N = 100 . . . . . . . . . . . . . . . . . 87 4.3 Computation complexity; N = 800, P = 2N = 1600 . . . . . . . . . . . . . . . . 88 4.4 Computation complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.1 Summary of the IMM algorithm (one cycle) . . . . . . . . . . . . . . . . . . . . . 111 xv CHAPTER 1 INTRODUCTION The doubly-selective channel estimation and equalization algorithms described in this disser- tation involve some background material in the wireless communication area. We will first briefly introduce these topics in this chapter. Starting with the characteristics and representations of wireless channels, two basis expansion models (BEM) used in this dissertation are introduced and compared. The pros and cons of different channel estimation and equalization approaches are then discussed. The fundamentals of the Viterbi decoder, a commonly used information detector in this dissertation, and the principles of Orthogonal Frequency-Division Multiplexing (OFDM) technology are also introduced. 1.1 Characteristics and Representations of Wireless Communication Channels In wireless telecommunications, multipath is the propagation phenomenon that results in radio signals? reaching the receiving antenna by two or more paths. Causes of multipath include atmo- spheric ducting, ionospheric reflection and refraction, and reflection from terrestrial objects, such as mountains and buildings. The effects of multipath include constructive and destructive interference, and phase shifting of the signal. This causes Rayleigh fading, named after Lord Rayleigh. Rayleigh fading is a statistical model for the effect of a propagation environment on a radio signal, such as that used by wireless devices. It assumes that the power of a signal that has passed through such a transmission medium (also called a communication channel) will vary randomly, or fade, according to a Rayleigh distri- bution - the radial component of the sum of two uncorrelated Gaussian random variables. Rayleigh 1 fading is used to refer to the rapid fluctuations of the received signal in both dimensions ? time and frequency. If we assume that fading is caused by the superposition of a large number of independent scattered components, then the in-phase and quadrature components of the received signal can be assumed to be independent zero-mean Gaussian processes. The envelope A of the received signal has a Rayleigh probability density function (pdf) given by fA (a) := 8> < >: a 2 exp ? ? a22 2 ? a ? 0; 0 a < 0 (1.1) with 2 being the time-average power of the received signal before envelope detection. The phase of the received signal is uniformly distributed with pdf f? ( ) := 12?; 2 [0;2?): (1.2) The autocorrelation function of the received signal for two-dimensional isotropic scattering and an omnidirectional receiving antenna is given by [17] RA(?) = 2 cos(!c?)J0(!m?) (1.3) where !c is the carrier radian frequency, J0(?) is the zero-order Bessel function of the first kind and !m is the maximum Doppler radian frequency spread. The autocorrelation function of the Rayleigh fading channels is periodic in lag and its envelope decays slowly after the initial zero-crossing. In a multipath propagation environment, several delayed and scaled versions of the transmitted signal arrive at the receiver. The span of path delays is called delay spread. Delay spread causes frequency-selective fading as the channel acts like a tapped delay line filter. Time-selective fading 2 due to scatter or transmitter/receiver motion results in a Doppler spread, i.e., a pure tone spreads over a finite spectral bandwidth. The frequency- and time- selective Rayleigh fading channel is the channel model we consider in this proposal. 1.1.1 Jakes? Model As described above, a Rayleigh fading channel itself can be modeled by generating the real and imaginary parts of a complex number according to independent normal Gaussian variables. Any model simulating the Rayleigh fading channel has to exhibit the statistical behaviors given in (1.1) - (1.3). In [34], Jakes popularized a time-varying model for Rayleigh fading based on summing sinu- soids. The model supposes the received signal g(t) at time t is g(t) = E0 LX l=1 Cl cos(!ct+!mtcosAl +'l) (1.4) where E0 is the amplitude of the transmitted cosine wave, Cl is a random variable representing the attenuation of the l-th path, Al is a random variable representing the angle of arrival of the l-th ray with respect to the direction of motion of the receiver, 'l is a random variable representing the phase shift undergone by the l-th ray. Note that the stochastic signal g(t) representing the flat fading signal can be characterized by L sets of triples (Cl;Al;'l). The random variables Cl, Al, and 'l are assumed statistically independent. 3 To reduce the complexity, the simplified Jakes? model selects: Cl = 1pL; (1:5a) Al = 2?lL ; (1:5b) 'l = 0; (1:5c) where l = 1;2;:::;L. Furthermore, L is of the form L = 4M +2 where M is a positive integer. However, the simplifying relationships forced in (1.5) make this simulation model determinis- tic and wide-sense nonstationary [53]. Various modifications of Jakes? model have been proposed, which we call the family of Jakes? simulators. Among the Jakes? simulator family, [81] is worthy of mention since it generates a wide-sense stationary process and its second-order correlation statis- tics match desired reference model (1.4) exactly. Following [81], the normalized low-pass fading process of the statistical sum-of-sinusoids simulation model is defined by X (t) = Xc (t)+jXs (t); (1:6a) Xc (t) = 2pM MX l=1 cos(#l)cos(!mtcosfil +`); (1:6b) Xs (t) = 2pM MX l=1 sin(#l)cos(!mtcosfil +`) (1:6c) with fil = 2?l?? + 4M ; l = 1;2;:::;M where fil, `l, and #l are statistically independent and uniformly distributed over [??;?) for all l. As M !1, the envelope jXj is Rayleigh distributed and the phase ?X (t) is uniformly distributed 4 over [??;?), for which the pdf?s are given by fjXj(x) = xexp ?x 2 2 ? ; x ? 0; f?X ( ) = 12?; 2 [??;?): A minor defect, however, occurs in model (1:6a) when !m = 0 or the Doppler spread is small: A Rayleigh distribution cannot be guaranteed [77]. This problem can be easily resolved by replacing a common phase ` by `l, which is also uniformly distributed over [??;?) for all l. The simulation model is revised as [77]: X (t) = Xc (t)+jXs (t); (1:7a) Xc (t) = 2pM MX l=1 cos(#l)cos(!mtcosfil +`l); (1:7b) Xs (t) = 2pM MX l=1 sin(#l)cos(!mtcosfil +`l): (1:7c) 1.1.2 Complex Exponential Basis Expansion Model (CE-BEM) Statistical modeling of the channel is well motivated when time-varying path delays arise due to a large number of scatterers. Deterministic basis expansion models have gained popularity for wireless applications, especially when the multipath is caused by a few strong reflectors and path delays exhibit variations due to the mobiles [26]. The time-varying taps are expressed as a super- position of time-varying bases (complex exponentials when modeling Doppler effects) with time invariant coefficients. By assigning time variations to the bases, rapidly fading channels with coher- ence time as small as a few tens of symbols can be captured. 5 Consider a time-varying channel with impulse response h(t;?) (response at time t to an unit impulse at time t??) which includes transmit-receive filters as well as doubly-selective propagation effects. Let s(t) denote the complex baseband, continuous-time input signal (with symbol duration Ts), and x(t) denote the complex baseband, continuous-time received signal. The noise-free re- ceived signal x(t) is the convolution of s(t) and h(t;?) [41]: x(t) = Z 1 0 h(t;?)s(t??)d?: (1:8) Let H(f;?) = R1?1h(t;?)e?j2?ftdt be the Fourier transform of h(t;?); H(f;?) is the delay- Doppler spreading function of the channel. If jH(f;?)j ? 0 for j?j > ?d, then ?d is called the (multipath) delay-spread of the channel; if jH(f;?)j ? 0 for jfj > fd, the fd is called the Doppler spread of the channel [13]. If s(t); x(t) and h(t;?) in (1:8) are sampled at symbol rate, then by [41], for t = nTs 2 [t0;t0 +NTs), the sampled signal x(n) := x(t)jt=nTs has the representation x(n) = LX l=0 h(n;l)s(n?l) (1:9) where Ts is the symbol duration. Over the block interval of [t0;t0 + NTs), the channel impulse response h(n;l) can be represented using QF + 1 coefficients fwq(l)gQFq=0, which remain invariant during this block but are allowed to change for the next block, and QF + 1 Fourier basis functions that are used to describe the temporal variation of the channel and are common for each block. Then for the block of [t0;t0+NTs), the discrete-time baseband equivalent channel model based on complex exponential basis expansion can be described as [13, 41]: h(n;l) = QFX q=0 wq(l)ej!qn; (1:10) 6 where !q := 2?T (q ? QF2 ); q = 0;1;:::;QF; (1:11a) L := b?d=Tsc; (1:11b) QF ? 2dfdNTse: (1:11c) There are two slightly different CE-BEMs involved in this dissertation. One is referred to as the critically-sampled CE-BEM because the BEM period equals the length of the observed window. The other uses a longer BEM period and is thus referred to as the oversampled CE-BEM. Section 4.2.1 provides the reader more details about oversampled CE-BEM. Note that the basis functions in critically-sampled CE-BEM are orthogonal, while in over-sampled CE-BEM they are not. 1.1.3 Discrete Prolate Spheroidal Basis Expansion Model (DPS-BEM) It has been known that the Fourier basis function based CE-BEM model has the major draw- back that the rectangular window associated with the discrete Fourier transform (DFT) introduces spectral leakage [44], which results in the floor in the bit error rate (BER) [3]. In [76, 77], the BEM coefficients are expanded by the orthogonal discrete prolate spheroidal (DPS) sequences resulting in a basis expansion model (DPS-BEM). The DPS sequences have a double orthogonality prop- erty: They are orthogonal over the finite set f0;:::;N ?1g and the infinite set f?1;:::;1g = Z simultaneously. This remarkable property enables parameter estimation without the drawbacks of windowing in the case of the Fourier basis expansion. Let Ts denote the symbol interval. For a channel with a multipath delay spread of ?d sec and a Doppler spread of fd Hz, ?Dmax := fdTs is the maximum normalized Doppler bandwidth. An ideal basis function should have at least two properties: It is band-limited to the normalized 7 frequency range [?fdTs;fdTs]; its energy is time-concentrated in a certain time interval [0;N ?1]. Thus, given the maximum normalized Doppler bandwidth fdTs and the window size N, we seek a sequence ?(n) to maximize ? = PN?1 n=0 j?(n)j 2 P1 m=?1j?(m)j2 (1:12) with the band-limited constraint ?(n) = Z fdTs ?fdTs ?(f)ej2?fndf (1:13) where ?(f) = 1X m=?1 ?(m)e?j2?fm: (1:14) The DPS sequences f?q(n)g give us the solution to the constrained maximization problem [58]. In DPS-BEM, the DPS vectors ?q := [?q(0);:::;?q(N ? 1)]T 2 RN (called Slepian sequences in [77], which are time-windowed DPS sequences) with elements ?q(n) for n 2 f0;:::;N ?1g, are eigenvectors of the matrix C 2RN?N, fulfilling [77] C?q = ?q?q; (1:15) where ?1 ? ?1 ????? ?N are eigenvalues of matrix C. The (y;z) entries in matrix C are defined as: [C]y;z = sin[2?(y ?z)?Dmax]?(y ?z) ; (1:16) 8 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 x 10?3 10?4 10?3 10?2 10?1 ?Dmax Channel Estiamtion MSE CE?BEM DPS?BEM Figure 1.1: Basis expansion modeling error comparison between CE-BEM and DPS-BEM models where y;z 2f0;:::;N ?1g. In this case one takes QS ?d2?DmaxNe [77, 58]. 1.1.4 Modeling Error Comparison between CE-BEM and DPS-BEM In the following, we use generic notations Q and ?q(n) to indicate that the expressions are applicable to both CE-BEM and DPS-BEM basis functions. In a basis expansion representation over a time-block n = f0;1;:::;N ?1g, it is assumed that [26] h(n;l) = QX q=0 wq(l)?q(n): (1:17) 9 However, the true channel may not be exactly equal to this basis expansion since modeling error always occurs, so that we have to revise (1:17) as h(n;l) = QX q=0 wq(l)?q(n)+eBEM(n;l); (1:18) where eBEM(n;l) is the basis expansion modeling error. By the orthogonality principle, eBEM(n;l) should be orthogonal to the given basis set f?q(n)gQq=0 when the square error PN?1n=0 je(n;l)j2 is minimized. Then N?1X n=0 h(n;l)??q0(n) = wq0(l) N?1X n=0 j?q0(n)j2: (1:19) Since the orthogonal basis functions of CE-BEM and DPS-BEM satisfy PN?1n=0 j?q0(n)j2 = 1, the BEM coefficient is derived as wq0(l) = N?1X n=0 h(n;l)??q0(n): (1:20) Based on (1:19) and (1:20), the least squares approximation of the channel is given by ^h(n;l) = QX q0=0 wq0(l)?q0(n): (1:21) Fig. 1.1 shows the modeling error comparison between CE-BEM and DPS-BEM models. In this example, an SISO doubly-selective Rayleigh fading channel defined in (1.7) that is based on the modified Jakes model is considered. Since the Jakes model is more realistic as a practical wireless channel, we are trying to approximate a 3-tap Jakes channel by two BEMs: CE-BEM and DPS- BEM. We choose a data record length of 400 symbols, Ts = 25?s, average over Mfi = 1000 realizations of randomly generated channels, and plot the channel estimation mean square error 10 (MSE), which is defined as: MSE := 1M fiN MfiX fi=1 N?1X n=0 LX l=0 khfi(n;l)?^hfi(n;l)k2: (1:22) In Fig 1.1, the basis function dimensions QF and QS change with the maximum Doppler bandwidth ?Dmax := fdTs, and SNR=20dB. From the results, we notice that the channel estimation MSE of DPS-BEM is usually several orders of magnitude lower than that of the CE-BEM. Clearly DPS- BEM is better than CE-BEM when approximating a band-limited time-varying channel. 1.2 Channel Estimation and Equalization Approaches 1.2.1 Channel Estimation Approaches For channel state information (CSI) acquisition, three classes of approaches are available: the training-based approach, the blind approach and the semi-blind approach. In the following, we briefly describe these three approaches. In conventional training-based approaches, training sequences (known to the receiver) are time- multiplexed with the information sequence [21, 32, 63, 79]. Training symbols can be placed either at the beginning of each burst (as a preamble) or regularly throughout the burst. In rapidly fading or quasi-static fading channels, preamble-based training may not work well. This motivates em- bedding training symbols in each transmitted block, instead of concentrating them at the preamble. More recently, a superimposed training approach has been explored where the training sequences are added (superimposed) at a low power to the information sequence at the transmitter before modulation and transmission [65]. There is no loss in information rate, but the channel estima- tion using superimposed training will be interfered with by information symbols. The conventional 11 time-multiplexed training approach is attractive especially when it decouples symbol detection from channel estimation and thus simplifies the receiver implementation and relaxes the required channel identifiability conditions [52]. Blind approaches have been proposed to mitigate the multipath effects in wireless commu- nications. Blind equalization algorithms are usually based on optimization procedures trying to minimize some nonlinear functional(s) of the received samples [66]. Compared with a training- based approach, a blind approach avoids training and thus makes an efficient use of the available bandwidth [66, 25]. But on the other hand, blind algorithms typically require longer data records and entail higher complexity [66]. Other major drawbacks of blind approaches are the slow conver- gence time of the equalizer and possible misconvergence which takes place when the convergence process reaches a local minimum of the functional to be minimized. For certain applications these disadvantages can be unacceptable. Semi-blind approaches use a combination of training and blind cost functions. A training sequence is used in a semi-blind approach. At the receiver, the channel estimation depends on both the known training sequence and the unknown information sequence. This way, in addition to the information carried by the training symbols, the unknown information sequence is also exploited to enhance the channel estimation performance. Using a semi-blind approach allows the length of the training sequence to be shortened compared to the traditional training-based approaches [27, 78]. Compared with training-based approaches and blind approaches, semi-blind approaches have a relative better bandwidth efficientcy than training-based approaches and converge faster than blind approaches. 12 1.2.2 Equalization Approaches With the emergence of next-generation wireless mobile communications, multimedia services have increasing demands for high data rates and high mobility. The high data rates give rise to frequency selectivity, while the mobility and carrier offset introduce time selectivity. To confront the doubly-selective effects of wireless channels, equalizers are usually employed at the receiver end. The existing equalizers can be divided into two types: block equalizers and serial equalizers. The interest in block equalization can be motivated as follows. When transmission channels are affected by both frequency and time selectivity, reliable communication can be achieved by dividing the information data stream into short blocks and by adding a header of known data to each block. The known symbols allow us to obtain the reliable channel identification and to prevent interference between two adjacent blocks. Receiver processing can be carried out on a block-by-block basis so that if the transmission channel does not change appreciably during the transmission of each block, the receiver has to cope with the frequency selectivity only. Block equalization strategies are used to compensate for this channel impairment [36, 18]. However, block equalizers are usually complex to design since the inversion of a large matrix is required. Especially, since a doubly-selective channel can not be diagonalized by a channel-independent transformation, the implementation of block time-varying (TV) equalizers, which collect and process in blocks all the available data in the received frame, leads to a very high computational complexity [5]. Serial equalizers process few data at a time and provide a flexible trade-off between complexity and performance [66]. 13 1.3 Optimal Maximum Likelihood Detector (Viterbi Decoder) In a communication system, the role of channel estimation is to aid in extracting the desired information data from the distorted receive symbols. Next we will briefly review the commonly used symbol detection technique - Viterbi detector. The Viterbi algorithm, originally introduced as a method for decoding convolutional codes, has become one of the most commonly used detectors in digital communications. Forney [23] has shown in 1972 that the algorithm solves maximum likelihood sequence detection (MLSD) of a pulse amplitude modulated (PAM) sequence of symbols with finite intersymbol interference (ISI) and memoryless noise. The algorithm has earned its place in almost every modern digital commu- nications textbook where it is recognized as the optimal sequence detector for memoryless noise. Consider a SIMO (single-input multiple-output) FIR (finite impulse response) linear channel with R outputs and discrete-time impulse response h(n;l). Let fs(n)g denote the input sequence to the SIMO channel. The noisy channel output is given by y(n) = LX l=0 h(n;l)s(n?l)+?(n) (1:23) where L+1 is the multipath channel length and ?(n) is the white complex Gaussian noise. Assume that the white Gaussian noise ?(n) is uncorrelated with fs(n)g, with mean Ef?(n)g = 0 and Ef[?(n+?)][?(n)]Hg = 2?IR?(?). Given s(n), y(n) is a R-dim Gaussian random vector with mean PLl=0h(l)s(n?l) and vari- ance 2?IR. The joint probability density function (pdf) ofy(n) givenfs(n);s(n?1);:::;s(n?L)g 14 is p(y(n)js(n);:::;s(n?L)) = 1(? ?)R exp 8< :? 1 2? y(n)? LX l=0 h(n;l)s(n?l) 29= ; (1:24) where s(n) = 0 for n < 0. The joint pdf of the random vectors fy(0); y(1); :::; y(N ? 1)g given the transmitted sequence fs(0); s(1); :::; s(N ?1)g is p(y(0);:::;y(N ?1)js(0);:::;s(N ?1)) = N?1Y n=0 1 (? ?)R exp 8< :? 1 2? y(n)? LX l=0 h(l)s(n?l) 29= ;; = 1(? ?)NR exp 8< :? 1 2? N?1X n=0 y(n)? LX l=0 h(l)s(n?l) 29= ;: (1:25) Taking the logarithm on both sides of the equation above, we have ln p( y(0);:::;y(N ?1)js(0);:::;s(N ?1)) = ?NRln(? ?)? 1 2 ? N?1X n=0 y(n)? LX l=0 h(n;l)s(n?l) 2 : (1:26) The ML (maximum likelihood) estimate of the input sequence fs(0); :::; s(N ? 1)g is the one that maximizes p(y(0);:::;y(N ?1) j s(0);:::;s(N ?1)); or equivalently maximizes ln p(y(0);:::;y(N ?1) j s(0);:::;s(N ?1)); 15 or minimizes the Euclidean distance N?1X n=0 y(n)? LX l=0 h(n;l)s(n?l) 2 : This MLSE (maximum likelihood sequence estimation) criterion is equivalent to the problem of estimating the state of a discrete-time ?finite-state machine?. In this case, the finite-state machine is the discrete-time channel with coefficients fh(n;l)g and its state at any time n is represented by the L most recent input symbols Staten = (s(n); s(n?1);:::; s(n?L+1)) where s(n) = 0 for n < 0. If the input symbols are M-ary, the finite-state machine has ML states. Consequently, the channel is described by an ML-state trellis and the Viterbi algorithm may be used to determine the most probable path through the trellis. In brief, we describe the Viterbi algorithm in the following 3 steps: Step 1. We begin with y(L), from which we compute the ML+1 metrics LX n=0 y(n)? LX l=0 h(n;l)s(n?l) 2 : The ML+1 possible sequences are divided into ML groups according to the ML states. From each group, we pick the one with the minimum metric, i.e., the most probable sequence, and assign to the surviving sequence the metric PM0(s(L); :::; s(1)) = min s(0) 8< : LX n=0 y(n)? LX l=0 h(n;l)s(n?l) 2 9= ;: 16 The M ?1 remaining sequences from each of the ML groups are discarded. Step 2. Upon reception of y(L+n), n ? 1, compute the ML+1 metrics y(L+n)? LX l=0 h(n;l)s(L+n?l) 2 +PMn?1(s(L+n?1); :::; s(n)): Again, the ML+1 sequences are divided into ML groups corresponding to the ML possible state (s(L + n);:::;s(n + 1)) and the most probable sequence from each group is selected while the other M ?1 sequences are discarded. The surviving metrics are PMn(s(L+n); :::; s(n+1)) = min s(n) 8 < : y(L+n)? LX l=0 h(n;l)s(L+n?l) 2 +PMn?1(s(L+n?1); :::; s(n)) 9 = ;: (1:27) Step 3. If y(L+n) is the last received sample, from the ML survivor sequences, pick the one as the ML (maximum likelihood) sequence estimator which has the minimum metric; otherwise, set n = n+1 and then go to step 2. 1.4 Orthogonal Frequency Division Multiplexing (OFDM) Frequency division multiplexing is a technology that transmits multiple signals simultaneously over a single transmission path, such as a cable or wireless system. Each signal travels within its own unique frequency range (carrier), which is modulated by the data (text, voice, video, etc.). Orthogonal frequency division multiplexing (OFDM) distributes the data over a large number of subchannels that are spaced apart at precise frequencies (see Fig. 1.2). This spacing provides the ?orthogonality? in this technique which prevents the demodulators from seeing frequencies other 17 subchannelmag nitu de carrier channel Figure 1.2: Subchannels are 312 kHz wide in 802.11a and HyperLAN II than their own. The benefits of OFDM are high spectral efficiency, resiliency to radio frequency (RF) interference, and lower multipath distortion. This is useful because in a typical terrestrial broadcasting scenario there are multipath-channels (i.e. the transmitted signal arrives at the receiver using various paths of different length). Since multiple versions of the signal interfere with each other (intersymbol interference) it becomes very hard to extract the original information. OFDM has already been included in digital audio/video broadcasting (DAB/DVB) standards in Europe, and has been successfully applied to high-speed digital subscriber line (DSL) modems in the United States. Recently, it has also been proposed for digital cable television systems and local area mobile wireless networks, such as those specified in the IEEE802.11a, and the HIPERLAN/2 standards [15]. By implementing an inverse fast Fourier transform (IFFT) at the transmitter and a fast Fourier transform (FFT) at the receiver, OFDM converts an intersymbol interference (ISI) channel into parallel ISI-free subchannels with gains equal to the channel?s frequency response val- ues on the FFT grid. To eliminate interblock interference (IBI) between successive IFFT-processed blocks, a cyclic prefix (CP) of length no less than the channel order is inserted per transmitted block. Discarding the CP at the receiver not only suppresses IBI, but also converts the linear channel con- volution into circular convolution, which facilitates diagonalization of the associated channel matrix (see, e.g., [71]). An OFDM transceiver diagram is shown in Fig. 1.3. 18 P/S QAM decoder invert channel = frequencydomain equalizer S/P quadrature amplitude modulation (QAM) encoder N-IFFT add cyclic prefix P/S D/A +transmit filter N-FFT S/P remove cyclic prefix TRANSMITTER RECEIVER N subchannels N complex samples N complex samplesN subchannels receive filter + A/D multipath channel Bits 00110 Figure 1.3: An OFDM transceiver diagram 1.5 Outline and Contribution The dissertation is organized in the following chapters and the author?s contributions are as follows: Chapter 2: The channel estimation for doubly-selective channels is considered using time- multiplexed training. The time-varying channel is assumed to be well-described by a basis expan- sion model using discrete prolate spheroidal sequences as the bases (DPS-BEM). The popular linear least squares and minimum mean-square-error approaches are exploited to estimate the basis expan- sion coefficients. Computer simulations based on Monte Carlo runs are provided. With the channel estimation MSE and bit error rate as the performance measures, we find that the channel estima- tion based on DPS-BEM significantly outperforms the more widely used complex exponential basis expansion model-based channel estimation. 19 Certain aspects of pilot symbol aided modulation (PSAM) parameter design for DPS-BEM- based doubly-selective channels is investigated, following the CE-BEM results in [41, 75]. The optimum time-multiplexed training structure design based on an asymptotic DPS expression is pre- sented by minimizing the DPS-BEM-based channel estimation MSE. The training power allocation problem is also addressed in this chapter. Chapter 3: The channel estimation approaches proposed in Chapter 2 are then extended to multiuser MIMO systems in this chapter. We suppose there are multiple users at the transmit side, and each user has one antenna. Chapter 4: The conventional Kalman filter is used as a time-varying (TV) minimum mean- square-error (MMSE) equalizer for doubly-selective channels. A formulation of FIR decision feed- back equalizer is proposed for doubly-selective channels. The proposed equalizers have the main advantages that they do not incur the approximation error inherent in BEM modeling of equalizers. The BER performance and the computational complexity of the proposed design are investigated by means of Monte Carlo computer simulations, and compared with the existing BEM-based TV equalizers. Chapter 5: An adaptive channel estimation scheme, exploiting the oversampled CE-BEM, is presented for doubly-selective channels where we track the BEM coefficients via a multiple model approach. In the past work the number of BEM coefficients used to model the doubly-selective channels for channel estimation has been based on an upper bound on the channel Doppler spread. The higher the Doppler spread, the more the number of BEM coefficients leading to a higher channel estimation variance. In this chapter we propose to use a multiple model framework where several candidate Doppler spread values are used to cover the range from zero to an upper bound, leading to multiple CE-BEM channel models, each corresponding to an assumed value of the Doppler spread. 20 Subsequently the well known interacting multiple model (IMM) algorithm is used for symbol de- tection based on multiple state-space models corresponding to the multiple estimated channels. Chapter 6: The pilot-aided doubly-selective channel estimation for OFDM systems is con- sidered in this chapter. The time-varying channel is described by CE-BEM or DPS-BEM. The ?optimum? training strategies proposed in Chapter 2 are applied to OFDM systems under doubly- selective channels. Compared to the traditional frequency-domain training design, the main ad- vantages of time-domain training for OFDM system is that the information symbols are not con- taminated by the training symbols as in the frequency-domain training case. The performance of frequency-domain training-based channel estimation and time-domain training-based channel esti- mation is presented and compared. Chapter 7: The dissertation concludes in Chapter 7 with future research topics suggested. 21 CHAPTER 2 SISO DOUBLY-SELECTIVE CHANNEL ESTIMATION USING DISCRETE PROLATE SPHEROIDAL BASIS EXPANSION MODELS AND TIME-MULTIPLEXED TRAINING 2.1 Introduction Doubly-selective channel estimation using complex exponential basis expansion model (CE- BEM) and time-multiplexed training is considered in [41, 75], where CE-BEM based on Fourier basis functions is applied to represent the time-variant channel. However, since the Fourier basis expansion has the major drawback that the rectangular window associated with the discrete Fourier transform (DFT) introduces spectral leakage [44], the bit error rate (BER) suffers an error floor [3, 76]. In [76, 77], the linear minimum mean-square-error (MMSE) channel estimation using discrete prolate spheroidal (DPS) sequences is considered. It is shown that DPS-BEM-based approaches significantly outperform CE-BEM-based approaches for the doubly-selective channel estimation and data detection. To acquire the channel state information at the receiver, training symbols are usually peri- odically inserted during transmission, which is known as pilot symbol aided modulation (PSAM) [16]. Optimization of the PSAM for CE-BEM based doubly-selective channel models has been considered in [41, 75] where the time-multiplexed training sequence is designed to minimize the channel estimation mean-square-error (MSE). In the case of CE-BEM with independent basis ex- pansion coefficients, minimizing the channel estimation MSE is also shown (in [41, 75]) to be equivalent to maximizing a lower bound on the estimated channel-based average capacity. No such considerations are to be found in [76, 77] where the doubly-selective is represented by DPS-BEM. The linear MMSE channel estimator for DPS-BEM-based MIMO-OFDM (multiple input multiple 22 output-orthogonal frequency division multiplexing) doubly-selective channels is introduced in [49], but the training design problem is not considered. In this chapter, we consider the channel estimation for doubly-selective single input single output (SISO) channels described by DPS-BEM. Both linear least squares (LS) and minimum mean- square-error (MMSE) estimators are presented and compared. Our system model is exactly as in [41] except that instead of CE-BEM as in [41] we use DPS- BEM. In [41, 75], the linear MMSE channel estimator is used, which requires knowledge of the noise variance and of the covariance matrix of the channel basis expansion coefficients. While the former may be known at the receiver, the latter is seldom known. In [41], the latter is assumed to be known and diagonal. For the Jakes? model, the basis expansion coefficients for a given tap are not mutually uncorrelated, hence the diagonal assumption does not always hold true. The linear LS channel estimator does not need to know the covariance matrix or make any assumption regarding its nature. On the other hand, the performance of the MMSE channel estimator is better than that of the LS estimator; however, the difference is negligible at high SNRs. [41] does not consider the LS channel estimation whereas [77] has used the LS channel estimator but not the MMSE estimator. Certain aspects of PSAM parameter design for DPS-BEM-based doubly-selective channels is also considered, following the CE-BEM results in [41, 75]. Since the Slepian sequences as a solution to (1:15) are hard to work with analytically, we give asymptotic DPS expressions based on some heuristic considerations. Then the optimum time-multiplexed training structure design based on asymptotic DPS expressions is presented by minimizing the DPS-BEM-based channel estimation MSE. The training power allocation problem is finally addressed. 23 2.2 System Model Consider a doubly-selective single input single output (SISO) finite impulse response (FIR) linear channel. Let h(n;l) denote the symbol-rate impulse response (the channel response at time n to a unit input at time n ? l), where n 2 [0;1;:::;N ? 1] and l 2 [0;L] capture the time- and frequency- selectivity of the channel, respectively. Over a time-block of size N, given N orthonormal functions of ?q(n), the following representation is always true h(n;l) = N?1X q=0 wq(l)?q(n); (2:1) where ?q(n) is the q-th basis function and the basis expansion coefficient wq(l) is fixed over the data block. As the above representation is not parsimonious, the following BEM is used to approximate model (2:1): hBEM(n;l) = QX q=0 wq(l)?q(n); (2:2) where only Q + 1 << N basis functions are involved. Hence, the channel modeling error can be expressed as: eBEM(n;l) = h(n;l)?hBEM(n;l) = N?1X q=Q+1 wq(l)?q(n): (2:3) Let Ts denote the symbol interval. For a channel with a multipath delay spread of ?d sec and a Doppler spread of fd Hz, in the complex exponential basis expansion model (CE-BEM) [56, 38], 24 one takes ?(F)q (n) := ej!qn; !q := 2?(q ? QF2 )=N; L := b?d=Tsc and QF := 2d?DmaxNe where ?Dmax := fdTs is the maximum normalized Doppler bandwidth. After normalization to unit norm, we have ?(F)q (n) = 1pNe(i2?(q?QF=2)n=N): (2:4) In the discrete prolate spheroidal sequence-based BEM (DPS-BEM), the DPS vectors ?(S)q 2 RN (called Slepian sequences in [77], which are time-windowed DPS sequences) with elements ?(S)q (n) for n 2f0;:::;N ?1g, are eigenvectors of the matrix C 2RN?N, fulfilling [77] C?(S)q = ?q?(S)q ; (2:5) where ?q are eigenvalues of matrix C. The (y;z) entries in matrix C are defined as: [C]y;z = sin[2?(y ?z)?Dmax]?(y ?z) ; (2:6) where y;z 2f0;:::;N ?1g. In this case one takes QS ?d2?DmaxNe [77, 58]. In the following, as in [77], we will use a general notation for the basis expansion quantities ?q(n), Q, wq, and h to indicate that all expressions are applicable to any set of orthonormal basis functions ?q(n). 25 Let fs(n)g denotes transmitter?s information sequence. Using the discrete-time baseband equivalent channel model, the received sequence at the receive antenna can be written as x(n) = LX l=0 hBEM(n;l)s(n?l)+?(n); (2:7) where ?(n) is the additive complex Gaussian noise at the receive antenna, with zero-mean and variance 2?. Plugging (2:2) into (2:7), we can rewrite x(n) as: x(n) = QX q=0 ?q(n) " LX l=0 wq(l)s(n?l) # +?(n): (2:8) We consider block transmission as in [41], where transmitted symbols are collected into N?1 blocks with s = [s(0);s(1);:::;s(N ? 1)]T as the 0th block and received x(n)?s are also collect into blocks with x = [x(0);x(1);:::;x(N ? 1)]T as 0th block. To avoid inter-block interference (IBI), as in [41], L guard zeros are inserted in each block at the transmitter. Then the matrix-vector input-output relationship of (2:8) is given by x = QX q=0 D?qWqs+?; (2:9) where ? is defined similarly to x, D?q = diag[?q] with ?q := [?q(0);?q(1);:::;?q(N?1)]T , and Wq?s are N ?N lower triangular Toeplitz matrices with 1st column [wq(0);wq(1);:::;wq(L); 0;:::;0]T . 26 2.3 Channel Estimation Since ?q(n) are known by the receiver, the objective of the channel estimator is to find basis expansion coefficients in (2:2) from the received samples corresponding to the training symbols. The proposed channel estimation relies on time-multiplexed training symbols at known positions. As in [41], each transmitted block s consists of J segments (sub-blocks) of training and in- formation symbols b(n) and c(n), respectively, and each segment has the same length. Then the general structure of s is s = [bT1 ;cT1 ;:::;bTJ;cTJ]T; (2:10) where bj with length Nb and cj with length Nc, for all j 2 [1;J], denote training and information symbol sub-blocks, respectively. Therefore, N = J(Nb + Nc) with Nb > L. Let M = Nb + Nc denote the sub-block size. Obviously, the first L symbols in the ?training part? of the jth subblock of the received signal are contaminated by information symbols in the preceding (j?1)th subblock. In the similar way, the first L symbols in the ?information part? of the jth subblock of the received signal are also contaminated by the last L training symbols in the current jth subblock. In order to avoid the inter-subblock interference (ISBI) so that the channel estimation is decoupled from data detection, we will choose the first and the last L symbols in each training subblock to be zeros, as in [41]. Definebj := [b((j?1)M);b((j?1)M+1);:::;b((j?1)M+Nb?1)]T . Further define ?D?q;j = diag[ ??q;j] where ??q;j = [?q((j?1)M +L);?q((j?1)M +L+1);:::;?q((j?1)M +Nb?1)]T . Then the ISBI free received subblock can be written as ?xb;j = QX q=0 ?D? q;j ?Wqbj + ??b;j; (2:11) 27 where ?x(r)b;j := [xb((j ?1)M + L);xb((j ?1)M + L + 1);:::;xb((j ?1)M + Nb ?1)]T , ??b;j is defined similarly, and (Nb ?L)?Nb matrix ?Wq is given by ?Wq = 2 66 66 64 wq(L) ::: wq(0) ... ... ... wq(L) ::: wq(0) 3 77 77 75: (2:12) Gathering training symbols per block, we obtain ?xb = QX q=0 2 66 66 64 ?D? q;1 ?Wqb1 ... ?D? q;J ?WqbJ 3 77 77 75+ ??b: (2:13) According to the commutativity property of convolution, we have ?Wqbj = Bjwq with wq := [wq(0);:::;wq(L)]T and Bj a (Nb ?L)?(L+1) Toeplitz matrix given by Bj := 2 66 66 64 bj(L) ::: bj(0) ... ... ... bj(Nb ?1) ::: bj(Nb ?L?1) 3 77 77 75; (2:14) where bj(l) := b((j ?1)M +l). Therefore, (2:13) can be rewritten as ?xb = 'w + ??b; (2:15) 28 with simple substitutions, where the [J(Nb ?L)]?[(Q+1)(L+1)] matrix ' := 2 66 66 64 ?D? 0;1B1 ::: ?D? Q;1B1 ... ... ... ?D? 0;JBJ ::: ?D? Q;JBJ 3 77 77 75; (2:16) and w := [wT0 ;wT1 ;:::;wTQ]T: (2:17) 2.3.1 Least-squares Channel Estimation The linear least-squares (LS) channel estimator based on (2:15) is ^wLS = ?LS?xb; (2:18) where ?LS = ('H')?1'H. Define the estimation error of BEM parameters as ~wLS := w? ^wLS. Then the covariance matrix of ~wLS is R~wLS := E[ ~wLS ~wHLS] = 2??'H'??1 : (2:19) As a result, the MSE of ~wLS is 2~wLS := tr(R~wLS) = 2?tr?('H')?1?: (2:20) 29 Using [52, Lemma 1], 2~wLS is lower bounded by (S := K(Q+1)(L+1)) 2~wLS ? 2? SX k=1 1 [('H')]k;k = 2 ? SX k=1 1 ['H']k;k (2:21) where the equality holds if and only if 'H' is a diagonal matrix. By the arithmetic-geometric mean inequality [31, p. 535], 2? SX k=1 1 ['H']k;k ? 2 ?S ? SY k=1 1 ['H']k;k !1=S (2:22) where the equality holds iff ?'H'?k;k are all equal. Equivalently, we need 'H' to be a diagonal matrix with all its diagonal entries equal. 2.3.2 Linear Minimum Mean-Square-Error Channel Estimation The linear minimum mean-square-error (MMSE) channel estimator based on (2:15) is ^wMMSE = ?MMSE?xb; (2:23) where ?MMSE = 2?R?1w +('H')?1'H. This estimator requires Rw := E?wwH? to be known at the receiver. Define the estimation error of BEM parameters as ~wMMSE := w? ^wMMSE. Then the covariance matrix of ~wMMSE is R~wMMSE := E[ ~wMMSE ~wHMMSE] = ? R?1w + 1 2 ? ('H') ??1 : (2:24) 30 As a result, the MSE of ~wMMSE is 2~wMMSE := tr(R~wMMSE) = tr " R?1w + 1 2 ? ('H') ??1# : (2:25) Since our analysis allows for correlated channels, the BEM coefficients wq(l) are not necessar- ily independent. Eigen-decomposition of Rw yields Rw = Uw?wU?1w where U?1w = UHw . Since tr(AB) = tr(BA), (2:25) can be rewritten as 2~wMMSE = tr " ??1w + 1 2 ? U?1w ('H')Uw ??1# : (2:26) Similar to (2:21), by [52, Lemma 1], 2~wMMSE is lower bounded by 2~wMMSE ? X i 1h ??1w + 1 2 ? U?1w ('H')Uw i i;i (2:27) where the equality holds if and only if U?1w ('H')Uw is a diagonal matrix. This is true if 'H' is a diagonal matrix with all its diagonal elements equal. Similar as in (2:21)-(2:22), 2~wMMSE is lower bounded by 2~wMMSE ? S ? 2 64Y i 1h ??1w + 1 2 ? U?1w ('H')Uw i i;i 3 75 1 S (2:28) where the equality holds if and only if ??1w + 1 2 ? U?1w ?IR ?('H')?Uw is a diagonal matrix with all its diagonal entries equal. Equivalently, we need 'H' to be a diagonal matrix with all its diagonal entries equal provided that diagonal ?w has all its diagonal entries equal; unfortunately, the latter is not necessarily true (at least for a channel tap with Jakes? spectrum). 31 2.3.3 Channel Estimation Error Given estimated BEM parameters ^wq(l) via LS or MMSE estimators, the channel impulse response is then given by: ^hBEM(n;l) = QX q=0 ^wq(l)?q(n): (2:29) There are two sources of channel estimation error: one is from the difference between hBEM(n;l) and ^hBEM(n;l), the other is from the channel modeling error eBEM(n;l) in (2:3). Therefore, the mean square value of channel estimation error is expressed as: 2~h = N?1 N?1X n=0 LX l=0 E ? hBEM(n;l)?^hBEM(n;l)+eBEM(n;l) 2 : (2:30) Since the following orthogonality is true for both CE-BEM and DPS-BEM models E ?h hBEM(n;l)?^hBEM(n;l) iH eBEM(n;l) = 0; (2:31) we have 2~h = 2~w +N?1 N?1X n=0 LX l=0 E n [eBEM(n;l)]H eBEM(n;l) o | {z } 2BEM : (2:32) The channel modeling error 2BEM has an analytic expression from Niedzwiecki?s results in [51]: 2BEM ? 1? Z ? 0 ?(n;!)trfShh(!)gd!; (2:33) where ?(n;!) is the instantaneous parameter matching characteristics of a basis function estimator: ?(n;!) = j1?H(n;!)j2; (2:34) 32 H(n;!) is the instantaneous frequency response of the basis expansion estimator: H(n;!) = fT(n) N?1X n0=0 f(n)e?i!(n?n0); f(n) := [?0(n);?1(n);:::;?Q(n)]T; (2:35) the power spectral density Shh(!) is derived from the autocorrelation of h(n): Rhh(?) := E[h?(n+?)h(n)]; Rhh(?) = 12? Z ? ?? Shh(!)ei!?d!: (2:36) The modeling error for CE-BEM (referred to as 2CE) and DPS-BEM (referred to as 2DPS) models are analyzed in [77]. We have also shown some simulation results earlier in Chapter 1 (Fig. 1.1). For a 3-tap Jakes? channel, 2DPS is several orders of magnitude smaller than 2CE. 2.4 Optimum Training Design Observe from (2:21) that in order to achieve the lower bound of 2~wLS, The LS estimator re- quires 'H' to be a diagonal matrix with all its diagonal entries equal. Observe from (2:27) and (2:28) that in order to achieve the lower bound of 2~wMMSE, The MMSE estimator also requires 'H' to be a diagonal matrix to achieve (2:27) and for both it and ?w to be diagonal with all their respective diagonal entries equal to achieve (2:28). Unfortunately, in general, the diagonal ?w does not necessarily have all its diagonal entries equal. We will design the training schemes to make 'H' to be a diagonal matrix with all its diagonal entries equal which will achieve the lower bound 33 in (2:22) for the LS channel estimator and in (2:27) (but not in (2:28)) for the linear MMSE channel estimator. Suppose that we choose 'H' = fiI(Q+1)(L+1) for some fi > 0 (2:37) Then by (2:16) we must have JX j=1 BHj ?DH?q1;j ?D?q2;jBj = fiI?(q1 ?q2): (2:38) For CE-BEM, it turns out that [41] JX j=1 ?DH? q1;j ?D? q2;j = 1 MINb?L?(q1 ?q2) (2:39) Note that in [41], (2:4) is not normalized; here it is. By (2:16) and (2:38), for all k?s and q?s, the training sequence should be designed to satisfy JX j=1 BHj ?DH?q1;j ?D?q2;jBj = JX j=1 ?DH? q1;j ?D? q2;j: (2:40) Under (2:39), following [41] and [75], we pick Nb = 2L + 1 and bTj = [0TL;bk;0TL]T where 0L is a size L null column, in which case 'H' = b2MI. Therefore, with Pb := Jb2 denoting the total training power, we can obtain fi = PbN (recall that N = JM). 34 Plugging (2:37) into (2:22), (2:28) and (2:32), the LS and MMSE lower bounds of channel estimation error are derived as 2~h LS = N 2? Pb (L+1)(QF +1)+ 2 CE; (2:41) 2~h MMSE = (L+1)(QF+1)X t=1 ? ???1t + Pb 2?N ??1 + 2CE; (2:42) where ??t is the t-th diagonal entry of matrix ?w, i.e. ??t is the t-th eigenvalue of Rw. For DPS-BEM, we will use ?large? N approximation from the Appendix A for DPS-BEM basis functions to obtain an expression for the modeled part of channel estimation error. Using heuristic asymptotic (A:6), we can easily establish (note that asymptotic (A:6) corresponds to (2:4) and (A:3)) JX j=1 ?DH? q1;j ?D? q2;j ? 1 MINb?L?(q1 ?q2): (2:43) Therefore, for DPS-BEM mimicking (2:41) and (2:42), the lower bounds of channel estimation error are 2~h LS ? N 2? Pb (L+1)(QS +1)+ 2 DPS; (2:44) 2~h MMSE ? (L+1)(QS+1)X t=1 ? ???1t + Pb 2?N ??1 + 2DPS: (2:45) Remark 2.1 Note that (2:43) is critical for (2:44) and (2:45) to hold true and for the proposed training designs to be valid. The asymptotic Slepian sequences in (A:6) are only ?heuristic.? But we can ?verify? (2:43) by computing the results in (2:20) and (2:22) numerically and compare them with the results in (2:44). This is done in Section 2.6. 35 2.5 Training Power Allocation We assume that the time-varying channel h(n;l) is zero-mean, wide sense stationary (in n with fixed l) complex Gaussian with the same variance 2h. We also assume that the channel taps are mutually independent, i.e. h(n;l) is wide sense stationary uncorrelated scattering (WSSUS). To simplify the expressions, in this section we assume that the channel modeling error eBEM in (2:3) is zero. The received information symbols at the received antenna can be expressed as xc(n) = LX l=0 ^h(n;l)c(n?l) | {z } :=xs(n) + LX l=0 [h(n;l)?^h(n;l)]c(n?l)+?(n) | {z } =x?(n) ; (2:46) where ^h(n;l) = PQq=0 ^wq(l)?q(n) is used for data detection. Therefore, the signal power is given by 2xs(n) := E'jxs(n)j2? = E 8< : 2 4 flfl flfl fl LX l=0 ^h(n;l)c(n?l) flfl flfl fl 23 5 9= ; = ?Pc LX l=0 ? Ew ? E ?flfl flh(n;l)?^h(n;l) flfl fl 2jw +E'jh(n;l)j2?? = ?Pc h 2~h(n)+(L+1) 2h i ; (2:47) where the average power of information symbols is ?Pc := E'jc(n)j2?; (2:48) 36 and the effective noise power is: 2x?(n) = E 8< : 2 4 flfl flfl fl LX l=0 [h(n;l)?^h(n;l)]c(n?l) flfl flfl fl 23 5 9= ;+E 'j?(n)j2? = ?Pc 2~h(n)+ 2?; (2:49) where 2~h(n) := PLl=0 Ew ? E ?flfl flh(n;l)?^h(n;l) flfl fl 2jw . Define Wl := [w0(l);w1(l);:::;wQ(l)]T; W := [W0;W1;:::;WL]T; (2:50) By (2:17) and (2:50), we can get the following relationship: W = ?w; (2:51) where ? = 2 66 66 66 66 66 66 66 66 66 66 66 64 1 Lz}|{ 0:::0 ::: ::: 0 0:::0 1 Lz}|{ 0:::0 ::: ::: ::: ::: ::: 0 1 Lz}|{ 0:::0 ::: ::: ::: 0 0 Lz}|{ 0:::0 1 Lz}|{ 0:::0 ::: ... ... ... ::: ::: ::: ::: ::: 1 3 77 77 77 77 77 77 77 77 77 77 77 75 (Q+1)(L+1)?(Q+1)(L+1) : (2:52) 37 We also find that ?H? is always an identity matrix. Then 2~h(n) can be rewritten as 2~h(n) = LX l=0 EW ? E ?flfl flh(n;l)?^h(n;l) flfl fl 2jW = tr n ?(n)EW n covf ^W; ^WjWg o ?(n)H o ; (2:54) where ?(n) := [?0(n);?1(n);:::;?Q(n)]; ?(n) := I(L+1) ??(n): Based on (2:50) and (2:51), we have EW n covf ^W; ^WjWg o = ?EW fcovf ^w; ^wjWgg| {z } R~w ?H: (2:55) Based on the orthonormality of ?q(n), we have NX n=1 ?(n)H?(n) = I(L+1)(Q+1): (2:56) Therefore, the time-averaged of ? 2~h over information subblocks in the current block is ? 2~h := (N ?JNb)?1 X n 2~h(n) ? N?1 N?1X n=0 2~h(n) = 1Ntr'?R~w?H? = 1N 2~w (2:57) 38 Similarly, the time averaged signal and noise powers turn out to be ? 2xs := 1N NX n=1 2xs(n) = ?Pc[? 2~h +(L+1) 2h]; ? 2x? := 1N NX n=1 2x?(n) = ?Pc? 2~h + 2?: (2:58) Therefore, we obtain an effective average SNR for (2:46) as SNRd = ? 2xs ? 2x?: (2:59) Define the total information power and received signal power Pc := JNc ?Pc and P := Pb+Pc, respectively. Define the training power overhead fl := PbP c +Pb : Our objective is to maximize SNR with respect to fl under the constraint of a fixed P. Thus, incorporating those constraint-carrying variables into (2:59) and using the developed expression for average signal and noise powers in (2:59), we obtain the unconstrained cost SNRd(fl) = (1?fl)P JNc [? 2~ h +(L+1) 2 h] (1?fl)P JNc ? 2~ h + 2? : (2:60) Using the lower bound of the LS estimator in (2:44) (due to the lower bound of the MMSE estimator, the closed form of the optimal fl can not be obtained), we can explicitly write (2:59) as SNRd(fl) = f1fl 2 +f2fl +f3 g1fl +g2 ; (2:61) 39 where f1 = ?P(L+1) 2 h NcJ ; f2 = P(L+1) 2 h NcJ ? (L+1)(Q+1) 2? NcJ ; f3 = (L+1)(Q+1) 2? NcJ ; g1 = 2? ? (L+1)(Q+1) 2? NcJ ; g2 = (L+1)(Q+1) 2? NcJ : (2:62) Setting the first derivative of SNRd(fl) with respect to fl to zero, we obtain a quadratic equation in fl fl2 +2g2g 1 fl + f2g2 ?f3g1f 1g1 = 0 (2:63) with two roots, one of which is negative (fl < 0), and hence is excluded. The other root is given by flopt = g2g 1 " ?1+ s 1+ g1(f3g1 ?f2g2)g2 2f1 # : (2:64) 2.6 Numerical Examples In the following examples, we use binary phase shift keying (BPSK) and quadrature phase shift keying (QPSK) modulation. Each transmitted block has J = 10 subblocks, and each subblock has Nc = 30 information symbols and Nb = 2L + 1 training symbols with optimal structure [0L;b;0L], b > 0. A doubly-selective Rayleigh fading channel h(n;l) is simulated according to [77, 81] with the channel order L = 2, carrier frequency of 2GHz, data rate of 40 kbps, and thus, symbol duration Ts = 25?s. Therefore, each tap of the generated time-variant channel has a Jakes? 40 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 x 10?3 10?3 10?2 10?1 100 ?Dmax (2.20) (2.22) right hand side (2.41) (2.44) (2.20)+?DPS2 Figure 2.1: Channel estimation errors (with and without modeling errors):Numerical results derived from QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1, SNR=20dB spectrum; it is not generated using the assumed BEM modeling. Also, 3 taps of the channel are mutually independent. Depending on different maximum Doppler spread fds, a varying maximum normalized one-sided Doppler bandwidth ?Dmax = fdTs can be derived. Given ?Dmax, Jakes? spectrum and other information, we can calculate Rw and therefore, ?w and ??ts, needed in (2:28), (2:45) and elsewhere. The SNR refers to the ratio of total signal and training power to the total noise power, each per block. 2.6.1 Example 1: Approximation Errors As noted earlier in Remark 2.1, here we want to show the influence of approximation errors in ?D? q;j when the true Slepian sequences instead of the approximations in (A:6) are used. We compute (2:20) and (2:22) numerically with true Slepian sequences generated by (2:5), then compare them 41 0 5 10 15 20 25 3010 ?4 10?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE fd=40Hz, QS=2, LS Bound fd=40Hz, QS=2, MMSE Bound fd=100Hz, QS=3, LS Bound fd=100Hz, QS=3, MMSE Bound Figure 2.2: MSE lower bound comparison between LS (2:44) and MMSE (2:45) estimators 0 5 10 15 20 25 3010 ?4 10?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE 40Hz, QS=2, simu, MSE 40Hz, QS=2, simu, MSE?? 40Hz, QS=2, simu, MSE+? 100Hz, QS=3, simu, MSE 100Hz, QS=3, simu, MSE?? 100Hz, QS=3, simu, MSE+? 40Hz, QS=2, LS Bound 100Hz, QS=3, LS Bound Figure 2.3: Comparison between the LS channel estimation MSE lower bound in (2:44) and simu- lation results in (2:65), QS = d2?DmaxNe+1 42 0 5 10 15 20 25 3010 ?4 10?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE 40Hz, QS=2, simu, MSE 40Hz, QS=2, simu, MSE+? 40Hz, QS=2, simu, MSE?? 100Hz, QS=3, simu, MSE 100Hz, QS=3, simu, MSE?? 100Hz, QS=3, simu, MSE+? 40Hz, QS=2, MMSE Bound 100Hz, QS=3, MMSE Bound Figure 2.4: Comparison between the MMSE channel estimation MSE lower bound in (2:45) and simulation results in (2:65), QS = d2?DmaxNe+1 with (2:41) and (2:44). For the parameters stated earlier in this section (J=10, Nb=8, Nc=30, M = Nb + Nc=38, N = JM =380) the results are shown in Fig. 2.1, where SNR=20dB and the dimensions QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 change with the maximum Doppler bandwidth. [Here the minimum QF = 2d?DmaxNe and QS = d2?DmaxNe are not taken since a slightly higher values of Q?s can significantly reduce the modeling error. This is suggested in [77]]. From Fig. 2.1 we see that the CE-BEM lower bound in (2:41) is high due to ?large? modeling error 2CE even though the error for the modeled part is minimum, whereas the results in (2:20), (2:22) and (2:44) are close to each other due to ?small? modeling error 2DPS and ?close-to- minimum? (compare curves for (2:20) (exact error) and (2:22) (lower bound)) error for the modeled part. [We note that 2DPS and 2CE were obtained via Monte Carlo averaging, similar to [77].] 43 0 5 10 15 2010 ?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 2.5: LS channel estimation MSE with varying maximum normalized Doppler bandwidth, QS = d2?DmaxNe+1,QF = 2d?DmaxNe+1 2.6.2 Example 2: DPS-BEM Channel Estimation Performance In this case we pick b = 1 in training. The LS and MMSE estimators are used to estimate w, and then the channel is estimated as in (2:29). Based on Mr Monte Carlo runs, the channel estimation MSE is calculated as (hk corresponds to the kth run) MSE = (MrN)?1 MrX k=1 N?1X n=0 LX l=0 j^hk(n;l)?hk(n;l)j2: (2:65) In Fig. 2.2, the lower bounds in (2:44) and (2:45) are plotted using QS = 2 for fd = 40Hz and using QS = 3 for fd = 100Hz. [The MMSE bound needs ??ts which requires knowledge of the Doppler spread. Note also that for both fd = 40Hz and fd = 100Hz, the minimum QS = d2?DmaxNe are actually QS = 1 and QS = 2, respectively; however, a slightly higher value of 44 0 5 10 15 2010 ?4 10?3 10?2 10?1 100 SNR(dB) BER ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 2.6: BER with varying maximum normalized Doppler bandwidth using BPSK modulation, QS = d2?DmaxNe+1,QF = 2d?DmaxNe+1 QS = d2?DmaxNe + 1 = 3 for fd = 100Hz yields the smaller modeling error, which becomes significant at high SNRs]. Then they are compared with the simulation results (averaged over 200 Monte Carlo runs) in Figs. 2.3 and 2.4 for fd = 40Hz and 100Hz; also shown are ? bounds on the simulation averages. It can be seen that the theoretical results are consistent with the simulation results for fd =40Hz indicating that the optimal pilot design does minimize the channel MSE when using DPS-BEM. For fd=100 Hz, there is a ?small gap? between theory and simulations at high SNRs which is probably attributable to modeling error (?small? but nonzero). Furthermore, the performance of the MMSE estimator outperforms that of the LS estimator at low SNR, and they converge to each other at high SNR. 45 0 5 10 15 20 10?2 10?1 100 SNR(dB) BER ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 2.7: BER with varying maximum normalized Doppler bandwidth using QPSK modulation, QS = d2?DmaxNe+1,QF = 2d?DmaxNe+1 2.6.3 Example 3: CE-BEM versus DPS-BEM In Fig. 2.5, the LS channel estimation MSE (2:65) versus SNR under different maximum Doppler bandwidths (?(S)Dmax is for DPS-BEM, ?(F)Dmax is for CE-BEM) are plotted. It is clear that the MSE of DPS-BEM is consistently smaller than that of CE-BEM. Fig. 2.6 takes BER (average over 2000 Monte Carlo runs) as a performance measure to compare the performance between DPS- BEM and CE-BEM. A Kalman filter formulation is used for information detection after the channel estimation. Comparing with Fig. 2.5 makes it quite clear that the significantly reduced MSE for the DPS-BEM channel estimation leads to a pronounced reduction in BER compared to the CE-BEM case. 46 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.910 ?4 10?3 10?2 10?1 100 ? BER vDmax=0.001 vDmax=0.003 vDmax=0.007 vDmax=0.01 Figure 2.8: Simulations-based BER versus fl for SNR=15dB The plotting in Fig. 2.7 is exactly the same as Fig. 2.6 except that the information sequences are QPSK signals. It is seen from Figs. 2.6 and 2.7 that the BER by using QPSK information symbols are worse than that using BPSK symbols, as expected. 2.6.4 Example 4. Training Power Allocation Here we vary training power (by varying b) with fixed total transmitted power. The BER versus optimum fl based on simulation results (averaged over 1000 Monte Carlo runs) is shown in Fig. 2.8 for SNR=15dB where we used BPSK modulation and a Viterbi detector based on the estimated channel for data detection. We also varied ?Dmax according to different maximum Doppler spread fd. In Fig. 2.9, we plot the optimum theoretical values of fl (derived in (2:64)) versus the received signal SNR. Comparing Figs. 2.8 and 2.9, we see that the two show mutually consistent results 47 5 10 15 20 25 300.1 0.12 0.14 0.16 0.18 0.2 0.22 0.24 SNR(dB) ? opt vDmax=0.001 vDmax=0.003 vDmax=0.007 vDmax=0.01 Figure 2.9: Theoretical flopt (2:64) versus received signal SNR supporting our theoretical results: the optimal (simulations based) fl inferred from Fig. 2.8 is in good agreement with the theoretical flopt of Fig. 2.9. 2.7 Conclusion The channel estimation for doubly-selective channels was considered using time-multiplexed training. The time-varying channel was assumed to be well-described by a basis expansion model using discrete prolate spheroidal sequences as bases. Training designs for time-multiplexed training based on minimization of the channel estimation mean-square-error were investigated. Both least squares and minimum mean-square-error approaches were exploited to estimate the basis expansion coefficients. Computer simulation examples were presented where the channel was generated via 48 Jakes? models with different Doppler spreads. In these examples the DPS-BEM model significantly outperforms the more widely used complex exponential basis expansion model. 49 CHAPTER 3 MIMO DOUBLY-SELECTIVE CHANNEL ESTIMATION USING DISCRETE PROLATE SPHEROIDAL BASIS EXPANSION MODELS AND TIME-MULTIPLEXED TRAINING 3.1 Introduction The prospect of extraordinary improvements in the capacity of wireless networks has drawn considerable attention to multiple-input multiple-output (MIMO) communication techniques. MIMO methods employ multiple transmitter and receiver antennas to increase the data rate and to achieve spatial diversity. Traditionally, multiple antennas have been used on the receiver side to combat the multipath fading. The receive antennas see independently faded versions of the same signal. The receiver combines these signals so that the resultant signal exhibits considerably reduced amplitude variability (fading) in comparison with the signal at any one antenna. This is called diversity gain. Diversity is characterized by the number of independently fading branches, also known as the di- versity order and is equal to the number of receive antennas in single-input-multiple output (SIMO) channels. However, recent advances have shown that using multiple antennas at both the transmit- ter and the receiver can significantly increase the data rate and improve the performance [22, 24]. By employing multiple transmitter antennas, multiple spatial channels are supported in the same frequency band, thus data can be transmitted in parallel which results in an increased data rate. In this chapter, the approaches proposed in Chapter 2 are extended to the MIMO system. We consider the problem of channel estimation for the doubly-selective MIMO channels described by DPS-BEM. Time-multiplexed training is used to estimate the channel. Illustrative simulation exam- ples are provided to show the performance of channel estimation and data detection under a MIMO system. 50 3.2 Multiuser MIMO Channels Consider a multiuser channel with K users and R receive antennas leading to a MIMO system with K inputs and R outputs. Let h(r;k)(n;l) denote the symbol-rate impulse response (the channel response at time n to a unit input at time n?l) of the doubly-selective MIMO FIR linear channels between the kth user?s transmit antenna and the rth receive antenna, where n 2 [0;1;:::;N ? 1] and l 2 [0;L] capture the time- and frequency- selectivity of the channel, respectively. In a general basis expansion representation over a time-block, the following is always true: h(r;k)(n;l) = N?1X q=0 w(r;k)q (l)?q(n); (3.1) where ?q(n) is the q-th basis function and the basis expansion coefficient w(r;k)q (l) is fixed over the data block. As the above representation is not parsimonious, the following basis expansion model is used to approximate model (3.1): h(r;k)BEM(n;l) = QX q=0 w(r;k)q (l)?q(n); (3.2) where only Q + 1 ? N basis functions are involved. Hence, the channel modeling error between h(r;k)(n;l) and h(r;k)BEM(n;l) can be expressed as: e(r;k)BEM(n;l) := h(r;k)(n;l)?h(r;k)BEM(n;l) = N?1X q=Q+1 w(r;k)q (l)?q(n): (3.3) 51 Let fsk(n)g denote the kth transmitter?s information sequence. The received sequence at the rth receive antenna can be written as x(r)(n) = KX k=1 LX l=0 h(r;k)(n;l)sk(n?l)+?(r)(n); (3.4) where ?(r)(n) is the additive complex Gaussian noise at the rth receive antenna, with zero-mean and variance 2?. Plugging (3.2) into (3.4), we can rewrite x(r)(n) as: x(r)(n) = KX k=1 QX q=0 ?q(n) " LX l=0 w(r;k)q (l)sk(n?l) # +?(r)(n): (3.5) We consider block transmission as in [41], where transmitted symbols for the kth transmitter are collected into N ? 1 blocks with sk = [sk(0);sk(1);:::;sk(N ? 1)]T as the 0th block and received x(r)(n)?s are also collect into blocks with x(r) = [x(r)(0);x(r)(1);:::;x(r)(N ? 1)]T as 0th block. To avoid inter-block interference (IBI), as in [41], L guard zeros are inserted in each block at the transmitter. Then the matrix-vector input-output relationship of (3.5) is given by x(r) = KX k=1 QX q=0 D?qW(r;k)q sk +?(r); (3.6) where ?(r) is defined similarly to x(r), D?q = diag[?q] with ?q := [?q(0);?q(1);:::;?q(N ?1)], and W(r;k)q s are N ?N lower triangular Toeplitz matrices with 1st column h w(r;k)q (0);w(r;k)q (1); :::;w(r;k)q (L);0;:::;0 iT . 52 3.3 Channel Estimation As in [41], each transmitted block sk consists of J segments (sub-blocks) of training and information symbols bk(n) and ck(n), respectively, and each segment has the same length. Then the general structure of sk is sk = [bTk;1;cTk;1;:::;bTk;J;cTk;J]T; (3.7) where bk;j with length Nb and ck;j with length Nc, for all j 2 [1;J], denote training and informa- tion symbol sub-blocks, respectively. Therefore, N = J(Nb+Nc) with Nb > L. Let M = Nb+Nc denote the sub-block size. Obviously, the first L symbols in the ?training part? of the jth subblock of the received signal are contaminated by information symbols in the preceding (j?1)th subblock. In the similar way, the first L symbols in the ?information part? of the jth subblock of the received signal are also contaminated by the last L training symbols in the current jth subblock. In order to avoid the inter-subblock interference (ISBI) so that the channel estimation is decoupled from data detection, we will choose the first and the last L symbols in each training subblock to be zeros, as in [41]. Define bk;j := [bk((j?1)M);bk((j?1)M +1);:::;bk((j?1)M +Nb?1)]T . Further define ?D? q;j = diag[ ??q;j] where ??q;j = [?q((j?1)M +L);?q((j?1)M +L+1);:::;?q((j?1)M + Nb ?1)]T . Then the ISBI free received subblock can be written as ?x(r)b;j = KX k=1 QX q=0 ?D? q;j ?W(r;k)q bk;j + ??(r)b;j; (3.8) 53 where ?x(r)b;j := [xb((j ?1)M + L);xb((j ?1)M + L + 1);:::;xb((j ?1)M + Nb ?1)]T , ??b;j is defined similarly, and (Nb ?L)?Nb matrix ?W(r;k)q is given by ?W(r;k)q = 2 66 66 64 w(r;k)q (L) ::: w(r;k)q (0) ... ... ... w(r;k)q (L) ::: w(r;k)q (0) 3 77 77 75: Gathering training symbols per block, we obtain ?x(r)b = KX k=1 QX q=0 2 66 66 64 ?D? q;1 ?W(r;k)q bk;1 ... ?D? q;J ?W(r;k)q bk;J 3 77 77 75+ ?? (r) b : (3.9) According to the commutativity property of convolution, we have ?W(r;k)q bk;j = Bk;jw(r;k)q with w(r;k)q := [w(r;k)q (0);:::;w(r;k)q (L)]T and Bk;j a (Nb ?L)?(L+1) Toeplitz matrix given by Bk;j := 2 66 66 64 bk;j(L) ::: bk;j(0) ... ... ... bk;j(Nb ?1) ::: bk;j(Nb ?L?1) 3 77 77 75; (3.10) where bk;j(l) := bk((j ?1)M +l). Therefore, (4.9) can be rewritten as ?x(r)b = KX k=1 'kw(r;k) + ??(r)b = 'w(r) + ??(r)b ; (3.11) 54 with simple substitutions, where the [J(Nb ?L)]?[(Q+1)(L+1)] matrix 'k := 2 66 66 64 ?D? 0;1Bk;1 ::: ?D? Q;1Bk;1 ... ... ... ?D? 0;JBk;J ::: ?D? Q;JBk;J 3 77 77 75; ' := ['1;:::;'K] (3.12) and w(r;k) := 2 66 66 64 w(r;k)0 ... w(r;k)Q 3 77 77 75; w (r) := 2 66 66 64 w(r;1) ... w(r;K) 3 77 77 75: (3.13) Since the matrix ' is common for all receivers, after collecting all ?x(r)b and w(r) for different r, we get xb = (IR ?')w +?b; (3.14) where w is defined as w := ? w(1)T ??? w(R)T ?T ; (3.15) xb and ?b are defined similarly. 3.3.1 Linear Least-Squares Channel Estimator The linear least-squares (LS) channel estimator based on (3.14) is ^wLS = ?LSxb; (3.16) 55 where ?LS = (IR ? ('H'))?1(IR ?'H). Define the estimation error of BEM parameters as ~wLS := w? ^wLS, then the covariance matrix of ~wLS is R~wLS := E[ ~wLS ~wHLS] = 2??IR ?('H')??1 : (3.17) As a result, the MSE of ~wLS is 2~wLS := tr(R~wLS) = 2?tr h? IR ?('H')??1 i : (3.18) Using [52, Lemma 1], 2~wLS is lower bounded by (S := K(Q+1)(L+1)) 2~wLS ? 2? RSX i=1 1 [IR ?('H')]i;i = R 2 ? SX i=1 1 ['H']i;i (3.19) where the equality holds if and only if 'H' is a diagonal matrix. By the arithmetic-geometric mean inequality [33, p. 535], R 2? SX i=1 1 ['H']i;i ? R 2 ?S ? SY i=1 1 ['H']i;i !1=S (3.20) where the equality holds iff ?'H'?i;i are all equal. Equivalently, we need 'H' to be a diagonal matrix with all its diagonal entries equal. 3.3.2 Linear MMSE Channel Estimator The linear minimum mean-square-error (MMSE) channel estimator based on (3.14) is ^wMMSE = ?MMSExb; (3.21) 56 where ?MMSE = ? 2?R?1w +(IR ?('H'))??1 (IR ? 'H). This estimator requires Rw := E?wwH?to be known at the receiver. Define the estimation error of BEM parameters as ~wMMSE := w? ^wMMSE. Then the covariance matrix of ~wMMSE is R~wMMSE := E[ ~wMMSE ~wHMMSE] = ? R?1w + 1 2 ? ?I R ?('H') ???1 : (3.22) As a result, the MSE of ~wMMSE is 2~wMMSE := tr(R~wMMSE) = tr " R?1w + 1 2 ? ?I R ?('H') ???1 # (3.23) Since our analysis allows for correlated channels, the BEM coefficients w(r;k)q (l) are not nec- essarily independent. Eigen-decomposition of Rw yields Rw = Uw?wU?1w where U?1w = UHw . Since tr(AB) = tr(BA), (3.23) can be rewritten as 2~wMMSE = tr " ??1w + 1 2 ? U?1w ?IR ?('H')?Uw ??1# : (3.24) Similar as in (3.19), by [52, Lemma 1], 2~wMMSE is lower bounded by 2~wMMSE ? X i 1h ??1w + 1 2 ? U?1w (IR ?('H'))Uw i i;i (3.25) where the equality holds if and only if U?1w ?IR ?('H')?Uw is a diagonal matrix. This is true if 'H' is a diagonal matrix with all its diagonal elements equal. Similar to (3.19)-(3.20), 2~wMMSE is 57 lower bounded by 2~wMMSE ? (RS)? 2 64Y i 1h ??1w + 1 2 ? U?1w (IR ?('H'))Uw i i;i 3 75 1 RS (3.26) where the equality holds if and only if ??1w + 1 2 ? U?1w ?IR ?('H')?Uw is a diagonal matrix with all its diagonal entries equal. Equivalently, we need 'H' to be a diagonal matrix with all its diagonal entries equal provided that diagonal ?w has all its diagonal entries equal; unfortunately, the latter is not necessarily true (at least for a channel tap with Jakes? spectrum). 3.3.3 Channel Estimation Error After deriving the estimated BEM parameters ^w(r;k)q (l) by the LS or MMSE estimators, the channel impulse response is then given by: ^h(r;k)BEM(n;l) = QX q=0 ^w(r;k)q (l)?q(n): (3.27) Here we consider that the channel estimation error is from two sources: one is from the difference between h(r;k)BEM(n;l) and ^h(r;k)BEM(n;l), the other is from the channel modeling error e(r;k)BEM(n;l) in (3.3). Therefore, the mean square error of channel estimation error is expressed as: 2~h = N?1 RX r=1 KX k=1 N?1X n=0 LX l=1 E ? h(r;k)BEM(n;l)?^h(r;k)BEM(n;l)+e(r;k)BEM(n;l) 2 : (3.28) Since the following orthogonality is true for both CE-BEM and DPS-BEM models E ?h h(r;k)BEM(n;l)?^h(r;k)BEM(n;l) iH e(r;k)BEM(n;l) = 0; 58 we have 2~h = 2~w +N?1 RX r=1 KX k=1 N?1X n=0 LX l=0 E ?h e(r;k)BEM(n;l) iH e(r;k)BEM(n;l) | {z } := 2BEM : (3.29) For simulations presented in Section 3.6 we calculate 2BEM by averaging over Monte Carlo runs. 3.4 Optimum Training Design Observe from (3.19) that in order to achieve the lower bound of 2~wLS, The LS estimator re- quires 'H' to be a diagonal matrix with all its diagonal entries equal. Observe from (3.25) and (3.26) that in order to achieve the lower bound of 2~wMMSE, The MMSE estimator also requires 'H' to be a diagonal matrix to achieve (3.25), and for both it and ?w to be diagonal with all their respective diagonal entries equal to achieve (3.26). Unfortunately, in general, the diagonal ?w does not necessarily have all its diagonal entries equal. We will design the training schemes to make 'H' to be a diagonal matrix with all its diagonal entries equal which will achieve the lower bound in (3.19) for the LS channel estimator and in (3.25) (but not in (3.26)) for the linear MMSE channel estimator. Suppose that we choose 'Hk1'k2 = 8> < >: fiI(Q+1)(L+1) ; for k1 = k2 0 ; for k1 6= k2; (3.30) 59 or, equivalently PJ j=1B H k1;j ?D H ?q1;j ?D?q2;jBk2;j = fiI ; for k1 = k2;q1 = q2 PJ j=1B H k1;j ?D H ?q1;j ?D?q2;jBk2;j = 0 ; for k1 = k2;q1 6= q2 PJ j=1B H k1;j ?D H ?q1;j ?D?q2;jBk2;j = 0 ; for k1 6= k2;for all q (3.31) for some fi > 0. For CE-BEM, it is shown in [41] that JX j=1 ?DH? q1;j ?D? q2;j = 8> < >: 1 MINb?L ; for q1 = q2 0 ; for q1 6= q2 (3.32) By (3.12) and (3.31), for all k?s and q?s, the training sequence should be designed to satisfy JX j=1 BHk1;j ?DH?q1;j ?D?q2;jBk2;j = JX j=1 ?DH? q1;j ?D? q2;j (3.33) for some > 0. Under (3.32), following [41] and [75], we pick Nb = K(L + 1) + K and bTk;j = [0k(L+1)?1;bk;0(K?k)(L+1)+L] where 0k(L+1)?1 is a size k(L+1)?1 null column, in which case 'Hk 'k = b2kMI. Therefore, with Pbk := Jb2k denoting the total training power from the kth transmitter, we can obtain fi = PbkN (recall that N = JM). Since fi should not be a function of k, we take bk = b leading to Pbk := Pb for all k. 60 Plugging (3.30) into (3.20), (3.26) and (3.29), the LS and MMSE lower bounds of channel estimation error are derived as 2~h LS = 2~wLS + 2CE = N 2? Pb RK(L+1)(QF +1)+ 2 CE; (3.34) 2~h MMSE = 2~wMMSE + 2CE = RK(L+1)(QF+1)X t=1 ? ???1t + Pb 2?N ??1 + 2CE; (3.35) where ??t is the t-th diagonal entry of matrix ?w, i.e. ??t is the t-th eigenvalue of Rw. For DPS-BEM, using the heuristic asymptotic (A:6), we can easily establish JX j=1 ?DH? q1;j ?D? q2;j = 8> < >: 1 MI(Nb?L) ; for q1 = q2 0 ; for q1 6= q2: (3.36) Therefore, for DPS-BEM mimicking CE-BEM, the lower bounds of the channel estimation error are 2~h LS = N 2? Pb RK(L+1)(QS +1)+ 2 DPS; (3.37) 2~h MMSE = RK(L+1)(QS+1)X t=1 ? ???1t + Pb 2?N ??1 + 2DPS: (3.38) Remark 3.1. Note that (3.36) is critical for (3.37) and (3.38) to hold true and for the proposed training designs to be valid. The asymptotic Slepian sequences in (A:6) are only ?heuristic.? But we can ?verify? (3.36) by computing the results in (3.18) and (3.20) numerically and compare them with the results in (3.37). This is done so in Sec. 3.6. 61 3.5 Training Power Allocation We assume that the time-varying channel h(r;k)(n;l) is zero-mean, WSS complex Gaussian with the same variance 2h for each tap. We also assume that the channel taps are mutually indepen- dent, i.e. h(r;k)(n;l) is WSSUS. To further simplify the analysis, we assume the channel correlation matrices are the same across r 2 [1;:::;R]. The received information symbols at the rth received antenna can be expressed as x(r)c (n) = KX k=1 LX l=0 ^h(r;k)(n;l)ck(n?l) | {z } :=xs(n) + KX k=1 LX l=0 [h(r;k)(n;l)?^h(r;k)(n;l)]ck(n?l)+?(r)(n) | {z } =x?(n) ; (3.39) where ^h(r;k)(n;l) = PQq=0 ^w(r;k)q (l)?q(n) is used for data detection. Therefore, similar to the single user case in Section 2.5, the signal power of all receivers is given by 2xs(n) = RX r=1 E'jxs(n)j2? = RX r=1 E 8< : KX k=1 2 4 flfl flfl fl LX l=0 ^h(r;k)(n;l)ck(n?l) flfl flfl fl 23 5 9= ; = ?Pc RX r=1 KX k=1 LX l=0 ? Ew ? E ?flfl flh(r;k)(n;l)?^h(r;k)(n;l) flfl fl 2jw +Enjh(r;k)(n;l)j2o? = ?Pc h 2~h(n)+RK(L+1) 2h i ; (3.40) where the average information power per user: ?Pc := E'jck(n)j2?: (3.41) 62 The effective noise power is: 2x?(n) = RX r=1 E 8< : KX k=1 2 4 flfl flfl fl LX l=0 [h(r;k)(n;l)?^h(r;k)(n;l)]ck(n?l) flfl flfl fl 23 5 9= ;+ RX r=1 E n j?(r)(n)j2 o = ?Pc RX r=1 " KX k=1 LX l=0 Ew ? E ?flfl flh(r;k)(n;l)?^h(r;k)(n;l) flfl fl 2jw # +R 2? = ?Pc 2~h(n)+R 2? (3.42) where 2~h(n) := PRr=1PKk=1PLl=0 Ew ? E ?flfl flh(r;k)(n;l)?^h(r;k)(n;l) flfl fl 2jw . Define W(r;k)l := [w(r;k)0 (l);w(r;k)1 (l);:::;w(r;k)Q (l)]T; W(r;k) := [W(r;k)0 ;W(r;k)1 ;:::;W(r;k)L ]T; W(r) := [W(r;1);W(r;2);:::;W(r;K)]T; W := [W(1);W(2);:::;W(R)]T: (3.43) By (3.15) and (3.43), we can get the following relationship: W = ?w; (3.44) 63 where ? = 2 66 66 66 66 66 66 66 66 66 66 66 64 1 Lz}|{ 0:::0 ::: ::: 0 0:::0 1 Lz}|{ 0:::0 ::: ::: ::: ::: ::: 0 1 Lz}|{ 0:::0 ::: ::: ::: 0 0 Lz}|{ 0:::0 1 Lz}|{ 0:::0 ::: ... ... ... ::: ::: ::: ::: ::: 1 3 77 77 77 77 77 77 77 77 77 77 77 75 (Q+1)(L+1)?(Q+1)(L+1) (3.45) and ? = IRK ??: (3.46) We also find that ?H? is always an identity matrix. Then 2~h(n) can be rewritten as 2~h(n) = RX r=1 KX k=1 LX l=0 EW ? E ?flfl flh(r;k)(n;l)?^h(r;k)(n;l) flfl fl 2jW = tr n ?(n)EW n covf ^W; ^WjWg o ?(n)H o ; (3.47) where ?(n) := [?0(n);?1(n);:::;?Q(n)]; ?(n) := IRK(L+1) ??(n): 64 Based on (3.43) and (3.44), we have EW n covf ^W; ^WjWg o = ?EW fcovf ^w; ^wjWgg| {z } R~w ?H: (3.48) Based on the orthonormality of ?q(n), we have NX n=1 ?(n)H?(n) = IRK(L+1)(Q+1): (3.49) Therefore, the time-averaged of ? 2~h over length N is ? 2~h := (N ?JNb)?1 X n 2~h(n) ? N?1 N?1X n=0 2~h(n) = 1Ntr'?R~w?H? = 1N 2~w: (3.50) In a similar way, the time averaged signal and noise power can be expressed as ? 2xc = 1N NX n=1 2xc(n) = ?Pc[? 2~h +RK(L+1) 2h]; ? 2xn = 1N NX n=1 2xn(n) = ?Pc? 2~h +R 2?: (3.51) Therefore, we obtain an effective average SNR of (3.39) as SNRd = ? 2xc ? 2xn: (3.52) Define the total information power and received signal power Pc := JNc ?Pc and P := Pb+Pc, respectively. Define the training power overhead fl := PbPc+Pb . Our objective is to maximize SNR with respect to fl under the constraint of a fixed P. Thus, incorporating those constraint-carrying 65 variables into (3.52) and using the developed expression for average signal and noise powers in (3.52), we obtain the unconstrained cost SNRd(fl) = (1?fl)P JNc [? 2~ h +RK(L+1) 2 h] (1?fl)P JNc ? 2~ h + 2? : (3.53) Using the lower bound of the LS estimator in (3.37) (due to the lower bound of the MMSE estimator, the closed form of the optimal fl can not be obtained), we can explicitly write (3.52) as SNRd(fl) = f1fl 2 +f2fl +f3 g1fl +g2 ; (3.54) where f1 = ?PRK(L+1) 2 h NcJ ; f2 = PRK(L+1) 2 h NcJ ? RK(L+1)(Q+1) 2? NcJ ; f3 = RK(L+1)(Q+1) 2? NcJ ; g1 = 2? ? RK(L+1)(Q+1) 2? NcJ ; g2 = RK(L+1)(Q+1) 2? NcJ : (3.55) Setting the first derivative of SNR(fl) with respect to fl to zero, we obtain a quadratic equation in fl fl2 +2g2g 1 fl + f2g2 ?f3g1f 1g1 = 0 (3.56) 66 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 x 10?3 10?3 10?2 10?1 100 ?Dmax (3.18) (3.20) righ hand side (3.34) (3.37) (3.18)+?DPS2 Figure 3.1: Channel estimation errors (with and without modeling errors): numerical results derived from QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1, SNR=25dB the two roots, one of which is negative (fl < 0), and hence is excluded. The other root is given by flopt = g2g 1 " ?1+ s 1+ g1(f3g1 ?f2g2)g2 2f1 # : (3.57) 3.6 Numerical Examples In the following examples we consider a multiuser system with K = 2 users and R = 2 receivers. We use binary phase shift keying (BPSK) and quadrature phase shift keying (QPSK) modulation. Each transmitted block has J = 10 subblocks, and each subblock has Nc = 30 infor- mation symbols and Nb = 3L+2 training symbols with optimal structure ?0k(L+1)?1;b; 67 0 5 10 15 20 25 3010 ?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE fd=40Hz, QS=2, LS Bound fd=40Hz, QS=3, MMSE Bound fd=100Hz, QS=2, LS Bound fd=100Hz, QS=3, MMSE Bound Figure 3.2: MSE lower bound comparison between LS (3.37) and MMSE (3.38) estimators 0 5 10 15 20 25 3010 ?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE 40Hz, QS=2, simu, MSE 40Hz, QS=2, sinu, MSE+? 40Hz, QS=2, sinu, MSE?? 40Hz, QS=2, LS Bound 100Hz, QS=3, simu, MSE 100Hz, QS=3, simu, MSE+? 100Hz, QS=3, simu, MSE?? 100Hz, QS=3, LS Bound Figure 3.3: Comparison between channel estimation MSEs lower bound in (3.37) and simulation results (3.58) 68 0 5 10 15 20 25 3010 ?3 10?2 10?1 100 101 SNR(dB) Channel Esitamation MSE 40Hz, QS=2, simu, MSE 40Hz, QS=2, simu, MSE+? 40Hz, QS=2, simu, MSE?? 40Hz, QS=2, MMSE Bound 100Hz, QS=3, simu, MSE 100Hz, QS=3, simu, MSE+? 100Hz, QS=3, simu, MSE?? 100Hz, QS=3, MMSE Bound Figure 3.4: Comparison between channel estimation MSEs lower bound in (3.38) and simulation results (3.58) 0(K?k)(L+1)+L?, b > 0. A doubly-selective Rayleigh fading channel h(r;k)(n;l) is simulated ac- cording to [77, 81] with channel order L = 2, carrier frequency of 2GHz, data rate of 40 kbps, and thus, symbol duration Ts = 25?s. Therefore, each tap of the generated time-variant channel has a Jakes? spectrum; it is not generated using the assumed BEM modeling. Also, 3 taps of the channel are mutually independent. Depending on different maximum Doppler spread fds, a varying maximum normalized one-sided Doppler bandwidth ?Dmax = fdTs can be derived. Given ?Dmax, Jakes? spectrum and other information, we can calculate Rw and therefore, ?w and ??ts, needed in (3.25), (3.38) and elsewhere. A Kalman filter formulation is used for information detection after the channel estimation. The SNR refers to 1= 2? where the information sequence power per user is normalized to one and the channel power (per user) is also normalized to unity. 69 0 5 10 15 2010 ?3 10?2 10?1 100 101 SNR(dB) Channel Estimation MSE ?Dmax(S) =0 ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 3.5: Channel estimation MSE with varying maximum normalized Doppler bandwidth, QF = 2d?DmaxNe and QS = d2?DmaxNe 3.6.1 Example 1: Approximation Errors As noted earlier in Remark 3.1, here we want to show the influence of approximation errors in ?D? q;j when the true Slepian sequences instead of the approximations in (A:6) are used. We com- pute (3.18) and (3.20) numerically with true Slepian sequences generated by (2:5), then compare them with (3.34) and (3.37). For the parameters stated earlier in this section (J=10, Nb=8, Nc=30, M = Nb + Nc=38, N = JM =380) the results are shown in Fig. 3.1, where the dimensions QF = 2d?DmaxNe and QS = d2?DmaxNe change with the maximum Doppler bandwidth and SNR=25dB. From Fig. 3.1 we see that the CE-BEM lower bound in (3.34) is high due to ?large? modeling error 2rmCE even though the error for the modeled part is minimum, whereas the re- sults in (3.18), (3.20) and (3.37) are close to each other due to ?small? modeling error 2DPS and ?close-to-minimum? (compare curves for (3.18) (exact error) and (3.20) (lower bound)) error for 70 0 5 10 15 2010 ?2 10?1 100 101 SNR(dB) Channel Estimation MSE ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 3.6: Channel estimation MSE with varying maximum normalized Doppler bandwidth, QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 the modeled part. [We note that 2DPS and 2CE were obtained via Monte Carlo averaging, similar as in [77].] 3.6.2 Example 2: Channel Estimation Performance In this case we pick b = 1 in training. The LS and MMSE estimators are used to estimate w, and then the channel is estimated as ^h(r;k)(n;l) = PQq=0 ^w(r;k)q (l)?q(n). Based on Mr Monte Carlo runs, the channel estimation MSE is calculated as MSE = (MrN)?1 MrX fi=1 RX r=1 KX k=1 N?1X n=0 LX l=0 j^h(r;k)fi (n;l)?h(r;k)fi (n;l)j2: (3.58) 71 0 5 10 15 2010 ?4 10?3 10?2 10?1 100 SNR(dB) BER ?Dmax(S) =0 ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 3.7: BER with varying maximum normalized Doppler bandwidth for BPSK modulation, QF = 2d?DmaxNe and QS = d2?DmaxNe In Fig. 3.2, the lower bounds in (3.37) and (3.38) are plotted using QS = 2 for fd = 40Hz and using QS = 3 for fd = 100Hz. [The MMSE bound needs ??ts which requires knowledge of the Doppler spread. Note also that for both fd = 40Hz and fd = 100Hz, the minimum QS = d2?DmaxNe are actually QS = 1 and QS = 2, respectively; however, a slightly higher value of QS = d2?DmaxNe+ 1 = 3 for fd = 100Hz yields smaller modeling error which has been proved in Example 1]. Then they are compared with the simulation results (averaged over 200 Monte Carlo runs) in Figs. 3.3 and 3.4 for fd = 40Hz and 100Hz; also shown are ? bounds on the simulation averages. It can be seen that the theoretical results are consistent with the simulation results for fd =40Hz indicating that the optimal pilot design does minimize channel MSEs when using DPS- BEM. For fd=100 Hz, there is a ?small gap? between theory and simulations at high SNRs which is probably attributable to modeling error (?small? but nonzero). Furthermore, the performance of 72 0 5 10 15 2010 ?2 10?1 100 SNR(dB) BER ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 3.8: BER with varying maximum normalized Doppler bandwidth for QPSK modulation, QF = 2d?DmaxNe and QS = d2?DmaxNe 0 5 10 15 2010 ?4 10?3 10?2 10?1 100 SNR(dB) BER ?Dmax (S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 3.9: BER with varying maximum normalized Doppler bandwidth for BPSK modulation, QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 73 0 5 10 15 2010 ?3 10?2 10?1 100 SNR(dB) BER ?Dmax(S) =0.001 ?Dmax(S) =0.003 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.003 ?Dmax(F) =0.005 Figure 3.10: BER with varying maximum normalized Doppler bandwidth for QPSK modulation, QF = 2d?DmaxNe+1 and QS = d2?DmaxNe+1 MMSE estimator outperforms that of LS estimator at low SNR, and they converge to each other at high SNR. 3.6.3 Example 3: CE-BEM versus DPS-BEM In Fig. 3.5, the LS channel estimation MSE (3.58) versus SNR under different maximum Doppler bandwidths (?(S)Dmax is for DPS-BEM, ?(F)Dmax is for CE-BEM) are plotted. It is clear that the MSE of DPS-BEM is consistently smaller than that of CE-BEM. However, we notice that the chan- nel estimation error based on DPS-BEM suffers an error floor, too. This can be alleviated by taking QS to be larger than d2?DmaxNe at the cost of more computations, as Fig. 3.6 shows. Fig. 3.7 and Fig. 3.9 take BER (average over 2000 Monte Carlo runs) as a performance measure to compare the performance between DPS-BEM and CE-BEM. Comparing with Fig. 3.5 and Fig. 3.6 make it quite 74 clear that the drastically reduced MSE for the DPS-BEM channel estimation leads to a pronounced reduction in BER compared to the CE-BEM case. The BER performances under QPSK modulation are plotted in Fig. 3.8 and Fig. 3.10, which are worse than those of BPSK modulation, as expected. 3.7 Conclusion In this chapter, the channel estimation approaches and optimum training design proposed in Chapter 2 were extended to multiuser MIMO system. Illustrative simulation examples were pro- vided to show the performance of channel estimation and data detection under MIMO system. The system model and performance analysis in Chapter 3 are consistent with those in Chapter 2. The numerical results of MIMO system (Chapter 3) outperforms the SISO system (Chapter 2) due to the diversity gain. 75 CHAPTER 4 TIME-VARYING EQUALIZATION FOR DOUBLY-SELECTIVE CHANNELS 4.1 Introduction Well-known techniques of equalization include (a) linear equalization (LE), (b) decision feed- back equalization (DFE), and (c) maximum likelihood sequence estimation (MLSE) [66]. Linear equalizers are the simplest computationally whereas MLSE yields (near-)optimum performance but is computationally demanding. DFE typically provides a good compromise between complexity and performance. In this chapter we consider LE and DFE for doubly-selective channels modeled via basis expansion models (BEM). Design of equalizers for wireless communication systems over doubly-selective channels has been studied in the literature [26, 67, 45, 46, 3, 5, 68]. These equalizers may be divided into two types: block equalizers and serial equalizers. The block equalizers are usually complex to design since inversion of a large matrix is required. Especially, since a doubly-selective channel can not be diagonalized by a channel-independent transformation, the implementation of block time-varying (TV) equalizers, which collect and process in blocks all the available data in the received frame, leads to a very high computational complexity [5]. On the other hand, serial equalizers are more favored since they process few data at a time and provide a flexible trade-off between complexity and performance [66]. The TV serial equalizers in [45, 46, 3, 5, 68] rely on a particular basis expansion model (BEM) of the TV channel impulse response, namely complex exponential (CE) BEM, and the knowledge of the BEM coefficients at the receiver. Furthermore, they also use a CE-BEM representation for the TV equalizer; therefore, when a low-order CE-BEM model is used for the equalizer, it incurs an approximation error inherent in CE-BEM modeling of equalizers. 76 Thus, their performances are highly related to the choice of the number of BEM coefficients and the equalizer order. It is well known that the Kalman filter, a linear recursive minimum mean-square-error (MMSE) filter, is the best linear MMSE detector for a given detection delay. It provides a symbol detection method of obtaining the true MMSE performance within an implementable structure having a fi- nite number of filter weights. The Kalman filter has been widely used in channel estimation and equalization over wireless channels [74]. In this chapter we exploit the Kalman filter as a TV linear MMSE equalizer for doubly-selective channels. An alternative formulation of the FIR DFE based on a CE-BEM channel model is also proposed for doubly-selective channels. The main advantages of the proposed LE and DFE are fourfold: (i) The design process does not rely on a specific basis expansion model for the underlying channel; therefore, it can be applied to any doubly-selective channel model. (ii) The proposed equalizers rely solely on the channel model and therefore, do not incur any approximation error inherent in CE-BEM modeling of equalizers. (iii) Only one parameter, the equalizer delay, will influence the performance of the Kalman filter; only three parameters, the equalizer delay, and feedforward and feedback filter lengths, will influ- ence the performance of proposed DFE. (iv) The computational complexity in terms of the number of flops turns out to be much lower than existing BEM-based TV equalizers. The simulation results will show that the proposed equalizers can achieve the same or an improved bit error rate (BER) performance than the equalizers in [45, 46, 3, 5, 68], without incurring the approximation error inherent in BEM modeling of equalizers. 77 4.2 Linear Equalization 4.2.1 System Model Consider a doubly-selective finite impulse response (FIR) linear channel with single input and multiple outputs (SIMO). The discrete time impulse response h(r)(n;l) denotes the time-varying impulse response of channel that includes transmit-receive filters as well as doubly-selective propa- gation effects between the transmit antenna and the rth receive antenna, where n 2 [0;1;:::;N ?1] and l 2 [0;L] capture the time- and frequency- selectivity of the channel, respectively. Let s(n) denote the transmitted symbols which is input to the SIMO channel, the received sequence at the rth receive antenna can be written as x(r)(n) = LX l=0 h(r)(n;l)s(n?l)+?(r)(n); (4.1) where ?(r)(n) is the additive complex Gaussian noise at the rth receive antenna, with zero-mean and variance 2?. In [45, 46, 3, 5, 68], the designs of TV equalizers depend on a BEM of the time-varying channel, given by [26]: h(r)(n;l) = QX q=0 w(r)q (l)?q(n); (4.2) where w(r)q (l) is the basis expansion model parameter (coefficient), ?q(n) is the basis expansion function, and Q+1 is the basis dimension that satisfies 2d?DmaxNe? Q ? N ?1 with ?Dmax the maximum normalized Doppler bandwidth. The above model is valid over a block of N symbols over which the BEM coefficients remain time-invariant. The BEM coefficients may change from block to block. Therefore, we will refer to the equalizers of [45, 46, 3, 5, 68] as BEM-based equalizers. 78 More specifically, the complex exponential basis functions [26] are used in [45, 46, 3, 5, 68], where ?q(n) = ej2?(q?Q=2)n=P: (4.3) if P = N where N is the block size in symbols, the CE-BEM is said to be critically sampled whereas when P > N, it is said to be oversampled [37]. The oversampling reduces frequency spacing of complex exponentials and gives a better representation of the channel impulse response. [68] uses P = 2N whereas [5] has used P = N. Collecting the symbols 'x(r)(n)?r=Rr=1 received by the R receivers into the vector x(n) := [x1(n);x2(n);:::;xR(n)]T 2CR, we can obtain the matrix-vector form of (4.1): x(n) = LX l=0 Q=2X q=?Q=2 wq(l)s(n?l)ej2?qn=P +?(n); (4.4) where wq(l) := [w(1)q (l);:::;w(R)q (l)]T 2CT and ?(n) := [?(1)(n);:::;?(R)(n)]R 2CR. If the input vector of a BEM-based equalizer of order L0 is defined as y(n) := [xT(n);xT(n? 1);:::;xT(n?L0)]T 2CR(L0+1), the output of the equalizer can be written as: ^s(n) = gH(n)y(n); (4.5) where the vector g(n) 2 CR(L0+1) collects all the equalizer parameters and d is the equalization delay. The following model assumptions are considered throughout this chapter: (H4.1): The information symbols s(n) consists of zero-mean, finite-alphabet of independent and identically distributed (i.i.d.) random variables, satisfying Efs(m)s?(n)g = 2s?(m?n). 79 (H4.2): The measurement noise ?(r)(n) in Eq. (3.1) is uncorrelated with s(n), and Ef?(m)??(n)g = 2??(m?n). 4.2.2 Existing Linear Time-Varying MMSE Equalizers In [45, 46, 3, 5, 68] both zeroforcing and MMSE linear equalizers have been considered. Since the Kalman filter yields a linear MMSE equalizer, in this section we will restrict ourselves to exist- ing TV MMSE equalizers. First we briefly review two linear TV MMSE equalizers from [5] and [68], respectively. The design of these equalizers assumes availability of the CE-BEM coefficients w(r)q (l)s of the channel. BLM Equalizer [5] In [45, 46, 3, 5] one seeks ^s(n) = L0?dX l0=d Q0=2X q0=?Q0=2 RX r=1 g(r)q0 (l0)ej2?q0n=Px(r)(n?l0); (4.6) where design parameters are d, L0, Q0 and equalizer coefficients g(r)q0 (l0), invariant over n 2f0;1;:::; N ?1g. Notice that the structure of the equalizer is that of a CE-BEM. Define g(r) := h g(r)?Q0=2(?d);:::;g(r)?Q0=2(L0 ?d);g(r)?Q0=2+1(?d);:::;g(r)Q0=2(?d);:::;g(r)Q0=2(L0 ?d) iT (4.7) and gblm = h g(1)T;g(2)T;:::;g(R)T iT 2CR(L0+1)(Q0+1): (4.8) 80 The TV MMSE equalizer proposed in [45, 46, 3, 5](henceforth referred to as BLM) provides an explicit frequency-domain representation, by turning a TV equalization problem into a simpler time- invariant (TI) filtering design, which only involves the TI basis expansion parameters of the doubly- selective channel. The (TV MMSE) BLM equalizer can be expressed as [5]: gblm = Hblm " HHblmHblm(n)+ 2? 2sI(Q+Q0+1)(L+L0+1) #?1 ed (4.9) where the [R(Q0+1)(L0+1)]?[(Q+Q0+1)(L0+L+1)] matrix Hblm collects TI BEM parameters and TV complex exponential basis functions as given in Sec. V in [5], d 2 f0;1;:::;L+L0g is the delay of the equalizer, and ed 2 R(Q0+Q+1)(L0+L+1) is an unit vector with the element 1 in the (d+1)st position. Computational Complexity: The inverse in (4.9) requires O(K3) flops (one flop is roughly one multiply-and-accumulate operation) where K = (Q + Q0 + 1)(L + L0 + 1) and O(K3) = K3 +0:5K2 +0:5K if one uses modified Cholesky decomposition (i.e. UD-decomposition) based approach to matrix inverse ([28] Table 6.13). This has been called design complexity (equalizer design) in [5]. For implementation of (4.6), one needs NR(Q0+1)(L0+1) flops; this has been called implementation complexity in [5]. For numerical comparisons in Sec. 4.2.4, we assume that the inverse of a positive-definite matrix has been computed via the modified Cholesky decomposition method. FRESH Equalizer [68] The MMSE solution to the frequency-shift TV equalizer proposed in [68] (referred to as FRESH) gives the canonical frequency-domain representation of the optimal norm TV-MMSE equalizers, which leads the optimal FRESH equalizer design to construct the TI Fourier coefficients of optimal 81 equalizer weights gopt(n). The discrete Fourier series (DFS) expansion relationship of gopt(n) is: gopt(n) = P?1X p=0 gp;optej2?np=P: (4.10) Estimation of gopt(n) via estimation of gp;opt is discussed in [68] for zero-foring equalization with a specified equalization delay. It is straightforward to modify the design to obtain a linear MMSE equalizer; for instance, add the noise variance term to eq. (26) in [68] just as has been done in (4.9). However, the implementation complexity of the FRESH representation of the optimal TV MMSE equalizer maybe quite large for ?large? values of N. Therefore, a low-complexity im- plementation of the optimal FRESH equalizer (refer to as a sub-optimum FRESH method) is also derived in [68] by evaluate only Q0+1 Fourier coefficients in (4.10), which is similar to that consid- ered in BLM equalizer design. So the DFS expansion for sub-optimum FRESH equalizer is given by gsubopt(n) = Q0=2X p=?Q0=2 gp;suboptej2?np=P (4.11) wheregp;subopt = gp;opt for p = 0;1;:::;Q0=2 andgp;subopt = gp+P;opt for p = ?1;?2;:::;?Q0=2. Computational Complexity: As discussed in [68], design complexity of both optimal and suboptimal FRESH equalizers involves P ? O[(L + L0 + 1)3] + (P log2 P)(L + L0 + 1)2 flops where O(K3) = K3 + 0:5K2 + 0:5K when one uses a UD-decomposition approach to positive- definite matrix inversion. For implementation, one needs NRP(L0 + 1) flops for optimal FRESH and NR(Q0 +1)(L0 +1) flops for suboptimal FRESH equalizer. Remark 4.1: The design of both BLM and FRESH equalizers rely on the CE-BEM repre- sentation of the channel. They assume that the BEM parameters w(r)q (l) are known at the receiver. It is still not clear if these design methods apply to other basis expansion models. However, the 82 simulation results in [5] illustrate that the BEM modeling errors have a significant influence on the performance. Remark 4.2: Three parameters have to be considered or optimized for BLM and FRESH equalizers design, d, L0 and Q0. 4.2.3 Kalman Filter with Equalization Delay d The Kalman filter has been widely used in channel estimation and equalization over wireless channels; see [74] and references therein. It requires a state-space model of the underlying system. Define the state vector s(n) s(n) := [s(n);s(n?1);:::;s(n?d)]T 2Cd+1; (4.12) the state transition matrix ' and the input vector ? ' := 2 6401?d 0 Id 0d?1 3 752R(d+1)?(d+1); ? := [1;0 1?d]T;2Rd+1 (4.13) and the observation matrix H(n) H(n) := [h(n;0);h(n;1);:::;h(n;L);0R?(d?L)] 2CR?(d+1); (4.14) where h(n;l) := [h(1)(n;l);:::;h(R)(n;l)]T 2 CR. Based on these definitions and the system model in Section 4.2.1, we have the time-invariant state equation: s(n) = 's(n?1)+?s(n); (4.15) 83 and the time-varying observation equation: x(n) = H(n)s(n)+?(n): (4.16) The Kalman filter algorithm is given as follows [74], [59] where ^s(njn) denotes the linear MMSE estimate of s(n) based on observations x(k), k = 1;2;:::;n. Initialization: At time n = 0, ^s(1j0) = Efs(1)g = 0 and V^s(1j0) = 2sId+1. Filtering: At time n = 1;2::: Vz(n) = H(n)V^s(njn?1)HH(n)+ 2?IR; (4.17) K(n) = V^s(njn?1)HH(n)V ?1z (n); (4.18) z(n) = x(n)?H(n)^s(njn?1); (4.19) ^s(njn) = ^s(njn?1)+K(n)z(n); (4.20) V^s(njn) = [Id+1 ?K(n)H(n)]V^s(njn?1); (4.21) V^s(n+1jn) = 'V^s(njn)'H + 2s??H; (4.22) ^s(n+1jn) = '^s(njn): (4.23) Since ^s(njn) = [^s(njn);^s(n ? 1jn);:::;^s(n ? djn)]T , we extract its last term ^s(n ? djn) as the desired equalized output. Remark 4.3: For Kalman filter, the design process does not rely on a particular basis expansion model as long as the estimated/fitted channel impulse response is known at the receiver, so it can be applied to any doubly-selective channel model. 84 Table 4.1: Operation summary for Kalman filter Operation flops H(n)V^s(njn?1) (d+1)2R Vz(n) 12(d+1)R2 + 12(d+1)R Vz(n)?1(n) R3 + 12R2 + 12R K(n) (d+1)R2 V^s(njn) 12(d+1)2R+ 12(d+1)R Total C = 32(d+1)2R+ 32(d+1)R2 +(d+1)R+R3 + 12R2 + 12R Remark 4.4: Only one parameter, equalization delay d, is needed for the Kalman filter design and will influence its performance. Design Complexity: Computations in (4.17),(4.18),(4.21) and (4.22) comprise the design equa- tions for Kalman filtering. Following Table 6.5 in [28], the required number of flops C per time-step are listed in Table 4.1. Therefore, for a transmitted block of size N symbols, one needs NC flops. Implementation Complexity: Computations in (4.19),(4.20),and (4.23) comprise the imple- mentation equations for Kalman filtering. The number of flops needed per time-step are 2R(d+1) where given the nature of ', (4.23) does not require any flops. Therefore, for a transmitted block of size N symbols, one needs 2NR(d + 1) flops. On the other hand, both BLM and suboptimal FRESH equalizers require NR(Q0 +1)(L0 +1) flops each. 4.2.4 Numerical Examples In this section, the BER performance and the computational complexity of the proposed Kalman filter are investigated by means of Monte Carlo computer simulations, and compared with BEM- based BLM [5] and FRESH [68] equalizers. For computational complexity calculations, we assume 85 that the inverse of a positive-definite matrix has been computed via the modified Cholesky decom- position method. A random time- and frequency- selective Rayleigh fading channel is simulated according to [81] with channel order L = 3 (4 taps). For different l?s, h(n;l)?s are mutually independent, satisfy Jakes? model, and each tap is generated via the method of [81] given the symbol duration Ts and the Doppler spread fd. It is important to point out that each channel tap follows the Jakes? spectrum, rather then the assumed BEM representation. The data were generated using the double-selective channel described above. However, for equalizer design one needs CE-BEM representation of the true channel; this was obtained by a least-squares fit of the assumed BEM to the true channel in each Monte Carlo run, just as in [5] and [68], to obtain the BEM coefficients (which vary from run-to-run). These BEM coefficients were used in the designs of [5] and [68], as well as in Kalman filtering where h(n;l) in (4.14) is generated via (4.2) with fitted BEM parameters (i.e. h(n;l) in (4.14) is not the true channel, but its BEM approximation). Note that one could have directly used the Jakes? channel h(n;l) in the Kalman filter implementation of the linear MMSE equalizer unlike the approaches of [5] and [68]. However, this would not be a fair comparison with the approaches of [5] and [68]. Most importantly, this would not illustrate the effects of modeling errors since practical channels are rarely Jakes? channels although their use in simulations and analysis is widespread. In all simulations, the transmitter transmits binary phase shift keying (BPSK) and quadrature phase shift keying (QPSK) modulated symbols. The SNR refers to the energy per bit over one-sided noise spectral density. 86 Table 4.2: Computation complexity; N = 50, P = 2N = 100 Equalizer Design Complexity(flops) Implementation Complexity(flops) FRESH-OPT [68] P ?O[(L+L0 + 1)3] + (Plog2P)(L+L0 + 1)2 = 171;939 NRP(L0 + 1) = 70;000 FRESH-SUBOPT [68] P ?O[(L+L0 + 1)3] + (Plog2P)(L+L0 + 1)2 = 171;939 NR(Q0 + 1)(L0 + 1) = 13;300 BLM [5] O(K3) = 12;193;565 NR(Q0 + 1)(L0 + 1) = 13;300 Kalman filter (proposed) NC = 8;350 2NR(d+ 1) = 1;200 Example 1: BER versus SNR under Simulation Parameters in [68] We consider the same simulation parameters as in [[68], Experiment 3], i.e., the block size (number of information symbols) is N = 50, P = 2N (oversampled CE-BEM with a factor of 2), the number of receive antennas R = 2, symbol duration Ts = 160us, the maximum Doppler spread fd = 100Hz, the equalization delay d = 5 symbols and Q = 2dfdPTse = 4. For BEM- based equalizers (both BLM and FRESH), the equalizer order L0 = 6 and the number of Fourier coefficients (equalizer BEM coefficients) Q0 = 18, as in [[68], Experiment 3]. The BER averaged over 10;000 Monte Carlo runs versus SNR is shown in Fig. 4.1 for the four approaches: BLM [5], optimum FRESH [68], suboptimum FRESH [68] and the proposed Kalman filter solution. Note that the Kalman filter does not need L0 or Q0. The results for BPSK modulation are plotted in Fig. 4.1. It is seen from Fig. 4.1 that the performances of the four approaches are very close each other. The computational complexity measured in terms of flops for entire block is shown in Table 4.2. Notice that the Kalman filter requires significantly fewer flops than the other two approaches, both for design as well as implementation. Fig. 4.2 plots the BER versus SNR results for QPSK modulation, where the information se- quences are QPSK signals. Although the performance of Kalman filter is slightly worse than the other two equalizers at high SNR, the three approaches have similar performances in this case. 87 0 5 10 1510 ?5 10?4 10?3 10?2 10?1 100 SNR(dB) BER FRESH?OPT FRESH?SUBOPT BLM Kalman filter (proposed) Figure 4.1: BER performance versus SNR using BPSK modulation, averaged over 10,000 runs. BLM denotes the method of [5]; FRESH-OPT and FRESH-SUBOPT are methods of [68]. N = 50, P = 100, Q = 4, L = 3, d = 5, Q0 = 18, L0 = 6 Table 4.3: Computation complexity; N = 800, P = 2N = 1600 Equalizer Design Complexity(flops) Implementation Complexity(flops) FRESH-OPT [68] P ?O[(L+L0 + 1)3] + (Plog2P)(L+L0 + 1)2 = 11;130;924 NRP(L0 + 1) = 33;280;000 FRESH-SUBOPT [68] P ?O[(L+L0 + 1)3] + (Plog2P)(L+L0 + 1)2 = 11;130;924 NR(Q0 + 1)(L0 + 1) = 274;400 BLM [5] O(K3) = 37;989;672 NR(Q0 + 1)(L0 + 1) = 274;400 Kalman filter (proposed) NC = 22;000 2NR(d+ 1) = 35;200 88 0 5 10 1510 ?4 10?3 10?2 10?1 100 SNR(dB) BER FRESH?OPT BLM Kalman filter Figure 4.2: BER performance versus SNR using QPSK modulation, averaged over 10,000 runs Example 2: BER versus SNR under Simulation Parameters in [5] Now the simulation parameters in [[68], Fig. 11] are used where N = 800, R = 2, Ts = 25us, fd = 100Hz, d = 10, L0 = 12, and Q0 = 12. Two cases are considered: P = 2N and P = N, leading to Q is 8 and 4, respectively. The results are shown in Fig. 4.3 which were obtained by carrying out 1000 Monte Carlo runs. When P = N, the performance of the Kalman filter and BLM equalizer [5] are quite close to each other as in Fig. 4.1. The error floors at high SNR are caused by the BEM channel modeling error. However, the Kalman filter significantly outperforms the BLM equalizer [5] when P = 2N, the case where the channel modeling errors in approximating a Jakes? channel with CE-BEM are significantly smaller compared the case of P = N: recall that the data are generated via the true Jakes? channel. The computational complexity measured in terms of number of flops for entire block is shown in Table 4.3 for the case P = 2N = 1600. Notice 89 2 4 6 8 10 12 14 1610 ?7 10?6 10?5 10?4 10?3 10?2 10?1 SNR(dB) BER FRESH?OPT, Q=4, P=N FRESH?SUBOPT, Q=4, P=N BLM, Q=4, P=N Kalman filter (proposed), Q=4, P=N FRESH?OPT, Q=8, P=2N FRESH?SUBOPT, Q=8, P=2N BLM, Q=8, P=2N Kalman filter (proposed), Q=8, P=2N Figure 4.3: BER performance versus SNR using BPSK modulation, averaged over 1,000 runs. BLM denotes the method of [5]; FRESH-OPT and FRESH-SUBOPT are methods of [68]. Kalman filter is based on P = 800 when Q = 4 and on P = 1600 when Q = 8. P = N corresponds to critically sampled CE-BEM and P = 2N corresponds to oversampled CE-BEM. N = 800, P = 800 or 1600, Q = 4 or Q = 8, L = 3, d = 10, Q0 = 12, L0 = 12 90 0 5 10 15 2010 ?7 10?6 10?5 10?4 10?3 10?2 10?1 100 SNR(dB) BER BLM, P=N, Q=4 Kalman, Q=4 BLM, P=2N, Q=8 Kalman, Q=8 Figure 4.4: BER performance versus SNR using QPSK modulation, averaged over 1,000 runs 0 5 10 15 2010 ?7 10?6 10?5 10?4 10?3 10?2 10?1 SNR(dB) BER CE?BEM, P=N, Q=4 DPS?BEM, Q=4 CE?BEM, P=2N, Q=8 DPS?BEM, Q=8 Figure 4.5: BER performance versus SNR For DPS-BEM and CE-BEM channel modeling using Kalman filtering, BPSK modulation 91 0 5 10 15 2010 ?7 10?6 10?5 10?4 10?3 10?2 10?1 100 SNR(dB) BER CE?BEM, P=N,Q=4 DPS?BEM, Q=4 CE?BEM, P=2N, Q=8 DPS?BEM, Q=8 Figure 4.6: BER performance versus SNR For DPS-BEM and CE-BEM channel modeling using Kalman filtering, QPSK modulation again that the Kalman filter requires significantly fewer flops than the other two approaches, both for design as well as implementation In Fig. 4.4 the BER performances for QPSK modulation are plotted under two schemes: BLM and Kalman filter. The results in Fig. 4.4 are very similar to Fig. 4.3, except that the BER by using QPSK information symbols are worse than that using BPSK symbols, as expected. Example 3: Performance of Kalman Filter Using DPS-BEM Now we test the performance of the Kalman filer by using Discrete Prolate Spheroidal (DPS) BEM , in addition to CE-BEM, in (4.3), for approximating the true Jakes? channel. As we noted earlier, the Kalman filter has the flexibility that it is not restricted to a particular BEM and can be applied to any doubly-selective channel model. In Fig. 4.5, we compare the BER performances of 92 the Kalman filter for CE-BEM and DPS-BEM cases by using the simulation parameters in Example 2. It is known that the channel modeling error of DPS-BEM is several magnitudes smaller then that of critically sampled (P = N) CE-BEM [77], which is the reason why the BER performance of DPS-BEM case is better then CE-BEM for P = N, Q = 4. For the oversampling case of P = 2N and Q = 8, the performances of DPS-BEM and CE-BEM are very close to each other since the modeling error differences are not so pronounced any more. This example shows the flexibility of the Kalman filter: its application is not limited to the CE-BEM channel model unlike FRESH [68] and BLM [5] equalizers. Without loss of generality, in Fig. 4.6 we again plot the simulation results under QPSK modu- lation where the information symbols are QPSK signals. 4.3 Decision Feedback Equalization 4.3.1 System Model Consider a doubly-selective finite impulse response (FIR) linear channel with single input and multiple outputs (SIMO), where the expressions of input and output of the SIMO channel are the same as (4.1)-(4.4) in Section 4.2.1. Consider an FIR DFE with equalization delay d, feedforward (FF) filter of length lf and feed- back (FB) filter of length lb. Let ^s(n) be the ?soft? estimate of symbol s(n) and let ~s(n) denote its quantized (hard decision) value. Then the soft output of the DFE is given by ^s(n?d) = lf?1X m=0 fTm(n)x(n?m)? lbX k=1 bk(n)~s(n?d?k) (4.24) 93 where the R-column vectors fm(n)?s and scalars bk(n)?s are the tap-gains of FF and FB time- varying filters at time n. Note that both FF and FB filters are FIR. In the minimum mean-square error (MMSE) design of DFE, one seeks the tap-gains to minimize Efjs(n?d)?^s(n?d)j2g. As discussed in [2] and [57, Sec. 3.3], one first designs the FB filter assuming that ~s(n) = s(n) (i.e. no decision errors), and then one designs the FF filter given the FB filter. 4.3.2 Time-Varying FIR MMSE DFEs In this section we first briefly review the TV FIR MMSE DFE from [46],[3]. Then our pro- posed formulation is presented. The design of these equalizers assumes availability of the CE-BEM coefficients w(r)q (l)s of the channel. FIR MMSE DFE of [46],[3] In [46],[3], one approximates time-varying FF and FB tap-gains via another sets of CE-BEMs, leading to ^s(n?d) = lf?1X l0=0 Q0 2X q0=?Q02 RX r=1 f(r)q0 (l0)ej2?qnP x(r)(n?l0)? lbX l00=1 Q00 2X q00=?Q002 bq00(l00)ej2?qnP ~s(n?d?l00) (4.25) where design parameters are d, lf, lb, Q0, Q00 and equalizer FF coefficients f(r)q0 (l0) and FB coef- ficients bq00(l00), invariant over n 2 f0;1;:::;N ? 1g. Notice that the structure of the FF and FB parts of the equalizer is that of a CE-BEM. The design equations may be found in [46],[3]; in particular, see [46, Sec. 5.2]. The TV FIR MMSE DFE proposed in [46],[3] (henceforth referred to as BLM: Barhumi, Leus, Moonen) provides an explicit ?frequency-domain? representation, by turning a TV equalization problem into 94 a simpler time-invariant (TI) filtering design, which only involves the TI basis expansion parameters of the equalizer tap-gains. For details, we refer the reader to [46, Sec. 5.2]. We now provide details from [46, Sec. 5.2] (modified to conform to the notation in this paper). Define the [lb(Q00 +1)+1]?1 vector ~b = [bQ00 2 ;lb ;bQ00 2 ;lb?1 ;:::;bQ00 2 ;1 ;:::;b1;1;b0;lb;:::;b0;1;0;b?1;lb;:::;b?1;1;:::;b?Q00 2 ;1 ]T; the [lf(Q0 +1)]?1 vector ~f(r) = [f(r) Q0 2 ;lf?1 ;:::;f(r)Q0 2 ;0 ;:::;f(r)?Q0 2 ;0 ]T; and the [Rlf(Q0 +1)]?1 vector ~f = [ ~f(1)T;:::; ~f(R)T]T: Define the lf ?[lf +L] Toeplitz matrix W(r)q := 2 66 66 64 w(r)q (L) ??? w(r)q (0) ... ... w(r)q (L) ??? w(r)q (0) 3 77 77 75; the [(Q0 +1)lf]?[(Q+Q0 +1)(lf +L)] matrix H(r) := 2 66 66 64 ?Q2 W(r)q ??? ??Q2 W(r)q ... ... ?Q2 W(r)q ??? ??Q2 W(r)q 3 77 77 75 95 and the [R(Q0 +1)lf]?[(Q+Q0 +1)(lf +L)] matrix H := h H(1)T;:::;H(R)T iT ; where ? := diagf1;ej2?=P;:::;ej2?(lf?1)=Pg. Define a [(Q00 + 1)lf]?[(Q + Q0 + 1)(L + lf)] ?selection? matrix P := 2 66 66 64 IQ00 2 ?P1 0fi?fl P2 0fi?fl IQ00 2 ?P1 3 77 77 75 with fi = (Q00 +1)lb +1, fl = (Q+Q0 ?Q00)(L+lf)=2, P1 := [0lb?[L+lf?1?lb?d)];Ilb;0lb?(d+1)]; P2 := [0(lb+1)?[L+lf?1?lb?d)];Ilb+1;0(lb+1)?d]: Let e denote the [(Q00+1)lb +1]?1 unit vector with a one in position 1+lb +(Q00lb=2). Then the MMSE DFE tap-gains are given by [46, Sec. 5.2] ~bMMSE = R?1MMSEe eTR?1MMSEe ?e; (4.26) RMMSE = P ? ?2? HHH+ ?2s I??1PH; (4.27) ~fTMMSE = ~bTMMSEP ? HHH+ 2? 2sI !?1 HH: (4.28) Computational Complexity: To design the feedforward and feedback filter coefficients, the inverse in (4.28) and (4.26) require 2?O(K3) flops (one flop is roughly one multiply-and-accumulate 96 operation) where K = (Q+Q0+1)(L+lf) and O(K3) = K3+0:5K2+0:5K if one uses modified Cholesky decomposition (i.e. UD-decomposition) based approach to matrix inverse [2, Table 6.13]. This has been called design complexity (equalizer design) in [3]. For implementation of (4.25), one needs NR(Q0 + 1)lf flops for feedforward part and N(Q00 + 1)lb flops for feedback part; this has been called implementation complexity in [3]. For numerical comparisons in Section 4.3.3, we assume that the inverse of a positive-definite matrix has been computed via the modified Cholesky decomposition method. Remark 4.5: The design of BLM DFEs relies on CE-BEM representation of the channel. They assume that the BEM parameters w(r)q (l) are known at the receiver. It is not clear if these design methods apply to other basis expansion models. However, the simulation results in [5] illustrate that the BEM modeling errors have a significant influence on the equalizer performance. Remark 4.6: Five parameters have to be considered or optimized for BLM DFE design: d, lf, lb, Q0 and Q00. Proposed MMSE DFE with Time-Varying Taps Here we follow [2] (see also [57, Sec. 3.3]) where a time-invariant channel is considered. Their results extend to time-varying channels in a straight-forward fashion; therefore, we simply state the final results instead of repeating the entire derivation with obvious changes. Using the estimated channel, the symbol decisions are made by an FIR MMSE-DFE [2]. Given the lengths of the feedforward (FF) and the feedback (FB) filters as lf and lb respectively, the estimate of the information symbol at time n with equalization delay d is given by (4.24). Stack the 97 inputs of the FF filter at time n into a ?tall? vector xf (n) := ? xT (n) xT (n?1) ??? xT (n?lf +1) ?T ; and also define ?f (n) likewise. By (4.4), we have xf (n) = H(n)sf (n)+?f (n) (4.29) where H(n) := 2 66 66 64 h(n;0) ??? h(n;L) ... ... ... h(n?lf +1;0) ??? h(n?lf +1;L) 3 77 77 75 (4.30) and sf (n) := ? s(n) s(n?1) ??? s(n?lf ?L+1) ?T : We further define sb (n) := ? s(n?d) s(n?d?1) ??? s(n?d?lb) ?T : By the assumption that fs(n)g are i.i.d. with variance 2s, and based on (4.29), we have Rss (n) := E'sb (n)sHb (n)? = 2sIlb+1; Rsx (n) := E'sb (n)xHf (n)? = 2s'HH (n); Rxx (n) := E'xf (n)xHf (n)? = 2sH(n)HH (n)+ 2vIRlf 98 where ' := ? 0(lb+1)?d Ilb+1 0(lb+1)?(lf+L?d?lb?1) ? . Let f (n) and b(n) denote the vectors of time-varying taps of FF and FB filters, f (n) := ? fT0 (n) fT1 (n) ??? fTlf?1 (n) ?T ; b(n) := ? 1 b1 (n) b2 (n) ??? blb (n) ?T : Assuming the decisions f~s(n)g are correct and equal to fs(n)g, the FF and the FB time-varying filters of the MMSE-DFE are given by [2] bMMSE (n) = R ?1 ? e0 eT0R?1? e0; (4.31) fMMSE (n) = R?1xx (n)RHsx (n)bMMSE (n) (4.32) where e0 := ? 1 0 0 ??? 0 ?T and R? := Rss (n)?Rsx (n)R?1xx (n)RHsx (n): (4.33) Computational Complexity: To design the proposed MMSE DFE, we need to compute the inverse of a Rlf ?Rlf matrix to obtain the feedforward filter coefficients (as in eq. (4.32)), and we need to compute the inverse of a (lb +1)?(lb +1) matrix to obtain the feedback filter coefficients (as in eq.(4.31)). Therefore, the required number of flops is O((Rlf)3)+O((lb +1)3). The implementation complexity associated with eq. (4.24) requires NRlf flops for the feed- forward part and Nlb flops for the feedback part. 99 0 5 10 15 2010 ?7 10?6 10?5 10?4 10?3 10?2 10?1 100 SNR(dB) BER BLM LE, R=1 BLM LE, R=2 BLM DFE, R=1 BLM DFE, R=2 Proposed DFE, R=1 Proposed DFE, R=2 Figure 4.7: BER performance versus SNR, averaged over 1,000 runs, BPSK signal. N = 800, P = 1600, Q = 8, L = 3, d=5, Q0=12, lf=12, Q00 = 4, lb = 3. R denotes the number of receive antennas. Remark 4.7: For the proposed MMSE DFE, the design process does not rely on a particular basis expansion model as long as the estimated/fitted channel impulse response is known at the receiver, so it can be applied to any doubly-selective channel model. Remark 4.8: Only three parameters, equalization delay d and filter lengths lf and lb, are needed for the proposed filter design and will influence its performance. 4.3.3 Numerical Examples In this section, the BER performance of the proposed DFE solution are investigated by means of Monte Carlo computer simulations, and compared with BEM-based BLM DFE solution of [46],[3]. 100 0 5 10 15 2010 ?6 10?5 10?4 10?3 10?2 10?1 100 SNR(dB) BER BLM LE, R=1 BLM LE, R=2 BLM DFE, R=1 BLM DFE, R=2 Proposed, R=1 Proposed, R=2 Figure 4.8: BER performance versus SNR, averaged over 1,000 runs, BPSK signal. N = 800, P = 1600, Q = 8, L = 3, d=5, Q0=12, lf=12, Q00 = 4, lb = 3. R denotes the number of receive antennas. A random time- and frequency- selective Rayleigh fading channel is simulated according to [81] with channel order L = 3 (4 taps). For different l?s, h(n;l)?s are mutually independent, satisfy Jakes? model, and each tap is generated via the method of [81] given the symbol duration Ts and the Doppler spread fd. It is important to point out that each channel tap follows the Jakes? spectrum, rather then the assumed BEM representation. The data were generated using the double-selective channel described above. However, for equalizer design one needs CE-BEM representation of the true channel; this was obtained by a least-squares fit of the assumed BEM to the true channel in each Monte Carlo run, just as in [46], [5] and [68], to obtain the BEM coefficients (which vary from run-to-run). These BEM coefficients were used in the designs of [46],[3] and [5], as well as in our proposed DFE solution. 101 Table 4.4: Computation complexity Equalizer Design Flops Implementation Flops BLM DFE [46],[3] 62,611,290 261,600 Proposed DFE 14,198 21,600 In our simulations, the transmitter transmits binary or quaternary phase shift keying (BPSK/ QPSK) modulated symbols. The SNR refers to the energy per symbol over one-sided noise spectral density. We consider the simulation parameters quite similar to those in [46],[3] and [5, Fig. 11], i.e., the block size (number of information symbols) is N = 800, P = 2N (oversampled CE-BEM with a factor of 2), the number of receive antennas R = 1;2, symbol duration Ts = 25 ?s, the maximum Doppler spread fd = 100Hz, the equalization delay d = 5 symbols and Q = 2dfdPTse = 8. For BEM-based equalizers (both BLM LE and BLM DFE), the equalizer lengths lf = 12 and lb = 3 with corresponding number of Fourier coefficients (equalizer BEM coefficients) Q0 = 12 and Q00 = 4. The BER averaged over 1,000 Monte Carlo runs versus SNR is shown in Fig. 4.7 for the three approaches when using BPSK signal: BLM DFE [46],[3], BLM LE [5], and our proposed DFE solution. Note that our formulation does not need Q0 or Q00. It is seen from Fig. 4.7 that the DFE solutions outperform the LE solution, and the performance improves with increasing number of receive antennas R. Furthermore, our proposed solution outperforms the BEM-based DFE of [46],[3]. The computational complexity measured in terms of number of flops for the entire block is shown in Table 4.4. Notice that our DFE formulation requires far fewer flops than the BEM-based DFE of [46],[3]. Finally, Fig. 4.8 shows the BER results for QPSK signals for the same set of parameters as for Fig. 4.7. We see comparative performance similar to Fig. 4.7 in Fig. 4.8. 102 4.4 Conclusion In this chapter, we exploited the conventional Kalman filter and DFEs as time-varying mini- mum mean-square-error equalizer for doubly-selective channels modeled via basis expansion mod- els (BEM). Recently there has been much interest in designing time-variant serial FIR (finite im- pulse response) linear equalizers and FIR DFEs using complex exponential (CE) BEMs for equal- izers in addition to using CE-BEM for modeling the channel itself. We showed that a Kalman filter formulation of the linear equalizer and an alternative formulation of the FIR DFE based on a CE- BEM channel model yields same or improved BER at a much lower computational cost, without incurring the approximation error inherent in CE-BEM modeling of equalizers. 103 CHAPTER 5 A MULTIPLE MODEL APPROACH TO DOUBLY-SELECTIVE CHANNEL ESTIMATION USING EXPONENTIAL BASIS MODELS 5.1 Introduction In order to ?accurately? model the underlying doubly-selective channel, the number of BEM coefficients used to model the doubly-selective channels for channel estimation has been based on an upper bound on the channel Doppler spread. The higher the Doppler spread, the more the number of BEM coefficients, which leads to a higher channel estimation variance. This, in turn, leads to higher bit error rate (BER) when the estimated channel is used for data detection and the actual Doppler spread is (much) less than the upper bound. In this chapter we propose to use a multiple model framework where several candidate Doppler spread values are used to cover the range from zero to an upper bound, leading to multiple CE-BEM channel models, each corresponding to an assumed value of the Doppler spread. Subsequently the well known interacting multiple model (IMM) algorithm [11] is used for symbol detection based on multiple state-space models corresponding to the multiple estimated channels. The multiple model (or hybrid system) approach assumes the system to be in one of a finite number of models (i.e., that is described by one out of a finite number of models). Each model is characterized by its parameters ? the models differ in Doppler spread here. For each model a filter ?matched? to its parameters is yielding model-conditioned estimates and covariances. A mode probability calculator ? a Bayesian model comparator ? updates the probability of each mode using the likehood function (innovations) of each filter and the prior probability of each model. Then an estimate combiner computes the overall estimate and the associated covariance as the weighted 104 sum of the model-conditioned estimates and the corresponding covariance ? via the (Gaussian) mixture equations. Among all the multiple model approaches, the interacting multiple model is considered to be the best compromise between complexity and performance. The IMM approach computes the state estimate that accounts for each possible current model using a suitable mixing of the previous model conditioned estimate depending on the current model. In this chapter an adaptive channel estimation scheme, exploiting the over-sampled complex exponential basis expansion model (CE-BEM), is presented for doubly-selective channels where we track the BEM coefficients via the multiple model approach. The chapter is organized as follows. First, the system model and objectives are provided. Second, the IMM algorithm and configura- tion are briefly summarized. The performances of the proposed design are finally illustrated by simulation examples. 5.2 System Model and Objectives 5.2.1 System Model Consider a doubly-selective (time- and frequency-selective) FIR (finite impulse response) lin- ear channel. Let fs(n)g denotes a scalar sequence which is the input to time-varying channels with the discrete-time response fh(n;l)g (the channel response at time n to a unit input at time n?l). Then the symbol-rate noisy channel output at the rth receive antenna is given by (n = 0;1;:::; r = 1;2;:::;R) y(r)(n) = LX l=0 h(r)(n;l)s(n?l)+?(r)(n) (5.1) 105 where v(r)(n) is the zero-mean white complex-Gaussian noise with variance 2v. We assume that 'h(r)(n;l)? (r = 1;:::;R) represents a wide-sense stationary uncorrelated scattering (WSSUS) vector channel [54]. In CE-BEM [26, 48, 37], over the k-th block consisting of an observation window of TB symbols, the channel is represented as (?nk := (k?1)TB) h(r)(n;l) = QX q=1 w(r)q (l)ej!qn; n = ?nk;:::;?nk +TB ?1; (5.2) where one chooses (l = 0;1;:::;L, and K is an integer) T := KTB; K ? 1; Q ? 2dfdTTse+1; (5.3) !q := 2?T [q ?(Q+1)=2]; q = 1;2;:::;Q; (5.4) L := b?d=Tsc; (5.5) ?d and fd are respectively the delay spread and the Doppler spread, and Ts is the symbol duration. The BEM coefficients w(r)q (l)?s remain invariant during this block, but are allowed to change at the next block, and the Fourier basis functions 'ej!qn? (q = 1;2;:::;Q) are common for each block. If the delay spread ?d and the Doppler spread fd of the channel (or at least their upper-bounds) are known, one can infer the basis functions of the CE-BEM [48]. Treating the basis functions as known, estimation of a time-varying process is reduced to estimating the invariant coefficients over a block of length TB symbols. Note that the BEM period is T = KTB whereas the block size is TB symbols. If K > 1 (e.g. K = 2 or K = 3), then the Doppler spectrum is said to be over-sampled [37] compared to the case K = 1 where the Doppler spectrum is said to be critically sampled. In 106 [26, 48] only K = 1 (henceforth called CE-BEM) is considered whereas [37] considers K ? 2 (henceforth called over-sampled CE-BEM). 5.2.2 Block-Adaptive Channel Estimation [48] Here we summarize the time-multiplexed training approach of [48]. In Sec. 5.4 we provide simulation comparisons with results of [48]. In [48] each transmitted block of symbols fs(n)gTB?1n=0 is segmented into P subblocks of time-multiplexed training and information symbols. Each sub- block is of equal length lb symbols with ld information symbols and lt training symbols (lb = ld+lt). If s denotes a column-vector composed of fs(n)gTB?1n=0 , then s is arranged as s := ? bT0 cT0 bT1 cT1 ??? bTP?1 cTP?1 ?T (5.6) where bp (p = 0;1;???P ? 1) is a column of ld information symbols and cp is a column of lt training symbols. We clearly have TB = Plb. Given (5.1) and CE-BEM (5.2), [48] has shown that (5.6) is an optimum structure for K = 1 with lt = 2L+1, P ? Q and cp := ? 0TL 0TL ?T ; > 0: (5.7) Thus, given a transmission block of size TB, (2L+1)P symbols have to be devoted to training and the remaining TB ?(2L + 1)P are available for information symbols. This design has been used by others for oversampled CE-BEM also [37]. 107 Let np := plb+ld+L, (p = 0;1;???P?1), denote the location of (nonzero) ?s in the optimum cp?s in the P subblocks. Then by design, received signal (assuming timing synchronization) y(r)(np +l) = h(r)(np +l;l)+v(r)(np +l) (5.8) for l = 0;1;??? ;L. Using (5.2) in these y(r)(np + l)?s, one can uniquely solve for w(r)q (l)?s via a least-squares approach. The channel estimates are given by the CE-BEM (5.2) using the estimated BEM coefficients. 5.2.3 Objectives Suppose that we collect the received signal over a time interval of ?T symbols. We wish to estimate the time-variant channel using a channel model and time-multiplexed training (such as that discussed in Sec. 5.2.2 and [48]), and subsequently using the estimated channel, estimate the information symbols. For CE-BEM, if we choose ?T as the block size, then in general Q value will be very high requiring estimation of a large number of parameters, thereby degrading the channel estimation performance. If we divide ?T into blocks of size TB, and then fit CE-BEM block by block, we need smaller Q. This is the solution considered in this chapter (and also [48]). In practical situations, over a large ?T, the actual Doppler spread fd is likely to vary. Absent any prior knowledge, a commonly used solution [48, 37] is to use an upper bound on the anticipated fd (based on the maximum vehicle speed, e.g.) and pick Q accordingly. In this chapter we investigate a multiple model framework where several candidate Doppler spread values are used to cover the range from zero to an upper bound, leading to multiple CE-BEM channel models, each corresponding to an assumed value of the Doppler spread. Multiple model approach has been extensively used in target tracking applications [11, 7, 64] and more recently, has been used for tracking dispersive DS-CDMA 108 channels using multiple autoregressive (AR) models in [30]. In this chapter we propose to use such an approach in conjunction with BEM?s. 5.3 Multiple Model Approach 5.3.1 Multiple Models Let fd;u denote an upper bound on the anticipated Doppler spread fd. Let fd;1, fd;2,..., fd;M denote our M candidate Doppler spreads and let Qm, 1 ? m ? M, denote the corresponding values of Q from (5.3). Then we have M candidate channel impulse responses indexed by m over the k-th block consisting of an observation window of TB symbols, h(m;r)(n;l) = QmX q=0 w(m;r)q (l)ej!qn;n = ?nk;?nk +1;:::;?nk +TB ?1: (5.9) We will use a Kalman filter with equalization delay d for data detection using the estimated channel. Define y(n) := [y(1)(n); y(2)(n); :::; y(R)(n)]T; sd(n) := [s(n);s(n?1);:::;s(n?d)]T; ?s(n) := Efs(n)g; ~s(n) := s(n)? ?s(n); ' := 2 6401?d 0 Id 0d?1 3 75; ? := [1;01?d]T; Hd(n) := [h(m)(n;0);h(m)(n;1);:::;h(m)(n;L);0R?(d?L)]; h(m)(n;l) := [h(m;1)(n;l);:::;h(m;R)(n;l)]T; (5.10) 109 where ?(n) is defined just as y(n) and integer d ? L. Assume data symbols are zero-mean and white. If s(n) is a data symbol, we have ?s(n) := 0, ~s(n) := s(n); if s(n) is a training symbol, ?s(n) := s(n), ~s(n) := 0. Then the underlying state-space model corresponding to the mth channel is given by the state and the measurement equations sd (n) = 'sd (n?1)+??s(n)+?~s(n); (5.11) y(n) = H(m)d (n)sd (n)+v(n): (5.12) In (5.11) ?s(n) and ~s(n) are defined just as sd(n). Consider a set of TB received symbols divided up into P subblocks as in Sec. 5.2.2. For model m, we estimate the BEM coefficients w(m;r)q (l) via the least-squares approach of Sec. 5.2.2 using the training symbols. Then the estimated channel for the mth model is given by ^h(m;r)(n;l) = PQm q=1 ^w (m;r)q (l)ej!qn. 5.3.2 Interacting Multiple Model Data Detection Using the M estimated channels from each block of received symbols, we obtain the M models with state equation (5.11) and measurement equation y(n) = ^H(m)Td (n)sd (n)+?(n); (5.13) where ^H(m)d (n) is as in Section 5.3.1 with h(m) (n;l) replaced with estimated ^h(m) (n;l). Now our task is to estimate sd(n) given y(k), k ? n, and the M models specified by (5.11) and (5.13). In (5.13) we treat ^H(m)d (n) as true H(m)d (n). 110 Table 5.1: Summary of the IMM algorithm (one cycle) Interaction (i;j = 1;2;???M): predicted mode probability: ??j (k) = Pi pij?i(k?1) mixing probability: ?ijj = pij?i(k?1)=??j (k) ^s0dj(k?1jk?1) = Pi ^sdi(k?1jk?1)?ijj V0dj(k?1jk?1) = PiVdi(k?1jk?1)?ijj +Xj where the ?spread-of-the-means? term in the mixing is Xj = Pi[^sdi(k?1jk?1)? ^s0dj(k?1jk?1)] ?[^sdi(k?1jk?1)? ^s0dj(k?1jk?1)]H?ijj Filtering (i;j = 1;2;???M): ^sdj(kjk?1) = '^s0dj(k?1jk?1)+??s(k) Vdj(kjk?1) = 'V0dj(k?1jk?1)'H + 2~s??T measurement residual: zj = y(k)?Hdj^sdj(kjk?1) residual cov.: Dj = H(j)d Vdj(kjk?1)H(j)Hd + 2vIR fliter gain: Gj = Vdj(kjk?1)H(j)Hd D?1j ^sdj(kjk) = ^sdj(kjk?1)+Gjzj Vdj(kjk) = Vdj(kjk?1)?GjDjGHj likelihood function: ?j = [det(?Dj)]?1e?zHj D?1j zj mode probability: ?j(k) = ? ? j ?jP i ? ? i ?i Combination: ^sd(kjk) = Pj ^sdj(kjk)?j Vd(kjk) = Pj Vdj(kjk)?j +X where the ?spread-of-the means? term in combination is X = Pi[^sdi(kjk)? ^sd(kjk)][^sdi(kjk)? ^sd(kjk)]H?i(k) 111 We propose to use the IMM algorithm [11] to estimate sd(n). In order to do this, in keeping with [11], we allow transitions among the M models (this also allows consideration of time-varying fd) where these transitions are governed by a first-order homogeneous Markov chain with transition probabilities pij, i;j 2 f1;2;:::;Mg, PMj=1 pij = 1. The data symbols input to the channel ~s(n) are treated as Gaussian random variables. The operation of IMM algorithm in one cycle is summa- rized in Table 5.1 where 2~s = 2s = Efjs(n)j2g for information symbol, = 0 for training symbol. Table 1 provides one-cycle (one time sample update) of the IMM algorithm. The required initial- ization for the algorithm is as follows: at time k = 0, ^s(1j0) = Efs(1)g = 0 and its covariance V^s(1j0) = 2sId+1. Having obtained the IMM estimate ^sd(njn) of sd(n), we estimate s(n) with equalization delay d by quantizing the (d+1)st component of ^sd(njn). 5.4 Numerical Examples A random time- and frequency-selective Rayleigh fading channel is considered. We take L = 2 (3 taps) in (5.1), number of receive antennas R = 2, and h(r)(n;l) are zero-mean, complex Gaussian with variance 2h = 1=(L+1). For different l?s and r?s, h(r)(n;l)?s are mutually independent and satisfy the Jakes? model. To this end, we simulated each single tap following [81] (with a correction in the appendix of [77]). We consider a communication system with carrier frequency of 2GHz, data rate of 40kBd (kilo-Bauds), therefore Ts = 25?s, and a varying Doppler spread fd in the range of 0Hz to 200Hz, or the normalized Doppler spread fdTs from 0 to 0:005 (corresponding to a maximum mobile ve- locity from 0 to 108km=h). The additive noise was zero-mean complex white Gaussian. The (receiver) SNR refers to the average energy per symbol over one-sided noise spectral density. The time-multiplexed training scheme of [48] described in Sec. 5.2.2 is adopted, where during data 112 0 5 10 15 2010 ?3 10?2 10?1 SNR(dB) BER BPSK Signal Q upperbound, linear shape channel Q upperbound, step shape channel Multiple model, linear shape channel Multiple model, step shape channel Figure 5.1: IMM with three models, BER vs SNR with BPSK information symbols. sessions the information sequences is modulated by BPSK or QPSK with unit power. The train- ing session is described by (5.7) with = p2L+1 so that the average symbol power of training sessions is equal to that of data sessions. 5.4.1 Example 1: IMM with Three Models We generated a random doubly-selective channel as discussed earlier but with two different profiles of varying fd?s as follows: 1. fd=0 Hz for 1 ? n ? 420, fd=100 Hz for 421 ? n ? 840, fd=200 Hz for 841 ? n ? 1260, fd=100 Hz for 1261 ? n ? 1680, fd=0 Hz for 1681 ? n ? 2100. We picked K = 2, TB = 175 and P = 5. Each subblock has 35 symbols with 30 information symbols in the beginning and 5 training symbols at the end (see Sec. 5.2.2). This channel is named as the Step Shape time-varying channel. 113 0 5 10 15 2010 ?3 10?2 10?1 100 SNR(dB) BER QPSK Signal Q upperbound, linear shape channel Q upperbound, step shape channel Multiple model, linear shape channel Multiple model, step shape channel Figure 5.2: IMM with three models, BER vs SNR with QPSK information symbols. 2. Now fd varies linearly from 0Hz to 200Hz over 1 ? n ? 1050, and fd varies linearly from 200Hz to 0Hz over 1051 ? n ? 2100. This channel is named as the Linear Shape time- varying channel. Two variations on channel estimation schemes are compared using an equalization delay d = 5: 1. Q Upper bound: We used a fixed Q for all blocks with Q=5= upper bound (denoted by ?Q upper bound? in the figs.). With 5 subblocks per non-overlapping block (total 60 blocks), we estimated the channel for each block via the approach of Sec. 5.2.2. Then we used Kalman filtering with d = 5 (no IMM) to detect the information symbols. 2. Proposed Multiple Model: Here we used overlapping blocks by shifting blocks by one subblock. We used three models M = 3 with Q1=1, Q2=3 and Q3=5. The channels are estimated over one block, then we shifted to the right by one subblock (35 symbols), and 114 estimated the 3 candidate channels again, and so on. For transition probability matrix we picked 2 66 66 64 0:9 0:1 0 0:05 0:9 0:05 0: 0:1 0:9 3 77 77 75 which reflects the fact that transitions in fd do not jump over an intermediate value. The three models had equal initial probabilities of 1=3. The bit error rate (BER) of each scheme was studied by averaging over 200 runs where in each run, a symbol sequence of length 2100 is generated and fed into a random doubly-selective channel generated with specified fd?s. The first 70 symbols were discarded in evaluations. In Figs. 5.1 and 5.2, the performances of the two schemes under different SNR?s are compared for BPSK and QPSK information sequences, respectively. It is readily seen that overestimating Doppler spread leads to a performance deterioration compared to the proposed IMM approach relying on a multiple model formulation. 5.4.2 Example 2: IMM with Two Models In this example, the varying Doppler spread fd is in the range of 0Hz to 100Hz. Again two variations on channel estimation schemes are compared: 1. Q Upper bound: We used a fixed Q for all blocks with Q=3= upper bound (denoted by ?Q upper bound? in the figures). With 5 subblocks per non-overlapping block (total 50 blocks), we estimated the channel for each block via the approach of Sec.5.2.2. Then we used Kalman filtering with d = 5 (no IMM) to detect the information symbols. 115 2. Proposed Multiple Model: Here we used overlapping blocks by shifting blocks by one sub- block. We used two models M = 2 with Q1=1 and Q2=3. The channels are estimated over one block, then we shifted to the right by one subblock (35 symbols), and estimated the 2 candidate channels again, and so on. For transition probability matrix we picked 2 640:9 0:1 0:1 0:9 3 75 The two models had equal initial probabilities of 1=2. In all numerical results, the bit error rate (BER) of each scheme was studied by averaging over 200 runs where in each run, a symbol sequence of length 1750 (total 50 blocks) is generated and fed into a random doubly-selective channel generated with specified fd?s. Step Shape Time-Varying Channel We generate the Step Shape random doubly-selective channel with varying fd as follows: fd=0 Hz for 1 ? n ? 584, fd=100 Hz for 585 ? n ? 1168, and fd=0 Hz for 1169 ? n ? 1750. In Figs. 5.3 and 5.4, the performances of the two schemes under different SNR?s are compared for BPSK and QPSK information sequences, respectively. It is readily seen that overestimating Doppler spread leads to a performance deterioration. The proposed IMM approach relying on a multiple model formulation provides a good performance improvement. Fig. 5.5 plots how the average mode probabilities ? (in Table 5.1) change with time. It can be seen from the figure that model 2 (Q2 = 3) that is supposed to capture larger Doppler frequency can also capture model 1 (Q1 = 1 for fd = 0Hz), while model 1 can not capture model 2. 116 Linear Shape Time-Varying Channel In this example the Linear Shape random doubly-selective channel is generated with varying fd linearly: fd is from 0Hz to 100Hz for 1 ? n ? 875, and fd is from 100Hz to 0Hz for 876 ? n ? 1750. Again the performances of the two schemes under different SNR?s are compared in Fig. 5.6 and Fig. 5.7 for BPSK and QPSK information sequences, respectively. Fig. 5.8 plots how the average mode probabilities ? change with time. The Effect of Training Sequence on Mode Probability How does the training sequence structure in (5.7) influence the mode probability is tested in this example. The random channel is generated by fixing fd = 0 for 1 ? n ? 1750 (frequency- selective and time-invariant channel). Model 1 with Q = 1 and Model 2 with Q = 3 are exploited for symbol detection. Suppose the exact channel information regarding Model 1 and Model 2 is available at the receiver. Clearly Model 1 should be the right model being chosen with higher mode probabilities than Model 2. In one case, the training symbols with structure as (5.7) are used. The resulting average mode probability (averaged over 200 iterations) is plotted in Fig. 5.9. Similar to the plottings in Fig. 5.5 and Fig. 5.8, we see that the mode probabilities between blocks are inconsistent. In the other case, no training symbols are inserted in the transmitted signal. The average mode probability result is shown in Fig. 5.10. It is seen that the mode probabilities under this case are consistently smooth. The comparison between Fig. 5.9 and Fig. 5.10 illustrates that the inserted zeros in training structure (5.7) result in the inconsistency of mode probability. 117 0 5 10 15 2010 ?4 10?3 10?2 10?1 SNR(dB) BER BPSK Signal Q upperbound Multiple Model Figure 5.3: IMM with two models. BER vs SNR with BPSK information symbols. Step shape time-varying Channel 0 5 10 15 2010 ?3 10?2 10?1 SNR(dB) BER QPSK Singal Q upperbound Multiple Model Figure 5.4: IMM with two models. BER vs SNR with QPSK information symbols. Step shape time-varying Channel 118 0 200 400 600 800 1000 1200 1400 16000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Symbol Index AAverage Mode Probability Model 1, Q=1 Model 2, Q=3 Figure 5.5: Average mode probability of IMM. Step shape time-varying channel. SNR=20dB 0 5 10 15 2010 ?4 10?3 10?2 10?1 SNR(dB) BER BPSK Signal Q upperbound Multiple Model Figure 5.6: IMM with two models. BER vs SNR with BPSK information symbols. Linear Shape Time-Varying Channel 119 0 5 10 15 2010 ?3 10?2 10?1 SNR(dB) BER QPSK Signal Q upperbound Multiple Model Figure 5.7: IMM with two models. BER vs SNR with QPSK information symbols. Linear Shape Time-Varying Channel 0 200 400 600 800 1000 1200 1400 16000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Symbol Index Average Mode Probability Mode 1, Q=1 Mode 2, Q=3 Figure 5.8: Average mode probability of IMM. Linear shape time-varying channel. SNR=20dB 120 0 50 100 150 200 250 300 350 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 Symbol Index Average Mode Probability Wrong Model Correct Model Figure 5.9: Average mode probability of IMM. Time-invariant channel. With training insertion. SNR=20dB 0 50 100 150 200 250 300 3500 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Symbol Index Average Mode Probability Wrong Model Correct Model Figure 5.10: Average mode probability of IMM. Time-invariant channel. Without training insertion. SNR=20dB 121 5.5 Conclusion An adaptive channel estimation scheme, exploiting the oversampled complex exponential ba- sis expansion model (CE-BEM), was presented for doubly-selective channels where we tracked the BEM coefficients via a multiple model approach. In the past work the number of BEM coefficients used to model the doubly-selective channels for channel estimation has been based on an upper bound on the channel Doppler spread. The higher the Doppler spread, the more the number of BEM coefficients, which leads to a higher channel estimation variance. In this chapter we proposed to use a multiple model framework where several candidate Doppler spread values were used to cover the range from zero to an upper bound, leading to multiple CE-BEM channel models, each correspond- ing to an assumed value of the Doppler spread. Subsequently the well known interacting multiple model (IMM) algorithm was used for symbol detection based on multiple state-space models cor- responding to the multiple estimated channels. Numerical examples were presented to illustrate the proposed approach. The results showed that the IMM approach relying on multiple models had a better performance than traditional overestimating Doppler spread scheme. 122 CHAPTER 6 DOUBLY-SELECTIVE CHANNEL ESTIMATION FOR OFDM SYSTEMS USING DPS-BEM AND TIME-MULTIPLEXED TRAINING 6.1 Introduction Wireless multicarrier (MC) communication systems utilize multiple complex exponentials as information-bearing carriers. MC transmissions thus retain their shape and orthogonality when propagating through linear time-dispersive media. They were first conceived and implemented with analog oscillators in the 60s [42, 83], but it was not until their all-digital implementation with the Fast Fourier Transform (FFT), that their attractive features were unravelled and sparked widespread interest for adoption in various single user and multiple access (MA) communication standards [9]. Nowadays, MC systems such as the Orthogonal Frequency Division Multiplexing (OFDM) are included in the Digital Audio/Video Broadcasting (DAB/DVB) standards in Europe while the Discrete Multi-Tone (DMT), its wireline counterpart in the US, has been applied to high-speed Digital Subscriber Line (DSL) modems over twisted pairs [10]. The pilot-aided doubly-selective channel estimation for OFDM systems is considered in [62], where the channels are approximated by BEMs. The transceiver block diagram is shown in Fig. 6.1. Since the channel estimation is based on frequency-domain training, the receiver can find no subcarrier that solely depends on pilots and thus is not contaminated by information symbols. Due to time-variation, the resulting channel matrix (include IFFT and FFT) is no longer diagonal IFFT FFTCP /ZP insertion CP /ZP removalchannel Channel estimationTraining insertion Symbol detection Figure 6.1: OFDM transceiver block diagram in [62] 123 IFFT FFTCP /ZP insertion CP /ZP removalchannel Channel estimationTraining insertion Symbol detection Figure 6.2: Proposed OFDM transceiver block diagram matrix, which results in the very complicated channel estimation or equalization procedure [6]. In [62], a receiver window is used to suppress the out of band interference, and it is assumed that the channel matrix is approximately banded after windowing. It is also not clear what is the ?optimum? strategy to place the frequency-domain training symbols. The linear MMSE channel estimator for DPS-BEM-based MIMO-OFDM (multiple input multiple output-orthogonal frequency division multiplexing) doubly-selective channels is introduced in [49], but their channel estimation suffers from the frequency-domain training problem, too. In this chapter, we will apply the optimum time-multiplexed training based channel estima- tion introduced in Chapter 2 to OFDM systems under doubly-selective channels. The time-varying channel is described by CE-BEM or DPS-BEM. The time-domain training clusters are inserted after IFFT at the transmitter and the channel estimation proceeds before FFT at the receiver (see Fig. 6.2). In this way, the ?optimum? training strategy and the corresponding channel estima- tion schemes proposed before can be directly applied to MIMO-OFDM systems. Compared to frequency-domain training design, the main advantage of time-domain training for OFDM system is that the information symbols are not contaminated by the training symbols as the frequency-domain training. The performance of frequency-domain training-based channel estimation and time-domain training-based channel estimation are compared by simulations. 124 6.2 System Model Fig. 6.2 depicts the proposed baseband block diagram of a cyclic prefix (CP)-OFDM system, where the jth Nc ?1 information block ~cj := [c((j ?1)Nc);c((j ?1)Nc +1);:::;c((j ?1)Nc +Nc ?1)]T (6.1) is first precoded by the IFFT matrix FHNc with (m;k)th entry ?FH Nc ? m;k = 1p Nce j2?mk=Nc; (6.2) to yield the so-called ?time domain? block vector cj = FHNc~cj: (6.3) Then the training sequence bj of length Nb and cyclic prefix (CP) cpj of length Ncp is inserted be- tween each cj. CP is inserted at the transmitter and discarded at the receiver to avoid the interblock interference (IBI) [72]. The entries of the resulting redundant block sj := [cpTj ;bTj ;cTj ] are finally sent sequentially through the channel. Suppose there are totally J blocks for transmission. Then the general structure of transmitted signal s with length N := Ncp +Nb +Nc is s := [cpT1 ;bT1 ;cT1 ;:::;cpTJ;bTJ;cTJ]T: (6.4) 125 Consider the doubly-selective single input single output FIR linear channel, the same as in Section 2.2. Then the matrix-vector input-output relationship is given by x = QX q=0 D?qWqs+?; (6.5) where x := [x(0);x(1);:::;x(N ?1)]T , ? is the zero-mean white complex-Gaussian noise defined similarly to x, D?q = diag[?q] with ?q := [?q(0);?q(1);:::;?q(N ?1)]T , and Wq?s are N ?N lower triangular Toeplitz matrices with 1st column [wq(0);wq(1);:::;wq(L);0;:::;0]T . This system model in (6.5) is exactly the same as in (2:9). Comparing (2:10) with (6.4), and (2:9) with (6.5), we notice that the IBI free received signal is the same as that in Chapter 2 after CP removal at the receiver. Therefore, the LS/MMSE channel estimator and optimum training design presented in Chapter 2 can be directly applied here without any change. We will skip the theoretical expressions which would be the same as in Chapter 2. 6.3 Doubly-Selective Channel Estimation for OFDM Systems Using Frequency-Domain Train- ing [62] Consider an OFDM system with M subcarriers. The frequency domain transmitted signal is defined as: ~x := [tT1 ;uT1 ;tT2 ;uT2 ???tTP;uTP]T wheretp (p = 1;2;???P) is a column of Mt training symbols anduj is a column of Mu information symbols. Let M = (Mt +Mu)P. As illustrated in Fig 6.1, the OFDM symbol ~x is first modulated by the IFFT operation x = FHM ~x: (6.6) 126 We ignore the symbol index in (6.6) since only one OFDM symbol is considered. The modulated symbol x is then concatenated by a CP and sent over the channel. If the channel is assumed to be time-varying (TV) and approximated by a BEM, as in [62], the received signals at the receiver after CP removal and FFT operation is given by y = FMRcpHTcpx+v = QX q=0 Dq?q~x+v; (6.7) where Tcp := [INcp?M;IM] and Rcp := [0M?Ncp;IM] are CP insertion and CP removal matrices, respectively; H represents the channel matrix in time-domain; v is the zero-mean white complex- Gaussian noise; Dq is a circulant matrix whose first column is the frequency response of the qth basis function Dq := FMdiagf?qgFHM (6.8) and ?q is a diagonal matrix whose diagonal is the frequency response of the BEM coefficients corresponding to the qth basis function [62] ?q = diagfFL[wq;0;:::;wq;L]Tg: (6.9) FL stands for the first L + 1 columns of the matrix FM. The least squares (LS) channel estimator can be achieved based on (6.7) as in [[62], Section IV. B]. 127 Due to the time-variation, the channel matrix in the frequency domain is no longer diagonal, but approximately banded. Therefore, the channel estimation approach based on (6.7) suffers a large estimation error especially with a high Doppler spread. 6.4 Numerical Examples In this section, the numerical results of the proposed time-domain (TD) training channel es- timation (Sec. 6.2, referred to as TDE) are given and compared with the frequency-domain (FD) channel estimation (Sec. 6.3, referred to as FDE). We use binary phase shift keying (BPSK) modu- lation in all examples. To make a relatively fair comparison between TDE and FDE cases, we want to keep the same transmission rates in both schemes. For TDE scheme, the OFDM system has Nc = 30 subcarriers. There are Nb = 2L + 1 training symbols with optimal structure [0L;b;0L], b > 0 in every OFDM symbol and J = 10 OFDM symbols are transmitted sequentially. For FDE scheme, an OFDM system with M = (Mt + Mu)P subcarriers is considered. The subcarriers that are reserved for pilots are grouped in P = 10 equidistant clusters, each containing Mt = 2L + 1 pilot tones. We pick Mu = 30. Inside each cluster, the scheme referred to as ?frequency-domain Kronecker delta? (FDKD) in [35] are exploited, where a nonzero pilot is located in the middle of the cluster with zero guard bands on both sides. This equidistant pilot cluster scheme finds its practical advantage in [60] although the channel follows the bathtub-shaped Doppler spectrum in that case. Another important reason of using FDKD training pattern here is that it is convenient to keep the same transmission rate with TDE scheme. The doubly-selective Rayleigh fading channel is simulated according to [77, 81] with channel order L = 2, carrier frequency of 2GHz, data rate of 40 kbps, and thus, symbol duration Ts = 25?s. 128 0 5 10 15 20 25 3010 ?4 10?3 10?2 10?1 100 101 SNR(dB) MSE FDE, fd=4, ?Dmax=fd*Ts=1e?4 FDE, fd=40, ?Dmax=fd*Ts=1e?3 TDE, fd=4, ?Dmax=fd*Ts=1e?4 TDE, fd=40, ?Dmax=fd*Ts=1e?3 Figure 6.3: LS Channel estimation MSE comparison between TDE and FDE with varying ?Dmax Therefore, each tap of the generated time-variant channel has a Jakes? spectrum; it is not gener- ated using the assumed BEM modeling. Also, the 3 taps of the channel are mutually independent. Depending on different maximum Doppler spread fds, a varying maximum normalized one-sided Doppler bandwidth ?Dmax = fdTs can be derived, where Ts is the symbol duration. A Kalman filter formulation is used for information detection after the channel estimation. The SNR refers to 1= 2? where the information sequence power is normalized to one and the channel power is also normalized to unity. 6.4.1 Example 1: Channel Estimation Performance In this example, the LS channel estimator is used in both TDE and FDE schemes to estimate w, and then the channel is estimated as in (2:29). The channel estimation MSE is calculated as in (2:65). Fig. 6.3 plots the channel estimation MSE (averaged over 200 Monte Carlo runs) versus 129 SNR under different normalized maximum Doppler bandwidths, where fd = 4 or 40Hz. It is clear that the MSE of time-domain training channel estimation is consistently smaller than that of frequency-domain training channel estimation. 6.4.2 Example 2: CE-BEM versus DPS-BEM The LS channel estimator in Example 1 is based on the DPS-BEM channel model. In this example we compare the LS channel estimation MSE of TDE under CE-BEM and DPS-BEM. Fig. 6.4 plots the MSE (2:65) versus SNR under different maximum Doppler bandwidths (?(F)Dmax is for CE-BEM, and ?(S)Dmax is for DPS-BEM). Especially, we take QF = 2d?DmaxNe for CE-BEM and QS = d2?DmaxNe DPS-BEM. It is seen from Fig. 6.4 that the channel estimation performances of DPS-BEM outperform that of CE-BEM for all ?Dmax. Fig. 6.5 takes BER (average over 2000 Monte Carlo runs) as a performance measure to compare the performance between DPS-BEM and CE-BEM for TDE. Comparing with Fig. 6.4 makes it clear that the significantly reduced MSE of the DPS-BEM channel estimation leads to a pronounced reduction in BER compared to the CE-BEM case. 6.5 Conclusion In this chapter, we applied the optimum time-multiplexed training based channel estimation in- troduced in Chapter 2 to OFDM systems under doubly-selective channels. The time-varying channel was described by CE-BEM or DPS-BEM. The time-domain training clusters are inserted after IFFT at the transmitter and the channel estimation proceeds before FFT at the receiver. Compared to frequency-domain training design, the main advantage of time-domain training for OFDM system 130 0 5 10 15 20 25 3010 ?3 10?2 10?1 100 101 SNR(dB) MSE ?Dmax(S) =0.001 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.005 Figure 6.4: LS Channel estimation MSE comparison between DPS-BEM and CE-BEM with varying ?Dmax, TDE 0 5 10 15 20 25 3010 ?3 10?2 10?1 100 SNR(dB) BER ?Dmax(S) =0.001 ?Dmax(S) =0.005 ?Dmax(F) =0.001 ?Dmax(F) =0.005 Figure 6.5: BER comparison between DPS-BEM and CE-BEM with varying ?Dmax, TDE 131 is that the information symbols are not contaminated by the training symbols as in the frequency- domain training case. The simulation results confirmed the claims. 132 CHAPTER 7 SUMMARY AND FUTURE WORK With the emergence of next-generation wireless mobile communications, multimedia services have placed increasing demands for high data rates and high mobility. The high data rates give rise to frequency selectivity, while the mobility and carrier offset introduce time selectivity. In this dissertation, the channel estimation and equalization for frequency-selective and time-selective channel were considered. 7.1 Summary of Original Work In Chapter 2, the channel estimation for single-input single-output frequency- and time- selec- tive channels was considered using time-multiplexed training. The time-varying channel was as- sumed to be well-described by a basis expansion model using discrete prolate spheroidal sequences as bases (DPS-BEM). Both linear least squares and minimum mean-square-error approaches were exploited to estimate the basis expansion coefficients. Training designs for time-multiplexed train- ing based on minimization of channel estimation mean-square-error were investigated. The issue of training power allocation was addressed. Then the proposed channel estimation approaches in Chapter 2 was extended to multiuser multiple-input multiple-output doubly-selective channels in Chapter 3. The linear equalization and decision feedback equalization of doubly-selective channels mod- eled via BEMs were introduced in Chapter 4. There has been much interest in designing time- variant serial finite impulse response linear and DFE equalizers using complex exponential BEMs for equalizers in addition to using CE-BEM for modeling the channel itself. We showed that the 133 Kalman filter formulation of the linear equalizer and an alternative formulation of the FIR DFE based on a CE-BEM channel model yields the same or improved BER at a lower computational cost, without incurring the approximation error inherent in CE-BEM modeling of equalizers. An adaptive channel estimation scheme, exploiting the oversampled complex exponential ba- sis expansion model (CE-BEM), was presented for doubly-selective channels where we tracked the BEM coefficients via a multiple model approach in Chapter 5. In the past work the number of BEM coefficients used to model the doubly-selective channels for channel estimation has been based on an upper bound on the channel Doppler spread. The higher the Doppler spread, the more the number of BEM coefficients, which leads to a higher channel estimation variance. We proposed to use a multiple model framework where several candidate Doppler spread values were used to cover the range from zero to an upper bound, leading to multiple CE-BEM channel models, each corresponding to an assumed value of the Doppler spread. Subsequently, the well known interact- ing multiple model (IMM) algorithm was used for symbol detection based on multiple state-space models corresponding to the multiple estimated channels. Orthogonal Frequency-Division Multiplexing (OFDM), a digital multi-carrier modulation scheme, has developed into a popular scheme for wideband wireless communication due to its high spec- tral efficiency and simple equalization. In Chapter 7, we extended the optimum time-multiplexed training-based channel estimation introduced in Chapter 2 to OFDM systems under a doubly- selective channels. Compared to the traditional frequency-domain training design, the main ad- vantage of time-domain training design for OFDM system is that the information symbols are not contaminated by the training symbols as in the frequency-domain training case. In all chapters, numerical examples based on computer simulations were presented to illustrate the proposed approaches and confirm the conclusions. 134 7.2 Possible Future Directions So far we have assumed that the coefficients of basis expansion model (BEM) are fixed over data blocks. In fact, the BEM coefficients may also undergo changes. Instead of the basis expansion model, another way to model time-varying channels is via au- toregressive (AR) process, particularly the first order AR process [19]. Suppose h(n;l) represents a wide-sense stationary uncorrelated scattering (WSSUS) channel. It is common to use the following first-order AR model to describe it: h(n;l) = fih(n?1;l)+?(n); (7.1) where fi is the AR coefficient, and the driving noise ?(n) is zero-mean complex Gaussian with variance 2? and statistically independent of h(n ? 1;l). Assume that h(n;l) is also zero-mean, complex Gaussian with variance 2h. Then fi = 1 2 h Efh(n;l)h?(n?1;l)g; (7.2) 2? = 2h(1?jfij2): (7.3) It is a tractable model, where the channel is assumed to be Markovian; i.e., for the current channel symbol, the effect of channel symbols other than the immediately preceding one is negligible [73]. This Markovian assumption has been verified for Rayleigh fading channels in [73], by considering the mutual information between channel symbols. AR models describe temporal variation on a symbol-by-symbol update basis, while BEMs depict the evolution of the channel over a period (block) of time. 135 An AR model is not appropriate for a fast fading channels because the channel tracking depends on the inserted training. For information sessions, channel estimates can only be obtained based on the results from the previous training session [40]. However, it could be a good way to track the basis expansion coefficients in BEMs. Up to this point, we suppose that the basis expansion coefficients are fixed over data blocks. In fact, the BEM coefficients may also undergo changes, but not as fast as the channel variations. In the next step, we will model the doubly-selective channel by exploiting the CE-BEM for the overall time-variant channel and an AR model for the BEM coefficients. Recall the BEM model in (2:2). Stack the BEM coefficients into vectors wl = [w1(l);w2(l);:::;wQ]T: (7.4) Suppose the whole data block is divided into J sub-blocks, where the coefficient vector in (7.4) for the jth sub-block (j = 1;2;:::;J) is denoted as wl(j) and updated every sub-block. Since a fading channel well follows the Markov model, we further assume that the BEM coefficients of each block are Markovian, too. The first-order AR process for BEM coefficients is then given by: wl(j) = fiwl(j ?1)+?l(j); (7.5) where ?l(j) defined similar to wl(j), is zero-mean complex Gaussian noise and statistically inde- pendent of wl(j ?1). Based on the AR model in (7.5), a Kalman filter can be applied to track the BEM coefficient for each block. After deriving the estimated BEM coefficients for jth sub-block ^wl(j), the estimated channel impulse response for the whole jth sub-block can be given, via the 136 CE-BEM, as ^h(n;l) = [ej!0n;ej!1n;:::;ej!Qn]T ^wl(j): (7.6) It would be interesting to explore this approach and compare it with our proposed approach. Multiple Model Approach. In applying IMM we treated the estimated channel as the true channel. It would be interesting to incorporate estimated channel statistics, e.g., estimation error variance, into the IMM algorithm. 137 BIBLIOGRAPHY [1] S. Adireddy, L. Tong, and H. Viswanathan, ?Optimal placement of training for unknown chan- nels,? IEEE Trans. Inf. Theory, vol. 48, no. 8, pp. 2338-2353, Aug. 2002. [2] N. Al-Dhahir and J.M. Cioffi, ?MMSE decision-feedback equalizers: finite-length results,? IEEE Trans. Inform. Theory, vol. 41, pp. 961-975, July 1995. [3] I. Barhumi, G. Leus, and M. Moonen, ?Time-varying FIR decision feedback equalization of doubly-selective channels,? in Proc. IEEE Global Commun. Conf, pp. 2263-2268, San Francisco, CA, Dec. 2003. [4] I. Barhumi, G. Leus, and M. Moonen, ?Time-varying FIR equalization for doubly selective channels,? in Proc. IEEE Int. Conf. on Commun., vol. 5, no. 1, pp. 3246-3250, May. 2003. [5] I. Barhumi, G. Leus, and M. Moonen, ?Time-varying FIR equalization for doubly selective channels,? IEEE Trans. Wireless Commun., vol. 4, no. 1, pp. 202-214, Jan. 2005. [6] I. Barhumi, G. Leus, and M. Moonen, ?Equalization for OFDM Over Doubly Selective Chan- nels,? IEEE Trans. Signal Process., vol. 54, no. 4, pp. 1445-1458, Apr. 2006. [7] Y. Bar-Shalom and X. R. Li, Estimation and Tracking: Principles, Techniques and Software. Norwood, MA: Artech House, 1993. [8] I. Barhumi, G. Leus, and M. Moonen, ?Estimation and direct equalization of doubly selective channels,? EURASIP Journal on Applied Signal Process., article ID: 62831, pp. 1-15, vol. 2006. [9] J. A. C. Bingham, ?Multicarrier modulation for data transmission: An idea whose time has come,? IEEE Communications Magazine, pp. 5-14, May 1990. [10] J. A. C. Bingham, ADSL, VDSL, and Multicarrier Modulation. Wiley-Interscience, 2000. [11] H.A.P. Blom and Y. Bar-Shalom, ?The interacting multiple model algorithm for systems with Markovian switching coefficients,? IEEE Trans. Automatic Control, vol. 33, No. 8, pp. 780- 783, Aug. 1988. [12] H. B?olcskei, R. W. Heath Jr., and A. J. Paulraj, ?Blind channel identifi- cation and equalization in OFDM-based multi-antenna systems,? IEEE Trans. Signal Process., vol. 50, no. 1, pp. 96-109, Jan. 2002. [13] P.A. Bello, ?Characterization of randomly time-variant channels,? IEEE Trans. Comm. Sys- tems, vol. CS-11, pp. 360-393, Dec. 1963. 138 [14] S. Benedetto and E. Biglieri, Principles of Digital Transmission with Wireless Applications. New York: Kluwer/Plenum, 1999. [15] Broadband Radio Access Networks (BRAN); HIPERLAN Type 2 Technical Specification Part 1-Physical Layer, Eur. Telecommun. Standards Inst. (ETSI), DTS/BRAN030 003-1, 1999. [16] J. K. Cavers, ?An analysis of pilot symbol assisted modulation for Rayleigh fading channels,? IEEE Trans. Veh. Technol., vol. 40, pp. 686-693, Nov. 1991. [17] R. H. Clarke, ?A statistical theory of mobile radio reception?, Bell Systems Technical Journal pp. 957-1000, July-August 1968. [18] S. N. Crozier and D. D. Falconer, ?Reduced complexity short block data detection techniques for fading dispersive channels,? IEEE Trans. Vehic. Technol., vol. 41, pp. 255-265, Aug. 1992. [19] M. Dong, L. Tong, and B. Sadler, ?Optimal insertion of pilot symbols for transmissions over time-varying flat fading channels,? IEEE Trans. Signal Process., vol. 52, pp. 1403-1418, May. 2004. [20] S. N. Diggavi, N. Al-Dhahir, A. Stamoulis, and A. R. Calderbank, ?Differential space-time transmission for frequency-selective channels,? in Proc. 36th Conf. Information Sciences Sys- tems. Princeton, NJ, pp. 859-862, Mar. 20-22, 2002. [21] S. A. Fechtel and H. Meyr, ?Optimal parametric feedforward estimation of frequency-selective fading radio channels,? IEEE Trans. Commun., vol. 42, no. 2/3/4, pp. 1639-1650, Feb./Mar/Apr. 1994. [22] G.J. Foschini and M.J. Gans, ?On limits of wireless communications in fading environment when using multiple antennas,? Wireless Personal Communications, vol. 6, no. 3, pp. 311-335, 1998. [23] G. D. Forney Jr., ?Maximum-likelihood sequence estimation of digital sequences in the pres- ence of intersymbol interference,? IEEE Trans. Inform. Theory, vol. IT-18, pp. 363-378, March 1972. [24] D. Gesbert, H. Bolcskei, D. Gore, and A. Paulraj, ?Outdoor MIMO wireless channels: capacity and performance prediction,? IEEE Trans. Commun., vol. 50, no. 12, pp. 1926-1934, 2002. [25] G. B. Giannakis, Y. Hua, P. Stoica, and L. Tong, Signal Processing Advances in Wireless and Mobile Communications, - Volume I, Trends in Channel Estimation and Equalization, Engle- wood Cliffs, NJ: Prentice-Hall, 2000. [26] G. B. Giannakis and C. Tepedelenlio?glu, ?Basis expansion models and diversity techniques for blind identification and equalization of time-varying channels,? Proc. IEEE, vol. 86, pp. 1969- 1986, Nov. 1998. 139 [27] A. Gorokhov and P. Loubaton, ?Semi-blind second order identification of convolutive chan- nels,? in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing, Munich, Germany, pp. 3905- 3908, April 1997. [28] M. S. Grewal and A. P. Andrews, Kalman filtering: theory and practice. Prentice-Hall: Engle- wood Cliffs, NJ, 1993. [29] B. Hassibi and B. M. Hochwald, ?How much training is needed in multiple- antenna wireless links?? IEEE Trans. Inf. Theory, vol. 49, no. 4, pp. 951-963, Apr. 2003. [30] T.-J. Ho and B.-S. Chen, ?Tracking of dispersive DS-CDMA channels: An AR-embedded modified interacting multiple-model approach,? IEEE Trans. Wireless Commun., vol. 6, pp. 166- 174, Jan. 2007. [31] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge, UK: Cambridge Univ. Press, 1985. [32] P. Heher, S. Kaiser, and P. Robertson, ?Two-dimensional pilot-symbol-aided channel estima- tion by Wiener filtering,? in Proc. Int. Conf. Acoust., Speech, Signal Process., vol. 3, Mnich, Germany, pp. 1845-1848, 1997. [33] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge, UK: Cambridge Univ. Press, 1985. [34] W. C. Jakes, Microwave Mobile Communications, New York: John Wiley & Sons Inc., Feb. 1975. [35] A. P. Kannu and P. Schniter, ?MSE-optimal training for linear time-varying channels,? in Proc. Int. Conf. Acoust., Speech, Signal Process., Philadelphia, USA, pp. 789-792, Mar. 2005. [36] G. K. Khaleh, ?Channel equalization for block transmission,? IEEE J. Select. Areas Commun., vol. 13, pp. 110-121, Jan. 1995. [37] G. Leus, ?On the estimation of rapidly time-varying channels,? in Proc. European Signal Pro- cessing Conf., vol. 3, pp. 2227-2230, Vienna, Austria, Sept. 2004. [38] G. Leus, S. Zhou, and G. B. Giannakis, ?Orthogonal multiple access over time- and frequency- selective channels,? IEEE Trans. Inf. Theory, vol. 49, pp. 1942-1950, Aug. 2003. [39] Z. Liu, G. B. Giannakis, S. Barbarossa, and A. Scaglione, ?Transmitantennae space-time block coding for generalizedOFDMin the presence of unknown multipath,? IEEE J. Select. Areas Com- mun., vol. 19, no. 7, pp. 1352-1364, Jul. 2001. [40] Z. Liu, X. Ma, and G. B. Giannakis, ?Space-time coding and Kalman filtering for time- selective fading channels,? IEEE Trans. Commun., vol. 50, no.2, pp. 183-186, 2002. [41] X. Ma, G. B. Giannakis and S. Ohon, ?Optimal training for block transmissions over doubly selective wireless fading channels,? IEEE Trans. on Signal Process., vol. 51, pp. 1351-1366, May. 2003. 140 [42] G. C. Porter, ?Error distribution and diversity performance of a frequency differential PSK HF modem,? IEEE Transactions on Communications, vol. COM-16, pp. 567-575, Aug. 1968. [43] J. G. Proakis, Digital Communications, 3rd edition, Singapore: McGraw-Hill Book Co, 767- 768, 1995. [44] J. G. Proakis and D. G. Manolaks, Digital Signal Processing, Third ed., Englewood Cliffs, NJ: Prentice-Hall, 1996. [45] G. Leus, I. Barhumi, and M. Moonen, ?MMSE time-varying FIR equalization of doubly- selective channels,? in Proc. Int. Conf. Acoust, Speech, Signal Process., vol. 4, pp. IV 485-488, Apr. 2003. [46] G. Leus, I. Barhumi, and M. Moonen, ?Low-complexity serial equalization of doubly-selective channels,? in Proc. of the Baiona Workshop on Signal Process. in Commun., pp. 69-74, Baiona, Spain, Sep. 2003. [47] X. Li and T. F. Wong, ?Turbo equalization with nonlinear Kalman filtering for time-varying frequency-selective fading channels,? IEEE Trans. Wireless Commun., vol. 6, no. 2, pp. 691-700, Feb. 2007. [48] X. Ma, G. B. Giannakis and S. Ohno, ?Optimal training for block transmissions over doubly selective channels,? IEEE Trans. Signal Processing, vol. 51, no. 5, pp. 1352-1366, May 2003. [49] C. F. Mecklenbr?auker, J. Wehinger, T. Zemen, F. Hlawatsch, and H. Art?es, Smart Antennas - State of the Art. EURASIP book series, Hindawi Publishing Co., Chap. 1.4., 2004. [50] M. Medard, ?The effect upon channel capacity in wireless communications of perfect and imperfect knowledge of the channel,? IEEE Trans. Inf. Theory, vol. 46, no. 3, pp. 933-946, May 2000. [51] M. Niedzwiecki, Identification of Time-Varying Processes. New York: Wiley, 2000. [52] S. Ohno and G. B. Giannakis, ?Capacity maximizing MMSE-optimal pilots for wireless OFDM over frequency-selective block Rayleigh-fading channels,? IEEE Trans. Inform. Theory., vol. 50, pp. 2138-2145, Sept. 2004. [53] M. F. Pop and N.C. Beaulieu, ?Limitations of sum-of-sinusoids fading channel simulators,? IEEE Trans. Commun., vol. 49, no. 4, pp. 699-780, Apr. 2001. [54] T.S. Rappaport, Wireless Communications: Principles and Practice. 2nd Ed., Upper Saddle River, NJ: Prentice-Hall, 2002. [55] A. M. Sayeed and B. Aazhang, ?Joint multipath-doppler diversity in mobile wireless commu- nications,? IEEE Trans. on Commun., vol. 47, pp.123-132, Jan. 1999. 141 [56] A. M. Sayeed, A. Sendonaris, and B. Aazhang, ?Multiuser detection in fast-fading multipath environment,? IEEE J. Sel. Areas Commun., vol. 16, pp. 1691-1701, Dec. 1998. [57] A.H. Sayed, Fundamentals of Adaptive Filtering. Wiley Interscience: Hoboken, NJ, 2003. [58] D. Slepian, ?Prolate spheroidal wave functions, Fourier analysis, and uncertainty - V: The discrete case,? Bell Syst. Tech. J., vol. 57, pp. 1371-1430, May-Jun. 1978. [59] M.D. Srinath, P.K Rajasekaran and R. Viswanathen, Introduction to Statistical Signal Process- ing with Applications. Prentice-Hall: Upper Saddle River, NJ, 1996 [60] A. Stamoulis, S. N. Diggavi, and N. Al-Dhahir, ?Intercarrier interference in MIMO OFDM,? IEEE Trans. Signal Process., vol. 50, no. 10, pp. 2451-2462, Oct. 2002. [61] P. Stoica and R. Moses, Introduction to Spectral Analysis, Upper Saddle River, NJ: Prentice- Hall 1997. [62] Z. Tang, R. C. Cannizzaro, G. Leus, and P. Banelli, ?Pilot-Assisted Time-Varying Channel Estimation for OFDM Systems,? IEEE Transactions on Signal Processing, vol. 55, pp. 2226- 2238, May. 2007. [63] M. K. Tsatsanis and Z. Xu, ?Pilot symbol assisted modulation in frequency selective fading wireless channels,? IEEE Trans. Signal Processing, vol. 48, pp. 2353-2365, Aug. 2000. [64] J.K. Tugnait, ?Tracking of multiple maneuvering targets in clutter using multiple sensors, IMMand JPDA coupled filtering,? IEEE Trans. Aerospace & Electronic Systems, vol. AES-40, pp. 320-330, Jan. 2004. [65] J. K. Tugnait and X. Meng, ?On Superimposed Training for Channel Estimation: Performance Analysis, Training Power Allocation, and Fram Synchronization,? IEEE Trans. Signal Process- ing, vol. 54, no. 2, pp. 752-765, Feb. 2006. [66] J. K. Tugnait, L. Tong, and Z. Ding, ?Single-user channel estimation and equalization,? IEEE Signal Processing Mag., vol. 17, no. 3, pp. 17-28, May 2000. [67] J. K. Tugnait and W. Luo ?Linear prediction error method for blind identification of period- ically time-varying channels? IEEE Trans. Signal Processing, vol. 50, no. 12, pp. 3070-3082, Dec. 2002. [68] F. Verde, ?Frequency-shift zero-forcing time-varying equalization for doubly selective SIMO channels,? EURASIP Journal on Applied Signal Process., artile ID: 47261, pp. 1-14, volume 2006. [69] H. Vikalo, B. Hassibi, B. Hochwald, and T. Kailath, ?Optimal training for frequency-selective fading channels,? in Proc. Int. Conf. ASSP, vol. 4, Salt Lake City, UT, pp. 2105-2108, May 7-11, 2001. 142 [70] X. Wang and H.V. Poor, ?Joint channel estimation and symbol detection in Rayleigh flat-fading channels with impulsive noise,? IEEE Commun. Letters, vol. 1, no. 1, Jan. 1997. [71] Z. Wang and G. B. Giannakis, ?Wireless multicarrier communications: Where Fourier meets Shannon,? IEEE Signal Processing Mag., vol. 47, pp. 29-48, May 2000. [72] Z. Wang, X. Ma and G. B. Giannakis, ?OFDM or single-carrier block transmissions?? IEEE Trans. Commun., vol. 52, pp. 380-394, Mar. 2004. [73] H. S. Wang and P.-C. Chang, ?On verifying the first-order Markovian assumption for a Rayleigh fading channel model,? IEEE Trans. Veh. Technol., vol. 45, no. 2, pp. 353-357, May. 1996. [74] X. Wang and H. V. Poor, ?Joint channel estimation and symbol detection in Rayleigh flat- fading channels with impulsive noise,? IEEE Commun. Letters, vol. 1, no. 1, Jan. 1997. [75] L. Yang, X. Ma, and G. B. Giannakis, ?Optimal training for MIMO fading channels with time- and frequency- selectivity,? in Proc. Int. Conf. Acoust, Speech, Signal Process., vol. 3, pp. 17-21, May. 2004. [76] T. Zemen and C. F. Mecklenbr?auker, ?Time-variant channel equalization via discrete prolate spheroidal Sequences,? in Proc. 37th Asilomar Conf. Signals, Syst. Comput., Pacific Grove, CA, invited paper, pp. 1288-1292, Nov. 2003. [77] T. Zemen and C. F. Mecklenbr?auker, ?Time-variant channel estimation using discrete prolate spheroidal sequences,? IEEE Trans. Signal Process., vol. 53, pp. 3597-3607, Sept. 2005. [78] Q. Zhao and L. Tong, ?Semi-Blind equalization by least squares smoothing,? in Proc. IEEE 32nd Asilomar Conf. Signals, Systems and Computers, Pacific Grove, CA, pp. 645-649, Nov. 1998. [79] Y. Zhang, M. P. Fitz, and S. B. Gelfand, ?A performance analysis and design of equalization with pilot aided channel estimation,? in Proc. 47th Veh. Technol. Conf., vol. 2, Phoenix, AZ, May 4-7, pp. 720-724, 1997. [80] L. Zheng and D. N. C. Tse, ?Communication on the grassmann manifold: A geometric ap- proach to the noncoherent multiple-antenna channel,? IEEE Trans. Inf. Theory, vol. 48, no. 2, pp. 359-383, Feb. 2002. [81] Y. R. Zheng and C. Xiao, ?Simulation models with correct statistical properties for Rayleigh fading channels,? IEEE Trans. Commun., vol. 51, pp. 920-928, Jun. 2003. [82] S. Zhou, B. Muquet, and G. B. Giannakis, ?Subspace-based (semi-) blind channel estimation for block precoded space-time OFDM,? IEEE Trans. Signal Process., vol. 50, pp. 1215-1228, May 2002. 143 [83] M. S. Zimmerman and A. L. Kirsch, ?The AN/GSC-10 (KATHRYN) variable rate data modem for HF radio,? IEEE Transactions on Communications, vol. COM-15, pp. 197-205, Apr. 1967. [84] X. Meng, Estimation of Wireless Communications Using Superimposed Training: Approaches, Analysis, and Applications, Ph.D. dissertation, Auburn University, Auburn, AL, May 2005. [85] S. He, Doubly-Selective Channel Estimation and Equalization Using Superimposed Training and Basis Expansion Models, Ph.D. dissertation, Auburn University, Auburn, AL, Aug. 2007. 144 APPENDIX A ASYMPTOTIC DPS-BEM/ SLEPIAN SEQUENCES The Slepian sequences as solutions to (2:5) are hard to work with analytically. Following [61, Sec. 5.3.1] (in a different context), we will use asymptotic expressions (N ?large?) based on some heuristic considerations (as in [61, Sec. 5.3.1]). The entries in matrix C can also be expressed as [C]y;z = 12? Z 2??Dmax ?2??Dmax e?i(y?z)!d!: (A:1) Define fl := 2?Dmax and QS := Nfl. Let fl be chosen larger than 1=N so that we get QS ? 1. (To simplify the discussion, QS and N are assumed to be even integers in what follows.) For large N, we can approximate the integral in (A:1) as (! = 2?N p): C ? 1N QS=2X p=?QS=2 a 2? N p ? a? 2? N p ? := C0; (A:2) where a(!) := [1;e?i!;:::;e?i!(N?1)]T , and ?ps are the QS + 1 largest eigenvalues of the matrix C. Based on (2:24), the eigenvectors of the matrix C0 are derived as n 1p Na( 2? N p) oQS=2 p=?QS=2 with eigenvalues ?1. Therefore, if C0 is used to approximate C, the Slepian sequences in (2:2) and (2:5) can be expressed as ?(S)q (n) = 1pNe(?i2?(q?QS=2)n=N): (A:3) [As noted in [61, Sec. 5.3.1], C0 does not approximate C in any rigorous sense.] Obviously, the approximate Slepian sequences in (A:3) are complex-valued. Since the Slepian sequences are real, we want to find a matrix with real eigenvectors that can approximate C based on 145 C0. Since C0 is a real symmetric positive semi-definite matrix with real eigenvalues ?1, it readily follows that gr := 12pN(a+a?) and gi := 12ipN(a?a?) are also the eigenvectors of C0 and they are real. From (A:2), we notice that a? 2? N p ? = a ?2?N p ? : (A:4) Therefore, we can rewrite the matrix C0 as C0 = 0X p=?QS=2 gr 2? N p ? g?r 2? N p ? + 1X p=?QS=2 gi 2? N p ? g?i 2? N p ? : (A:5) With this expression of matrix C0, the normalized eigenvectors of matrix C0 are expressed as 'g r(2?N p) ?0 p=?QS=2 and 'g i(2?N p) ?1 p=?QS=2. Thus, the corresponding approximate Slepian se- quences for n 2f0;:::;N ?1g are ?(S)q;r (n) = r 2 Ncos(2?(q ? QS 2 )n=N); ? (S) q;i (n) = r 2 Nsin(2?(q ? QS 2 )n=N): (A:6) 146 APPENDIX B MATHEMATICAL NOTATIONS ? approximately equal to ? Kronecker product 0M?N M ?N all zeros matrix a lower case letters for scalars dae integer ceiling of a bac integer floor of a jaj magnitude of a a lower case letters in bold face for column vectors kak Frobenius norm of a A upper case letters in bold face for matrices A? complex conjugate of A Ay Moore-Penrose pseudo-inverse operation AH complex conjugate transpose of A AT transpose of A [A]n;m (n;m)-th entry of A A upper case calligraphic letters for matrices argmaxx f (x) value of x for which f (x) attains its maximum argminx f (x) value of x for which f (x) attains its minimum covf?g covariance operator 147 ?(?) Kronecker delta function, defined as ?(n) = 8> < >: 1 if n = 0 0 if n 6= 0, t 2Z J0(?) the zero-order Bessel function of the first kind diag[a] diagonal matrix with a on its main diagonal Ef?g expectation operator EHf?g expectation operator with respect to H IN N ?N identity matrix max(?) maximum value operator min(?) minimum value operator O(?) big O notation: f (x) = O(g(x)) as x ! a (a 2R[?1), iff jf (x)j? M jg(x)j as x ! a for some constant M > 0 R real field trfAg trace of a square matrix A Z integer field j p?1 148 APPENDIX C ABBREVIATIONS AM amplitude modulation AR auto-regressive AWGN additive white Gaussian noise BEM basis expansion model BER bit error rate BPSK binary phase-shift keying CE-BEM complex exponential basis expansion model CP cyclic prefex CSI channel state information DAB digital audio broadcasting DFS discrete Fourier series DFS DFT discrete Fourier transform DML deterministic maximum likelihood DMT discrete multi-tone DPS discrete prolate spheroidal DPS-BEM discrete prolate spheroidal basis expansion model DS-CDMA direct sequence - code division multiple access DSL digital subscriber line DVB digital video broadcasting 149 FB feedback FF feedforward FFT fast Fourier transform FIR finite impulse response FM frequency modulation IBI interblock interference IMM interacting multiple model ISBI inter-subblock interference ISI inter-symbol interference LS least squares LTI linear time-invariant MAC media access control MC multicarrier MIMO multiple-input multiple-output ML maximum likelihood MLSE maximum likelihood sequence estimation MSE mean square error MMSE minimum mean square error m.s. mean-square MUI multiple-user interference 150 NCMSE normalized channel mean square error OFDM orthogonal frequency division multiplexing PAM pulse amplitude modulation pdf probability density function PN pseudo-noise PSAM pilot symbol aided modulation QPSK quadrature phase-shift keying RF Radio Frequency SIMO single-input multiple-output SISO single-input single-output SNR signal-to-noise ratio TI time invariant TM time-multiplexed TV time-varying WSSUS wide sense stationary uncorrelated scattering 151