1 THESIS FOR THE DEGREE OF MASTER OF SCIENCE IN COMMUNICATION ENGINEERING Efficient Feedback Design for MIMO systems MUHAMMAD UMER ZIA Department of Signal and Systems CHALMERS UNIVERSITY OF TECHNOLOGY Göteborg, Sweden, May 2, 2011 Examiner: Prof. Thomas Eriksson 2 ABSTRACT Feedback in a communication system enables the transmitter to employ channel adaptive signaling and avoid interference which leads to improvements in all performance metrics. In the case of a multiple-input multiple-output (MIMO) channel, research has repeatedly shown that by sending small number of information bits as feedback about the channel conditions to the transmitter, optimal channel adaptation can be achieved. MIMO feedback specifies a precoding matrix which activates the dominant channel modes at the transmitter. When the feedback channel is severely limited, important issues are how to quantize and compress the information needed at the transmitter. In this process the design should balance amount of feedback, its complexity and associated performance. This thesis addresses the efficient use of channel state information to improve the communication systems by employing precoding matrix transformation and quantizer design. Key words:-Limited feedback, MIMO systems, Vector quantizer, MIMO precoder design, procoder matrix transformations. 3 Acknowledgements I would like to thank ALLAH Almighty who gave me courage to complete this thesis work. Afterwards, I would like to thank my supervisor Prof. Thomas Eriksson for giving me opportunity to work on this interesting topic and giving me enough time for guidance as this topic was new to me. His valuable guidance during the entire thesis period developed the understanding of the subject and made it possible for me to achieve the required results. I would like to thank all my teachers especially Tomas Mckelvey and Nima Seifi for their guidance and advice in the thesis. Finally I would like to say thanks to my parents and siblings for their love and support. Muhammad Umer Zia Göteborg, Sweden, May 2, 2011 4 Abbreviations used in the text MIMO Multiple-Input Multiple-Output SISO Single-Input Single-Output AWGN Additive White Gaussian Noise BER Bit Error Rate QPSK Quadrature Phase Shift Keying QAM Quadrature Amplitude Modulation CSI Channel Side Information CSIR Channel Side Information at the Receiver CSIT Channel Side Information at Transmitter ZMSW Zero-Mean Spatially White SVD Singular Value Decomposition LBG Linde-Buzo-Gray MSE Mean Squared Error WMSE Weighted Mean Square Error MAE Mean Absolute Error DM Delta Modulation SNR Signal to Noise Ratio 5 List of Figures Figure 1-1.1: MIMO Channel ............................................................................................. 7 Figure 1-2: MIMO Feedback [1] ........................................................................................ 9 Figure 2-1: MIMO channel transformation [2] ................................................................. 12 Figure 2-2: SISO channel [2] ............................................................................................ 12 Figure 3-1: Vector quantizer structure [6] ........................................................................ 21 Figure 4-1: Feedback scheme based on Givens rotation .................................................. 24 Figure 4-2: Givens Rotation, (C, θ) Data points (Green) Codebook points (Red) ........... 25 Figure 4-3: Jacobi Rotation, (θ1, θ2) Data points (Green) Codebook points (Red) .......... 25 Figure 4-4: QPSK plot, Givens feedback, Quantization level 4 ....................................... 26 Figure 4-5: QPSK plot, Givens feedback, Quantization level 8 ....................................... 26 Figure 4-6: QPSK plot, Givens feedback, Quantization level 16 ..................................... 27 Figure 4-7: QPSK plot, Givens feedback, Quantization level 32 ..................................... 27 Figure 4-8: QPSK plot, Jacobi feedback, Quantization level 4 ........................................ 27 Figure 4-9: QPSK plot, Jacobi feedback, Quantization level 8 ........................................ 27 Figure 4-10: QPSK plot, Jacobi feedback, Quantization level 16 .................................... 28 Figure 4-11: QPSK plot, Jacobi feedback, Quantization level 32 .................................... 28 Figure 4-12: Error vector histogram, Givens rotation level 2 ........................................... 28 Figure 4-13: Error vector histogram, Jacobi rotation level 2 ............................................ 29 Figure 4-14: Error vector histogram, Givens rotation level 32 ......................................... 28 Figure 4-15: Error vector histogram, Jacobi rotation level 32 .......................................... 29 Figure 4-16: Mean Square error, Givens and Jacobi rotation ........................................... 29 Figure 4-17: Mean Square error, Givens and Jacobi rotation ........................................... 30 Figure 4-18: SNR curve .................................................................................................... 30 Figure 4-19: SNR AWGN vs. SNR f(MSE), Quantization level 16 ................................ 31 Figure 4-20: QPSK plot, SNR 20dB and quantization noise of 16 level vector quantizer. ........................................................................................................................................... 31 Figure 4-21: QPSK plot, SNR 15dB and quantization noise of 16 level vector quantizer. ........................................................................................................................................... 31 Figure 4-22: QPSK plot, SNR 10dB and quantization noise of 16 level vector quantizer. ........................................................................................................................................... 32 Figure 4-23: QPSK plot, SNR 5dB and quantization noise of 16 level vector quantizer. ........................................................................................................................................... 32 Figure 4-24: SNR f(MSE) vs. W, Quantization level 8 .................................................... 33 Figure 4-25: SNR f(MSE) vs. W, Quantization level 16 .................................................. 33 Figure 4-26: SNR vs.BER ................................................................................................. 34 6 Contents CHAPTER 1 ......................................................................................................... 7 1 Introduction ......................................................................................................................................... 7 1.1 MIMO Channel Model ..................................................................................................................... 7 1.2 MIMO Feedback Model ................................................................................................................... 8 1.3 MIMO Functions .............................................................................................................................. 9 1.4 Scope .............................................................................................................................................. 10 CHAPTER 2 ....................................................................................................... 11 2 Matrix Transformations ................................................................................................................... 11 2.1 Singular Value decomposition ....................................................................................................... 11 2.2 Householder Transformation .......................................................................................................... 13 2.3 Givens Rotation .............................................................................................................................. 15 2.4 Jacobi Rotation ............................................................................................................................... 16 CHAPTER 3 ....................................................................................................... 20 3 Quantizer Design ............................................................................................................................... 20 3.1 Introduction .................................................................................................................................... 20 3.2 Distance Measure ........................................................................................................................... 20 3.3 Vector Quantizer ............................................................................................................................ 21 3.4 LBG Algorithm .............................................................................................................................. 22 CHAPTER 4 ....................................................................................................... 24 4 Simulation Results and Discussion .................................................................................................. 24 4.1 System Model ................................................................................................................................ 24 4.2 Transmit Precoding ........................................................................................................................ 24 4.3 Channel Modeling .......................................................................................................................... 24 4.4 Feedback Loop ............................................................................................................................... 25 4.5 Receiver Shaping ........................................................................................................................... 26 4.6 Error Analysis ................................................................................................................................ 26 4.7 Error Histogram ............................................................................................................................. 28 4.8 Mean Square Error and SNR .......................................................................................................... 29 4.9 AWGN Noise ................................................................................................................................. 30 4.10 Scaling factor ............................................................................................................................. 32 5 Conclusion ......................................................................................................................................... 34 6 Future Work ...................................................................................................................................... 34 7 References .......................................................................................................................................... 36 7 Chapter 1 1 Introduction MIMO technology has attracted attention in wireless communications, as it offers considerable increases in data throughput, enhanced resistance to interference, and reduces the deleterious effects of fading in wireless communication channels. MIMO systems provide a number of advantages over single-antenna-to-single-antenna communication. The two most vital advantages are reduction in sensitivity to fading by provided by multiple spatial paths and increase in capacity. The next sections explain MIMO channels and feedback models which are the bases of this technology. 1.1 MIMO Channel Model We consider a narrowband, point-to-point MIMO channel which consists of Mt transmit and Mr receive antennas as shown in figure 1.1 Figure 1-1.1: MIMO Channel The transmit data streams go through Mt × Mr paths which can be modeled by a channel matrix H. The MIMO system can be represented by the discrete time model as shown in equation 1.1.                                                                           MrMrMrMtMr Mt Mr N N X X HH HH Y Y . . . . . . ....... . . . . . . . . . ...... . . . 11 1 1111 (1.1) 8 where X is the input vector and N is an AWGN vector. We can write equation 1.1 by simply representing the vectors as bold letters as shown in equation 1.2 NHXY  The knowledge of the channel gain matrix H at the receiver, referred as channel state information at the receiver (CSIR) [2] can be determined easily by sending a pilot sequence for channel estimation. In SISO channels the effect of a propagation environment on a radio signal can be modeled by Rayleigh fading. Rayleigh fading is a reasonable model when there are many objects in the environment that scatter the radio signal before it arrives at the receiver. In a MIMO channel each element of the channel matrix represent a SISO path hence a MIMO channel matrix can also be modeled by Rayleigh faded elements. The Rayleigh fading model assumes that the magnitude of a signal that has passed through multipath fading channel will vary randomly in an unpredictable manner. When there are a large number of paths, and there are many objects in the environment that scatter the radio signal, the central limit theorem can be applied to model the impulse response of the channel as a complex-valued Gaussian random process. When the impulse response is modeled as a zero mean complex-valued Gaussian process the envelope of the channel response will therefore be Rayleigh distributed. In the Rayleigh flat fading channel model the channel is assumed to be independent and randomly varying in time for each transmit antenna. The real and imaginary parts of each complex element Hij of the channel matrix can be modeled by Gaussian distribution N having mean μ(Hij) =0 and variance σ2(Hij) =1/2 as represented by equation 1.3   )2/1,0(2/1,0 21 NiNHij  The Rayleigh flat channel model will be used in the simulations because it is simplest fading model in wireless environments and it gives good realizations of Raleigh fading. This work can be extended by including Doppler spread and frequency selective fading which are exhibited in different types of environment. 1.2 MIMO Feedback Model The availability of channel state information at the transmitter substantially improve capacity, quality, and reduce interference. The transmitter can customize the transmitted waveforms to improve the performance of the downlink channel in multi-input multi- output (MIMO) communication system. The transmitter can learn about the channel through a low rate feedback control channel which supplies channel state information (CSI). The feedback path can provide partial or complete channel state information to transmitter. The systems which supply partial CSI are commonly referred as limited or finite-rate feedback systems. If these systems are carefully designed, there benefits are nearly identical to systems having perfect channel knowledge at the transmitter. (1.2) (1.3) http://www.google.se/search?hl=sv&&sa=X&ei=4xc6TYP8Fs3zsgaOn9XzBg&ved=0CCYQvwUoAQ&q=benefit&spell=1 9 A communication link with a feedback control channel is shown in figure 1.2 [1]. After demodulation and channel estimation, the data and CSI is extracted. The CSI is compressed by transformation and quantization. This compressed CSI is send back to transmitter through finite rate control pipe. The transmitter uses this information to customize the transmitted signal for the channel. The feedback channel rate R is typically much smaller than the data pipe rate C to maximize efficiency. Figure 1-2: MIMO Feedback [1] The designing of feedback is an important issue because the feedback rate is fixed and is generally small to reduce system overhead. Moreover there are several channel parameters to send back. If the MIMO wireless channel is changing very fast over time due to mobility of the transmitter or receiver, frequent feedback is needed. All these issues emphasize the need of selected and limited feedback (or quantized feedback) with minimum error [1]. The imperfections like quantization error and delay in feedback reduce the performance of closed-loop MIMO systems. All above mentioned facts highlight the importance limited and selected channel state information which should be send back through feedback channel. We will discuss instantaneous feedback methods in this thesis i.e. those methods that attempt to inform the transmitter about the instantaneous channel state. Based on the framework illustrated in figure 1.2 our goal is to compress the channel coefficients by applying quantization algorithms to reduce the feedback. We will review the work done in this field which includes various combinations of transformation and quantization techniques and provide a synopsis of the role of limited feedback in the standardization of next generation MIMO systems. 1.3 MIMO Functions MIMO can be categorized functionally into three main categories. 1) Precoding 2) Spatial multiplexing 3) Diversity coding. 1. 3.1 Precoding Precoding is a multi-stream beamforming technique in which the user’s signal is multiplied with complex weights that adjust the magnitude and phase of the signal to and from each antenna. The result of precoding is the output from the array of antennas that forms a transmit/receive beam in the desired direction and minimizes the output in other http://en.wikipedia.org/wiki/Precoding http://en.wikipedia.org/wiki/Precoding 10 directions. The benefits of this are increase in the received signal gain, by making signals emitted from different antennas add up constructively, and to reduce the multipath fading effect. Note that precoding requires knowledge of channel state information (CSI) at the transmitter. 1. 3.2 Spatial multiplexing In spatial multiplexing, a high rate signal is split into multiple lower rate streams and each stream is independently encoded and transmitted from each of the multiple transmit antennas. These signals reach the receiver with different spatial signatures and the receiver separate these streams into parallel channel. Spatial multiplexing can be used with or without channel knowledge availability at transmitter. Spatial multiplexing can also be used for simultaneous transmission to multiple receivers. 1. 3.3 Diversity Coding In diversity coding, a single stream is coded using orthogonal coding and transmitted to exploit the independent fading in the multiple antenna links to enhance signal diversity. Diversity coding is generally implemented by using space time codes. Diversity coding techniques require no channel knowledge at the transmitter. 1.4 Scope The focus of this project is on the performance gain called multiplexing gain. The multiplexing gain of a MIMO system results from the fact that a MIMO channel can be decomposed into a number R of parallel independent channels. By multiplexing independent data onto these independent channels, we can get an R-fold increase in data rate in comparison to a system with just one antenna at the transmitter and receiver. http://en.wikipedia.org/wiki/Spatial_multiplexing http://en.wikipedia.org/wiki/Diversity_Coding 11 Chapter 2 2 Matrix Transformations In this chapter the different matrix transformations by which we can reduce size of the feedback matrix will be discussed. The transformation coefficients are send back in feedback which can generate the required feedback matrix at the receiver. The core idea behind these reversible transformations is to introduce zeros in the matrix, which are not needed to be send back. The singular value decomposition will be described in section 2.1 which can be used to convert the MIMO channel to independent SISO channels and provides us the optimal precoding matrix V. The Householder and Givens transformations described in section 2.2 and 2.3 use the SVD decomposition. In section 2.4 the Jacobi rotation is described. Instead of transmit precoding and receiver shaping with U and V, the Jacobi rotation matrix can be used to diagonalize the channel correlation matrix. 2.1 Singular Value decomposition A MIMO system can be used to achieve multiplexing gain by the decomposition of MIMO channel in to parallel independent channels [2]. In this section we will elaborate how to obtain independent MIMO channels by the help of singular value decomposition (SVD) of channel matrix H. Consider a MIMO channel with Mr × Mt channel gain matrix H and let RH denote the rank of H. According to matrix theory we can obtain singular value decomposition (SVD) of any matrix. Equation 2.1 shows decomposition channel matrix H by applying SVD HVUH  where U is Mr× Mr unitary matrix, V is Mt × Mt unitary matrix and Σ is a Mr×Mt diagonal matrix of singular values σi . The singular value σi is equal to the ith Eigen values of HHH and RH of these singular values are nonzero, where RH is the rank of the matrix H. We can get parallel decomposition of the channel if we apply transformation on the channel input X and output Y , these transformations are called transmit precoding and receiver shaping respectively [2]. Transmit precoding is a linear transformation which convert X ~ to X as shown in equation 2.2. XVX H ~  (2.2) The vector X ~ is multiplied with VH to generate X which is antenna input vector. In receiver shaping the channel output Y is multiplied with UH to split MIMO channel into RH (2.1) 12 parallel single-input single-output (SISO) channels with input X ~ and output Y ~ . The mathematical derivation of the process is shown in equation 2.3(a-e) [2]. )( ~ NHXUY H  (2.3a) )( NVXUU H  (2.3b) ) ~ ( NXVVUU HH  (2.3c) NUXVVUU HHH  ~ (2.3d) NX ~~  (2.3e) where Σ is the diagonal matrix of singular values of H with σi on the ith diagonal. By the help of this decomposition we can activate the dominant Eigen modes, and the resulting parallel channels do not interfere with each other. The MIMO transformation and resultant SISO channels with independent gains are shown in figure 2.1 and figure 2.2 respectively Figure 2-1: MIMO channel transformation [2] Figure 2-2: SISO channel [2] The multiplication by a unitary matrix does not change the distribution of noise and MIMO channel can support RH times multiplexing gain by sending independent data across each of the parallel channels. However, the channels have varying SNR due to the transform, so the capacities of the channels will be different. In a nutshell, SVD precoding in MIMO communications is important for interference pre- cancellation, and singular value decomposition (SVD) approach also leads to straightforward transmission architecture. To achieve multiplexing gain the transmit beamforming matrix V which is obtained through singular value decomposition is 13 required at the transmitter so matrix V is send back through feedback channel in point- to-point MIMO systems. 2.2 Householder Transformation The Householder transformation can be used as reversible matrix transformation to selectively introduce zeros in matrix as discussed in [3]. As the transformation is reversible, at the receiver it can be reversed with the help of transformation coefficients. It is important to note that the transformation coefficients are fewer then the feedback matrix elements so the process saves feedback channel bandwidth. Householder transformation is a linear transformation that describes a reflection about a plane. By the help of Householder reflector we can perform orthogonal triangularization process which reduces a matrix to triangular form by a sequence of orthogonal matrix operations. The Householder vector can be defined in equation (2.4) as xexv  1 (2.4) where e1 is a unit vector. The Householder reflection matrix can be constructed from v as shown in equation 2.5 vv vv IF * * 2 (2.5) If any vector x is multiplied by Householder reflection matrix F then it is reflected in hyper-plane perpendicular to v. To transform any matrix A in to upper triangular form the matrix should be multiplied by systematically design orthogonal matrices Qk such that the product (Qn, Qn−1 . . . Q1)*A is upper-triangular matrix. Each Qk is an orthogonal matrix of the form represented by equation 2.6        F I Qk 0 0 (2.6) where I is the (k − 1) × (k − 1) identity matrix. Each matrix Qk is designed to introduce zeros below the diagonal in column k while preserving previously introduced zeros. The method of the reversible Householder transformation is described in [3].This method is based on iterative quantization of beam forming matrix. The compression is achieved by 1) Sending transmit beam-forming vectors V instead of the channel matrix. 2) Feeds back the beam-forming vectors only for the active spatial channels. 3) Using house holder matrix repeatedly to reduce the size of vector by one in each iteration. 4) Use vector quantizer to quantize information. After Householder iterations the matrix becomes identity matrix except the phase shifts which need not to be send back according to [3]. The Householder reflection can be applied on each vector, and then the vector is quantized before sending it to transmitter. The phase shifts are not send back so the reconstructed V matrix may not necessarily be same as original. It is proven that by multiplying with global phase eiθ does not affect 14 the close loop MIMO system [3]. Moreover if the off diagonal entries of columns are made zero by applying transformation on unitary matrix, the rows automatically transformed in to zero. At the transmitter side beamforming matrix V is reconstructed. In reconstruction process the lowest dimension vector is combined with identity vector and recursively constructed by multiplying with F at each step as shown in equation 2.7                         0 0 0 1 0 00 001 32 1 VF FV The Householder matrices F2 and F1 can be constructed from V2 and V1 using the equation (2.8) 2 2 w ww IF H  (2.8) where 1evw  The pseudo algorithm described in [3] is as follows "1: Compute singular value decomposition of the downlink channel matrix H with size m by n as (1), and obtain the first k columns of the beam-forming matrix V, where k is the number of active spatial channels. 2: Let V=V1:k which is a temporary matrix and is formed by the first k columns of V. 3. For i = 1: min (k, n-1) 3.1. Let vi =Vi: 1, which is the first column of V. 3.2. Quantize vi by finding i H ciu vuargmax Vi  where ci is a codebook of unit n-i+1 vectors. 3.3. Record the index of vi in the codebook for feedback 3.4 Construct a Householder reflection matrix as 2 2 w ww IF H  where 1evw  and e1 is the unit vector with all zero elements except the first equal to one. 3.5. Conduct Householder reflection on V as V=FiV. To reduce complexity, one only needs to compute columns and rows of V other than the first one. 3.6. Update V=V2: n-i+1, 2:k End " (2.7) 15 2.3 Givens Rotation The Givens rotation is used to selectively introduce zeros into a matrix to make it an identity matrix. The Givens rotation can be applied to the V matrix to reduce the size of matrix by half as the transformation parameters are fewer than the matrix elements. The matrix V can be reconstructed by using transformation parameters. A real Givens rotation is shown in equation 2.9                    0 r b a cs sc (2.9) where c and s represent and respectively and )/(tan 1 ab 22 bar  . A complex Givens rotation can be formulated by help of two rotation angles. Equation 2.10 shows complex Givens rotation and its effect on complex matrix                       0)( )( 21 21 21 1 2 1 2 11 irr ibb iaa ces esc i i   (2.10) The angles θ1 and θ2 can be determined from input vector as shown in equation 2.11c. 2 2 2 1 aaRa  , and         1 21tan a a a (2.11a) 2 2 2 1 bbRb  , and         1 21tan b b b (2.11b)           a b R R1 1 tan , and ba  2 (2.11c) As compared to Householder reflection the Givens based unitary precoding method has better performance in terms of complexity, feedback resources and quantization noise [4]. It is an SVD-based MIMO pre-coding technique, the MSS is required to send beam- forming matrix V. According to the [4] by successful Givens rotation we can get the identity matrix as shown in equation 2.12 VGGGGI NN 1,21,31 .......   (2.12) Please note that identity matrix in equation 2.12 contains entries in the diagonals which are termed as phase shifts. These phase shifts are not sent in feedback as close loop MIMO system is unaffected if rotated by a phase shift [4]. The compression is achieved by sending transformation parameters i.e. C1 and θ2 instead of matrix V. These parameters are real as compared to complex elements in Householder transformation. The matrix V reconstructed by implementing the equation 2.13 IGGG H NN HH 1,1,31,2r .... V  (2.13) 16 2.4 Jacobi Rotation The Jacobi method consists of a sequence of orthogonal transformation designed to annihilate off-diagonal matrix elements. It can be used to diagonalize autocorrelation matrix R by transmit precoding and receiver shaping with Jacobi matrix J and JH respectively [5]. A Jacobi rotation is just a plane rotation Qkl which annihilate element (k,l) of an object matrix. Successive transformations undo previously set zeros, but the off-diagonal terms eventually get smaller and smaller, until they get nearly zero, leftover is the only is the diagonal with Eigen values [5]. The method is for symmetric matrices, it’s simple and stable algorithm but it becomes slow when matrix grows larger. For the real matrices the Jacobi rotation is defend in equation 2.14                     1..0 .. . . . . . 0..1 cs sc Qkl (2.14) For any matrix A (only 4 elements are shown which are important for transformation) as given in equation 2.15                    *..* .. . . . . . *..* qqqp pqpp aa aa A (2.15) The rotation of the form kl T kl AQQ will transform matrix A in to A as shown in equation 2.16                    ** .0. . . 0 . . . *..* ll kk a a A (2.16) 17 The T klQ multiplication from the left changes only rows p and q of matrix A while multiplication of klQ from the right changes only columns p and q. The changed elements of matrix A are shown in equation 2.17.                    nqnp qnqqqpq pnppppp qp aa aaaa aaaa aa A 1 1 11 (2.17) By multiplying kl T kl AQQ and using the symmetry of A, we can get the required elements shown in equation 2.18(a-e). rqrprp sacaa  (2.18a) rprqrq sacaa  (2.18b) pqqqpppp scaasaca 222  (2.18c) pqqqppqq scaacasa 222  (2.18d) )()( 22 qqpppqpq aascasca  (2.18e) As Jacobi method introduce zeros in off-diagonal elements so by setting pqa = 0 in equation 2.18e to get 2.19 pq ppqq a aa sc sc 2 )( 2 )( 2cot 22     (2.19) Setting t = s/c and θ = 2cot equation 2.19 can be written in form of quadratic equation as shown in equation 2.20 0122  tt (2.20) By solving for t we get two roots shown in equation 2.21 12  t (2.21) By rationalization we can write it in more convenient form 1 1 2    t and in negative case 1 1 2     t (2.22) 18 1 )( 2    sign t (2.23) We can evaluate s and c as shown in equation 2.21 and 2.22 1 1 2   t c (2.24) cts  (2.25) Jacobi rotation for complex channel matrix is defined by J and given in equation 2.26         cs esec J ii 1 22 2 )()( ),(   (2.26) where parameters θ and θ2 can be obtained by the equations 2.27 and 2.28 respectively 01)tan()tan( 1 12 11222 1     r rr (2.27) 12 12 r r e i  (2.28) The Jacobi rotation is implemented as precoder transformation in [5] for 2*2 MIMO channel. In Jacobi rotation first channel correlation matrix is computed. The channel correlation matrix is obtained by multiplying the hermitian transpose of the estimated channel response matrix HH with H itself as given by equation 2.29 HHR H (2.29) The estimated channel response matrix H can be decomposed using SVD as shown in equation 2.30 HUDVH  (2.30) By putting value of equation 2.30 in equation 2.29 )()( HHH UDVUDVR  (2.31) As U and V are unitary and (AB) H = BHAH so equation 2.31 becomes HVVDR 2 (2.32) Comparing equation 2.30 and 2.32 it is obvious that diagonalizing the channel response matrix H to find the matrix V is equivalent to diagonalizing the channel correlation matrix R as stated in [5]. Jacobi rotation is used to perform the matrix diagonalization of channel correlation matrix R such that 2DRJJ H  (2.33) 19 Jacobi matrix parameters θ1 and θ2 are send in the feedback which is same amount of feedback as send by Givens rotation i.e. 2 parameter per rotation. As V, the J matrix is also unitary in nature. The paper [5] also describes smart procedure for updating feedback, managing delay and differential feedback. 20 Chapter 3 3 Quantizer Design 3.1 Introduction In this chapter quantization techniques for MIMO feedback will be discussed. Quantization is the process of mapping very large set of discrete or continuous values by a relatively small and finite set of values. The amount of compression has a direct effect on design of the quantizer and the quantizer has significant impact on the degradation of information incurred in the process. The quantizer structure consists of encoder and decoder mapping. The encoder divides the source output values into a number of intervals. These intervals in which all the source output lies can be represented by distinct codewords. There could be a lot of source output values that can fall in any given interval. The amount of compression achieved by quantizer is described in terms of rate and measured in bits/sample. Knowledge of the codeword only tells us the interval to which the sample value belongs and gives no clue of actual sample value, this makes encoder mapping irreversible. The difference between the original signal and the quantized signal is called quantization noise and is generally measured by distortion measures which are described in section 3.2. 3.2 Distance Measure The distance measures provide us a way to find the closest match between the code vectors and the input vector. The most commonly used distance measures are described in the following sections 3. 2.1 Mean Squared Error (MSE) The mean squared error (MSE) is a method of quantifying the difference between estimated and the true value. The mean square error is defined as square of the Euclidean distance between two vectors. Mean square error is mathematically shown in equation 3.1 )ˆ( 1 1    n i ii xx n MSE 3. 2.2 Weighted Mean Square Error In weighted mean square error, each error vector weighted according to some criteria. The weighted mean square error is mathematically shown in equation 3.2 )ˆ( 1 1    n i iii xxw n WMSE (3.1) (3.2) 21 3. 2.3 Mean Absolute Error The mean absolute error is a used to measure how outcomes are close to the actual value. The mean absolute error is the average of the absolute errors as show in equation 3.3    n i ii xx n MAE 1 )ˆ( 1 3.3 Vector Quantizer A vector quantizer Q maps vectors from an input set of vectors X to a finite set of codebook vectors C. Figure 3.1 shows the basic structure of the vector quantizer. Figure 3-1: Vector quantizer structure [6] Encoding sequences of samples instead of encoding individual samples separately provides codes having lower distortion for a given rate [6]. So instead of representing a single sample of the source output by a single codeword, a vector quantizer group source outputs together and encode them as a single block. After grouping lies the core part of vector quantizer i.e. generation of appropriate codebook and finding the closest vector that matches the codebook. The decoding is simpler than encoding as it mainly consists of a table lookup. This scheme is excellent for the applications in which the resources available for decoding are considerably less than encoding. At both sides of the encoder and decoder of vector quantizer, we have a same set of N- dimensional code vectors called the codebook which is selected to be representative of the vectors we generate from the source output. Each code vector of the codebook is assigned a binary index. The number of bits for binary index depends upon the number of vectors. At the encoder, the vector quantizer compares the input vector to each code- vector in order to find the code-vector closest to the input vector. After finding the closest vector the binary index which represents the closest vector is send as representative of the input vector. As the decoder has exactly the same codebook with same index and it can retrieve the code-vector from binary index. (3.3) 22 Most algorithms for obtaining codebooks are based on one particular approach called Linde-Buzo-Gray (LBG) algorithm [6]. The LBG algorithm needs training sequence for codebook generation, this training sequence can be obtained from a large database of sample output values. For example, if the source is a speech signal, then the training sequence can be obtained by recording several long voice conversations. This training sequence should be sufficiently large so that all the statistical properties of the source are captured by the training sequence [7]. The performance of vector quantizer can be measured by a distortion function. The most common methods of quantifying distortion are described in section 3.2. Suppose we have a codebook of size K, and L dimension the input vector. In order to specify which code-vector is selected log2(K) bits per vector are required. As each code vector contains L source output samples, so the number of bits per sample would be log2(K/L) which is expression for rate of vector quantizer. The optimal VQ design is associated with finding a codebook that partition the vector source in to number of code vectors such that mapping result in the smallest average distortion [6]. This requirement leads to design conditions given in section 3.3.1 and 3.3.2 3. 3.1 Nearest Neighbor Condition The encoding region Sn should consist of all vectors that are closer to code vector Cn than any of the other code vectors. A tie-breaking procedure will decide for those vectors which lie on the boundary of two regions [6]. This condition is expressed in equation 3.4  NnncxcnxxSn ,......2,1: 22  (3.4) 3. 3.2 Centroid Condition The code vector Cn should be equal to average of all those training vectors that are present in encoding region Sn. Also at least one training vector should belong to each encoding region. This condition is expressed in equation 3.5     nm nm Sx Sx m n x C  1 (3.5) 3.4 LBG Algorithm In this algorithm the first centroid is computed by taking the average of the entire training sequence. This initial code vector of the training set is then split into two by adding a fixed perturbation vector ε. The codebook now contains two code vectors and iterative algorithm starts with these two vectors as the initial codebook. The process is repeated until the desired number of code vectors or specific distortion is obtained. This algorithm can be summarized in following steps [8] 23 “Given number of code vectors N. Let  be a “small” number. 1. Let N = 1 and    M m mXMX 1 * 1 /1 2. Splitting: For i = 1, 2, . . . ,N set * 1 0 * 1 0 )1( )1( XX XX iN i      Set N = 2N. 4: Iteration: Let *0 aveave   . Set the iteration index i = 0. i) For m = 1, 2….., M, find the minimum value of 2 )(i nm XX  overall n = 1, 2, . .N. Let n* be the index which achieves the minimum. Set i *nm X )Q(X  . ii) Update the code vector      )( )( )(: )(:1 1 i n i n XXmQXm XXmQXm m i n X X iii) Set i = i + 1. iv) Calculate    m M mmd i ave XQXM 1 2 )(/1 v) 11 /   i ave i ave i ave  > ε go to step i. vi) Set i aveave  * for n = 1, 2. . . N set i nn XX * as the final code vectors. 5. Repeat Steps 3 and 4 until the desired number of code vectors is obtained." (3.6) (3.7) (3.8) (3.9) (3.10) 24 Chapter 4 4 Simulation Results and Discussion 4.1 System Model To investigate quantization noise and its effect on the system performance feedback schemes based on Givens and Jacobi rotation with vector quantizer in the feedback loop are considered in this chapter. It is already been proven that Givens rotation outperforms Householder transformation in terms of feedback resources and SNR [4]. Both system designs are discussed at transmitter, channel and receiver side. The schematic diagram of the system model based on Givens rotation is shown in figure 4.1. Figure 4-1: Feedback scheme based on Givens rotation 4.2 Transmit Precoding In Givens rotation model the QPSK symbols are formed with the help of random input bits. The transmit precoding by ̂ matrix is performed on QPSK symbols. The ̂ matrix is quantized version of V matrix obtained from SVD of channel. While in feedback based on Jacobi rotation the J matrix is used as precoding matrix. 4.3 Channel Modeling Computer based simulations require the mathematical representation of the channel, i.e. the channel model. From figure 4.1 it can be easily depicted that accurate and realistic method for generation of channel matrix H for codebook training as well as for system modeling is needed. As discussed earlier in chapter one, we can model input /output relationship of the channel by equation 4.1 NHXY  where X is input, N is AWGN process and H is channel matrix. For measuring quantization noise the AWGN noise is neglected the beginning. After modeling the effect of quantization noise, AWGN is included to see how system is affected by both noises. (4.1) 25 We assume that perfect channel knowledge is available at the receiver, moreover the block-fading channel model is assumed in this work. In block-fading channel model the channel consists of a finite number of blocks of N symbols. The fading gains of these blocks are independent and constant for single block. Block-fading channel model assumes slowly varying fading in time. 4.4 Feedback Loop As discussed earlier, the feedback loop sends channel state information (precoder matrix) to the transmitter. For the feedback scheme based on Givens rotation quantized version of Givens rotation parameter (C, θ) are transmitted back which construct quantized V matrix at transmitter. This quantized V matrix introduces quantization noise in the system. In case of Jacobi rotation system model the quantized version of matrix J parameters (θ1,θ2) are transmitted back which construct quantized J at transmitter. Most of the details regarding vector quantization and codebook training are already discussed in chapter 3. Here the distribution of (C,θ) and codebook points for Givens rotation scheme is presented to see how the implemented vector quantizer represent the cluster densities. Figure 4.2 shows the distribution of (C,θ) and codebook points. Figure 4-2: Givens Rotation, (C, θ) Data points (Green) Codebook points (Red) The distribution of (θ1, θ2) and codebook points for Jacobi rotation scheme is shown in figure 4.3 Figure 4-3: Jacobi Rotation, (θ1, θ2) Data points (Green) Codebook points (Red) In figure 4.2 we can clearly see that the point density is gradually increasing in y-axis direction which represents distribution of C, so we have more representative points of code book representing the cluster density near 0.8 value at y-axis. The points (θ1,θ2) 26 and code book points are more evenly distributed as compared to (C,θ) vector. The less dense clusters imply more quantization error which will be analyzed in section 4.6. 4.5 Receiver Shaping In Given based feedback the received data is multiplied with U matrix which is obtained from SVD of channel matrix H. The output of receiver shaping is SISO channels with λi gain for each “i” stream. In Jacobi rotation hermitian of the J matrix is multiplied with autocorrelation matrix R to get SISO channels with 2 i gain for each “i” stream. 4.6 Error Analysis The QPSK plots, error histogram and mean square error curve for both systems are examined to analyze error in both systems. In QPSK symbols are encoded by changing the phase of the transmitted waveform so any change in phase of received symbols represents noise in the system. As the quantization noise is similar in both streams so the single stream is examined in error analysis. The QPSK plots of different quantization levels for both feedback schemes are shown in figure 4.4-4.7 and figure 4.8-4.11 respectively. Figure 4-4: QPSK plot, Givens feedback, Quantization level 4 Figure 4-5: QPSK plot, Givens feedback, Quantization level 8 27 Figure 4-6: QPSK plot, Givens feedback, Quantization level 16 Figure 4-7: QPSK plot, Givens feedback, Quantization level 32 Figure 4-8: QPSK plot, Jacobi feedback, Quantization level 4 Figure 4-9: QPSK plot, Jacobi feedback, Quantization level 8 28 Figure 4-10: QPSK plot, Jacobi feedback, Quantization level 16 Figure 4-11: QPSK plot, Jacobi feedback, Quantization level 32 The plots of Givens and Jacobi rotation show that sufficient reduction in quantization error can be achieved by 8 level quantizer. The patterns in quantization noise in almost all plots are observed because of symmetry in quantized V matrix. The vector quantizer quantizes cluster or block of points to single point i.e. centroid that’s why it is also called “block quantization”. The quantization error of vector quantizer is inversely proportional to input point density. 4.7 Error Histogram The error histogram the error distribution looks like normal (Gaussian). By increasing the quantization level the distribution remains same but the variance of error is reducing and the histogram is compressing towards zero. The error histogram of both systems is compared on level 2 and level 32 as shown in figure 4.12-4.13 and 4.14-4.15 respectively Figure 4-12: Error vector histogram, Givens rotation level 2 Figure 4-14: Error vector histogram, Givens rotation level 32 29 Figure 4-13: Error vector histogram, Jacobi rotation level 2 Figure 4-15: Error vector histogram, Jacobi rotation level 32 4.8 Mean Square Error and SNR The most often used measure of distortion or noise contribution in signal is the mean squared error. SNR f(MSE) used for evaluating quantization noise as suggested by [6]. As we are interested in size of the quantization error relative to the signal, so the SNR can be defined as ratio of the average squared value of the source output and the mean square error as shown in equation 4.2 MSE rSignalPowe SNR  (4.2) The mean square error and aggregate SNR of the two feedback schemes are show in figure 4.16 and 4.17 respectively. The signal to noise ratio of the Givens based feedback schemes is found to be 2 to 2.5 dB better then Jacobi rotation. Due to the difference of input distribution of (C, θ) and (θ1, θ2), mean square error of feedback schemes based on Jacobi is higher than Givens based feedback scheme. Figure 4-16: Mean Square error, Givens and Jacobi rotation 30 Figure 4-17: Mean Square error, Givens and Jacobi rotation 4.9 AWGN Noise The system performance for Givens rotation feedback scheme is also examined in presence of AWGN noise. Any error correct code or equalization technique is not used and controlled amount white noise is added in the system by multiplying generated AWGN with noise variance sigma. To test the effect of both noises in the system AWGN of different variance and quantizer of level 8 and level 16 are used. Figure 4.18 shows the effect of AWGN in terms of bit error rate without any quantization noise and bit error rate with AWGN and quantization noise of 16 level VQ. Figure 4-18: SNR curve The figure 4.19 shows the relation between the SNR of AWGN and SNR f(MSE). 31 Figure 4-19: SNR AWGN vs. SNR f(MSE), Quantization level 16 The relationship between these SNR is found to be linear. The QPSK plot in figure 4.20- 4.23 shows the AWGN noise and quantization noise produced by 16 level vector quantizer. Figure 4-20: QPSK plot, SNR 20dB and quantization noise of 16 level vector quantizer. Figure 4-21: QPSK plot, SNR 15dB and quantization noise of 16 level vector quantizer. 32 Figure 4-22: QPSK plot, SNR 10dB and quantization noise of 16 level vector quantizer. Figure 4-23: QPSK plot, SNR 5dB and quantization noise of 16 level vector quantizer. 4.10 Scaling factor In Givens based feedback scheme the parameters (C,θ) are send back, as cosine is a periodic function whose values ranges from -1 to 1 for θ = –α to α. In our case the values generated are from 0 to 1. Due to this scaling, vector quantizer put more points in θ direction whose range is 4 times as compared to C. This problem can be solved by introducing a scaling weight W which shifts the range of C before quantization. The values of parameters can be rescaled after the quantization, before sending them back. This rescaling of the parameters is equivalent to implementing weighted mean square error in which each error vector weighted according to some criteria. Weighted mean square error is defined in section 3.2.2 as    n i iii xxw n WMSE 1 2)ˆ( 1 We can select wi to scale C parameter as        10 0w wi The weighted mean square error in that case will be scaling of error vector as given in equation 4.4 and 4.5 2 1 ˆ ˆ * 10 01                  n i CCw n WMSE  2 1 ˆ ˆ1            n i CwwC n WMSE  (4.3) (4.4) (4.4) (4.5) 33 The weight W can be found by selecting the range of weight values and looking SNR response after quantization. The figure 4.24 and 4.25 shows the scaling weight vs. SNR for quantization level 8 and 16 respectively Figure 4-24: SNR f(MSE) vs. W, Quantization level 8 Figure 4-25: SNR f(MSE) vs. W, Quantization level 16 The reduction in BER by selecting 2 as scaling factor of C parameter is shown in figure 4.26 34 Figure 4-26: SNR vs.BER 5 Conclusion This thesis presents detailed survey on existing and most significant methodologies for MIMO systems feedback. The transmission imperfections due to feedback quantization of CSI is extensively been treated in the literature. In this study two low rate feedback techniques for MIMO systems are compared and the error in system due to corresponding quantized feedback is analyzed. Numerical results show that the performance of Givens transformation performed on SVD of the channel matrix in a closed loop MIMO system is better than Jacobi rotation in terms of SNR. The difference between these two techniques lies in the distribution of transformation parameters. Both schemes are evaluated for 2×2 MIMO system. The Givens transformation scheme can be extended to m×n MIMO system (for m and n >2) but if we try to diagonalize m×n channel matrix (for m and n >2) with the help of Jacobi rotation, the successful transformation undo previously set zeros in off diagonal entries. In a nutshell the use of Givens decomposition in feedback loop is an effective means of reducing the amount of feedback and scheme can easily be applied to m×n MIMO system of order greater than 2 without additional complexity. 6 Future Work A lot of work is already going on adaptive schemes in which the feedback rate is optimized as a function of the channel quality [11]. When multiple sub-channels are available selecting dominant sub-channel also called "active sub-channel" for transmission is also widely discussed in literature. However in these designs, less attention has been paid to optimize the channel feedback by exploiting the matrix transformation such as QRD technique in conjunction 35 with SVD that decomposes the MIMO channel into layered sub-channels [12]. The author of this thesis is interested to work more in above mentioned areas. 36 7 References [1]: MIMO System Technology for Wireless Communication The Electrical Engineering and Applied Signal Processing Series Edited by Alexander Poularikas [2]: Wireless Communications Andrea Goldsmith Stanford University Copyright 2005 by Cambridge University Press. [3]: Improved Feedback for MIMO Precoding Qinghua Li, Xintian Eddie Lin, Ada Poon, Ho Minnie, Nageen Himayat, Shilpa Talwar [4]: Unified MIMO Pre-Coding based on Givens Rotation Mehdi Ansari, Hadi Baligh and Amir K. Khandani Wen Tong, Peiying Zhu, Ming Jia, Dongsheng Yu, Jianglei Ma ,Mo-Han Fong, Hang Zhang, Brian Johnson [5]: Efficient Feedback Design for MIMO SC-FDMA Systems Jung-Lin Pan, Member, IEEE, Robert Olesen, Member, IEEE, Don Grieco, Senior Member, IEEE InterDigital Communications Corp. Simon Yen, Student member, IEEE, Polytechnic University , 6 Metrotech Center, Brooklyn, NY 11201 [6]: Introduction to Data Compression Third Edition. Khalid Sayood, University of Nebraska [7]: Vector Quantization http://www.mqasem.net/vectorquantization/vq.html [8] : H. H. Nguyen, “Notes in informations and communications theories,” Department of Electrical Engineering, University of Saskatchewan, Saskatoon, Canada. [9]: A New Method of Channel Feedback Quantization for High Data Rate MIMO Systems Mehdi Ansari Sadrabadi, Amir K. Khandani, and Farshad Lahouti Coding & Signal Transmission Laboratory, Department of Electrical & Computer Engineering, University of Waterloo Waterloo, Ontario, Canada, N2L 3G1 [10]: MIMO Performance and Condition Number in LTE Test Application Note [11]: Adaptive Feedback Rate Control in MIMO Broadcast Systems Randa Zakhour, David Gesbert Mobile Communications Department, Institute Eurecom [12]: QRD-based Precoded MIMO-OFDM Systems With Reduced Feedback Kyeong Jin Kim, Man-On Pun, Ronald Iltis,TR2010-007 March 2010 http://www.mqasem.net/vectorquantization/vq.html