G a l l a g e r ' s R a n d o m C o d i n g E x p o n e n t for Differential Space T i m e M o d u l a t i o n by Siddharth K. Srinivasan B.E, Government College of Engineering, Pune (2001) A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF MASTER OF APPLIED SCIENCE in THE FACULTY OF G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E UNIVERSITY OF BRITISH COLUMBIA March 2006 © Siddharth Srinivasan, 2006 Abstract In this thesis, we study differential space-time modulation with multiple transmit and receive antennas over a frequency non-selective block fading channel in the absence of channel state information (CSI) at both the transmitter and the receiver. We focus on the analysis of the random coding exponent proposed by Gallager for such spacetime channels employing differential modulation withfinitesignal sets, and consider multiple symbol differential detection (MSDD) with an observation window size N. The underlying principle of MSDD is to utilize an increased observation window of N > 2 consecutively received space-time samples to yield decision variables on N — 1 spacetime data symbols. We thus take into account the channel memory, and can improve power efficiency over conventional differential detection, which employs N — 2. We extend previous work for a similar setup, in that we consider channels where the fading coherence interval is different from the MSDD observation window N, and can be arbitrary with L independent fading realizations per coding frame. We analyze the effect of arbitrary fading coherence intervals on the random coding exponent, and therefore analyze the achievable performance of coded transmission over block fading channels with low to moderate code lengths, i.e. with decoding delay constraints. In this context we also analyze space-time transmission systems with spatial correlation between antennas. Such an analysis allows for a fair comparison of DSTM with MSDD where the window size may vary but the coded diversity remains fixed. ii Abstract iii We also devise upper and lower bounds and approximations for the random coding exponent, which allows us to not only bound the achievable performance of such spacetime systems but also allows for efficient numerical evaluation of the random coding exponent by limiting the search space for the metric calculation. To this end, we make use of tree-search based sphere decoding algorithms for efficient decoding, and along with novel stopping criteria to control the accuracy of the approximation and correspondingly the computational complexity, we apply these sphere decoders for a reduction in complexity cost upto many orders of magnitude. The presented numerical results provide useful information on the performance of coded differential space-time transmission for short to moderate code lengths. Contents Abstract ii Contents iv List of Figures vii Acknowledgements x 1 Introduction 1 2 C h a n n e l M o d e l s a n d Differential E n c o d i n g 6 2.1 7 Multiple Transmit and Receive Antenna Systems with MSDD 2.1.1 2.2 Discrete Time Channel Model for Multiple Transmit and Receive Antenna Transmission 8 2.1.2 Differential Space Time Modulation: Vector Channel Model . . 9 2.1.3 Single Antenna Transmission: A Special Case 13 Signal Constellations for Differential Space Time Modulation 15 iv Contents v 2.2.1 Constellations from Group Codes: Cyclic Codes or Diagonal Signals 2.2.2 Constellations from Non-Group Codes 16 ••• 17 3 Gallager Random Coding Exponent for Differential Transmission and Noncoherent Reception 19 3.1 Introduction 19 3.2 Multiple Antenna Systems 20 3.2.1 Noncoherent Probability Density Functions 20 3.2.2 Random Coding Exponent and Channel Capacity 22 3.2.3 Reduced Complexity Metric to Calculate the Random Coding 3.2.4 3.3 Exponent 28 Results and Discussion 30 Single Antenna Systems 40 3.3.1 Noncoherent SISO Channel PDF 40 3.3.2 Random Coding Exponent and Capacity Analysis 41 3.3.3 Performance Analysis: Results and Discussion 42 4 Modified Tree-Search and Sphere Decoding M S D D Algorithms 4.1 Single Antenna Systems: Multiple Symbol Differential Sphere Decoding (MSDSD) 4.2 49 51 Multiple Antenna Systems: Tree Search based Sphere Decoding Algorithms 53 Contents 4.3 4.4 vi 4.2.1 Algorithms for Orthogonal Space-Time Codes 54 4.2.2 Algorithms for Diagonal Constellations 54 Bounds Using Tree-Search Algorithms 55 4.3.1 D = 1 and Spatially Uncorrelated Fading 57 4.3.2 D > 1 and Spatially Uncorrelated Fading 59 4.3.3 Upper Bound to the Random Coding Exponent 60 Performance Analysis and Results 60 4.4.1 Single Antenna Systems 61 4.4.2 Multiple Antenna Systems 65 5 Conclusions and Future Work 76 A Derivation of Gallager's Function with Coherent metric 80 B List of Symbols and Acronyms 84 List of Figures 2.1 Overlapping of consecutive 2NT X NT matrix symbols <fr[/e]. After right multiplication with the NT X NT submatrix S[k — 1] = Yl^Li V\k — Q of the previous matrix symbol <&[k — 1], only the bracketed regions i.e. NT x NT matrices S[k] are transmitted 2.2 10 Block diagrams for Differential Space-Time Modulation: Discrete Time Model and Vector Channel Model 3.1 11 Gallager Exponent vs Rate for DSTM, Orthogonal codes with CDD (N = 2),target rate R = 1 bit/(channel use): Effect of coding diversity . . . . 31 t 3.2. Required SNR (l$\og (E /N )) w s 0 vs t d in PSK samples, D^PSK and C (16). Dashed lines: DSTM, Solid lines: D4PSK 32 OD 3.3 Required 10\og (E /No) vs Decoding delay t^ in PSK samples. Target 10 s rate R =l bit/(channel use), CDD (N = 2) and MSDD with N = 3 . . t 3.4 Gallager Exponent results: Required SNR (lOlog (E /No)) w delay s 33 vs Decoding in PSK samples for DSTM with Orthogonal Codes Co£>(16) showing the effect of increasing D while keeping N constant: Reduced diversity. Solid horizontal line: channel capacity for DSTM, N = 3 . . vii 35 List of Figures viii 3.5 Comparison between D4PSK and DSTM: Diversity Analysis 3.6 Capacity CDSTM{N) results for DSTM, Orthogonal Codes with modula- • tion rate R m 36 = 2 bits/(channel use) 38 3.7 Capacity C {N) for DSTM 3.8 Capacity and Gallager functions for Single Antenna D4PSK 3.9 Gallager exponent E(R, N, D) vs Rate R, effect of coding diversity . . . DSTM 39 43 44 3.10 Gallager random coding exponent results: Single Antenna D4PSK, delaySNR analysis 45 3.11 Required 10log (E /No) 10 s vs coding delay t for single antenna D8PSK, d CDD(N = 2), fading coherence interval increasing with D 47 3.12 Gallager Exponent E(R, N, D) vs R for D4PSK (N = l) and 10 \og (E /N ) T W S = 0 10 dB 48 4.1 Stack algorithm bounds for D4PSK: MSDD with 99% accuracy 62 4.2 Random Coding Exponent for D4PSK: Lower bounds using Stack Algorithm with different accuracies. CDD (N = 2) and MSDD (N = 6) with 90% and 99% accuracy 4.3 63 Complexity and random coding analysis of Stack Algorithm, D4PSK and D8PSK with 99,90 and 85% accuracy 4.4 64 E(R, N, D)vsR for DSTM, different ST codes with R = 1 (bit/ch. use), t spatially correlated antennas 4.5 66 Required E /NQ vs decoding delay t for DSTM with CDD, Cor>(16) with S d R = l (bit/ch. use), spatially correlated antennas t 67 List of Figures 4.6 ix Random coding exponent for DSTMICOD(16) andCi>i(16) codes . . . 4.7 4.8 69 71 E(R, N, D) vs. R: D+PSK and 10 l o g ( £ / J V ) = 10 dB. (a): MSDD 10 s 0 with different N. (b): N = 6. Exact expression and approximation for E (R, N, D). n /L = 40 r 4.9 73 c Required 10\og (E /N ) w B 0 for P < 10~ vs. n . 4DPSK (N = 1) and 3 E c T 160D (NT = 2). n /L = 100, R = 1 bit/(scalar channel use): upper c bound approximation 75 Acknowledgements It gives me great pleasure to convey my gratitude to Dr. Lutz Lampe for his able guidance throughout the course of this work. I have learnt a lot from him and consider it a privilege to have worked with him. His constant encouragement and support helped me in overcoming the challenges I faced while pursuing this project. The numerous discussions we had were very fruitful and the team work was instrumental in allowing me to achieve the goals that I set out for. I would also like to thank all the professors of the Department of Electrical and Computer Engineering, specially Dr. Robert Schober, who taught me various courses and helped me enhance my knowledge. I thank all my colleagues in the Communication Theory Group, Dept. of ECE, UBC for creating a friendly and stimulating environment. I would also like to thank my family for being very patient and for believing in me during all these years. Without their love and support I would have not been the person I am today. x Chapter 1 Introduction The field of digital transmission systems has been long driven by the need for higher data rates, lower probabilities of error and reduced power consumption. Especially in the case of modern wireless communication systems, the quest for low power, bandwidth efficient digital communication systems has been the major area of research and development over the past years. The goal of this thesis is to contribute to the design and analysis of noncoherent wireless communication systems, and present a detailed analysis of the random coding exponent proposed by Gallager (see [10]) and its properties. In digital communication systems, the overall system model of the transmitter, the channel under consideration and the receiver is given by the equation r[k] = e h[k]s[k] + n[k] (1.1) je[k] relating the discrete time, complex valued data or transmit symbol s[k] to the received symbol r[k]. A time variant phase shift is taken into account by the term e^ \ k which is introduced generally by oscillator instabilities or by Doppler effects. The additive noise component n[k] is generally modeled as additive white Gaussian noise (AWGN). The techniques for detecting r[k] from s[k] can be broadly classified into two categories, 1 2 based on the knowledge about the phase shift 9[k\. In coherent detection, 9[k] is assumed to be perfectly known, implying the existence of a phase-synchronization mechanism, often involving the transmission of pilot tones or symbols (cf. e.g. [31, 30, 33, 3]). On the other hand, noncoherent detection assumes no knowledge about the phase, but treats the estimation of the transmitted data as well as the channel phase as one operation. The signal fading, which is one of the major disturbances in mobile communications is represented by h[k], and this enables us to distinguish between coherent detection with perfect channel state estimation (CSI) at the receiver, i.e., e^^/iffc] is presumed to be perfectly known by means of explicit channel estimation, and noncoherent detection without CSI where neither 9[k] nor h[k] are explicitly estimated for the purpose of data selection. One of the common ways to implement a noncoherent receiver is to base the estimation of the data vector on blocks of N > 2 received symbols (see [43]), also known as multiple-symbol differential detection (MSDD). This form of noncoherent reception assumes that the receiver is aware of the statistical characterization of the channel. The concept of noncoherent reception where explicit channel estimation is not required becomes even more attractive for the case of transmission systems employing multiple antennas at the transmit and receive points, where transmit diversity is achieved through the use of NT > 1 antennas at the transmitter. Such space-time (ST) communication systems employing N receive antennas require extensive training intervals R to estimate the N • N T R fading coefficients, and due to this restriction, space-time modulation formats which do not require the receiver to know or estimate the channel coefficients have been proposed (see [28,14]). We use an approach known as differential space-time modulation [16, 15], which generalizes the notion of differential phase-shift keying (DPSK) to multiple antenna transmission, and is a low complexity scheme providing full-antenna diversity. In this thesis, we study the application of bandwidth efficient noncoherent coded mod- 3 ulation to differential space-time coding for multiple transmit and receive antenna systems. We focus our research on the error exponent analysis of such systems, and consider a block fading channel of arbitrary fading coherence interval, i.e. where the channel remains constant over an arbitrary interval. This is an extension to previous work [24] on single antenna DPSK where the channel coherence interval was assumed to be equal to the MSDD observation interval N. Error exponent analysis is a powerful tool to study the achievable performance of coded transmission over fading channels with short to moderate code lengths due to e.g. delay constraints. In particular, random coding exponents have been used to bound error and/or outage probability for certain types of channels and different degrees of channel state information being available. In this context the block-fading channel model is often employed to (approximately) represent realistic fading channel scenarios with possibly non-ideal interleaving. More recently, random coding exponents for space-time (ST) modulation over block fading channels have been evaluated in [4, 18]. We consider Gallager's random coding exponent [10, Ch. 5] for ST transmission over block fading channels with no CSI at both the transmitter and the receiver. We consider bandwidth-efficient differential space-time modulation with practical signal constellations at the transmitter and power-efficient MSDD at the receiver. Chapter 2 introduces the discrete time, frequency non-selective block fading channel model under consideration, and also introduces the differential encoding technique used to resolve the ambiguities in the data detection. The concept of MSDD is described in detail, where blocks of iV consecutively received symbols are processed for joint detection of the corresponding data symbols. In particular, we consider spectrally efficient DPSK based encoding strategies for single antenna transmission and multiple antenna DSTM based on unitary signal elements. We also introduce the different signal constellations for DSTM that will be used throughout the thesis for analysis purposes. Chapter 3 is dedicated to the random coding exponent and its properties as a tool for 4 error exponent analysis. We focus on absolute performance limits of coded transmission over block fading channels, and to this end we consider Gallager's random coding exponent and, to a lesser degree, channel capacity as appropriate information theoretical parameters. We derive expressions for the random coding exponent for DSTM, and widen the range of block fading channels that can be analyzed by extending the definition of the random coding exponent to channels with arbitrary fading coherence intervals. For the sake of completeness, we present results corresponding to the case of single antenna transmission as well as DSTM, and show the effect of arbitrary fading coherence intervals on the random coding exponent. In Chapter 4, we present efficient decoding algorithms for DSTM with orthogonal and diagonal constellations. We describe in detail the need for such algorithms based on the analysis in Chapter 3, and describe how efficient tree-search based sphere decoding algorithms considerably reduce the computational complexity of the derived metrics, where the search space for the decoding algorithm increases exponentially with the length of the fading interval. In order to reduce this exponential dependency on the fading coherence interval, we devise modified sphere decoding algorithms (cf. e.g. [22]) to limit the complexity cost for ST transmission systems with arbitrarily large fading intervals. We also attempt to use a combination of the sphere decoding algorithms and a metric to upper and lower bound the random coding exponent and hence the probability of error. We devise a novel performance metric using the best maximum likelihood (ML) metrics obtained for the sphere decoding algorithms along with a stopping criteria, which not only allows us to bound the random coding exponent to a user-defined accuracy, but correspondingly also reduces the complexity cost for the decoder by several orders of magnitude, depending on the required accuracy. Finally in Appendix A, we derive in detail the expression for Gallager's random coding exponent used in this thesis, where the effect of transmit diversity is taken into account. We present results and analysis separately for multiple transmit and receive antenna 5 systems and single antenna systems, and present our findings at the end of each chapter. We make a note of the fact that the focus of this thesis is on block fading frequency nonselective channels with arbitrary fading coherence intervals, so the class of broadband communication systems entailing a frequency-selective or time-dispersive channel are nor directly addressed by this thesis, neither are channels with continuous fading. Nevertheless, by means of widely accepted multicarrier transmission technologies [2], which decompose a frequency-selective channel into a number of parallel frequency non-selective channels, the concepts proposed throughout the thesis can be applied to such broadband systems. Chapter 2 Channel Models and Differential Encoding This chapter briefly introduces the discrete time channel models and signal constellations used throughout the thesis for the single antenna systems considered as well as space-time transmission. In accordance with the proposed work, we distinguish between the single antenna channel with one transmit and one receive antenna and the multiple antenna channel with more than one transmit and/or receive antennas. The corresponding channels are thus referred to as single-input-single-output (SISO) and multiple-input-multiple-output (MIMO) channels respectively [23]. In section 2.1, we introduce the multiple transmit and receive antenna channel model that we will use throughout this thesis. We introduce the vector channel model of the system, and explain in detail the process of differential space-time modulation (DSTM) and multiple symbol differential decoding (MSDD) for noncoherent reception without channel state information (CSI). The block fading channel model for our MIMO channel is also described, along with the transmit diversity effect of the channel. We also describe, for reference, the single antenna channel model used in literature in section 2.1.3, and 6 2.1 Multiple Transmit and Receive Antenna Systems with MSDD 7 introduce the basic channel model and differential encoding for such a SISO channel model. Finally in section 2.2, we introduce the space-time signal constellations that we use throughout the thesis for analysis purposes, and mention in brief the design of orthogonal and diagonal space-time block codes for DSTM. . 2.1 Multiple Transmit and Receive Antenna Systems with MSDD Multiple symbol differential decoding works on blocks of N consecutively received matrix symbols (in the case of DSTM, these symbols are N T x N T matrices) such that decision variables on data symbols are based on independent evaluations of these blocks cf. e.g. [42, 8, 25, 9]. Since, in general, computational complexity grows exponentially with N, a judicious choice of N is required to balance performance and complexity. Since in MSDD, a constant phase offset does not reflect in decision metrics, differential encoding techniques are required to resolve phase ambiguities. This process of differential encoding can be achieved by multiplying the data carrying differential symbol by the previously transmitted symbol. Let S[k] be the reference symbol, and V[k] be the data carrying differential symbol drawn from a signal set V. The transmitted symbol at the current instant is then given by S[k] = V[k] • S[k - 1] (2.1) This process of differential encoding is applied to blocks of N symbols for MSDD, and at the receiver, N consecutively received symbols are grouped together to yield a decision on N — 1 differential data symbols. 2.1 Multiple Transmit and Receive Antenna Systems with MSDD 2.1.1 Discrete Time Channel Model for Multiple 8 Transmit and Receive Antenna Transmission In the previous section we introduced the concept of MSDD, and we use this concept to formulate our system model with multiple transmit and receive antennas. We consider space-time transmission with NT transmit antennas and NR receive antennas over a frequency non-selective block fading channel. We consider transmitting blocks of Af space-time symbols over a particular fading subchannel, and D such blocks are transmitted over one fading realization. Since the total number of fading realizations is L, one codeword spans n = LD(N - 1) (2.2) v differential symbols, i.e. the code length is n = n log (M). This is an extension c v 2 to work done in literature thus far, where the channel coherence interval and the MSDD observation window N were equal. Here, the channel remains constant for DN consecutive matrix symbols, and L such independent fading realizations are seen in one coding frame, thereby introducing a transmit diversity which is then used to parameterize our channel model. The transmitted symbols are NT x NT matrices denoted by Si d,n[k], where subscripts £, d, and n, 1<£<L, t l < d < D , l < n < N , specify the fading subchannel, the block transmitted over this subchannel, and the symbol position within this block, respectively, and fc G 2 is the time-index with respect to frames of (2.3) n = LDN s symbols. The £th subchannel is represented by the N xN T R channel matrix Hi[k]. For a compact notation, it is convenient to introduce the matrix notations S [k] A l4 S [k] 4 [SUk] ... Sl [k}f t D 2.1 Multiple Transmit and Receive Antenna Systems with M S D D 9 to represent the transmitted symbols, R , [k] e d 4 [Rj [k} Al Re[k] A jR^ik] . to represent the received symbols, and N [k] e = [Nj [k] • Nj [k]] A [NjAk]. Nl [k]f , , T dtN A1 D to represent the noise samples, corresponding to blocks of N and DN matrix-symbol transmissions respectively. 2.1.2 Differential Space Time Modulation: Vector Channel Model We consider the channel model from section 2.1.1, and apply differential space-time modulation at the transmitter to achieve the necessary transmit diversity. D S T M can be described by considering transmission of B x JV matrices ([28],[14]), if channel state T information is not available at the receiver. Hence during each modulation interval T, one row vector is transmitted, corresponding to using all NT antennas, assuming the channel remains constant for all B intervals. This approach is known as unitary space-time (ST) modulation. It is possible to show ([28]) that right multiplication of these B x NT matrices by arbitrary 7Y x N T T matrices does not affect the pairwise error probability, hence consecutive B x NT matrices can overlap by such submatrices, thereby increasing power and bandwidth efficiency. In the considered case, B = 2NT, the NT X NT unitary submatrices are chosen, without loss of generality to be the identity matrix I^ . T Hence the overlapping is achieved by successively right multiplying the current matrix symbol with the corresponding N T x N T unitary submatrices of all 2.1 Multiple Transmit and Receive Antenna Systems with MSDD #[«; - 1] *[fc -1] *[* -1] IN 10 IN T T V[k-1] V[k-1] S[/fc - 2] S[k - 3] S[k S[k - 2] S[fc - 2] S[fc - 1] - 1] S[k] S[k - 1] S[fc] S[k] S{k + 1] Figure 2.1: Overlapping of consecutive 2NT X AT matrix symbols <f?[k]. After right r multiplication with the N x N T T submatrix S[k — 1] = TJcii — C] °f the previous matrix symbol &[k — 1], only the bracketed regions i.e. NT X NT matrices S[k] are transmitted. previous matrix symbols. As an illustration, let V[k] be the chosen matrix for the current transmission. Hence the 2N x N transmit matrix &[k] = [lN V[k] ] . T T T T T At a given time instant k, &[k] is right multiplied by the unitary matrix s[k-i] = (2.4) l[v[k-c] This is illustrated in fig. 2.1. The block diagram of the equivalent system is shown in fig. 2.2. We map binary coded symbols to a D(N — 1)N x NT dimensional matrix T Vt[k] 4 [Vl4M VWW T • • • V^N-Wf, \<d<D (2.5) of D(N — 1) space-time N x NT data matrix symbols V^d [A;], 1 < n < N — 1,1 < T i7l d < D. The matrix symbols are taken from a signal set V as described in section 2.2. This signal set forms a space-time code with M = 2 NTRm elements, where Rm is the modulation rate in bits/(channel use), and one channel use corresponds to the use of all NT transmit antennas simultaneously. In our case of DSTM with unconstrained 2.1 Multiple Transmit and Receive Antenna Systems with MSDD (.dm V [k] "t.dl^l S [k] t Mapper Channel Encoder 11 Parallel/Serial Tlv t Differential Encoder Modified Block Binary data Fading Channel -R/,d[fe] -=a 1 Ri[k] fi/,d[fc] n* Channel Decoder Grouping and Reordering 1 1 1 (a) Discrete-time channel model for DSTM with MSDD St[k] V [k] t Differential Encoder Reference Symbol Extension St,D,N-l[k] Modified Random Generator J Block Fading Vector Channel Rt[k] (b) Equivalent vector channel model for DSTM with MSDD Figure 2.2: Block diagrams for Differential Space-Time Modulation: Discrete Time Model and Vector Channel Model 2.1 Multiple Transmit and Receive Antenna Systems with MSDD 12 block fading, DSTM can best be described by generating a block transmit matrix Se[k] 4 [S M Si M T • • • SeAN[k] ] , T lA T 4 T l < d < D (2.6) from the data block matrix Vf[k] via Se,d,n-j[k\ — Vt,d,n-i[k]Si d,n-j-\[k], l . < j < N - l t (2.7) where the reference symbol Se,D,N-i[k], which is an independent u.i.i.d random variable is taken arbitrarily from the signal set S. Since we are primarily interested in performance analysis using the random coding exponent, we can conveniently assume interleaving to be limited to blocks of L D N space-time symbols without imposing any more restrictions. Taking the expressions above and defining block matrix symbols 0/v S [k] 0N W T T S [k] 0N t (2.8) tA2 S [k] 4 e Si,d,DN-l [k] 0N t H [k] [He,dAk] H ,d,2[k) T ^ t N [k] ^ [Ne, [k} N 2[k T e we obtain the dil DNNT T e iA ••• ~ 1] • • • N , [k T ltd N X NR matrix Rt[k] of DN H , [k] ] , T tfd e e e T 1 < d<D - (DN - 1)] ] , 1 < d < D T T (2.9) (2.10) received samples as R [k] = S [k}H [k} + N [k] , e N 1< t < L , (2.11) where Nt[k] denotes additive spatially and temporally white circularly-symmetric Gaussian noise (AWGN) with variance a\ per complex scalar component. We also 2.1 Multiple Transmit and Receive Antenna Systems with MSDD 13 assume that the elements of iT^fc] are circularly-symmetric Gaussian distributed, i.e., block Rayleigh fading, with common variance o\ and possible spatial correlation, tl> \»x,l*2,vi,V2\] ^SUHeik^dHeik}}^)*} H , (2.12) which is assumed identical for all subchannels L At the receiver, MSDD with an observation window size N is applied. This means that the decoder input is based on independent processing of blocks of N received samples collected in Re, [k] corresponding to N — 1 differential symbols d VeAk} = [Vj [k}...Vj _ [k]] • T Al AN 1 We use the notations R 4 [RT[k]...R[[k]f V 4 [VT[*]...Vl[ib]] 4[V^.Jfc]Vj [ifc]...Vr [ib]] r r 2 i0 to represent the collection of all received samples and differential symbols corresponding to the transmission of one codeword. Throughout this thesis, for the sake of simplicity, we omit the frame index k, and use the representations X( [k] jd X ,Xe id {S,R,N}. e 2.1.3 = X( , X([k] — Single Antenna Transmission: A Special Case For the special case of N = N = 1, we revert back to the traditional single antenna T R transmission scenario with multiple symbol differential detection at the receiver. For a compact notation, it is convenient to introduce the vector notation x [k] e<d = [xj [k] x [k] ^ e tdtl ... xl [k]] , T d>N [xlik] • • • xl [k]f D , corresponding to blocks of N and DN vector-symbol transmissions, respectively, and x € {s, r, n} corresponding to the transmitted, received and noise vector block symbols respectively. 2.1 Multiple Transmit and Receive Antenna Systems with MSDD Here, instead of transmitting DNN? 14 x NR matrix symbols as in the ST case, we trans- mit differentially encoded vectors of length DN corresponding to the fading coherence interval, and we can represent the received vector as r [k] = s [k]h [k] + n [k] , t e e 1<£<L, e (2.14) where [xj [k] xp {k] 4 >dil 4 x [k] ... xJ [k]] T tdtN = [xj^k] ••• xl [k]] , T e , D corresponding to blocks of N and DN vector symbols transmissions respectively. Vector Channel Model for Single Antenna DPSK Similar to the DSTM case, we consider transmission of blocks of DN symbols over a frequency non-selective block fading channel, with L independent fading realizations per coding frame (see [19, 20, 27]). A sequence of information bits is encoded at the encoder, and mapped to data carrying differential symbols vi[k] = [v ,i[ ] t,dA k v k i4 -!]••• ve -i[k]] T AN (2.15) consisting of D(N — 1) scalar differential symbols vt^j[k] G V, 1 < j < N, 1 < d < D. Here, since we consider interleaving and deinterleaving as an integral part of the channel, a vector channel is considered between the transmitter and the receiver. Assuming interleaving to be restricted to frames of LDN symbols, as in the DSTM case, at the transmitter, the process of differential encoding can be described by generating the transmit vector of dimension DN -!]••• *W*;]] , l<d<D s [k] = [se Ak]s [k e 4 r W from the D(N — 1) dimensional data vector v^A^] i y se -j[k] An = ve, , -j[k] • a ,n-j-i[A], d n W (2.16) a 1 < 3 < N, 1 < d < D (2.17) 2.2 Signal Constellations for Differential Space Time Modulation 15 where the reference symbol is chosen arbitrarily from the signal set S due to noncoherent detection at the receiver. Here, the first (reference) symbol s^o^k] of the block 8i[k] is the last symbol of the previously transmitted block S£_i[/c]. As [21] and [35] note, this overlapping is advantageous with respect to spectral and power efficiency. Defining the DA-dimensional vectors of channel gains and noise samples corresponding to s [k] by t h [k] = [h [k]h [k -I]... ne[k] = [n i[k]n [k - 1]... n [k]\ l t eA1 w tA w h [k]] ,l T eAN T lAN <d<D (2.18) <d<D (2.19) respectively, the input-output relation of the vector channel is represented as r [k] = 8i[k]h [k] + n [k] t t (2.20) e where the fading gains hg[k] and the noise ni[k] are complex valued Gaussian random vriables with variances l/\/2 and a\ respectively per complex component. For the single antenna case too, throughout this thesis we omit the frame index k for the sake of simplicity. 2.2 Signal Constellations for Differential Space Time Modulation The signal constellations for DSTM that are supported in this thesis have been widely studied in literature ([16, 15, 36, 12, 17]). Signal Constellation design for DSTM basically involves design of constellations V = { V , V i , . . . , V -\} 0 M of M — 2 NTRm unitary matrices V , where Rm is the maximum supported bit rate in bits per channel m use, and one channel use corresponds to all NT antennas being used simultaneously. This ensures that throughout the course of this thesis, the rate Rm is independent of 2.2 Signal Constellations for Differential Space Time Modulation 16 the number of transmit antennas. We consider two basic kinds of signal constellations, namely constellations from Group Codes and Non-Group Codes ([36],Table 4). 2.2.1 Constellations from Group Codes: Cyclic Codes or Diagonal Signals To simplify design, group codes have been developed [16, 15, 36, 17], which form a group under matrix multiplication. A set of group codes implies V = S, i.e. the differential symbols are the same set as that of the transmitted symbols. Cyclic group codes or diagonal signals are defined as J2-KUl/M Q 0 J2wv,2/M 0 e Q C {M,ui,.. .,U ) CY NT e = < 0 where Ui € {0,..., M — 1}, J2nu 0 e Nr \m e {0,1,..., M - 1} /M 1 < I < NT are coefficients optimized with respect to minimum distance. Some particular diagonal signal constellations that we use later for analysis purposes are C (16,l,3) Cy 0 \m G {0,1... 15} j27r.3/16 (2.21) e for NT = 2 transmit antennas and modulation rate Rm — 2 bits per channel use and i^/9 o 0 e^- / 0 0 e C (9,1,2,5)= { CJ/ 0 2 0 9 j27! e \me {0,1...8} - / 5 9 for NT = 3 transmit antennas and Rm = 1 bits/(ch. use). (2.22) 2.2 Signal Constellations for Differential Space Time Modulation 2.2.2 17 Constellations from Non-Group Codes Based on group structures, in the case of group codes considered by [36], we consider another set of space-time constellations where V ^ 5 . Orthogonal Codes Codes from orthogonal designs ([39]) can be applied with good performance results for DSTM. For the special and widely considered case in literature of NT = 2 transmit antennas, DSTM based on Alamouti's space-time block code is considered and applied. These codes can be represented by COD(M) 1 = { < x -y* y x* {l,eTr,. \x,y€ )27T(-/M-1) 2 W . }, M = 2 ) (2.23) 21 where the two symbols x and y are taken from vMPSK constellations. Such codes yield good results and are used for analysis purposes, and also allow particularly simple detection [1, 40]. Cayley Codes Another class of non-group unitary constellations Ccai^r, M) has been proposed by Hassibi and Hochwald [12]. The differential matrix symbols are obtained via the Cayley Transform of jA, where A = Ylq=i A.Qa , and A\,..., q AQ are preselected N T x N T complex Hermitian matrices and a i , . . . , a are chosen from a set A with P real values. q Similar to previous work [23], we focus on the advantageous effect of transmit diversity considering low and moderate modulation rates of Rm = 1,2,3 bits/(channel use). One such Cayley constellation giving good performance and complexity results is the 2.2 Signal Constellations for Differential Space Time Modulation 18 Cayley Code C (2,4) given by Ca A = Aai + A a = A, [I +jA)-\l -jA) 2 -0.1853 0.8218 + 0.2694? 0.8218 - 0.2694J 0.1359 2 ai,a 2 2 -0.2935 -0.5885 - 0.5704; -0.5885 + 0.5704J 0.3452 G {-1,1} (2.24) for a modulation rate of Rm — 1 bit/(ch. use). We will use this particular diagonal code for the random coding analysis in later chapters. Chapter 3 Gallager Random Coding Exponent for Differential Transmission and Noncoherent Reception 3.1 Introduction In this chapter, performance limits of coded transmission from an information theoretic perspective are discussed. We discuss the performance of differential space-time modulation with MSDD using Gallager's random coding exponent [10] as a performance metric for the general block fading channel already described, and also use channel capacity to characterize the transmission system. Thefirstpart of the chapter focuses on multiple transmit and receive antenna systems, where we first introduce the required noncoherent channel probability density functions (PDFs) to characterize the block fading channel in section 3.2.1 and then analyze the random coding exponent for space-time modulation in section 3.2.2, and also introduce the channel capacity for our transmission scheme. We provide detailed derivations of the random coding exponent, 19 3.2 Multiple Antenna Systems 20 and explain in detail the effect of transmit diversity introduced due to our general block fading model on the random coding exponent. In section 3.2.3 we introduce a reduced complexity metric to calculate the error exponent, which eliminates the complexity drawback where the calculation of the channel metrics involved a high dimensional search space corresponding to the length DN of the channel coherence interval. We present results illustrating our analysis for DSTM in section 3.2.4, and to complete our analysis of the random coding exponent, we present the corresponding single antenna performance metrics and results in section 3.3. 3.2 Multiple Antenna Systems In this section, we introduce the noncoherent PDFs required to characterize the spacetime channel and introduce Gallager's random coding exponent for DSTM, along with a detailed derivation of the exponent for the block fading channel model under consideration. 3.2.1 Noncoherent Probability Density Functions For noncoherent transmission, the channel described in section 2.1.1 is completely characterized by the DN dimensional probability density function p(Re\Vt) for a given differential vector Vt. Under our block fading assumption, in order to characterize our vector channel model, we express the conditional noncoherent pdf (see [37]) as exp(-tr{Rf^- fl,}) 1 p(Re\V ) t (IT T NN (3.1) det{*tf})^ where * R = £ {R R?\V } Rl i t = N {a S Sf 2 R h t + all ) NNT (3.2) 3.2 Multiple Antenna Systems 21 is the conditional autocorrelation matrix of the received vector Re given the transmitted vector Ve, with some arbitrarily chosen Se,i- We note that det{\&ft} is independent of Ve. Equation 3.1 is the expression for the conditional noncoherent pdf of the output vector given the input vector each of length DN, and we differentiate from previous work where the channel coherence interval was equal to N. We represent the overall maximum-likelihood (ML) decoding metric as L D A(R\V) = Yl E KRt4\Vt4) , (3-3) 1=1 d=l where the metric increments X(Re,d\Ve,d) are log-likelihood expressions derived from the probability density function (pdf) p(Re,d\Ve,d)• The rationale for (3.3) is that since the size of the effective signal constellation and hence the complexity of soft-output MSDD increases exponentially with the window size N, the value for N has often to be chosen (much) smaller than the channel coherence interval of length DN, i.e., D > 1 (cf. e.g. [8]). The pdf for the received sequence R given the sequence of differential symbols V assuming coherent detection with CSI can be decomposed into the product (H = [Hj...Hlf) L D • p(R\V,H) = 1=1Hp(Re, \Ve,d,He) , d=l d (3.4) with the A^A^A^fl-dimensional pdf p(Re \Ve,d,He) = £ , 4 S(A 1 J e x p f - ^ ^ H l NN°N V n T (3.5) R We will use the pdf in (3.5) to derive certain metrics to bound the random coding exponent in section 3.2.3. 22 3.2 Multiple Antenna Systems 3.2.2 Random Coding Exponent and Channel Capacity We consider the random coding exponent to be the definitive information theoretic parameter to analyze the maximum data rate supported by the channel. Since channel capacity assumes infinite code length and zero error probability, for most practical applications we require an information theoretic performance measure that incorporates code length and/or decoding delay and error probability to give an accurate performance analysis. The random coding exponent proposed by Gallager relates code length or decoding delay to the reliability of the decoded data, namely the word error rate (WER) P . The random coding exponent is given by [10] w E(R , N, D) = max {E (p, N, D) - pR } V Q 0<p<l v (3.6) where Ry is the rate in bits per vector symbol, and E (p, N, D) is Gallager's function, 0 derived in the next section. From the random coding exponent, given the number n v of vector symbols vk per code word, the word error rate P is bounded by w P < 2- " n ' (3.7) E{Rv N) w Derivation of Gallager's Random Coding Exponent: We refer to Gallager's original derivation for the random coding exponent in [10], and modify it to reflect the block fading channel under consideration. Since we consider noncoherent transmission with L vector symbols V^d, each consisting of N — 1 components drawn from a signal set V, we denote the codeword of length L as Ve i.e. Vt = [ V l V l . . . V l } 1 2 D T (3.8) and the corresponding received vector R consists of L overlapping received blocks Re , 4 i.e. Ri — [Rj^Rj^ • symbol. • • RJ,D\ T- We assume the transmission rate is Ry bits per vector 3.2 Multiple Antenna Systems 23 At the receiver, we assume decoding metrics of the form D L d=l 1=1 corresponding to (3.3), where n = DNL denotes the dimension of R i.e. we assume w a memoryless channel. Let us assume that a particular codeword Vt is transmitted, and if X (R\Vt) < X (R\Vd) for some d^t nw the receiver decides in favor of another nw codeword. Then, given Vt and a set of codewords, the word error rate (WER) 2 RvL reads as (R\V )T (R)dR t where p (R\V ) nw (3.10) t is the n dimensional complex pdf of R given V and the indicator t w t function T (R) is given as t r(R) 4 | 1, if\ {R\V ) nw 0, < X {R\V ) t nw d for some d ? t otherwise (3.11) Upper bounding T (R) by t 2 "L K T (R) < t E K (R\V ) lK (R\V ) d=\,d^t r w w (3.12) p>0 d t (3.10) can be upper bounded by Pw,t < J Pn (R\Vt) w E d=\,d^t K„(R\Vd) X (R\v ) w dR, (3.13) t Now, additionally imposing p < 1, the random coding upper bound on the average WER P follows from averaging the right hand side of 3.12 with respect to V and w d 3.2 Multiple Antenna Systems 24 V . Assuming the codeword symbols V t t are chosen independently and identically 4 distributed with afixeddistribution Pr{Ve } 4 'D not subject to optimization, we have L IH! \ E P Pr{V , }\N(Rt, \V )&\ E D d dR (3.14) eid Hence we have P = - ( O(P<N,D)- R )^ 0< p< 1 L E w 2 P V (3.15) where Gallager's function E (p, N, D) is defined as 0 E (p,N,D) 0 ±^\og 2 ( I f Wc"- \[Y[Pr{V }\ (R \V )^p (R\V) i4 N t4 i4 nw \V6V("-- )d=l«=l L ' D L \ HIT E Pr{Vi }\ {RzAVi,d)^ 4 P X ) dR) N (3.16) Here, we reiterate the fact that the considered channel has L independent fading realizations per coding frame, and we can rewrite the expression for Gallager's function as £ (p,N,D) = 0 -1 l o g / •••/E---E(nf[ i ^ MRe,d\V ))^) Pr V 2 fnf[ fE-'-EM^KAiv^l^))^) \£=1 V d=l Vi • e4 v L ) dR .:.dR . x L J J (3.17) 3.2 Multiple Antenna Systems 25 We expand the above products to read E, p(Re\Vt)(nil \ ^Pr{Ve, }(\ (Re, \Vt, ))^ \v d \e=id=i N d ) ) ) ) d ttd dR ...dR . 1 L (3.18) Combining the product terms and interchanging the order of integration and summation, we have i? (p,JV £>) = - - l o g 0 ) 2 f... Ri D ^2(Pr{V ,d}(XN(Re,d\Ve,d))^-P(Re\Ve)) fH e R L dR . YsYlPriVt^MReAVe,*)^ v \ d=l t ..dR . x L , (3.19) Since each block of DN samples experiences independent fading and is independently processed at the receiver, we represent Ri... R L as Ri,l < i < L to give E (p,N,D) 0 =--log2n [ [YsXlPriV^NiR^Vw)^ e=i Ri D \ X R ( t dRe V J d=l V • \ v d=i Y,U i ^ ^ ^ ^) Pr V •piRelVi)) (3.20) Finally, we obtain D E (p,N,D) 0 = "^log / (^i\Pr{V }\ {Ri, \Vi,d)^-p{Ri\Vt) 2 D i4 i4 V t d=l d Rt Y,T[Pr{V }\ (Re, \V )^\ K N N d dR t>d e / (3.21) 3.2 Multiple Antenna Systems 26 Here, the product over all transmitted vectors L is equivalent to multiplying the results of each vector by L, since each vector represents an independent fading coherence interval. This expression 3.21 represents Gallager's function for any arbitrary channel with a fading coherence interval independent from the MSDD observation interval, and simulation results shown in section 3.2.4 demonstrate the effect of various fading coherence intervals on the random coding exponent. This is an invaluable tool to accurately demonstrate the effect of varying MSDD observation intervals with the coding diversity kept constant, and allows for analysis of a far wider range of channels that until now were restricted to having fading coherence intervals tied to N. Because of the varying fading coherence interval, for the noncoherent case we need to take a product over all possible A^-dimensional (or N — 1-dimensional differential symbols) transmitted vectors V"e,d within a transmitted vector of dimension DN and sum over all possible transmitted vectors Ve to obtain the DA-dimensional pdf L Pn (r\v) = w Hp(R , \Ve,i) (3.22) e i »=i where n = n .N is the codeword length for the block fading channel under considerw v ation having DN consecutive transmit vectors seeing the same fading coefficients. For the special case of D = 1, we refer to 3.14, and can express it compactly by optimizing with respect to p. Hence the random coding exponent E(R , N, D) is given V by EiRy, N, D) 4 max {EJ (p, N, D) - pR,} (3.23) 0 0<p<l and the expresion for Gallager's function , o t e ,, ) = 1 - 1 o g 2 ^ , v { ( ^ « l ) - l i 1 + ' M (3,4, with the WER bounded by p < R Lp 2 j v i Rt cN I E \v ev»-i t Pr{Ve }p (Re,i\Ve,i)^\ A N J dR e (3.25) 3.2 Multiple Antenna Systems 27 This is exactly the expression seen in [10] to calculate the random coding exponent for various channels and constellations. From information theory, we know that Gallager's function E (p, N, D) is upper bounded by the coherent channel with perfect channel 0 state information (CSI) as E csi(p, N, D). The performance of noncoherent transmis0t sion without CSI is clearly expected to improve as the MSDD observation length N increases, as the dependencies amongst received symbols are compromised by the increasing N, and the channel memory is more completely taken into account. However, when we look at the performance taking decoding delay constraints into account, we observe an interesting effect. We see that for noncoherent transmission over a block fading channel, where the channel coherence interval is equal to the MSDD observation window, the error exponent and the cutoff rate are decreasing functions of A^, and decreases substantially as the fading memory becomes large [29, 41]. This behavior illustrates the reduced diversity achievable by coding when the MSDD interval N increases and the delay (N — l)n is fixed, resulting in a higher WER as shown by 3.7. v Channel Capacity From information theory [10], the average mutual information I(;) in bits per vector symbol is given by v « i = { b * ic^Jr)} - (3 26) where p(R )=£ ,MRi,d\Vt,d) e4 Vt (3-27) is the average pdf of the channel output. Another information theoretic parameter to analyze the performance of block fading channels is the channel capacity C(N) where we will consider the input distribution to be uniformly distributed, and hence refer to "capacity" meaning constellation con- 3.2 Multiple Antenna Systems 28 strained capacity [23]. For the conventional case of channel coherence interval equal the the MSDD observation window N, the average mutual information V) =t ^ y l4 u (log } 2 (3.28) measured in bits per matrix symbol V is considered, where PNN N (Rl,d) T R = £v {PNN N (Re,d\Ve,d)} t<d T (3.29) R is the average pdf of the channel output. We normalize the channel capacity with respect to DN — 1 components per data vector symbol V ^ , giving w = Dihi c 3.2.3 • H R '* v *> - D i h • K icWr)} ^ 1330) Reduced Complexity Metric to Calculate the Random Coding Exponent In order to efficiently compute the random coding exponent for higher dimensions (i.e D, N » 1), we introduce a reduced complexity derivation of the random coding exponent in this section. We begin with the expression for the WER bound, obtained from Gallager's function given by 3.21. The average probability of decoding error P e is bounded by p e < 2 - P N T B n v j i^^p }\(R \V )^p{R^VM r{Vi4 i4 i4 (j2l[Pr{Ve }X(Re, \V )^] 4 \ V d=l E d dR e4 t / (3.31) 3.2 Multiple Antenna Systems 29 We note the simplification p(Rt\V ) 4 t Jp(Hi)p(Rt\Vt,Hi)dHi D H L (3.32) = \[p{Rt4\V^Hi)dH t Hi d = 1 where p(Rt\Vt, Ht) is the pdf for the received sequence Rt given the sequence of differential symbols Vt assuming coherent detection with CSI. Using the pdf's from section 3.2.1, 3.31 and 3.32, we can rewrite the expression for the probability of decoding as P E < - N 2 P n^mV, T R N V H)[exp(A(fl|V))]-rf? R ^n N xN t s T (3 R f^E [exp(A(H|y))]^ ) 33) d(H ,Rt) N e for 0 < p < 1, where the PDFs p(R\V, H) and A(K| V) have been described in section 3.2.1. Optimizing the parameter p such that the upper bound (3.33) becomes tightest, we can write P < 2~ - ^ ^ n E , N e (3.34) where E (R, N, D) is the random coding exponent given by r E (R, N, D) = max {E {p, N, D) - pN R] . r 0 0</9<l (3.35) T After manipulations using (3.3), (3.4), and (3.33), the Gallager function E (p, N, D) is 0 obtained as E (p,N,D) S VlA / J_ --—---log (N ~1)D = 0 2 \ex (X(Rt, \Vt )) P d ^p(Rt, \Vt, , , 4 d f 1 d N P (£ {ex (X(Rt, \Vt, ))^JI Vltd V d d {£ {p(Re, \Vt, ,Ht)}y Vt<d d d H )\ e J (3-36) 3.2 Multiple Antenna Systems 30 Here, using the Monte-Carlo technique we rewrite the integrations as expected values £(.) and again make use of 3.3 and 3.4 to rewrite Re 4 and Ve,d in terms of Re and Ve- In Appendix A, we look into this derivation of Gallager's function with reduced complexity in greater detail, and present only the result here for coherence. 3.2.4 Results and Discussion In this section, we discuss the performance of differential space time modulation based on channel capacity and the random coding exponent. The random coding exponent analysis from section 3.2.3 is an invaluable tool to calculate the random coding exponent for channels not restricted by previous analysis, where the channel fading coherence interval was tied to N. Here we first analyze the performance of DSTM, and the advantage over single antenna systems for the purpose of random coding exponent analysis, and show that orthogonal constellations perform better than any other kind of space-time code such as diagonal constellations. A ) R a n d o m C o d i n g Exponent Results In this section, we demonstrate the random coding exponent for differential space-time modulation for the channel under considerations with fading coherence interval varying and not constrained to N. We use the results from section 3.2.3 to obtain the simplified expression for Gallager's function and correspondingly the random coding exponent. In order to compare and analyze the random coding exponent for DSTM, we plot Gallager's exponent against the rate R as in the single antenna case to justify our claim that the above analysis enables us to analyze channels where the coding diversity is kept constant though the MSDD observation interval N may change. We also perform SNR-delay analysis for the exponent and compare it with the single antenna case, to fairly compare the potential advantages of DSTM with multiple transmit antennas over 3.2 Multiple Antenna Systems 31 Diversity L=10 - * — Diversity L=5 •e— Diversity L=2 Figure 3.1: Gallager Exponent vs Rate for DSTM, Orthogonal codes with CDD (N = 2),target rate R = 1 bit/(channel use): Effect of coding diversity t single antenna traditional DPSK. The decoding delay t is measured as the number of d scalar transmitted symbols required for decoding, i.e in this case t d = (DN - l)n d = (DN - (3.37) l)L where n = L is the number of vector symbols per code word. d 1) E(R, N, D) analysis for DSTM: In fig. 3.1, we illustrate the advantage of the derivation in section 3.2.3. When we compare schemes with different values for N and/or N , we use the normalized coherence length n /L = (N — l)£)log (M) as parameter T c 2 3.2 Multiple Antenna Systems 32 •S— D4PSK, N=3, D=1 D4PSK, N=2, D=1 * - DSTM,C(0D)16, N=2, D=1 6 - DSTM,C(0D)16, N=3, D=1 Decoding delay Figure 3.2: Required SNR (10\og (E /N )) 10 s 0 vs t d in PSK samples, D4PSK and COD (16). Dashed lines: DSTM, Solid lines: D4PSK to specify the amount of coded diversity (either temporally or spectrally) available. As a counterpart to the advantage of being able to compare different MSDD observation intervals N for the same coding diversity, we show the effect of different coding diversities n /L = 20,40,100 i.e coding diversities 10,5 and 2 respectively for DSTM c with orthogonal designs and target rate R — 2 bits/(channel use). We observe that t keeping the observation window N constant while increasing the diversity allows the transmitter to see more independent fading realizations, thereby increasing the coding diversity and correspondingly a better random coding exponent performance. 2) SNR-delay analysis for DSTM: Advantage over Single Antenna Systems: Here, we demonstrate the advantage, taking decoding delay constraints into account, of DSTM with multiple transmit antennas over single antenna modulation. Fig. 3.2 shows the required E /N /N S 0 R per received antenna to achieve a WER P < 0.001 as a function of w the decoding delay. We plot the random coding exponent for single antenna DPSK with 3.2 Multiple Antenna Systems 33 (a) CDD (N = 2): DSTM with CQD(16) (b) MSDD (N = 3): DSTM with C £>(16) 0 Figure 3.3: Required 101og (£ /A ) vs Decoding delay td in PSK samples. Target rate l 10 Rt=l s 0 bit/(channel use), CDD (N = 2) and MSDD with N = 3 3.2 Multiple Antenna Systems 34 CDD and MSDD, and compare it with the corresponding DSTM results. Interestingly, we note that not only do we get an added SNR boost by switching for N = 1 to NT = 2, T but for smaller delays t < 10 . . . 10 DSTM performs significantly better than DPSK. 2 3 d For the single antenna case we noted that for smaller delays, the gain obtained from MSDD is countered by the reduced diversity of not seeing enough independent fading realizations, hence the curves for different N's intersected. However, for DSTM we see that the potential advantage of DSTM remains even for small delays, effectively providing enough diversity via space-time coding to retain the advantage of MSDD. In fig. 3.3 we look more closely into the advantage of DSTM over single antenna systems. For this purpose, we compare CDD (N = 2) and MSDD with N = 3 for both schemes. We note of interest that while the advantage of DSTM over single antenna DPSK is apparent at high decoding delays where the situation closely resembles the capacity case with potentially infinite delay, the advantage of DSTM is more apparent for low delays. This shows that with reduced diversity available for low delays and a specific window size N, the DSTM advantage far exceeds the single antenna case due to the space-time coding and overlapping process. This result shows the beneficial advantages of transmit diversity with NT > 1 over standard single antenna differential modulation. 3) Effect of D: In order to characterize and analyze our proposed modified channel, we observe the effect increasing the fading coherence interval has on the random coding exponent. In fig 3.4, we show the effect increasing D has on the coding exponent. The curve for standard DSTM as in section 2.1.2 with D — 1 is shown as a reference. We observe that increasing D reduces the diversity observed on the channel by reducing the number of independent fading observations seen by the channel, hence requiring a higher SNR to achieve the same WER. This results in a degraded random coding exponent performance as seen by the increasing curves in the figure. Here we consider transmission of orthogonal codes with MSDD observation window N = 3, and change D to reflect the increased fading coherence interval. 3.2 Multiple Antenna Systems 35 DSTM,C(od)16,N=3,D=1 DSTM,C(od)16,N=3 D=3 10° d e c o d i n g delay Figure 3.4: Gallager Exponent results: Required SNR (10log (E /No)) 10 s vs Decoding delay td in PSK samples for DSTM with Orthogonal Codes COD (16) showing the effect of increasing D while keeping N constant: Reduced diversity. Solid horizontal line: channel capacity for DSTM, N = 3 Finally, in order to complete our introduction to the random coding exponent for DSTM, we compare E(R, N, D) for single antenna systems and DSTM from a coding diversity point of view. Fig. 3.5(a) compares the random coding exponent E(R, N, D) for single and multiple antenna systems where the coding diversity is the same in both cases. For a fair comparison, the normalized fading coherence length n /L is c taken in PSK samples, hence an accurate comparison between single and multiple antenna systems can be made. In each case, for diversities 10, 5, 2 i.e n /L = 20,40,100 c respectively, the random coding exponent obtained from DSTM offers a significant advantage over the single antenna case. We keep in mind the fact that since the WER bound is inversely proportional to the random coding exponent P < 2~ v ( ' ' ) n E R N D (3.38) 3.2 Multiple Antenna Systems 36 (a) E(R, N, D) vs R comparison between DPSK and DSTM: Overall Diversity L = 10,5,2, DSTM with Con(16), Rtarget — 1 bit/(ch. use) vs Single Antenna D^PSK (b) Required SNR vs decoding delay: DSTM fading coherence length n /L c vs D4PSK and = 100 fixed: Advantage of DSTM over single antenna modulation Figure 3.5: Comparison between D4PSK and DSTM: Diversity Analysis 3.2 Multiple Antenna Systems 37 a higher random coding exponent implies better performance since less E /N s 0 is re- quired to achieve the same WER. In fig. 3.5(b), the random coding exponent is shown as a function of the total decoding delay for the case when the transmitted vec- tor length DN is maintained constant. We plot the SNR 10 \og (E /N ) w to achieve P < 10 e -3 b 0 required according to (3.33) as function of code length n for transmisc sion with rate R = 1 bit per scalar channel use. The normalized coherence length is n /L c = 100, i.e. L degrees of freedom, and thus coded diversity increases linearly with code length n . Two things are interesting to note. First, increasing A^ consistently c improves power efficiency regardless of n . This is decidedly different from [24], where c coded diversity was decreasing with AT. Second, the gain due to transmit diversity increases with decreasing n . c This result reiterates the benefits of spatial transmit diversity if coded diversity is limited, e.g., due to delay constraints. B) Capacity Results In fig. 3.6 we compare the channel capacity obtained with DSTM with that from single antenna DPSK, and see the potential advantages of coding over multiple antennas i.e NT > 1. In 3.6(a), we plot the normalized capacity C(N) over the SNR i.e 10\og (E /N /Nii) w s 0 for CDD (N — 2). We can see that increasing the number of transmit antennas NT from 1 to 2 consistently increases the gain by about 2 dB in power efficiency for NR = 1. We take constellations with the best performance [[16, 15, 36, 17]], and refer to section 2.2 to obtain the best constellations. As a summary, the rates and the corresponding DSTM constellations are given as follows Modulation Rate Rm in bits/(channel use) NT =2 1.0 CCM(2,4) 2.0 CW16) 3.0 CW64) 3.2 Multiple Antenna Systems 38 (a) Capacity C{N) for DSTM: Advantage over DPSK. Solid lines: DSTM, N = 2; Dashed lines: D4PSK, N = 2; Dashdotted lines: DSTM, MSDD (N = 3) B N=2 e N=3 1 N=4 i / / /fl M Af \ 0* J S N R (101og (E./JV )dB) 10 0 -t (b) Capacity C(N) for DSTM: Orthogonal Codes with modulation rate R m = 2 bits/(channel use), MSDD with N G {2,3,4} Figure 3.6: Capacity CDSTM(N) rate Rm = 2 bits/(channel use) results for DSTM, Orthogonal Codes with modulation 3.2 Multiple Antenna Systems 39 (a) C(N) for Rm = 2 bits/(ch. use), orthogonal and diagonal con- stellations for N = 2,3,4 2 r —Urffcifi-ffl : m m m m m i fir '0 0 5 10 SNR (101ogio(B./JV )) [dB] 0 (b) C{N) for COD(-), rates R m = l,2 bits/(ch. Figure 3.7: Capacity C TM(N) DS for use) DSTM 40 3.3 Single Antenna Systems The advantage of MSDD with DSTM is shown in fig. 3.6(b), where we show the effect of increasing N on the channel capacity. As expected, while operating under unconstrained decoding delay scenarios for channel capacity, the increasing MSDD observation window N provides an increase in channel capacity for any given SNR of interest. Noting from [23] that in a perfectly interleaved fading channel, time diversity is utilized through channel coding, and additional transmit diversity is limited, we take into consideration N T = 2 DSTM analysis. As mentioned, the best DSTM constellations are taken according to table 3.2.4, and this can be seen fromfig.3.7(a). A comparison is shown between orthogonal constellations and diagonal constellations for N = 2,3,4, and we can see than orthogonal constellations perform best for modulation rate R m = 2 bits/(channel use). We also show in fig. 3.7(b) the capacities for 2 different modulations rates i.e Rm = 1,2 bits/(channel use), and N — 2,3,4. The constellations are taken from table 3.2.4. 3.3 Single Antenna Systems For the case of NT = NR = 1, traditional single antenna differential modulation with MSDD results. The analysis of the random coding exponent exactly follows along the lines of 3.2.3, and we forego the analysis and present only the results, which we apply in section 3.3.3 for performance analysis using the random coding exponent. 3.3.1 Noncoherent SISO Channel P D F For noncoherent transmission over a single transmit and receive antenna system, the channel described in 2.1.3 is completely characterized by the N dimensional pdf p(re,d[k] of the received vector r^A;] given the transmitted vector t^,d[A:]. Since r condi- tioned on s^d[fc] is the sum of zero-mean complex Gaussian random variables, the 3.3 Single Antenna Systems 41 conditional pdf according to [32] reads as ''* p ( r where yj hh 1 | 3 w l t ) ^ e t M W ^ M = + ( 3 ' 3 9 ) is the autocorrelation matrix. From this equation, the conditional proba- bility p(^,d[^]|v^d[A;]) is obtained by averaging the above probability p(r£ [A;]|s^[&]) )d with respect to the reference symbol S( d[k]. For trie-special case of M-ary DPSK, the t averaging mentioned above can be omitted, and we can further simplify the pdf 3.39 as iKrwWW*]) = + ( - °) 3 4 analogous to the multiple transmit and receive antenna metric. 3.3.2 Random Coding Exponent and Capacity Analysis As previously mentioned, we disassociate the channel coherence interval from the MSDD observation window, making the channel fading remain constant for DN symbols, where DN — 1 transmitted differential symbols are differentially encoded to produce transmission vectors of length DN. The analysis for the random coding exponent closely follows from the analysis done in section 3.2.3, so only the result will be reproduced here. Following the theoretical analysis, the random coding exponent for single antenna differential modulation can be written compactly as E(p, N, D) = max {E {p, N, D) - p.R,} 0<p<l (3.41) 0 with Gallager's function E (p, N, D) given by 0 E (p,N,D) 0 = -— ( log 2 f \^X{Pr{v }\{r \vt4)^ i4 u UV " V d = 1 D , i4 d=l 1 \P ^Y\Pr{v }\(rt \vi )^\ V -pM*)/) • l4 4 Y dr 4 e ) (3.42) ' 3.3 Single Antenna Systems 42 Once again, we apply the metric simplification from section 3.2.3 to reduce the number of candidate vectors for maximum likelihood decoding, by rewriting the expression for Gallager's function as D d=l £ Vld ^exp(X{r \v ))~^p(r \v , e4 i4 e4 h )} e4 e (3.43) {exp(A(r |«/, ))^}y /id {v d {p{r \v M)}Y £ l ltd t4 t4 Channel Capacity As discussed in section 3.2.2, channel capacity is another essential information theoretic tool to classify the memoryless block matrix channel between the transmitted symbols ve and the received symbols r^ . 4 Similar to the single antenna case, "capacity" in 4 this case refers to the associated mutual information normalized with the respect to each channel use i.e N — 1 as C ^ = jrh- = {log 2 } (3-44) Fig. 3.8(a) demonstrates the channel capacity for single antenna DPSK for different rates R = 1,2,3 bits/(channel use), and fig. 3.8(b) illustrates the random coding exponent for different MSDD observation intervals N for single antenna DPSK. Both channel capacity and the random coding exponent are demonstrated and explained in section 3.3.3. 3.3.3 Performance Analysis: Results and Discussion In this section, the presented analysis for the random coding exponent for single antenna DPSK as well as channel capacity are discussed. Correspondingly, channel ca- 3.3 Single Antenna Systems 43 -a— N=2,D=1 - e — N=3,0=1 - * — N=5,D=1 — « — DPSK —6— D4PSK — a — D8PSK £ °' r 8 \ . \ "x -10 -5 0 5 10 15 20 25 S N R (101og (E./JV )dB) 10 (a) 30 35 0 0.2 0.4 V \ 0.6 ~* 0 Channel capacities C(N) for sin- gle antenna DPSK, Rates R v = 1,2,3 \ 0.8 1 Rate in bi!s/(channel use) 1.2 1.4 1.6 (b) Random coding exponent E(R, N, 1) for single antenna DJ^PSK bits/'(channel use) Figure 3.8: Capacity and Gallager functions for Single Antenna DJ^PSK pacity and the word error rate obtained from the random coding exponent are analyzed as a function of the required signal to noise ratio 101og (£ /A ), and decoding delay l 10 r 5 0 in PSK samples t respectively. As general and interesting cases, for single antenna d modulation we consider 4-ary and 8-ary modulation supporting 2 and 3 bits/(channel use) respectively. Specifically, we consider D4PSK and D8PSK as suitable signal constellations for transmission. Throughout the thesis we consider block fading channels as already discussed in section 2.1.3. R a n d o m C o d i n g Exponent Results In this analysis, unlike channel capacity which has been discussed at length in literature, we put our transmission system under decoding delay constraints. As mentioned, we consider the random coding exponent to be a necessary and adequate information theoretic tool to analyze the transmission system, and to this end we discuss the average 3.3 Single Antenna Systems (a) E(R,N,D) 44 vs Rate R bits/(channel use) for single antenna D4PSK, CDD (N = 2) Diversity L=10 0 0.1 (b) E(R,N,D) 0.2 0.3 0.4 0.5 0.6 Rate R bits/(ch. use) —• 0.7 0.8 0.9 1 vs Rate R bits/(channel use) for single antenna D4PSK, MSDD (N = 6), decoding delay in PSK symbols=100 Figure 3.9: Gallager exponent E(R,N,D) vs Rate R, effect of coding diversity 3.3 Single Antenna Systems 45 (b) Required 10log (E /No) 10 s vs Coding Delay tj, in PSK symbols, standard MSDD vector channel with channel coherence interval=N i.e D = 1 Figure 3.10: Gallager random coding exponent results: Single Antenna D4PSK, delaySNR analysis 3.3 Single Antenna Systems 46 signal to noise ratio (SNR) yielding a random coding exponent, which in turn leads to a word error rate (WER) not greater than a given threshold P . Also, in order to clearly w emphasize the effect of various block fading scenarios on the random coding exponent, we show the Gallager exponent E(R, N, D) as a function of rate R in addition to the Gallager exponent-delay-SNR examples, to clearly illustrate the effect of the channel coherence interval on the random coding exponent. In all cases, we consider either D8PSK or D4PSK with supported rate 3 and 2 bits/(channel use) respectively and a block fading channel with channel coherence interval DN — 1 differential symbols. The target rate considered is R = Rv/(D.(N — 1)) where R^ is the rate in bits/(vector symbol). In figure 3.9, we show the random coding exponent E(R, N, D) as a function of rate R for D4PSK, where the decoding delay ta is kept fixed at 100 PSK samples, and the transmission diversity obtained by the varying fading coherence interval is changed. From figure 3.9(a) we note that as the fading diversity L is increased from 2 to 5 to 10, the random coding exponent increases, agreeing with our discussing wherein for the same decoding delay, the channel sees more independent fading realizations, thereby increasing the diversity and correspondingly the random coding exponent. The same argument is employed for figure 3.9(b), where instead of CDD as in the previous figure, MSDD with N = 6 is employed. In figure 3.10, the effect of MSDD is shown. For a fair comparison, the normalized coherence length DN is kept constant at 12, and the MSDD observation window N is varied. From this, we can clearly see the beneficial effect of increasing N while keeping the overall diversity constant, as the differential encoding effect becomes more apparent. Fig. 3.10(b) shows the required 10log (E /N ) 10 s 0 required to obtain a WER not greater than 0.001 i.e P < 0.001. For long delays, the situation resembles the w capacity case, where the decoding delay does not affect the performance significantly, and the effect of MSDD is apparent in the reduced SNR required to achieve a particular 3.3 Single Antenna Systems 47 D e c o d i n g delay (a)CDD(N —• D e c o d i n g delay = 2) (b)MSDD(N Figure 3.11: Required 10\og (E /N ) 10 s 0 -+ = 3) vs coding delay td for single antenna D8PSK, CDD(N — 2), fading coherence interval increasing with D WER. However for shorter delays, the effect of shorter component codes or the reduced diversity seen from the fewer independent fading realizations outweighs the effect of MSDD, and the curves intersect where increasing the observation window results in a deterioration in performance for td < 10 . . . 10 . 2 3 In order to demonstrate the effect of the channel with fading coherence interval not equal to N, we observe from figure 3.11 the effect of increasing D while keeping JV the same. Increasing D effectively reduces the number of independent fading realizations seen for a given decoding delay td, hence reducing the effective coding diversity. The effect of this reduction can be seen in the increased SNR required to achieve a particular WER as D increases. Finally, fig. 3.12 shows E(R, N, D) as function of R for D4PSK transmission, SNR 10 log (E /No) 1Q s = 10 dB, and fixed normalized coherence length n /L = 40. As can be seen from fig. 3.12, and as expected from MSDD performance c results in e.g. [8], the random coding exponent for MSDD approaches that of coherent detection with CSI, which is included as reference curve, with increasing N. Figure 3.12: Gallager Exponent E(R,N,D) lOlogioC&yJVo) = 10 dB vs R for D4PSK (N T = I) and Chapter 4 Modified Tree-Search and Sphere Decoding MSDD Algorithms In the previous chapter, we derived expressions for the random coding exponent for both single antenna systems and DSTM where the channel coherence interval was independent from the MSDD observation window. This helped us analyze a wide range of channels without any restrictions on the channel coherence interval, for example if the coding diversity was kept fixed but the MSDD observation window N was allowed to vary for analysis of different MSDD strategies. However, one drawback of this derivation was that the expression for Gallager's function E (p, D, N) given by 0 (4.1) 49 50 involved summing over all possible vectors V'i of length N, where the value for N 4 could involve an extremely high complexity cost as the complexity for MSDD increases exponentially with not only N but also with the number NT of transmit antennas and the modulation rate i? . In order to reduce the complexity cost for analysis of such m block fading channels, we make use of efficient tree-search algorithms to overcome the complexity limitations of MSDD for differential space-time modulation([34]), and with novel modifications to this tree-search approach we obtain an efficient implementation of Gallager's random coding exponent for our block fading channel under consideration. Furthermore, we propose a novel "modified metric" using this stack algorithm to provide accurate bounds for the random coding exponent and time delay analysis, which reduces the computational cost for analysis of our modified block fading channel by many orders of magnitude. In section 4.1 we consider the tree-search algorithm for single antenna systems, and explain the working of the tree-search stack algorithm. This algorithm will later be extended to the DSTM case in section 4.2 for Alamouti's N T xN T for N — 2 code T as well as diagonal DSTM constellations, where we use a modified sphere decoding algorithm to obtain computational efficiency during our search. We then achieve accurate bounds for the random coding exponent as well as the time-delay analysis of the random coding exponent in section 4.3 by using a combination of efficient modified tree-search algorithms, the modified performance metric for calculation of the random coding exponent and a novel sorting approach that enables us to formulate an efficient "stopping criteria" to terminate our MSDD tree-search for an increase in computational efficiency. We also analyze the effect of this modified metric on the random coding exponent and formulate a tradeoff between the efficiency or complexity of the tree-search algorithm and the tightness of the corresponding bound on the random coding exponent. Since our work is focused primarily on space-time coding, the analysis done for single-antenna systems serves as a reference for the DSTM case, 4.1 Single Antenna Systems: Multiple Symbol Differential Sphere Decoding (MSDSB} where we include some more detail to the analysis. We present results for the various approximations and bounds in section 4.4 for multiple antenna transmission as well as single antenna DPSK for reference. 4.1 Single Antenna Systems: Multiple Symbol Differential Sphere Decoding (MSDSD) In this section, we review some efficient algorithms for reducing the complexity cost of MSDD, where the complexity for decoding increases exponentially with the MSDD observation window N. We mainly focus on tree-search algorithms for MSDD for single antenna systems, and apply sphere decoding to Maximum Likelihood-MSDD (ML-MSDD) also known as multiple symbol differential sphere decoding (MSDSD) (see [22]). In this section, we devise efficient sphere decoding algorithms for MSDD corresponding to [22], where we reproduce the results here to make the analysis in further sections clearer. For maximum likelihood MSDD (ML-MSDD), we obtain the estimate s} >d based on the observation of the A-dimensional received MSDD vector r. For the case of Rayleigh fading, the maximum likelihood decision rule is [13] (4.2) s , = argmin{r£ B >^} e d rf r with the correlation matrix Rrr = (4.3) £{re,dr? \s } d e4 Applying the Cholesky factorization of the inverse matrix C 1 = LL , and further H defining U = (L diag{re })*, where L, U are upper and lower triangular matrices H id 4.1 Single Antenna Systems: Multiple Symbol Differential Sphere Decoding (MSDSD^ respectively, we obtain the ML decision metric (4.4) se = argmin{C7s£ || } 2 td id This is generally regarded as a shortest vector problem that can be solved using sphere decoding. The sphere decoder examines only those candidate vectors se,d that lie within a sphere of radius (distance) R \Us , e (4.5) <R As has been discussed, due to the upper triangular form of U, the metric for ML detection (see 4.4) can be checked component-wise i.e. having found initial candidates Si for the N — i previous components Si, % +1 < / < N, where we eliminate the indices £, d for simplicity, we can obtain a condition for the zth component as follows. If the squared length, =n N d: +i l=i+l N (4.6) 3=1 where Uij is the U entry in row i and column j, 1 < i,j < N, then the candidates Sj have to satisfy the criteria N d1 = uu8i+ Yl +d 2 < R 2 i+l (4.7) Once a valid vector s is found (i = 1), then the radius is dynamically updated by R — \\Us\ \ and the sphere decoding is repeated with i — 2 and the updated radius. If no candidate vector s is found within the updated radius R, MSDSD stops. The stack algorithm used in this thesis basically eliminates one drawback of the sphere decoding algorithm, where searching needs to start from the beginning each time the decoded is called to provide the next best candidate. In the stack algorithm, we calculate an initial metric (or sphere decoding distance) from the upper triangular matrix U, and each time replace the path at the top of the stack with all its extensions. This process is repeated, and the first path of MSDD length N at the top of the stack 4.2 Multiple Antenna Systems: Tree Search based Sphere Decoding Algorithms 53 is the optimal path corresponding to the best transmitted vector Vc, . We then store d the stack and continue with this stack when the next best candidate is required (see section 4.4.1). 4.2 Multiple Antenna Systems: Tree Search based Sphere Decoding Algorithms As mentioned previously, similar to the single antenna case, the complexity of MSDD for differential space time modulation too increases exponentially with the MSDD observation interval N. A number of sub-optimum decoders have been proposed for DSTM specific to certain Space-Time constellations and/or MSDD observation intervals ([11],[38],[6]). Lattice reduction based techniques ([5]) and sphere decoding techniques ([7]) amongst others have been proposed in literature, and to this end we apply tree-search based sphere decoding algorithms for efficient decoding for our purpose. From [34]the maximum likelihood (ML) metric can be rewritten as a sum of N non-negative scalar terms 6 ^\\Ve, Rn,n,(t, ) + Xe, \\ 2 n d where (4.8) 2 d d N X, t d = S i e,d n+ t / - n and Rn,ue,d) = ^z^RjAdA f,e,d n,j,{e,d) j=n+l s (-) R < n < N - 1, n < j < N. pf 4 ] and (ai ) n) 2 9 denote the jth. coefficient of the nth order linear backward minimum mean squared error (MMSE) predictor for the discrete time random process Ht 4 variance respectively, and N-l d ±Yl 2 n i=n + N(. td and the corresponding = — 1. Defining + <W = C i + %> X 2 1 < n < TV - 1, (4.10) 4.2 Multiple Antenna Systems: Tree Search based Sphere Decoding Algorithms 54 where d? = 0 and d\ is the ML metric in 4.9, we simplify the notation by eliminating N £, d. We begin the sphere decoding algorithm at n = N — 1, and select the candidate transmitted vector V based on tentative decisions Vj = Vj, n + 1 < j < N — 1 and n we decrement n until the current metric d does not exceed a certain maximum metric n p i.e d < p. Once we reach the top of the "stack" i.e. have traversed through until n n = 1, we use the metric of the currently examined best candidate V n to reduce the search space by updating p = d\. If, for any n, d exceeds p, n is incremented and a n new candidate transmitted vector is examined. Once the sphere decoder reaches n = N meaning that there are no candidate vectors inside the current search sphere, the algorithm stops. 4.2.1 Algorithms for Orthogonal Space-Time Codes For orthogonal designs, given by a -b* a, be b a* VMPSK (4.11) it is relatively easy to show that 51 = j + Re{a a } + Re{b p }, 1 < n < N - 1 n with a ,p n n n n n n being functions of the elements in i t „ , X )n that the parameters a ,b n n n ) T l (4.12) respectively. It turns out minimizing the distance 6 are independent of each other, n hence the sphere decoding algorithm can be regarded as an extension of single antenna MSDSD as in section 4.1 to differential space-time modulation. 4.2.2 Algorithms for Diagonal Constellations For diagonal constellations, given by the set V 4 [diag{e^ \ c D ..., e^^}'|/ G {0,..., L - 1}} (4.13) 4.3 Bounds Using Tree-Search Algorithms 55 using the cosine approximation, the problem for minimizing S can be turned into a 2 Ar-dimensional lattice decoding [5, 26] of the form 0 h &2,1 &2,2 x = argmin \ xez r (4.14) N ON ,1 0 t bit N Tt XN T T To obtain x, we apply the sphere decoding algorithm and take advantage of the lower triangular structure of 4.14. We find possible candidates for Xi € Z and increase h 2 < i < NT, as long as 2 A Mi = |&i,izi - * i | 2 + E \ J> b lXl + ™j ~ b £ *J I 2 < r 2 (4.15) J=2 with Xj = [(tj — bj^x^/bjj]. If fJ,N < r, X\ is considered to be the temporary decoder T result, and the search continues with the updated radius r — /J,NT- The sphere decoder terminates when {bi^xi — t\\ > r. Hence the overall search is limited to a single dimension rather than the NT dimensional search space of ML-MSDD. 4.3 Bounds Using Tree-Search Algorithms In this section, we aim to present accurate bounds to the random coding exponent using the results from section 3.3.2 and the above mentioned tree-search or Stack based decoding algorithms. Here, we reintroduce the notations for the modified channel of coherence interval DN, and differentiate between the corresponding metrics for the block fading channel where the fading coherence interval is equal to the MSDD observation window N. We begin by revisiting the ML noncoherent metric PN{Re,d\Ve,d) given by ,0 i v x exp {-tv{Rl * R }) l d R l4 4.3 Bounds Using Tree-Search Algorithms 56 where *R = = *(°lSt,dS? £R A *<d e,d\ t,d} R + OJ ) N v R (4.17) 2 >d t NNT with some arbitrarily chosen Se,d,i- We note that det{*H} is independent of V t. 4 Inserting (4.17) into (4.16) the decoding metric follows as \ (R \V ,d) N e>d e = \og{p{R jV ,d)) - ll^.dll N al e 2 e i + R Oftll-Ri,d 5i,rf|l _9^_o , AT_2\ N al{ol + Nal) g (A-\a\ 2 I - ) 4 A r 1 8 R -N \og(* tet{V }) NNT R R . Since we would like to provide accurate bounds on the random coding exponent E(p,N,D), we begin with the already derived expression for Gallager's function for differential space-time modulation for the modified channel, with channel coherence interval DN given by Eo{p,N,D) = -—log Uv 2 f (^llPr{Vd}XN(Ri, \Ve )^ i W d ( •p (Rt\V ) 4 DN ^ d=i i J • J E L I ^ a } A N ( % | T ) ^ dRe ? r a \ V e J k=l (4.19) Different from the case of coherent detection with CSI, the MSDD metric \N{Re,d\Ve,d) cannot be split into individual terms depending only on Vi , 4tn averaging over the set V ^ - 1 1 < n < N — 1. Thus, instead of V is necessary in (4.19), which becomes com- putationally expensive for large values of N. We therefore consider an approximation of E (p, N, D) using only a subset V C V ^ 0 s - 1 of differential symbols to reduce compu- tational complexity when numerically evaluating E (p, N, D). We begin our analysis 0 with the special case of D — 1 and spatially uncorrelated fading, and based on the results obtained we look at the block fading channel under consideration, where the fading coherence interval is not fixed. 4.3 Bounds Using Tree-Search Algorithms 4.3.1 57 D — 1 and Spatially Uncorrelated Fading For the interesting special case of D = 1 and spatially uncorrelated channels, i.e., each block of N transmitted space-time symbols experiences independent fading and 4.16 is the correct ML decoding metric, the Gallager function can be simplified to E (p,N,D = l) = - 0 1 (N-1) £ 2 (4.20) {piReAVe^} VlA log (fv {p(fle,i|V i)})^ lll 4 Considering (4.20) it is reasonable to choose the subset V of the ML search space such s that the ratio r(C ) 4 aja < 1 (4.21) s with a a 4 ' ~ £ {p(R \Vt^} V(1 E (4.22) e>1 l ^ r M R ^ \ V ^ ) ) ^ (4-23) is maximized for a given cardinality C ±\V \<M S S N-1 (4.24) This means we only consider the dominating terms when averaging over V^i and to do so, we need to sort matrices V^,i 6 V ^ - 1 according to decreasing values of p{Re,i\V^i). A) Sorting: An efficient way to accomplish sorting without actually calculating p(Re,i\Ve,i) for all Vf,i G V ^ - 1 is to run a detection algorithm which returns the best (ML) and successively the next best estimates for Ve,i according to p(R^\Vt,i) a n d given R. tii 4.3 Bounds Using Tree-Search Algorithms 58 As this detection requires a tree search and the search metric is additive, we use a modified version of the stack algorithm as described in section 4.2, which continuously finds the next best signal point. We calculate the maximum likelihood metric using the tree-search based stack algorithm as described in the previous section, each time saving the stack and corresponding the path through the tree as we proceed. We then rerun the algorithm starting from the previously saved locations, thereby giving us the next best metric to the ML metric. We continue this process until sufficient accuracy and/or complexity has been reached according to 4.21. B) Choice of C : s For a given C the ratio r{C ) in (4.21) significantly varies depending on the realization s s Ri,\. It is therefore advisable not to fix C but to choose it adaptively when Montes Carlo integrating (4.20). To this end, let V ^ ' be the C th best term found by the s s stack algorithm. The upper bound a 4 a + (1- C /M - ) N u s 1 S (piRvlV^j) ^ >a (4.25) for a allows to lower bound r(C ) by s r(C ) > ^ . (4.26) s We then can choose C such that the lower bound exceeds a certain threshold value of, s e.g., 0.9 for 90% accuracy of the Stack Algorithm. We can then control the accuracy of our approximation, by modifying the parameter r(C ). A higher value of r(C ) closer s s to 1 indicates a higher accuracy, however it would also involve a higher complexity. In this case, rather than computing the additions or complex multiplications to gauge complexity, we define complexity as the number of candidate vectors in the signal space of dimension M DN that the stack algorithm tests in order to achieve a certain accuracy for the random coding exponent (RCE) bound. 4.3 Bounds Using Tree-Search Algorithms C) Bounds for 59 E (p,N,D): 0 Let us define (4.27) )})** (4.28) •p(Re,i\V ) ttl •p{Re,i\V ,i)+ e (4.29) {l-C /M ^)p{R^\Vf{ ) N ] s We note that {<j/ri) 1+p is used in (4.20). Since the function f(x) = x ^ "> is concave l l+p for 0 < p < 1, the inequalities (4.30) hold. Hence, E (p,N,D = 1) in (4.20) is, respectively, upper and lower bounded 0 when using the subset V s and replacing the exact ratio a/r] with a /n s s and a /r] , u u respectively. 4.3.2 D > 1 and Spatially Uncorrelated Fading In the previous section, we dealt with the special case of D = 1, where we reverted to the traditional block fading channel with the fading coherence interval equal to the MSDD observation interval. We outline a procedure to obtain lower bounds on the random coding exponent and Gallager's function E (p, N, D) for any general block 0 fading channel, i.e. D > 1 as well as spatially correlated fading. Although in this case the pdf p(Ri \Ve d, He) is used for Monte-Carlo integrating (3.36), and thus r(C ) 4 t s does not appear in the expression for Gallager's function, we extend the application of the bound (4.26) to determine the set V to these cases.. The reasons for this are that s 4.4 Performance Analysis and Results 60 (a) r(C ) (or its bound (4.26)) is still a good indicator whether the terms dominating s the argument in (3.36) for given Rz and Hi are taken into account and (b) sorting V^d according to a mixed criterion of exp(\(Rz d\Ve, ))~ ^ ^ p i 1+p d and p(Ri \V t ) or 4 4 p(Rt,d\Vt,d, H ) would depend on p. e We note that in this case, using only the set V does not result in bounds for the s Gallager function, but rather approximates Eo{p, N, D). 4.3.3 Upper Bound to the Random Coding Exponent We further explore the possibility of upper bounding the random coding exponent, thereby lower bounding the word error rate, by modifying the metric in 4.30. In order to achieve this, we assume that the tree-search based sphere decoder iterates through the ML probabilities in order, and assuming the C th iteration is in progress, s we approximate all the remaining M NrRm — C probabilities with the most recent s output of the sphere decoder, i.e. PN(Re,d\V^d)^ K Cs We therefore approximate the contributions of the remaining candidate vectors to the most pessimistic value, since our sphere decoder outputs the channel probabilities in ML order. We see that this approximation is actually a very accurate upper bound to the random coding exponent, and using the lower and upper bounds previously derived, the word error rate for any particular block fading channel can be accurately bounded through our analysis and with a computational efficiency many orders of magnitude better than the ML solution. 4.4 Performance Analysis and Results We illustrate the various sphere decoding decoding algorithms explained in this chapter through various illustrative examples. We use these decoding algorithms to upper and lower bound the random coding exponent and correspondingly the probability of 4.4 Performance Analysis and Results 61 error, and show how our approach results in a significant reduction in computational complexity for the random coding exponent. 4.4.1 Single Antenna Systems We illustrate the tree search algorithms for single antenna systems namely the stack algorithm, and show how we can obtain accurate bounds for the random coding exponent using a combination of the tree-search algorithms and a stopping criteria ratio. We illustrate how modifying the ratio r(C ), which acts as an accuracy parameter for s our approximation, affects the lower bound to the random coding exponent, and we also show the complexity advantage that we gain from using the modified tree-search decoding algorithm to obtain recursively the best noncoherent metrics. In fig. 4.1(a), we show the Gallager random coding exponent as a function of the decoding delay t^, and plot it against the SNR (101og (/^ /A )) required to achieve a WER < 10e . -3 10 s 0 We show the results for CDD (N = 2) as well as MSDD (N = 3,4, 5,6) for single antenna D4PSK as before. In order to provide a good approximation for the exponent we bound it using the stack algorithm (see section 4.1), and fix the accuracy parameter to 90%. We can then fix the accuracy for the stack approximations by controlling the parameter C - In fig. 4.1 we fix this parameter so that the ratio in 4.26 does not exceed 0.9, thus s giving us an accuracy of 90%. We can see that using this criteria to approximate the random coding exponent does not involve a great deal of loss in the approximation, the maximum loss never exceeds 0.1 dB. However, the complexity advantage gained by using efficient stack algorithms is significant, and justifies the negligible loss in accuracy. For example, in fig. 4.1(b) we compute the complexity for the random coding exponent bound in fig. 4.1(a). We can clearly see that for the scenario in fig. 4.1(a), the ML solution would involve M ^ ~ ^ D N 1 — 4 = 1024 test vectors and their corresponding 5 4.4 Performance Analysis and Results 62 (a) Random Coding Exponent for DJPSK: Lower bound using Stack Algorithm. Overall accuracy 99%, according to 4-26 (b) Complexity analysis for Stack algorithm: D4PSK with N = 2,3,4,5,6, 90%,99% accuracy of Stack algorithm Figure 4.1: Stack algorithm bounds for D4PSK: MSDD with 99% accuracy 4.4 Performance Analysis and Results 63 - a — N=6,99% Stack Accuracy . _ • _ . N=6, 90% Stack Accuracy N=6,D=1, RCE N=3,D=1, RCE N=3, 99% Stack Accuracy B GJ\ ; \\ \ V \ T h 1 4 \ \ \3 : w \• \ 1 2 L 1 1 • i 1 10 2 i i j i_ * 10 i 1 i i_ 1 10 3 D e c o d i n g delay 1 1 1 4 — • Figure 4.2: Random Coding Exponent for DJ^PSK: Lower bounds using Stack Algorithm with different accuracies. CDD (N = 2) and MSDD (N = 6) with 90% and 99% accuracy metrics to be calculated. However, for SNR's of interest to us such as an overall E /NQ S of 10 dB, the number of test vector needed to provide a 99% approximation to the true random coding exponent is almost 10 orders of magnitude less (approx. 10 ). Similar results are obtained for smaller values of N, however the cases of interest 2 where the overall signal space would be too large begin from about N > 4. As a comparison, we also show the reduction in complexity that could be achieved if the accuracy constraint was further reduced to 90%, however the savings in complexity do not justify the negligible improvement to the random coding approximation. This can 4.4 Performance Analysis and Results 64 (a) Random Coding Exponent for D8PSK: Lower bound using Stack Algorithm. Overall accuracy 99%, according to 4-26 (b) Complexity analysis: D4PSK and D8PSK with N = 5,7, different accuracies of Stack algorithm with same ML search space Figure 4.3: Complexity and random coding analysis of Stack Algorithm, D4PSK and D8PSK with 99,90 and 85% accuracy 4.4 Performance Analysis and Results 65 be seen iffig.4.2, where we compare the lower bound achieved with different accuracies of the stack algorithm. We see that reducing the complexity from 99% to 90% shows a marked difference in accuracy to the true RCE, however the reduction in complexity is not significant, as we see from fig. 4.1(b). In fig. 4.3, we show the effectiveness of the stack algorithm for D8PSK, and compare the complexity advantage gained with the corresponding D4PSK signal space. In each case, the ML estimate would have to take into account the same number of signal points, however the stack algorithm for each accuracy performs significantly better for D4PSK than D8PSK. The advantage gained is again in orders of magnitude, and is thus an invaluable tool too accurately approximate the random coding exponent for higher dimensions where a ML decoder would be prohibitive. In fig.4.3(a), we demonstrate the accuracy for smaller values of N i.e CDD with N — 2 and MSDD with N — 3 and can see that even with extremely limited vector search spaces, the Stack algorithm does an excellent job of approximating the exponent, as the accuracy of the decoder increases with the size of the search space. 4.4.2 Multiple Antenna Systems Bounds using Sphere Decoding for Spatially Correlated Antennas Similar to the case of D > 1 and spatially uncorrelated fading, we analyze the transmission scheme where spatial correlation results in a loss of diversity. In previous sections, we look at the case of a general block fading channel considering spatially uncorrelated fading, i.e the channel between each transmitter and each receiver is modeled as an independent fading channel, with the fading coherence interval equal to DN. Here we also present and analyze some results for the case of spatially correlated channels, which also provides us with interesting insights into the behavior of such channels. We begin with the case of spatial correlation, where the channel between each transmitter and receiver does not experience independent fading, but is correlated with a param- 4.4 Performance Analysis and Results 66 — * — 16OD,rho=0 •e— 16OD,rho=0.5 •B— 16OD,rho=0.8 Single Antenna D4PSK 16OD,rho=0.99 0.5 Rate R bits/(ch. use) 1 —• (a) Orthogonal Codes: Coding diversity 10 i.e n /L = 20 c - 16DI,rho=0 16DI,rho=0.5 16DI,rho=0.8 16DI,rho=0.99 D4PSK 0.3 A 0.15 0.1 . ^ 0.5 Rate R bits/(ch. use) (b) Diagonal constellations: Coding diversity 5 i.e n /L = 40 c Figure 4.4: E(R,N,D)vsR for DSTM, different ST codes with Rt = 1 (bit/ch. use), spatially correlated antennas. 4.4 Performance Analysis and Results 10 - : • 67 Correlation 0 (DSTM,C(od)16,N=2,D=1) :" Correlation Factor 0.5 Correlation Factor 0.9 Correlation Factor 0.8 — Decoding delay Figure 4.5: Required E /N S 0 vs decoding delay td for DSTM with CDD, COD(16) with Rt = 1 (bit/ch. use), spatially correlated antennas eter we denote as p. We model this spatial correlation, for example with N = 2 and T N R = 1 by generating Gaussian random variables #1,52 such that g = p.g + y/l - p 2 r 2 5 l (4.31) where the greater the value of p, greater is the correlation. For p = 0, we revert to the uncorrelated channel scenario. In fig. 4.4(a), we plot the random coding exponent E(R, N, D) against the rate R for orthogonal constellations, with a target rate Rt = I bit/(channel use). We plot this exponent for different values of the parameter p indicating different levels of correlation between antennas. Wefindthat the performance of the system w.r.t the random coding exponent deteriorated significantly as p approaches the fully correlated case i.e p = 1, and at that Value of p = 1, the performance of the overall space-time model approaches that of an equivalent single antenna system. This is because as the antennas become more correlated, the channel between the NT — 2 transmit antennas and the N = 1 receive antennas becomes the same, and the overall R 4.4 Performance Analysis and Results 68 effect is the same as if there was a single channel between the transmitter and the receiver, (p = 1 implies that the channels are the same). Fig. 4.4(b) illustrates the same effect for the case of diagonal constellations with the normalized coherence interval n /L = 40 implying a coded diversity of 5. c In order to clearly visualize the effect of spatial diversity on the random coding exponent, we plot the required E /N s 0 vs the decoding delay t in PSK samples in fig. 4.5. d We can see that corresponding to fig. 4.4, as the spatial correlation between antennas increases, a significant drop in the RCE performance results, and this bears out our E(R, N, D) analysis showing that the performance of DSTM with spatially correlated antennas approaches that of the single antenna transmission system as the correlation factor p increases towards 1. Diagonal vs Orthogonal Constellations We present some simulation results to justify our claims from the previous section, where we devised tree-search based sphere decoders for orthogonal and diagonal constellations, in order to accurately represent the random coding exponent for differential space time modulation with high dimensions and correspondingly large matrix search spaces. We also look into different space-time constellations as in the capacity analysis in chapter 3 from a random coding exponent point of view. We present simulation results related to the bounds for E (p, N, D), and to this end, we analyze the sphere 0 decoding algorithms for orthogonal and diagonal constellations first, and demonstrate the effectiveness of these algorithms be comparing the bounds obtained using such efficient decoding algorithms with the true calculation of the random coding exponent. In fig. 4.6(a), we compare the random coding exponent E(R, N, D) for two commonly used space-time constellations namely orthogonal constellations and diagonal constellations. We see that for a modulation rate Rm = 2 bits/(channel use), the orthogonal constellations consistently outperforms the diagonal constellation. This is also demon- 4.4 Performance Analysis and Results (a) E(R,N,D) for DSTM: Orthogonal Cou(16) 69 and diagonal Cjr)/(16) codes, Rtarget — 1 bit/(channel use) (b) RCE for DSTM: (b) Stack algorithm for orthogonal and diagonal codes, Rtarget = 1 bit/(ch. use) Figure 4.6: Random coding exponent for DSTM:CQD{^) and Co/(16) codes 4.4 Performance Analysis and Results 70 strated by the capacity results from chapter 3. Combining this with the modified block fading channel, we demonstrate also the effect of coding diversity on the random coding exponent, where the normalized channel coherence length n /L is changed to reflect c different coding diversities. We see that for both diagonal as well as orthogonal constellations, an increase in diversity results in an increase in the random coding exponent performance, reflecting the effect of seeing more independent fading realizations per codeword for the same delay. We also present in fig. 4.6(b) the lower bounds to the exponents in fig. 4.6(a) obtained using the sphere decoding algorithms from section 4.3. We fix the accuracy of the sphere decoding algorithms to 90%, and observe that we can very closely approximate the random coding exponent to within ± 0.1 dB. Lower Bounds to the R a n d o m C o d i n g Exponent using Sphere Decoding As mentioned, we have described the method to use efficient tree-search based algorithms to bound the random coding exponent for single as well as multiple transmit antenna transmission systems. We have shown illustrative examples in 4.4.2 to show the effect of the modified block fading channel on the random coding exponent with D > 1. Here we present some examples analyzing the E /N s 0 performance of our ap- proximations and bounds to the random coding exponent, and observe the effectiveness of our proposed scheme to accurately lower bound the exponent for different cases of single antenna transmission and DSTM, with the fading coherence interval independent of N. In fig. 4.7(a), we plot the required E /N s 0 in dB against the decoding delay td for single antenna D8PSK, where the MSDD observation interval N — 2, and D varies to reflect different fading coherence intervals. We also lower bound the random coding exponent using the stack algorithm with 99% accuracy. We observe that though the overall performance of the system deteriorates with increasing D, because of the reduced diversity observed due to fewer independent fading realizations seen by each codeword, the stack approximation nevertheless gives us an accurate bound to the ran- 4.4 Performance Analysis and Results 10 71 10" Decoding delay fcj (a) SNR-delay analysis, D8PSK with CDD (N = 2) and varying D 2,3,5,10 with lower bound using stack approximation: effect of D 400 600 Decoding delay (b) Random coding exponent for DSTM bounds. Figure 4.7: 1200 vs DPSK, Sphere decoder 4.4 Performance Analysis and Results dom coding exponent even for higher values of D » 72 N. This proves our claim that by a novel combination of sphere decoding/stack algorithms and a performance metric designed to optimize the search space for the random coding exponent calculation, we obtain very accurate bounds to the exponent and at the same time increase the efficiency of the analysis by many orders of magnitude over current analysis techniques. Fig. 4.7(b) shows the application of the sphere decoding algorithm from section 4.2 to lower bound the random coding exponent for DSTM, where the constellation chosen is the orthogonal constellation COD(16), and we can compare the performance of single antenna DPSK with DSTM. We see that for the same transmitted vector length DN for both single and multiple antenna systems, the performance of MSDD consistently improves with N for both DPSK and DSTM. This is different from our earlier analysis when we kept the overall coding diversity constant, and hence as D increased, the performance degraded due to reduced independent fading intervals seen by the system. We also note that the stack algorithm for DPSK and the sphere decoding algorithms for DSTM provide an excellent bound to the random coding exponents. Our proposal has the added advantage of being computationally effective as compared to current techniques to analyze the random coding exponent. As an excellent example, we provide the approximation (bound) for the random coding exponent for N = 6 with DSTM in fig. 4.7(b), where the computation of the exponent would involve a best metric search through 1, 048, 576 or 1 million candidate vectors, and would limit the channels which could be analyzed purely due to computational complexity. U p p e r Bounds using Sphere Decoding In this section, we complete our analysis of the random coding exponent for single antenna and multiple antenna systems by attempting to upper bound the exponent with an innovative approximation to the metric in section 4.3. In this case, in fig. 4.8(a) we begin with the single antenna case for the Gallager exponent E(R, N, D) for D4PSK 4.4 Performance Analysis and Results 73 -1 -e— -*— -e— -6>— -4— N=2 N=3 N=6 N=11, Approx. lower bound N=11, Approx. upper bound Coherent with CSI — B — Exact - *• - Approx. from upper bound - *• - Approx. from lower bound -3 •N = 6 >0\* \\\ .. . \ \ \ V\V' \ \ \ \ °\ \. . .\. \ \ \ \ \ -10 0.5 (b) ' Figure 4.8: E(R, N, D) vs. R: D4PSK and Wlog (E,/N ) 10 0 1.5 = 10 dB. (a): MSDD with different N. (b): N = 6. Exact expression and approximation for E (R, N, D). r njL = 40. and NT — 1. We plot the random coding exponent as a function of rate R in fig. 4.8(a) to serve as a reference, and can see that the exponent approaches the performance of coherent detection with CSI as the MSDD observation window Af increases. Since the complexity associated with A^ > 10 becomes prohibitive to simulate, we present the upper and lower bound approximations using 4.30 to bound the true random coding exponent, and hence the overall W E R . Fig. 4.8(b) gives us a much clearer insight into this approximation where we plot the bounds on a logarithmic scale along with the true R C E for N = 6. Extending this approximation the the multiple antenna case, in fig. 4.9, 4.4 Performance Analysis and Results 74 we refer back to fig. 4.7(b) to compare the performance of single antenna DPSK and DSTM, but we upper bound the random coding exponent along with the true RCE. We can see that our analysis does indeed give us an excellent upper bound to the random coding exponent To this end, we show the SNR 101og (.E'&/iVo) required to achieve 10 Pe < 10~ according to (3.33) as function of code length n for transmission with rate 3 c R = 1 bit per scalar channel use. The normalized coherence length is n /L = 100, i.e., c degrees of freedom L and thus coded diversity increase linearly with code length n . c Two things are interesting to note. First, increasing N consistently improves power efficiency regardless of n . This is decidedly different from [24], where coded diversity c was decreasing with N. Second, the gain due to transmit diversity increases with decreasing n . This result reiterates the benefits of spatial transmit diversity if coded c diversity is limited, e.g. due to delay constraints. 4.4 Performance Analysis and Results Figure 4.9: Required 10\og (E /N ) w b 0 75 for P < 1(T vs. 3 e n. c 4DPSK (N T = 1) and 160D (N = 2). n /L — 100, R — 1 bit/(scalar channel use): upper bound approxiT mation c Chapter 5 Conclusions and Future Work In this thesis, we consider coded space-time transmission with multiple antennas over a block fading channel with an arbitrary fading coherence interval and a finite code length, with differential encoding applied at the transmitter. We focus our attention on error exponent analysis of such channels, namely the calculation of the random coding exponent proposed by Gallager. Our work differed from previous work in this field, which limited error exponent analysis to block fading channels with the fading interval equal to the MSDD observation window N. • To this end, we derived an expression for the random coding exponent for differential space-time modulation and MSDD over a block fading space-time channel where the fading coherence interval is arbitrary. This extension to previous work is particularly important as it allows for a fair comparison of MSDD with different window sizes but fixed coded diversity. • Furthermore, we devised upper and lower bounds and approximations for the random coding exponent using tree-search based sphere decoding algorithms for orthogonal and diagonal space-time codes. These sphere decoding algorithms en- 76 77 able efficient Monte-Carlo integration, and reduce the complexity cost by several orders of magnitude at SNR's of interest. • To achieve this, we proposed a novel performance metric to control the accuracy of the approximation, and correspondingly the computational complexity. We illustrated the potential advantage of our analysis with several numerical results to demonstrate the usefulness of our approximations, the improvements with increasing observation interval N and the benefits of spatial transmit diversity even in highly correlated channels for coded DSTM transmission with short or moderate code lengths. Through our investigations, we believe that we have formulated a novel and innovative approach to calculate the random coding exponent for a wide range of channels, and have provided researchers with an invaluable technique to calculate such exponents with a performance efficiency increase of several orders. Through our analysis and subsequent simulations, we can summarize our findings as follows: • The performance of the random coding exponent for DSTM with MSDD approaches that of coherent detection with perfect channel state information. • The analysis allows for accurate comparisons of systems with fixed coded diversity but different MSDD observation windows. The random coding exponent performance degrades with an increase in the fading coherence interval for the same code length, effectively reducing the overall diversity due to a reduced number of independent fading realizations. • If the transmit diversity increases, the random coding exponent performance improves correspondingly, reiterating the benefit of our analysis where we enable accurate analysis of block fading channels with arbitrary fading intervals. Previous work limited the analysis of the random coding exponent to block fading 78 channels without the advantage of analyzing the effect of coding diversity, as the channel coherence interval was equal to N. • We also devised bounds and approximations for the random coding exponent using efficient decoding techniques such as tree-search based sphere decoding algorithms. We found that the novel performance metric we devised to control the accuracy of the approximation enabled an excellent approximation to the random coding exponent, at the same time reducing the computational complexity of the analysis by several orders of magnitude. Another advantage to our approach was the flexibility to balance the degree of accuracy of the approximation with the complexity cost. We concluded that reducing the accuracy from 99% of the full-search approach (taking all possible candidate vectors into account) to 90% gave us only a marginal improvement in computational complexity, as opposed to the improvement of several orders of magnitude in computational complexity when reducing the accuracy from the full-search to 99%. • Different from previous work, we also took into consideration the effect of spatial correlation between antennas, and through suitable examples demonstrated the random coding exponent for such systems with varying degrees of correlation. We concluded that as the spatial correlation approached full correlation (the parameter p in our analysis approached 1), the performance of DSTM degraded and became equivalent to a single antenna link between the transmitter and the receiver. • We also successfully outlined a procedure to provide an accurate upper bound to the random coding exponent, and along with the lower bound obtained from the sphere decoding algorithms coupled with a suitable performance metric, we demonstrated a technique to bound the error exponent performance of coded transmission over a multiple antenna link with MSDD. 79 In our opinion, there are a number of interesting and advantageous research topics for future work in this field. The work done in this thesis can further be used to analyze channels with frequency selective fading or time-varying channels. We can also combine the analysis from this thesis with different coding strategies such as bit-interleaved coded modulation (BICM) or hybrid coded modulation (HCM). We could also consider the application of the analysis from this thesis to the design of noncoherent coded modulation schemes for multiuser communications and for extremely high bandwidthefficient MIMO systems. Appendix A Derivation of Gallager's Function with Coherent metric In this appendix, we present the derivation of Gallager's function with reduced complexity metric given by 3.36 in detail. The channel is the block fading channel considered throughout this thesis channel, seeing L independent fading realizations, where the channel remains constant for DN symbols (PSK symbols or matrix symbols corresponding to single antenna or DSTM respectively). For simplicity, we denote the N dimensional vectors Re [k], Vi^k] as R, Vi respectively, we begin with the expression 4 for Gallager's function E (p, N, D) 0 (A.l) where R is the vector of overlapping symbols of length L.D.N = ri , n = LDN, ny = w w L.D. In our analysis, without any loss of generality we can consider non-overlapping 80 81 blocks, as such a system would have the same performance as a system with overlapping when M S D D is applied and noncoherent transmission is considered. Thus E {p,N,D) 0 = j±log [ 2 I E niMV }A(J*|V«) 4 -/»/(i+p) P(«|V) R6C t=l ViSV^- 1 (A.2) Since p(Hiv)=n (j^iv ) P (A.S) / and p(Jfc|V*) = Jp(H )p(Re\Ve,H )dH e e t Hi = (A.4) E ^ Jp(Hi)p(Re\Si,H )dH e t so where So is the reference symbol, we get E (p,N,D) 0 = —log £=1 so 2 ^ [ ( n ^ v j A ^ iy . ) - p / ( l + p ) E Pr{V }A^(iJ |V0 '' ] dRt 1/(1+ i ) i (A.5) Since each block of L samples experiences independent fading, we separate the product 82 over L.D and obtain E (p,N,D) n = —log. Q / DN Vy t ^ E / 50 fiPrwmivr^ f E R eC e=1 / 6 V D<"-i>t=l P(HMRe\Se,H )dH t e ff. i=i Vjev*- 1 (A.6) -1 °g LD 1 2 ^ E / n ^ Pr{V }A(ii |V,) i t=l V j G V ^ - n {^} (^i^) E pr A _p/(i+p) ^i^^) ) 1/(1+p) i 1 (A.7) Since p ( ^ | 5 / , = \\p{Ri\S h Hi), i=l E (p,N,D) 0 = -^log |( 2 ^E 53 /yWn Pr{^}A(H |V )-"/( ").p(H |^,^)] 1+ Pr{VjA(R |V ) i i i 1/(1+ ' i i ,) J (A.8) \dHidRe Rewriting the above equation using the relation p(R , H , s ) - p(Rt, H \s ) • p(s ) = J^P( ^ r e e 0 t 0 0 H \s ) e 0 (A.9) 83 we get E (p,N,D) D -1 E Q / / Pi***, H , s ) • f[ e 0 (A.10) PriViMRilVi) '^ ) 1 \dHedRe Finally, in order to efficiently use Monte Carlo techniques we write Gallager's function in terms of expected values as ( D E (p,N, D) = 0 S --\og II £RI,HA 2 {exp(\(R \V ))-T^p(R \V ,H )} Vi i i i (5v {exp(A(H |V )) ^})' 1 i (£ i i {piRilV^He)})- 1 Vi i e (A.11) Appendix B List of Symbols and Acronyms In this appendix, we summarize the important symbols and list the acronyms used throughout this thesis. Operators argmax{.} argument maximizing the expression in brackets diag{.} diagonal matrix with diagonal entries of vector argument Sx{.) expectation with respect to X Pr{.} probability Re{.},Im{.} real and imaginary parts of a complex number (•)* Hermitian transposition (•) transposition (•)* complex conjugation |.| magnitude of a complex number T 84 Constants j imaginary unit: j = — 1 TT the number pi: TT = 3.14159265358979... e Euler number: e = 2.718281828... Ox X x X all-zero matrix Ix X x X identity matrix 2 Sets c signal constellation c matrix (space-time) signal constellation N natural numbers R real numbers S alphabet of scalar transmit symbols s alphabet of matrix (space-time) transmit symbols V alphabet of scalar data symbols V alphabet of matrix (space-time) data symbols z integer numbers C[i\,C[n] binary code symbol H[k] Ricean fading process N[k] discrete time zero-mean white Gaussian noise R[k] received (matrix) signal sample S[k] transmit (matrix) symbol V[k] data (matrix) symbol Miscellaneous Functions cos(.) cosine function det{.} determinant of matrix argument Kronecker delta function exp(.) exponential function log(-) logarithm to base e log (.) logarithm to base 2 logio(-) logarithm to base 10 p(-) probability density function p(-l-) conditional probability density function sin(.) sine function tr{.} trace of a matrix 2 Variables Scalars C(.) constellation constrained channel capacity Ccsi capacity of coherent transmission with perfect CSI 87 D number of blocks of length N transmitted over one fading interval random coding exponent 3>(v) Gallager's function E average received energy per information bit E average received energy per symbol /(•;•) average mutual information k scalar and matrix (space-time) symbol discrete-time, index, respectively AO log-likelihood metrics based on conditional PDFs L number of independent fading realizations per codeword I index of block within one fading realization M size of PSK symbol alphabet riy number of vector symbols per code word n number of vector symbols per code word for arbitrary block fading channel N observation window size for noncoherent detection b s D N 0 single sided power spectral density of passband noise process N number of transmit antennas N number of receive antennas Pw word error rate p parameter of random coding exponent R data rate in bits per channel use T R modulation rate in bits per channel use Ry data rate in bits per vector symbol a variance 2 noise variance u decoding delay T modulation interval 88 Matrices H[k] matrix of fading samples N[k) matrix of noise samples R[k] matrix of received signal samples S[k] matrix of space-time transmitted signal samples S [k] diagonal matrix of transmit symbols V[k] matrix of space-time data symbols V [k] diagonal matrix of space-time data symbols D D autocorrelation matrix Acronyms AWGN additive white Gaussian noise BER bit error rate CDD conventional differential detection CSI channel state information DPSK differential phase shift keying dB decibel DSTM differential space-time modulation MIMO multiple input multiple output ML maximum likelihood MLD maximum likelihood decoding MMSE minimum mean squared error MSDD multiple symbol differential decoding MSD-SD multiple symbol differential sphere decoding pdf probability density function PEP pairwise error probability PSK phase shift keying RCE random coding exponent SA stack algorithm SD sphere decoding SISO single input single output SNR signal-to-noise ratio ST space-time u.i.i.d. uniformly, independently and identically distributed WER word error rate Bibliography [1] S.M. Alamouti. A Simple Transmitter Diversity Scheme for Wireless Communications. IEEE J. Select. Areas Commun., 16(7):1451-1458, October 1998. [2] J.A.C. Bingham. ADSL, VDSL, and Multicarrier Modulation. John Wiley and Sons, New York, 2000. [3] J.K. Cavers. An Analysis of Pilot Symbol Assisted Modulation for Rayleigh Fading Channels. IEEE Trans. Veh. Technol., 40(4):686-693, November 1991. [4] N. Chiurtu and T.L. Marzetta. Random Coding Exponents For Unitary SpaceTime Modulation. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), page 301, Lausanne, June/July 2002. [5] K.L. Clarkson, W. Sweldens, and A. Zheng. Fast multiple antenna differential decoding. IEEE Trans. Commun., 49:253-261, February 2001. [6] T. Cui and C. Tellambura. Multiple-Symbol Differential Unitary Space-Time Demodulation with Reduced Complexity. Proc. of IEEE International Conference on Communications (ICC), Seoul, May 2005. [7] M.O. Damen, A. Chkeif, and J.C. Belfiore. Lattice code decoder for Space-Time codes. IEEE Commun. Lett, pages 161-163, May 2000. 90 BIBLIOGRAPHY 91 [8] D. Divsalar and M.K. Simon. Multiple-Symbol Differential Detection of MPSK. IEEE Trans. Commun., 38(3):300-308, March 1990. [9] D. Divsalar, M.K. Simon, and M. Shahshahani. The Performance of Trellis-Coded MDPSK with Multiple Symbol Detection. IEEE Trans. Commun., 38(9):13911403, September 1990. [10] R.G. Gallager. Information Theory and Reliable Communication. John Wiley and Sons, 1968. [11] C. Gao, A. Haimovich, and D. Lao. Multiple-Symbol Differential Detection for Space-Time Block Codes. Conference on Information Sciences and Systems, Princeton University, March 2002. [12] B. Hassibi and B.M. Hochwald. Cayley Differential Unitary Space-Time Codes. IEEE Trans. Inform. Theory, 48(6): 1485-1503, June 2002. [13] P. Ho and D. Fung. Error Performance of Multiple-Symbol Differential Detection of PSK Symbols Transmitted over Correlated Rayleigh Fading Channels. IEEE Trans. Commun., 40:25-29, October 1992. [14] B.M. Hochwald and T.L. Marzetta. Unitary Space-Time Modulation for MultipleAntenna Communications in Rayleigh Flat Fading. IEEE Trans. Inform. Theory, 46:543-564, March 2000. [15] B.M. Hochwald and W. Sweldens. Differential Unitary Space-Time Modulation. IEEE Trans. Commun., 48(12):2041-2052, December 2000. [16] B.L. Hughes. Differential Space-Time Modulation. IEEE Trans. Inform. Theory, 46(7):2567-2578, November 2000. [17] B.L. Hughes. Optimal Space-Time Constellations from Groups. IEEE Trans. Inform. Theory, 49(2):401-410, February 2003. BIBLIOGRAPHY 92 [18] J. Jalden, M. Skoglund, and B. Ottersten. On the Random Coding Exponent of Multiple Antenna Systems Using Space-Time Block Codes. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), page 188, Chicago, June 2004. [19] G. Kaplan and S. Shamai (Shitz). Error Probabilities for the Block-Fading Gaussian Channel. AEU, Int. Journal of Electronics, 49(4):192-205, 1995. [20] R. Knopp. Coding and Multiple-Access Over Fading Channels. PhD Thesis, Ecole Polytechnique Federale de Lausanne, 1997. [21] R. Knopp and H. Leib. M-ary Phase Coding for the Noncoherent AWGN Channel. IEEE Trans. Inform. Theory, 40(6):1968-1984, November 1994. [22] L. Lampe, R. Schober, V. Pauli and C. Windpassinger. Multiple-Symbol Dif- ferential Sphere Decoding. IEEE Trans. Commun., 53(12):1981-1985, December 2005. [23] L. Lampe. Noncoherent Coded Modulation. PhD Thesis, Universitat ErlangenNiirnberg, 2002. [24] L. Lampe and R. Fischer. Random Coding Exponent Based Design of Coded Modulation for Multiple-Symbol Differential Detection. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), page 163, Washington, June 2001. [25] H. Leib and S. Pasupathy. Optimal Noncoherent Block Demodulation of Differential Phase Shift Keying (DPSK). Archiv fiir Elektronik und Ubertragungstechnik (International Journal of Electronics), 45(5):299-305, 1991. [26] C. Ling, W. Mow, K. Li, and A. Kot. Multiple Antenna Differential Lattice Decoding. IEEE J. Select. Areas Commun., 23:1821-1829, September 2005. [27] E. Malkamaki and H. Leib. Coded Diversity on Block-Fading Channels. Trans. Inform. Theory, 45(2):771-782, March 1999. IEEE BIBLIOGRAPHY 93 [28] T.L. Marzetta and B.M. Hochwald. Capacity of a Mobile Multiple-Antenna Communication Link in Rayleigh Flat Fading. IEEE Trans. Inform. Theory, 48:139157, January 1999. [29] R.J. McEliece and W.E. Stark. Channels with Block Interference. IEEE Trans. Inform. Theory, 30(l):44-53, January 1984. [30] J.P. McGeehan and A.J. Bateman. Phase Locked Transparent Tone-In-Band (TTIB). IEEE Trans. Commun., 32:81-87, January 1984. [31] U. Mengali and A.N.D'Andrea. Synchronization Techniques for Digital Receivers. Plenum Press, New York, 1997. [32] K. Miller. Complex Stochastic Processes. Addison Wesley, New York, 1974. [33] M.L. Moher and J.H. Lodge. TCMP - A Modulation and Coding Strategy for Rician Fading channels. IEEE J. Select. Areas Commun., 7(9):1347-1355, December 1989. [34] V. Pauli and L. Lampe. Tree Search Multiple Symbol Differential Decoding for Unitary Space Time Modulation. Submitted to IEEE Trans. Commun., preprint available from http://www.ece.ubc.ca/ lampe/'publicat.html, 2005., 2005. [35] D. Raphaeli. Improvement of Noncoherent Orthogonal Coding by Time Overlapping. IEEE Proceedings-Communications, 141(5):309-311, October 1994. [36] A. Shokrollahi, B. Hassibi, B.M. Hochwald, and W. Sweldens. Representation Theory for High Rate Multiple-Antenna Code Design. IEEE Trans. Inform. Theory, 47(6):2335-2367, September 2001. [37] S. Srinivasan, L. Lampe, and V. Pauli. On the Random Coding Exponent for Differential Modulation and Detection. Submitted to ISIT 2006, Seattle, January 2006. BIBLIOGRAPHY 94 [38] P. Tarasak and V. Bhargava. Reduced Complexity Multiple Symbol Differential Detection of Space-Time Block Code. Proc. of IEEE Wireless Communications and Networking Conference (WCNC), Orlando, Florida, March 2002. [39] V. Tarokh and H. Jafarkhani. A Differential Detection Scheme for Transmit Diversity. IEEE J. Select. Areas Commun., 18(7):1168-1174, July 2000. [40] V. Tarokh, H. Jafarkhani, and A.R. Calderbank. Space-Time Block Codes from Orthogonal Designs. IEEE Trans. Inform. Theory, 45(5):1456-1467, July 1999. [41] J. Ventura-Traveset, G. Caire, E. Biglieri, and G. Taricco. Impact of Diversity Reception on Fading Channels with Coded Modulation-Part II: Differential Block Detection. IEEE Trans. Commun., 45(6):676-686, June 1997. [42] S.G. Wilson, J. Freebersyser, and C. Marshall. Multi-Symbol Detection of M DPSK. Proc. of IEEE Global Telecommunications Conference (Globecom), pages 47.3.1-47.3.6, November 1989. [43] J. Wolfowitz. Memory Increases Capacity. Information and Control, 11:423-428, 1967.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Gallager’s random coding exponent for differential...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Gallager’s random coding exponent for differential space time modulation Srinivasan, Siddharth K. 2006
pdf
Page Metadata
Item Metadata
Title | Gallager’s random coding exponent for differential space time modulation |
Creator |
Srinivasan, Siddharth K. |
Date | 2006 |
Date Issued | 2010-01-08 |
Description | In this thesis, we study differential space-time modulation with multiple transmit and receive antennas over a frequency non-selective block fading channel in the absence of channel state information (CSI) at both the transmitter and the receiver. We focus on the analysis of the random coding exponent proposed by Gallager for such spacetime channels employing differential modulation with finite signal sets, and consider multiple symbol differential detection (MSDD) with an observation window size N. The underlying principle of MSDD is to utilize an increased observation window of N > 2 consecutively received space-time samples to yield decision variables on N - 1 spacetime data symbols. We thus take into account the channel memory, and can improve power efficiency over conventional differential detection, which employs N = 2. We extend previous work for a similar setup, in that we consider channels where the fading coherence interval is different from the MSDD observation window N, and can be arbitrary with L independent fading realizations per coding frame. We analyze the effect of arbitrary fading coherence intervals on the random coding exponent, and therefore analyze the achievable performance of coded transmission over block fading channels with low to moderate code lengths, i.e. with decoding delay constraints. In this context we also analyze space-time transmission systems with spatial correlation between antennas. Such an analysis allows for a fair comparison of DSTM with MSDD where the window size may vary but the coded diversity remains fixed. We also devise upper and lower bounds and approximations for the random coding exponent, which allows us to not only bound the achievable performance of such space-time systems but also allows for efficient numerical evaluation of the random coding exponent by limiting the search space for the metric calculation. To this end, we make use of tree-search based sphere decoding algorithms for efficient decoding, and along with novel stopping criteria to control the accuracy of the approximation and correspondingly the computational complexity, we apply these sphere decoders for a reduction in complexity cost upto many orders of magnitude. The presented numerical results provide useful information on the performance of coded differential space-time transmission for short to moderate code lengths. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | Eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2010-01-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0092579 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2006-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/17770 |
Aggregated Source Repository | DSpace |
Download
- Media
- ubc_2006-0312.pdf [ 4.29MB ]
- Metadata
- JSON: 1.0092579.json
- JSON-LD: 1.0092579+ld.json
- RDF/XML (Pretty): 1.0092579.xml
- RDF/JSON: 1.0092579+rdf.json
- Turtle: 1.0092579+rdf-turtle.txt
- N-Triples: 1.0092579+rdf-ntriples.txt
- Original Record: 1.0092579 +original-record.json
- Full Text
- 1.0092579.txt
- Citation
- 1.0092579.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 7 | 0 |
France | 4 | 0 |
India | 3 | 0 |
Japan | 2 | 0 |
Germany | 1 | 0 |
Russia | 1 | 0 |
Indonesia | 1 | 0 |
Ukraine | 1 | 0 |
Canada | 1 | 0 |
Vietnam | 1 | 0 |
Pakistan | 1 | 0 |
China | 1 | 0 |
City | Views | Downloads |
---|---|---|
Unknown | 9 | 0 |
Ashburn | 4 | 0 |
Mumbai | 2 | 0 |
Tokyo | 2 | 0 |
Saint Petersburg | 1 | 0 |
Salt Lake City | 1 | 0 |
Norwood | 1 | 0 |
Islamabad | 1 | 0 |
Hanoi | 1 | 0 |
Munich | 1 | 0 |
Beijing | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0092579/manifest