@prefix vivo: .
@prefix edm: .
@prefix ns0: .
@prefix dcterms: .
@prefix skos: .
vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Electrical and Computer Engineering, Department of"@en ;
edm:dataProvider "DSpace"@en ;
ns0:degreeCampus "UBCV"@en ;
dcterms:creator "Maranda, Brian Howard"@en ;
dcterms:issued "2010-04-22T22:54:34Z"@en, "1982"@en ;
vivo:relatedDegree "Master of Applied Science - MASc"@en ;
ns0:degreeGrantor "University of British Columbia"@en ;
dcterms:description "The problem of computing the probability P[sub f](M,N) of more than M bit errors in a block of N bits for a Rayleigh-fading channel in the presence of additive white Gaussian noise is considered. In the case of very slow Rayleigh fading, analytical formulas for P[sub f](M,N) have been derived in the literature, but these formulas are not well suited for numerical computation. Several simple approximations for the special case P[sub f](O,N) have also appeared in the literature, but apparently no work has been done for the case M > 0. In this thesis an accurate approximation for P[sub f](M,N) is derived, and a bound on the error in this approximation is given. Also included are approximations for P[sub f](M,N) when selection diversity is employed. If very slow fading is not assumed, there exist no known analytical methods for the computation of the block-error probability. Simulations are performed on a digital computer for this case. Furthermore, an empirical formula is derived that can be used to estimate easily and accurately the output of the simulator. The consequence is a great saving of time and effort in the computation of a value of P[sub f](M,N) that is more realistic than that provided under the assumption of very slow fading."@en ;
edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/24089?expand=metadata"@en ;
skos:note "THE COMPUTATION OF THE BLOCK-ERROR RATE ON A RAYLEIGH-FADING CHANNEL IN THE PRESENCE OF ADDITIVE WHITE GAUSSIAN NOISE by BRIAN HOWARD MARANDA B.Sc, University Of B r i t i s h Columbia, 1979 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES Department Of E l e c t r i c a l Engineering We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA November 1982 © Brian Howard Maranda, 1982 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of E l e c t r i c a l E n g i n e e r i n g The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date December 2, 1982 DE-6 (3/81) i i Abstract The problem of computing the p r o b a b i l i t y Pf(M,N) of more than M b i t errors in a block of N b i t s for a Rayleigh-fading channel in the presence of additive white Gaussian noise i s considered. In the case of very slow Rayleigh fading, a n a l y t i c a l formulas for Pf(M,N) have been derived in the l i t e r a t u r e , but these formulas are not well suited for numerical computation. Several simple approximations for the special case P f(0,N) have also appeared in the l i t e r a t u r e , but apparently no work has been done for the case M > 0. In t h i s thesis an accurate approximation for Pf(M,N) i s derived, and a bound on the error in t h i s approximation i s given. Also included are approximations for Pf(M,N) when selection d i v e r s i t y i s employed. If very slow fading i s not assumed, there exist no known an a l y t i c a l methods for the computation of the block-error p r o b a b i l i t y . Simulations are performed on a d i g i t a l computer for t h i s case. Furthermore, an empirical formula i s derived that can be used to estimate e a s i l y and accurately the output of the simulator. The consequence i s a great saving of time and e f f o r t in the computation of a value of Pf(M,N) that i s more r e a l i s t i c than that provided under the assumption of very slow fading. i i i Table of Contents Abstract i i Table of Contents i i i L i s t of Tables v L i s t of Figures v i L i s t of Main Symbols v i i Acknowledgement x 1. Introduction 1 2. Very Slow Rayleigh Fading 6 2. 1 Background 7 2.1.1 The AWGN channel 7 2.1.2 The fading channel 9 2.1.3 The computation of Pf(M,N): Series expressions 11 2.1.4 The computation of Pf(M,N): Numerical integration 15 2.1.5 Approximate methods for the computation of P f(0,N) 17 2.2 A new approach to approximating Pf(M,N;r) 24 2.2.1 Introduction 24 2.2.2 Error analysis 28 2.2.3 The approximation to P f(0,x;r) 36 2.2.4 The approximation to P f(M,x;r) 40 2.3 I n f i n i t e series expansions 45 2.3.1 Introduction and notation 45 2.3.2 Extension of formula (2.1.26) 50 2.3.3 Extension of formula (2.1.24) 53 2.4 Div e r s i t y 58 2.4.1 Introduction 58 2.4.2 Approximations 60 3. A model for c a l c u l a t i n g block-error rates on slow Rayleigh fading channels 65 iv 3.1 The simulator 67 3.1.1 Implementation 67 3.1.2 Description of the algorithm 67 3.1.3 Generation of the fading sequence 70 3.1.4 Simulation results 74 3.2 Derivation of the empirical formula 81 3.2.1 Introduction 81 3.2.2 The model 81 3.2.3 Numerical results 84 4. Conclusions 99 References 102 Appendix A 105 Appendix B 108 B . I No d i v e r s i t y 1 08 B. 2 Div e r s i t y 111 Appendix C 113 C. 1 Existence of the expansions 113 C.2 Expressions for the c o e f f i c i e n t s in (2.3.15) 115 C.3 The asymptotic expansion of the c o e f f i c i e n t s 118 C.4 Derivation of the recurrence formula 121 V L i s t of Tables I Upper bounds for parameter values x = 100, 7o = 20 dB (r = 0.02) 34 II Upper bounds for parameter values x = 10, 7 0 = 5 dB (r = 0.6325) 34 III Asymptotic forms of the c o e f f i c i e n t s 52 IV Divisors 89 vi L i s t of Figures 2.1 The AWGN channel 7 2.2 The fading channel 9 2.3 P f(0,N) for d i f f e r e n t block sizes 18 2.4 P£(M,10) for M = 0, 1, 2, 3 19 2.5 Pf(0,l00) computed using (2.1.24) and numerical integration 22 2.6 The r e l a t i v e error in the approximation 31 2.7 P d(L,0,100) for L = 1, 2, 3, 4 62 3.1 Rayleigh cdf 73 3.2 Average fade time Tip) 75 3.3 Level-crossing rate Hip) 75 3.4 P (0,127) at d i f f e r e n t Doppler frequencies 77 3.5 P S(0,N) for d i f f e r e n t block sizes at 15.5 Hz 79 3.6 PS(M,63) for M = 0, 1, 2, 3 at 15.5 Hz 80 3.7 Formula (3.2.1) as a function of x for dif f e r e n t average SNR's 7 0 86 3.8 Plot of the d i v i s o r as a function of y0 at N = 255 and f D = 10.5 Hz 93 3.9 Plots of the curves that have been f i t t e d to the data in Table IV 94 3.10 P s(0,127) at d i f f e r e n t Doppler frequencies using the empirical formula 97 3.11 P s(0,N) for d i f f e r e n t block sizes at 15.5 Hz using the empirical formula 98 v i i L i s t of Main Symbols Symbol Meaning D e f i n i t i o n o t y p i c a l use a ^ n i f X ) c o e f f i c i e n t s in expansion (2.3.21) 54 a(t) Rayleigh fading process 9 A mean square of a(t) = E [ a ( t ) 2 ] 9 A ± parameters in curve f i t t i n g 9 1 bi(m,x) c o e f f i c i e n t s in expansion (2.3.15) 50 B Bernoulli numbers 49 n C Euler's constant = 0.57721 20 0 i s largely ignored in the l i t e r a t u r e . In t h i s thesis a method of approximation that allows a simple treatment of the case M > 0 is presented; t h i s new method y i e l d s a much better approximation to P f(0,N) as well. Furthermore, an approximation is given for Pf(M,N) in the more d i f f i c u l t case of selection d i v e r s i t y [25], (2) If the requirement of very slow fading i s relaxed the a n a l y t i c a l methods of (1) are no longer applicable, and Pf(M,N) must be computed by performing simulations. The simulations done for th i s thesis were performed on a d i g i t a l computer, and were t a i l o r e d to the mobile-radio environment. The emphasis here i s on mobile radio for the simple reasons that there i s a large amount of l i t e r a t u r e on the s t a t i s t i c a l properties of mobile radio and that some software has already been published in t h i s area [24], The main drawback of th i s approach i s the large amount of computer time required and the consequent high cost. To obviate the need for such simulations, an empirical formula i s derived that allows an accurate prediction of the simulation results when M = 0; t h i s empirical formula permits the easy computation of P f(0,N) when very slow fading i s not assumed. 5 The thesis has two main chapters, Chapters 2 and 3, which deal with cases (1) and (2) above. Chapter 4 presents the conclusions and a short discussion of possible topics for future investigation. 6 Chapter 2 Very Slow Rayleigh Fading In t h i s chapter we examine methods for the computation of Pf(M,N) for a channel subject to very slow Rayleigh fading in the presence of additive white Gaussian noise. Section 2.1 introduces the basic concepts and notation, and i s largely a review of what has been done in the l i t e r a t u r e . As we s h a l l see, almost a l l the results published to date deal with the special case of P f(0,N). In Section 2.2 we derive a new approximation to P (0,N), and show how the results can be extended to P (M,N) for M > 0. Moreover, an upper bound on the error in the approximation i s provided. In Section 2.3, the formulas of Section 2.2 are expanded into i n f i n i t e series (the approximations in the l i t e r a t u r e are e s s e n t i a l l y f i r s t - o r d e r expansions). F i n a l l y , in Section 2.4, approximations are derived for the computation of P (M,N) when selection d i v e r s i t y is employed. 7 2.1 Background 2.1.1 The AWGN channel We begin by reviewing several useful r e s u l t s for the transmission of one of two equally l i k e l y signals on the AWGN channel with steady-signal reception. The AWGN channel can be represented by n(t) Sj(t) 4 r-(t) Figure 2.1: The AWGN channel, where n(t) i s white Gaussian noise with two-sided power spectral density N0/2. Consider two signals s,(t) and s 2 ( t ) which are zero outside the i n t e r v a l 0 £ t £ T and which s a t i s f y • T ( t ) 2 dt. (i = 1, 2) (For the modulation schemes mentioned below, we may assume that s i ( t ) i s of th i s form.) Assume that with equal a p r i o r i p r o b a b i l i t y we send either s ^ t ) or s 2 ( t ) , and that the receiver i s optimum. Then the p r o b a b i l i t i e s of error for some important binary s i g n a l l i n g schemes are given by the following well-known expressions [23,29] p(y) = (1/2) exp(-d7) a = 1/2, noncoherent FSK (NCFSK) a = 1, d i f f e r e n t i a l PSK (DPSK) (2.1.1) 8 and a = 1/2, coherent FSK (CFSK) p(7> = (1/2) e r f c ( V a ^ ) (2.1.2) a = 1, PSK where 7 = E s/N 0 i s the signal-to-noise power r a t i o (SNR). Suppose now that we transmit a block of N b i t s . For NCFSK, CFSK, and PSK modulations the errors for d i f f e r e n t s i g n a l l i n g elements are independent, 2 and hence the p r o b a b i l i t y of m errors in a block of N b i t s i s where p = p ( 7 ) for a s p e c i f i c SNR 7 . The result (2.1.3) does not apply to DPSK modulation, since the d i f f e r e n t i a l encoding causes dependence between errors at the receiver. However, for those modulation techniques for which (2.1.3) does apply, we can immediately write down the p r o b a b i l i t y that more than M b i t s in a block are in error: 2 I f S i (t) i s zero outside the range 0 ^ t ^ T i t must have i n f i n i t e bandwidth — a signal cannot be both time-limited and band-limited (see Appendix 5B of [29]). Intersymbol interference, which causes some dependence between successive b i t s , may in practice be ignored on channels with s u f f i c i e n t l y large bandwidth. (2.1.3) N Pb(M,N) = Z (2.1.4) 9 The dependence of Pb (M,N) on the SNR 7 i s i m p l i c i t in equation (2.1.4); in those instances where we wish to make t h i s dependence clear we s h a l l write P b(M,N;7). From equation (2.1.4) we see that even i f the p r o b a b i l i t i e s Pfe(M,N) are the quantities of most interest, the pr o b a b i l i t y of b i t error retains i t s status as a fundamental unit for the measure of system performance. 2.1.2 The fading channel Let us now consider the case of nonselective, very slow Rayleigh fading in the presence of additive white Gaussian noise. As discussed in Section 9.2 of [23], nonselective fading can be represented as a purely m u l t i p l i c a t i v e process. The s p e c i f i c model we use i s shown in Figure 2.2. Figure 2.2: The fading channel. Here a(t) i s a stationary Rayleigh process with f i r s t - o r d e r density function a(t) n ( t ) S : ( t ) > r : ( t ) f.,,.(a) = (2a/A) exp(-a 2/A) (a > 0) (2.1.5) and s i ( t ) and n(t) are as before. The instantaneous SNR i s a random process which we define by 10 (2.1.6) Then from equations (2.1.5) and (2.1.6) i t follows that N 0 ZyiJ^ = — exp(-N o 7/AE s) T ( t ) AE S (7 * 0) (2.1.7) = To - 1 e x p ( ~ 7 / 7 0 ) , ( 7 * 0 ) A where 7 0 = AE S/N 0 i s the average SNR. From now on we s h a l l write simply f ( 7 ) for ^ y ^ f ) • Let us now assume that the fading process a(t) varies so slowly with respect to the s i g n a l l i n g rate that i t may be considered constant over the duration of each b i t ; t h i s i s what we mean by \"slow fading\". Under th i s assumption, the p r o b a b i l i t y of error for a p a r t i c u l a r b i t i s just the p r o b a b i l i t y p ( 7 ) of a b i t error on the AWGN channel. Thus for the slow-fading case we consider p ( 7 ) to be the p r o b a b i l i t y of a b i t error conditioned on the SNR 7 that results from a p a r t i c u l a r value of the fading m u l t i p l i e r . To compute p f, the average pr o b a b i l i t y of b i t error under fading conditions, we then average p ( 7 ) over a l l fading signal strengths. For the p a r t i c u l a r model considered here, the average i s taken over the d i s t r i b u t i o n f ( 7 ) given in (2.1.7). Then Note that equation (2.1.8) resembles a Laplace transform. To be 0 (2.1.8) 0 11 precise, p f = 7 0~ 1 P(7o\" 1), where P i s the Laplace transform of p(7). For p(7) as in (2.1.1), the integral (2.1.8) i s easy to evaluate a n a l y t i c a l l y ; for p(7) as in (2.1.2) the integral i s a b i t more d i f f i c u l t , and i t i s easiest just to consult a table of Laplace transforms. The re s u l t s are [23] a = 1/2, noncoherent FSK 1 r 1 i \\ (NCFSK) Pf = - (2.1.9) 2 L 1 + a7 0 a = 1, d i f f e r e n t i a l PSK (DPSK) a = 1/2, coherent FSK 1 r 1 l \\ (CFSK) Pf = ~ 2 L (1 + 1/a70) 1 - r • \\ (2.1.10) a = 1, PSK 2.1.3 The computation of Pf(M,N): Series expressions We come now to our main topic: the computation of the p r o b a b i l i t y Pf(M,N) of more than M errors in a block of N b i t s under fading conditions. Since b i t errors are no longer binomially d i s t r i b u t e d as in (2.1.3), Pf(M,N) i s not connected to p f, the pr o b a b i l i t y of b i t error under fading conditions, through (2.1.4). One approach to the computation of Pf(M,N) i s to extend the above analysis by assuming that the fading process i s so slow that the SNR 7 remains constant not only over a single b i t , but also over an entire block of N b i t s , and that the signal-to-noise r a t i o varies from block to block according to the d i s t r i b u t i o n t(y) of equation (2.1.7). In this thesis we s h a l l term such fading \"very slow\". Although the assumption of very slow fading becomes less and less r e a l i s t i c 12 as the block length becomes larger, we s h a l l see that based on th i s assumption we can derive results that are quite useful, p a r t i c u l a r l y in Chapter 3, where the assumption of very slow to the expression (2.1.8) for the average b i t - e r r o r p r o b a b i l i t y p f can be written down: where Pb(M,N;7) i s the prob a b i l i t y of error under steady-signal conditions given in equation (2.1.4). Equation (2.1.11) displays the dependence of Pf(M,N) on the average signal-to-noise r a t i o 7 0. If we were to follow the notational convention established for Pb(M,N) = Pb(M,N;7), we should write Pf(M,N) = Pf(M,N;70) in those cases where we desire to make the dependence on 7 0 c l e a r ; however, we s h a l l soon see that i t i s more convenient to indicate the dependence on y0 through the quantity r = 2/y0t and to write Pf(M,N) = P f(M,N;r). For 7 0 greater than 2 ( i . e . about 3 dB), r i s in the range 0 < r < 1, and for 7 0 >> 1, r s a t i s f i e s 0 < r << 1. Thus we are primarily concerned with small positive values of r. Since (2.1.4) does not apply to DPSK modulation (except in the t r i v i a l case N = 1), from now on we r e s t r i c t our attention to NCFSK, CFSK, and PSK. Substitution of (2.1.4) into (2.1.11) gives fading i s relaxed. An expression for Pf(M,N) that i s analogous (2.1.11) 0 13 Pf (M,N) = Z (|f) f p ( 7 ) m [ l \" p ( 7 ) ] N _ m f(7> d 7 m=M+ 1 \\ / JQ m=0 \\mU0 p ( 7 )m f l ~ P ( 7 ) 3 N m f ( 7 ) d 7 ( 2 . 1 . 1 2 ) 1m ? o (m)f0 1 \" 7 o - 1 Z (\") / P ( 7 ) m [ l - p ( 7 ) ] N _ m exp(- 7/7o) d 7 . Using the binomial expansion for [1 - p ( 7 ) ] N m we obtain Pf(M,N) = 1 - 7 o - 1 2 V(-1) k( NU N :m) / * p ( 7 ) m + k e x p ( - 7 / 7 o ) d 7 . m = 0 k = 0 \\ m/\\ k / J0 ( 2 . 1 . 1 3 ) Let us f i r s t look at the simplest case, when M = 0. We have N Z k=0 P f(0,N) = 1 - 7o-1.2 _ ( - D k ^ ) y * p ( 7 ) k exp(- 7/7o) d 7 ° ( 2 . 1 . 1 4 ) = 7 0 ' 1 Z ( \" D k + 1 fyj^ p ( 7 ) k e x p ( - 7 / 7 o ) d 7 , k=1 where in the la s t step the k = 0 term (which i s equal to 1) has been cancelled out. For N = 1, we obtain the results for p f = P f ( 0 , 1 ) given in equations ( 2 . 1 . 9 ) and ( 2 . 1 . 1 0 ) . For N > 1, we must evaluate the integral J 0 7 o - 1 / p ( 7 ) k exp(-7/7 0) d7 ( 2 . 1 . 1 5 ) for k > 1. Unfortunately, because of the complex form of p(7) for CFSK and PSK modulations, there appears to be no a n a l y t i c a l result for the integral when k > 1. However, in the case of NCFSK, p(7) has the simple form (l / 2 ) e x p ( - 7 / 2 ) and ( 2 . 1 . 1 5 ) can e a s i l y be evaluated: 1 4 To - 1 y0-'(W2)K I exp[- 7(k/2 + 1 / 7 o ) ] d 7 0 (!/2) k (!/2) k (2.1.16) where r = 2/y0. Substitution into (2.1.14) of the last expression appearing in (2.1.16) y i e l d s This equation appears in both [21] and [26] (with obvious differences in notation). Equation (2.1.17) can be used to compute P f(0,N;r) for small block lengths, but numerical d i f f i c u l t i e s begin to arise as N i s increased, and for very large block lengths these d i f f i c u l t i e s are substantial. The main problem with using the alternating series. (2.1.17) to compute P f(0,N;r) for large N i s the severe loss of s i g n i f i c a n t figures caused by cancellation between terms. Note also that the terms may become very large in magnitude. For example', take N = 100 and y0 = 100 = 20 dB (then r = 2/7 0 = 0.02). Using formulas which are derived in Section 2.2, we find Pf(0,100;0.02) = 8.57X10\" 2. However, the magnitude of the k = 50 term in (2.1.17) i s about 3.58X10 1 0. Then for the sum to y i e l d 8.57X10\" 2, i t is obvious that an enormous amount of cancellation between terms must take place, and hence to evaluate (2.1.17) on a computer to even one or two d i g i t s of accuracy requires multiple-precision arithmetic. Tests were run on the Amdahl 470 computer here at UBC to find the values of N N P f ( 0 , N ; r ) = - r L k=1 k + r (2.1.17) 15 for which the dire c t evaluation of the series (2.1.17) i s p r a c t i c a l . The calculations, were performed using double-precision arithmetic, and y0 was taken to be 20 dB. The value of N was steadily increased and the computed values of Pf(0,N;0.02) were compared with the correct values, which were computed using the methods of Section 2.2. For small values of N, (2.1.17) gave excellent r e s u l t s , but the accuracy steadily deteriorated as N increased, and for N = 80 only two s i g n i f i c a n t figures were obtained. For N > 90, the effect of cancellation was so dominant that the value of Pf computed via (2.1.17) was useless (for example, the computed value was sometimes negative). If we now consider 0 < M < N, then, for NCFSK, equation (2.1.13) leads to P (M,N) = 1 - r m= M /\\ N-m / \\ (-1/2) E d / 2 ) m (\") Z (V) = 0 Y7 k = 0 V k / k + m + r (2.1 .18) k M ™ /xA N _ m AT \\ (-1/2) = P f(0,N) - r 2 d / 2 ) m ( J L ( 7™ J . m=1 \\ m/ k=0 \\ k / k + m + r The numerical evaluation of (2.1.18) on a computer c l e a r l y runs into the same d i f f i c u l t i e s as before. 2.1.4 The computation of Pf(M,N): Numerical integration One way to avoid the d i f f i c u l t i e s in evaluating the summations above i s to compute Pf(M,N) by numerically integrating (2.1.12). (In the case of CFSK or PSK modulation, for which the integrals cannot be evaluated a n a l y t i c a l l y , t h i s 1 6 approach must be taken.) This procedure i s c a r r i e d out in [9] for N = 1, 10, 10 2, 10 3, 10\", 10 s, although only the special case M = 0 i s considered. The numerical integration of (2.1.12) i s also done in [21] as a check on approximations to P f(0,N) that are derived there [see equations (2.1.24) and (2.1.26)]; the values of N are 1, 10, 10 2, 10 3, 10\", and the case M = 0 i s s t i l l the only one considered. In later sections of th i s thesis, we s h a l l be deriving approximations to Pf(M,N), and naturally we s h a l l want to compare the results of these approximations with the exact results given by numerical i n t e g r a t i o n . 3 However, there are several reasons why the numerical results given in [9] and [21] are i n s u f f i c i e n t for our purposes. The main reason i s that numerical integration i s performed in [9] and [21] only for the simplest case M = 0, whereas we are interested in the case M > 0 as well. Also, the results in [9] are presented in the form of graphs that are not accurate enough for adequate comparison with the approximations we derive. The results in [21] are given to 4 s i g n i f i c a n t figures, but only for 7 0 in steps of 10 dB. For these reasons, equation (2.1.12) was numerically integrated on the Amdahl 470 for a more suitable range of parameters: N = 10, 10 2, 10 3, 10\" [ r e c a l l that for N = 1 there are the exact results (2.1.9)]; M = 0, 1, 2, 3; and 7 0 ranging from 0 to 50 dB in steps of 1 dB. The results for M = 0 and y0 = 0, 10, 20, 30, 40, 50 dB 3The results of the numerical integration are exact in the sense that a s p e c i f i e d number of s i g n i f i c a n t figures can be guaranteed in the computation of Pf(M,N). See Appendix A. 1 7 were compared with those given in [21], and were found to agree to 4 s i g n i f i c a n t figures in a l l but one case (in [21] they give P f = 5.814X10 _ 1 at N = 100 and 7 0 = 10 dB, whereas we calculated Pf = 5.806xl0~ 1). Some of the numerical results are graphed in Figures 2.3 and 2.4. The regularity of the curves, p a r t i c u l a r l y for high SNR's, suggests that the dependence of Pf(M,N;r) on M, N, and r can be characterized in a f a i r l y simple manner. The d e t a i l s of the numerical integration are described in Appendix A. 2.1.5 Approximate methods for the computation of P f(0,N) Another approach to the ca l c u l a t i o n of Pf(M,N) i s to approximate the sum (2.1.18) in such a way that numerical problems are avoided. It appears that approximations have been made in the l i t e r a t u r e only for the case M = 0, i . e . for (2.1.17) instead of (2.1.18). A simple approximation to (2.1.17) i s derived in [26]; t h i s approximation i s re-derived in [21] in almost pre c i s e l y the same way. The basis for the approximation i s to note that for 7 0 >> 1 we have r << 1, and so (2.1.19) k We now use the identity 18 o 0.0 10.0 20.0 30.0 40.0 50.0 60.0 Average signal-to-noise r a t i o r 0 in dB. Figure 2.3: P f (0,N) for d i f f e r e n t block s i z e s . 0 0.0 10.0 20.0 30.0 Average signal-to-noise r a t i o Figure 2.4: P f(M,lO) for M = 0 20 Z (l) (y \" D k A = Z y k/k - H N , (2.1.20) k=1 W k=1 A N where H N = Z k~1 (see exercise 13 of [13], Section 1.2.7). k=1 Substitution of (2.1.20) into (2.1.19) with y = 1/2 gives r N k i 2 r N k i P f(0,N;r) = r H N - Z (l/k2 ) = — H N - I (l/k2 ) . L k=1 J 7 o L k=1 J (2.1.21) The quantity in brackets in (2.1.21) i s well suited for numerical computation, even when N i s large. However, for large N the amount of computation required to evaluate (2.1.21) i s s u f f i c i e n t l y large that a computer i s s t i l l required. Thus i t would be convenient i f we could find some method to avoid the summations in (2.1.21); fortunately i t i s not hard to do so. From [13] we have the asymptotic expansion H N ~ log N + C + 1/2N - 1/12N2 + 1/120N\" (2.1.22) with an error less than 1/252N6. The logarithm in (2.1.22) i s the natural logarithm (logarithm to the base e). Since we s h a l l have no need to use common logarithms, log(') w i l l always denote the natural logarithm. The l e t t e r C denotes Euler's constant, which i s defined by C = lim {H - log N} (2.1.23) and which has a numerical value C = 0.57721. The summation N Z (l/ k 2 k ) in (2.1.21) converges extremely rapidly as N k=1 increases, and for N £ 10 i s well approximated by i t s l i m i t 21 I 0/k2 K) = log 2 (for N = 10 the r e l a t i v e error in this k=1 approximation is about 0.012%, and for N = 15 the r e l a t i v e error i s about 0.00026%). We then have P f(0,N;r) = r [log(N/2) + C + 1/2N - 1/12N2 + 1/120N4]. (2.1.24) Approximations similar to (2.1.24) are given in [21] and [26]. This approximation i s good for a f a i r l y wide range of block sizes N and signal-to-noise r a t i o s 7 0. For a fixed N, the approximation grows a r b i t r a r i l y good as y0 —=>• °° . However, the approximation i s poor for small signal-to-n.oise r a t i o s , as is shown by Figure 2.5, where the approximation (2.1.24) i s graphed for N = 100, along with the results obtained by numerical integration. If we now hold y0 fixed and consider the behavior of (2.1.24) as N -> » , we see that the approximation breaks down: the right-hand side of (2.1.24) goes to i n f i n i t y , although P f(0,N;r) i s of course less than unity. A s l i g h t l y d i f f e r e n t approximation that behaves better for large N is also derived in [21]. Although we do not go through the d e t a i l s here, the authors use what they c a l l a step function approximation to write r N M P f(0,N;r) = 1 - exp - r L ykJ (-1/2) ki (2.1.25) k=1 ^ ' k Note that the argument of the exponential function in (2.1.25) i s just the la s t expression in (2.1.19). In fact, i f the argument of the exponential in (2.1.25) i s small, taking the f i r s t - o r d e r term in the series expansion of the exponential y i e l d s (2.1.19). Using the asymptotic approximations just 22 0.0 10.0 20.0 30.0 40.0 50.0 60.0 Average s i g n a l - t o - n o i s e r a t i o r 0 i n dB. F i g u r e 2.5: P f ( 0 , l 0 0 ) computed using (2.1.24) and numerical i n t e g r a t i o n . 23 developed, we may write' P f(0,N;r) = 1 - exp{-r [log(N/2) + C + 1/2N - 1/12N2 + ...]} (2.1.26) As shown by numerical examples in [21], approximation (2.1.26) i s better o v e r a l l than (2.1.24), p a r t i c u l a r l y when N i s large and (2.1.24) f a i l s . Let us now consider the more d i f f i c u l t case M > 0, a case which apparently has not yet been tackled in the l i t e r a t u r e . From (2.1.18) we see that the problem can be broken up in such a way that we can employ the results already derived for P f(0,N). Thus the problem for M > 0 reduces to approximating the summation in the second equation of (2.1.18). It i s d i f f i c u l t , however, to work d i r e c t l y with the summation, and i t turns out that results can more e a s i l y be derived using a much dif f e r e n t method, which we consider in the next section. As a by-product of our investigation of the case M > 0 we s h a l l find a better approximation for the case M = 0 as well. Furthermore, whereas there i s no a n a l y t i c a l estimate of the error in the above approximations, we s h a l l be able to obtain e x p l i c i t bounds on the error in the approximations derived in the next sect ion. 24 2.2 A new approach to approximating Pf(M,N;r) 2.2.1 Introduction We s h a l l find i t most convenient to work with P(M,N;r) = 1 - Pf(M,N;r) = the p r o b a b i l i t y that there are M or fewer errors in a block of N b i t s . From equation (2.1.12) i t follows that M / N \\ /*°° m N-m -7/TO P(M,N;r) = TO\" 1 I (m) / p ( 7 ) [1 \" P(7>] e d 7 . m=0 \\ /Jo (2.2.1) This equation holds for NCFSK, CFSK, and PSK modulations. For reasons stated in the previous section we consider only NCFSK, for which p(7) = (1/2) exp(~7/2). Furthermore, we consider a generalization of (2.2.1), in which the block length N may be any real number x £ 1: P(M,x;r) = 7o\" 1 Z (*) / P(7> [1 ~ P(7>] e d 7 . m=0\\m/70 (2.2.2) It may not be clear why we consider non-integer block sizes x, but in Chapter 3, where we divide the o r i g i n a l block into sub-blocks, i t w i l l be a natural extension to think of the block size as an a r b i t r a r y real number. Also, i t turns out that the analysis for the extended case i s only s l i g h t l y more involved than i t would be i f we r e s t r i c t e d ourselves to integer block sizes N. The binomial c o e f f i c i e n t in equation (2.2.2) i s defined for real x by 2 5 x(x-1)(x-2) • • • (x-m+1) m! (2.2.3) T(1+X) r(1+x-m) rd+m) where r ( 0 i s the well-known Gamma function. The Gamma function occurs so frequently in what follows that i t i s worthwhile summarizing some of i t s properties here [28]. The Gamma function i s often defined for complex z in the right half plane by the integral oo T(z) = / t z _ 1 exp(-t) dt, Re(z) > 0 (2.2.4) J o where t z _ 1 = exp{(z-1)log(t)} and log(t) i s r e a l . It can be shown that r(z) as defined by the integral (2.2.4) i s analytic for Re(z) > 0, and that i t can be a n a l y t i c a l l y continued to the whole complex plane 4 = 6 dB we have r < 0.5, and so these tables cannot be used in the range of most int e r e s t . We might try substituting the binomial expansion of the factor (1 - t ) x m into (2.2.7), but t h i s just leads us back to (2.1.18), and i t was the d i f f i c u l t i e s in numerically evaluating (2.1.18) that led us to seek an alte r n a t i v e expression in the f i r s t place. There are some other problems with the expressions above. 27 Since P(0,x;r) —> 1 as 7 0 —> 0 0 [this is i n t u i t i v e l y obvious from the physical meaning of P(0,x;r)], i t follows from (2.2.9) that r 2 r Bx (r,1+x) -» 1 as r —> 0 +. This means that Bx (r,1+x) —>• as r —> 0 +, and so there could be numerical problems for large signal-to-noise r a t i o s . Consider also the block-error probability When 7o >> 1 and r 2 r B ^ r j l + x ) i s very close to unity, the right-hand side of (2.2.10) i s a subtraction of two nearly equal quantities. The result i s a loss of s i g n i f i c a n t figures. From the foregoing discussion i t may appear that (2.1.18) is a better starting point for approximating P f(M,x;r) than the al t e r n a t i v e expression (2.2.8). For example, an equation similar to (2.2.10) i s given in [21] (the authors consider only the case M = 0), but then (2.1.17) i s used as the s t a r t i n g point for deriving an approximation similar to (2.1.24). But we s h a l l see that (2.2.8) can serve as the foundation for excellent approximations to P (M,x;r). The most important observation to make, and, in fact, the observation that forms the basis for the approximations to follow, i s that the incomplete Beta function in (2.2.8) can be replaced by the Beta function with neg l i g i b l e error over a wide range of parameter values. We f i r s t introduce some new notation, l e t t i n g Q(m,x;r) denote the p r o b a b i l i t y of exactly m b i t errors in a block of x b i t s ; i t follows that P.(0,x;r) = 1 - r 2 r B,(r,1+x). r -i> (2.2.10) (2.2.11) 28 We also introduce the quantity 5(m ,x;r) = (^j r 2 r B(m+r,1+x-m). (2.2.12) The d e f i n i t i o n in (2.2.12) introduces a notational convention to which we w i l l adhere for the rest of thi s thesis: a quantity with a caret A indicates an approximation to the o r i g i n a l quantity that has been obtained by replacing the incomplete Beta function by the Beta function. Then (2.2.8) becomes M P(M,x;r) = L Q(m,x;r), (2.2.13) m=0 and, using the notational convention described above, M P(M,x;r) = I Q(m,x;r). (2.2.14) m=0 At We s h a l l use P to approximate P . Before we consider the advantages (and disadvantages) of doing so, we f i r s t examine the error incurred in making t h i s approximation. 2.2.2 Error analysis If we write Q(m,x;r) = Q (m, x; r ) - e(m,x;r) (2.2.15) then i t follows from equation (B.9) of Appendix B that e(m,x;r) s a t i s f ies 0 < e(m,x;r) < (*) . (2.2.16) V / 2 x~ m (1+x-m) The upper bound in (2.2.16) holds only when 0 < r < 1 (see Appendix B for a l l the r e s t r i c t i o n s under which the above 29 result holds). We think of e(m,x;r) as the error incurred by approximating Q with Q. Substituting (2.2.15) into (2.2.13), we find M M P(M,x;r) = E Q(m,x;r) - E e (m, x; r ) m=0 m=0 = P(M,x;r) - E(M,x;r), where from (2.2.16) i t follows that A M 0 < E(M,x;r) = E e(m,x;r) m=0 M (2.2.17) ( 2 . 2 . 1 8 ) <- 5 h — m=0 W 2 x\" r ' m (1+x-m) E(M,x;r) represents the error that results when we replace the incomplete Beta function in (2.2.8) by the Beta function, i . e . when we approximate P by P . We now examine how the upper bound in (2.2.18) depends upon i t s parameters, and then look at several numerical examples in order to get an idea of the magnitude of the numbers involved. As usual, we f i r s t consider the simplest case, M = 0. Then P(0,x;r) = P (0, x; r ) - E(0,x;r), where 0 < E(0,x;r) < r/2 x(l+x). The error bound r 1 (2.2.19) 2 X (1+x) 2 X _ 1 ( l + x ) 7 o goes to zero exponentially with increasing block size x, and so the error in the approximation rapidly becomes n e g l i g i b l e as x 30 increases. Also, the error bound varies inversely with the average signal-to-noise r a t i o y0l and so the error in approximation decreases as y0 increases. Note, however, that we refer here to the absolute error, whereas a more meaningful indicator of the error i s the r e l a t i v e error — in t h i s case, the error r e l a t i v e to P f, the quantity we wish to compute. From equation (2.1.23) we see that to a f i r s t approximation P f also varies inversely with 7 0. Since both P f and the error bound depend inversely on 7 0, changing 7 0 while leaving x fixed has l i t t l e e f fect on the r e l a t i v e error, even though P f and the error bound may change by several orders of magnitude. The reader may question the v a l i d i t y of t h i s conclusion, because the analysis i s based not on the actual error E(0,x;r), but on the upper bound given in (2.2.19), and a bounding technique d i f f e r e n t from that of Appendix B might y i e l d a tighter bound on E(0,x;r) with a d i f f e r e n t functional dependence on 7 0. However, tests have shown that the error bound in (2.2.19) i s quite t i g h t , and the conclusion drawn above does hold. An example i s given in Figure 2.6, in which both the r e l a t i v e error E(0,x;r)/P f(0,x;r) and the error bound (2.2.19), also divided by P (0,x;r), have been graphed for x = 10. There are several points to be made. (i) The upper bound on the error i s quite close to the actual error, although i t does not hold for 7 o less than about 3 dB [see the remark following (2.2.16)]. ( i i ) As 7 0 increases the r e l a t i v e error rapidly approaches a 31 Figure 2.6: The r e l a t i v e error in the approximation. 32 constant, and for y0 > 10 dB may be considered almost constant. Reference to Figure 2.3 shows that in contrast P f(0,l0;r) changes by several orders of magnitude over the same range of SNR values, ( i i i ) The r e l a t i v e error i s greatest for small values of y0, say 7o < i n dB. From the example in Figure 2.5 we see that (2.1.21) holds only for the s t r a i g h t - l i n e portions of the graphs in Figure 2.3, i . e . for y0 greater than about 10 or 15 dB (depending on the block s i z e ) . Thus the inverse dependence of P f with y0, a dependence that was used to predict a r e l a t i v e error that i s almost constant with respect to the SNR y0, does not hold for small values of the SNR. The reader should bear in mind that although the error, viewed as a function of y0, w i l l have the general shape of Figure 2.6 for a l l block sizes,.the exponential dependence of (2.2.19) on x so t o t a l l y dominates the behavior of the error term that for block sizes greater than 10 or so the error i s n e g l i g i b l e regardless of the value of y0, i . e . for 0 dB and above. It i s only for small block sizes (x less than about 10) that the increased error for y0 less than 10 or 15 dB becomes important, and i f we r e s t r i c t the average SNR to be greater than about 10 dB, the error in the approximation i s s t i l l quite small (less than 1% r e l a t i v e error) for x as small as 4 or 5. The only parameter range for which we expect the error to be appreciable i s when both the block size and SNR are small. 33 From (2.2.18) we see that when M > 0 the bound on E(M,x;r) i s a b i t more tedious to compute than i t i s for M = 0. However, the error term E i s usually so small that we may replace the upper bound in (2.2.18) with a much simpler bound that, although weaker than (2.2.18), i s more than s u f f i c i e n t for our purposes. In addition to the r e s t r i c t i o n s on r, x, and m given in Appendix B, we assume that M i s an integer s a t i s f y i n g 0 ^ m < M < x. It can then be shown using d e f i n i t i o n (2.2.3) that M-m M x-M We also have that 1/d+x-m) < 1/(1+X-M), and so z (A 1 < (A ' £ m-0\\7 2\"\" m (1+x-m) Y7 2 X \" M < 1+x-M> m-0 where we have put i- = M/2(x-M). Using the well-known result for the sum of a geometric series, we conclude, on the basis of (2.2.18) and the above inequality, that 0 < E(M,x;r) < if) r 1 - S M + 1 ^ 2x-M ( 1 + X _ M ) L (2.2.20) If £ = 1 the quantity in brackets should be replaced by M+1. Note that in the important case M = 0 the upper bounds in (2.2.18) and (2.2.20) are i d e n t i c a l . We now look at some numerical examples. In the tables below, the values of the upper bounds in (2.2.18) and (2.2.20) are given for two d i f f e r e n t block sizes and average signal-to-34 noise r a t i o s , and for M = 0, 1,2, 3. The parameters chosen for Table I, x = 100 and y0 = 20 dB, represent t y p i c a l values of the block size and average SNR. The parameters chosen for Table II, x = 10 and 7 0 = 5 dB, f a l l into the region where we expect the error in the approximation to sta r t to become large. Also provided are the values of P f(M,x;r), which were computed using numerical integration as described in Appendix A. The numbers in the tables are rounded off to the number of decimal places presented. M Bound in (2.2.18) Bound in (2.2.20) P f(M,x;r) 0 1 2 3 1.562x10\"3a 3. 171x10\" 3 2 3. 1 8 7 X 1 0 \" 3 0 2.1 1 4 X 1 0 \" 2 8 1.562X10- 3 4 3.171x10\"3 2 3. 188X10\" 3 0 2. 115x10- 2 8 8.567X10\" 2 6.738x10- 2 5.805X10\" 2 5.177X10\"2 Table I: Upper bounds for parameter values x = 100, TO = 20 dB (r = 0.02). M Bound in (2.2.18) Bound in (2.2.20) P f(M,x;r) 0 1 2 3 5.615x10\"5 1.291x10\"3 1.364X10\"2 8.776X10- 2 5.615X10\"5 1 .304X10\" 3 1.409X10\"2 9.413x10* 2 6.915x10\"1 4.969x10-1 3.412x10\"1 2.139x10-1 Table I I : Upper bounds for parameter values x = 10, 7o = 5 dB (r = 0.6325). Comparing the values of the two upper bounds given in the preceding tables, we see that the upper bound in (2.2.20) i s very t i g h t . It i s obvious, though, that for the choice of 35 parameters in Table I above the bound does not have to be very ti g h t , since the error incurred by replacing the incomplete Beta function in (2.2.8) by the Beta function i s smaller than Pf(M,100;0.02) by at least a factor of 10 2 5. The small magnitude of the error term demonstrates the effect of the exponential dependence on block s i z e . It i s clear that the error term w i l l be neg l i g i b l e for larger block sizes, since the effect of increasing x w i l l be to decrease the error estimate while increasing the error p r o b a b i l i t y P f(M,x;r). The parameters chosen for Table II are in that region where we expect the worst r e s u l t s : both the block size and the average signal-to-noise r a t i o are small. From the table we see that even in this case the error i s small r e l a t i v e to P f(M,lO;r), p a r t i c u l a r l y for small M. Using the bound ( 2 . 2 . 1 8 ) , we can conclude that the r e l a t i v e error in the approximation i s less than 0.0082% for M = 0, and less than 4.0% for M = 2. However, i f x i s very small we are able to compute P (M,N;r) d i r e c t l y from (2.1.17) (assuming an integer block s i z e , x = N). Of course, one usually desires to f i n d a single formula that w i l l work over the entire parameter range in which one i s interested: i t i s always a bother to have to consider separate cases. It i s evident from the examples provided above that the approximation (2.2.17) i s quite robust, in the sense that i t works well over a wide range of parameter values. So far we have only shown that we can approximate P by P with n e g l i g i b l e error over the parameter range of interest — we have yet to demonstrate that P i s easier to compute than P . 36 2.2.3 The approximation to P F ( 0 , x ; r ) The advantage of working with P instead of P i s that there i s an equation r e l a t i n g the Beta function to the Gamma function [28]: T(a) T(b) B(a,b) = . Re(a) > 0 (2.2.21) T(a+b) Re(b) > 0 Putting t h i s result into (2.2.12) we find rO+x-m) T(m+r) r 2 r , (2.2.22) T(1+x+r) and, substituting (2.2.22) into (2.2.14), we obtain M / \\ T(1+x-m) r(m+r) P(M,x;r) = r 2 r Z ( x) . (2.2.23) m=0 Y 7 T( 1+x+r) We begin our analysis with the special case M = 0 , which we consider in d e t a i l because, as w i l l be shown l a t e r , the general case M > 0 can be reduced to thi s special case. With M = 0 , equation (2.2.23) becomes T(1+x) T(r) P ( 0,x;r) = r 2 r (2.2.24) r(1+x+r) with an error in approximation less than r/2 x(1+x). Using the recurrence r e l a t i o n (2.2.6) we can write T(1+X) rd+r) P ( 0,x;r) = 2 r . (2.2.25) r( 1+x+r) Moving from (2.2.24) to (2.2.25) i s numerically b e n e f i c i a l , because a si n g u l a r i t y at r = 0 i s removed. This s i n g u l a r i t y of (2.2.24) at r = 0 occurs because T(r) has a pole there (and at r = -1, -2, -3, . . . ) , and hence r(r) goes to i n f i n i t y as r -» 0 + ( i . e . as y0 —> °° ). However, the poles of the Gamma 37 function are simple, and so r'T(r) has a removable s i n g u l a r i t y at r = 0; in fact lim r-T(r) = lim r(1+r) = T O ) = 1. r->0+ r->0 + (In other words, the residue of the T function at zero i s 1.) Of course, we should have anticipated such behavior when r i s near zero: while examining the behavior of equation (2.2.9) i t was noted that when r —> 0 + the incomplete Beta function B^(r,1+x) goes to i n f i n i t y in such a way that the product r 'B i s(r,1+x) approaches unity. Since the bound r/2 x(l+x) on the difference between (2.2.9) and (2.2.24) goes to zero as r —> 0* for a fixed x, the behavior of the two expressions must be the same near r = 0. Let us now consider some of the de t a i l s of numerically evaluating (2.2.25). The most obvious feature of (2.2.25) is that the Gamma function must be evaluated. This makes (2.2.25) inconvenient for use on a hand calculator, but i s no real drawback i f a computer i s available — the Gamma function i s a standard function of analysis and so there i s usually a packaged program available at any well-equipped computer i n s t a l l a t i o n (at UBC for example). However, even i f a Gamma function program is available we cannot just b l i n d l y evaluate (2.2.25) as i t stands, because the terms T(1+x) and T(l+x+r) may become very large. For example, T(101) = 100! = 9.33X10 1 5 7 and r(1001) = 1000! = 4.02X10 2 5 6 7, and both these numbers exceed the largest number that is e a s i l y representable on most computers. Thus to avoid overflow i t i s best to work with the logarithm of the Gamma function, and to write 38 rd+x) = exp[log Td+x) - log r(1+x + r ) ] . (2.2.26) r(1+x+r) Fortunately log r(-) has been analyzed almost as extensively as the Gamma function i t s e l f (see, for example, [28]), and there are programs available for evaluating t h i s function. There are several reasons why double-precision arithmetic should be used in the evaluation of (2.2.25). F i r s t , the subtraction in (2.2.26) w i l l result in a loss of s i g n i f i c a n t figures, p a r t i c u l a r l y for large block s i z e s . Also, our f i n a l goal i s the approximation of Pf(0,x;r) by P f(0,x;r) = 1 - P(0,x;r), (2.2.27) and the subtraction in t h i s equation w i l l also result in a loss of s i g n i f i c a n t figures. If a pre-written program for r(«) or log r(•) i s not available, there are several programs l i s t e d in the Collected Algorithms from the Association for Computing Machinery that may be used to evaluate these functions. These programs are based on either Chebyshev approximations or asymptotic expansions, and are s u r p r i s i n g l y simple and short (20 l i n e s or so). Thus, even i f a packaged program i s not available, the evaluation of T(•) or log r(«) poses no real problem, and can e a s i l y be done on a programmable c a l c u l a t o r , or can even be done manually on a hand calculator in a matter of minutes. Equation (2.2.25) was programmed for the Amdahl 470 using DLGAMA, which i s a UBC l i b r a r y routine for evaluating log T(•) to double-precision accuracy. Values of P f were computed for 39 N = 1 0, 102., 1 0 3 , 1 0\" and for y0 from 0 to 50 dB using equation (2.2.27), and were then compared with the corresponding values of P f obtained by numerical integration. There are at least three sources of error that could cause discrepancies between the two sets of r e s u l t s : (i) the error that results from approximating P f by P f. This source of error i s only important for N = 10, since for N = 10 2, 10 3, 10\" the error in approximation is so small that, barring a l l other sources of error, P f would approximate P f to at least double-precision accuracy (16 s i g n i f i c a n t figures on the Amdahl). For N = 10 we see from Figure 2.6 that the r e l a t i v e error in approximation approaches a constant value of about 4x10\" 5, and so, ignoring other sources of error, we expect about four s i g n i f i c a n t figures from (2.2.27) when N = 10. ( i i ) numerical error in the evaluation of (2.2.27), caused by the effects of performing arithmetic using a f i n i t e word-length. An example of t h i s type of error i s the loss of s i g n i f i c a n t figures discussed at the top of the previous page. ( i i i ) inaccuracy in the numerical integration. As described in Appendix A, the values of P f computed vi a numerical integration are accurate to at least f i v e s i g n i f i c a n t f igures. According to (i) and ( i i i ) , for N = 10 we can expect the 40 results to agree to about four s i g n i f i c a n t figures i f the error described in ( i i ) can be ignored. Comparison showed t h i s to be the case. For N = 10 2, 10 3, 10\", the only relevant sources of error are those in ( i i ) and ( i i i ) . Comparison showed that the values of P f computed using (2.2.27) agreed to f i v e s i g n i f i c a n t figures for almost a l l values of y0 with those calculated using numerical integration. Thus double-precision arithmetic was en t i r e l y adequate, and over the parameter range examined the source of error described in ( i i ) above was never very severe. In fact, in most cases the values of Pf computed using (2.2.27) were probably much more accurate than those obtained by numerical integration (and thus, in the end, were a better check on the numerical integration than vice versa). Generally, when the block size i s greater than about 10 b i t s the error in the approximation i s so small that i f we graph both the results obtained by numerical integration and the approximate results on the same graph, the scale of which i s as in Figure 2.3, the li n e s l i e on top of one another for the entire range 0 to 50 dB. 2.2.4 The approximation to P f(M,x;r) We start by approximating Q(m,x;r), the pr o b a b i l i t y of m bi t errors in a block of x b i t s , for m ^ 0. If we express the binomial c o e f f i c i e n t in equation (2.2.22) in terms of Gamma functions according to equation (2.2.3), we get 41 T(1+X) T(m+r) Q(m,x;D = r 2 . (2.2.28) r(1+x+r) r(1+m) For m = 1, 2, ... we can use (2.2.6) to write r(m+r) = r(r+1) • • • (r+m-1) T ( r ) . Using Pochhammer's symbol, which i s defined by (Do = 1 (2.2.29) (2.2.30) ( r ) m = r(r+l) • • • (r+m-1) for m = 1, 2, ... (see entry 6.1.22 of [1]), we can extend (2.2.29) to the case m = 0 and write T(m+r) = ( r ) m r ( r ) for m = 0, 1, 2, ... Then (2.2.28) becomes rd+x) r(r) Q(m,x;r) = r 2 (r) m/m! T( 1+x+r) (2.2.31) _ rd+x) r d+r) = 2 (Dra/m! . T( 1+x+r) Note that the expression in front of the term (r) r a/m! is just the approximation to P(0,x;r) given in equation (2.2.25). Thus Q(m,x;r) = P(0,x;r) (r) m/m! , (2.2.32) and hence Q(m,x;r) = P(0,x;r) (Dm/m! , (2.2.33) where a bound on the error in the approximation i s given in (2.2.16). If r « 1 ( i . e . i f the average SNR y0 i s large), i t can be shown from (2.2.30) that (r) m/m! = r/m for m £ 1. Then i f r << 1 and m > 1 we have that 42 Q(m,x;r) = P(0,x;r) r/m . (2.2.34) Equation (2.2.34) shows that when the SNR i s large, the pro b a b i l i t y that there are m b i t errors in a block varies approximately inversely with m. It i s now easy to write down an approximation for P(M,x;r) when M > 0: putting (2.2.32) into (2.2.14) y i e l d s P(M,x;r) = P(0,x;r) Z (r) m/m! . (2.2.35) m=0 From (2.2.17) we may write M P(M,x;r) = P(0,x;r) Z (r) m/m! - E(M,x;r), (2.2.36) m=0 where E(M,x;r) s a t i s f i e s (2.2.20). From (2.2.17) we also have that P(0,x;r) = P(0,x;r) + E(0,x;r), and substitution of t h i s equation into (2.2.36) yiel d s M P(M,x;r) = P(0,x;r) Z (r) m/m! + m=0 (2.2.37) M + E(0,x;rj Z (r) m/m! - E(M,x;r). m=0 Let us get a bound on the absolute value of the term M E(0,x;r) Z (r) m/m! \" E(M,x;r). (2.2.38) m=0 We use the following fa c t : i f a and b are posit i v e real numbers, then |a - b| ^ max{a, b}. Since both terms in (2.2.38) are p o s i t i v e , 43 M E(0,x;r) Z (r) m/m! - E(M,x;r) m=0 M < max{ E(O fx;r) Z (r) m/m!, E(M,x;r) } m=0 It i s easy to see that for 0 < r < 1 the inequality 0 < (r) m/m! < 1 holds, and hence, using the bound in (2.2.20), we have M max{ E(0,x;r) Z (r) /m!, E(M,x;r) } m=0 < max{ (M+1)E(0,x;r), E(M,x;r) } .M+1 \\ < max •G) (M+Dr / \\ r » x (1+x) ' W 2 X\" M (1+x-M) \\ - ~ 2* V7 K~n L r 1 - £ M + l n M / 2 X\" M (1+x-M) L i - { where £ = M/2(x-M). The la s t step follows upon noting that 2 M > M+1 for M £ 0, that 1/(1+x-M) > 1/(1+X), and that both and the quantity in square brackets are greater than unity. Summarizing, we have M P(M,x;r) = P(0,x;r) Z (r) m/m! (2.2.39) m=0 with an error in approximation that i s less than the upper bound in (2.2.20) when 0 < r < 1 and 0 £ M < x. Thus from our previous investigation we know that the error in approximation in (2.2.39) i s n e g l i g l i b l e for almost a l l cases of interest. 44 Equation (2.2.39) i s one of the major results of t h i s thesis, because i t demonstrates that the computation of P(M,x;r) can be reduced (approximately, at least) to the computation of P(0,x:r): given the value of P(0,x;r), computed by any method M at a l l , we need only compute the \"correction factor\" L (r) m/m! M m=0 in order to obtain P(M,x;r). The factor Z (r) m/m! poses no m=0 numerical problems, and for small M can e a s i l y be handled on a pocket c a l c u l a t o r . Equation (2.2.39) i s inte r e s t i n g from a t h e o r e t i c a l point of view; in practice, having no method to compute P(0,x;r) exactly, we use (2.2.35). This l a t t e r equation was programmed for the Amdahl 470, and the results were compared with the results obtained by numerical integration. The agreement between the results was very good, as our previous error analysis would lead us to expect. 45 2.3 I n f i n i t e series expansions 2.3.1 Introduction and notation In t h i s section we derive i n f i n i t e series expansions for P f, again considering only non-coherent FSK. With the approximations of Section 2.2 in mind, one might reasonably wonder about the need to develop i n f i n i t e series expansions. These expansions are useful in that they show the connection between the approximations developed in the l i t e r a t u r e ( i . e . the approximations discussed in Section 2.1) and those developed in the previous section. In p a r t i c u l a r , we s h a l l see how approximations (2.1.24) and (2.1.26) follow from the formulas of Section 2.2, and how these approximations can be made more accurate with l i t t l e added computational e f f o r t . Thus the formulas we derive in thi s section provide a simple computational alternative to the formulas of Section 2.2, although we s h a l l no longer have rigorous bounds on the error in the approximation. We s h a l l also see how to modify approximations (2.1.24) and (2.1.26) for the case M > 0. F i n a l l y , the formulas we derive here w i l l be used in our discussion of d i v e r s i t y (Section 2.4). Since the mathematical d e t a i l s are somewhat tedious, many of them have been placed in Appendix C: our primary objective i s to give those results'that the reader may fin d useful or interesting. Note that we may think of equation (2.1.21) as a f i r s t -order expansion of P f in terms of the quantity r = 2/y0. To show in what sense t h i s i s true, and how we can derive the higher-order terms of the expansion, we f i r s t go back to 46 equation (2.1.17): N / \\ (-1/2) P f(0,N;r) = - r L i ? ) k=1 \\ k/ k + r (2.3.1) For |r| < k, we may write 1 1 CO = = k-1 Z (-r/k) J. k + r kd+r/k) j = 0 Since the smallest value assumed by the index of summation k in equation (2.3.1) i s k = 1, the following equations are v a l i d for IrI < 1: N P f(0,N;r) = - r I (-1/2) k=1 = Z j-0 L (-1 ) Z (-r/k) J k j = 0 j + 1 N /NX (-1/2) 1 , k = i w J R (2.3.2) Z i = 1 N / \\ (-1/2) (-1) 1 Z / N k=1 k 1 The interchange in the order of summations in (2.3.2) is c l e a r l y v a l i d because one of the sums i s f i n i t e . Comparison of (2.1.19) and (2.3.2) shows that making the approximation of (2.1.19) i s equivalent to taking the f i r s t term of the series (2.3.2). Although the f i r s t c o e f f i c i e n t k=1 W k (2.3.3) i s not easy to compute d i r e c t l y for large N, we saw in Section 2.1 that the use of ide n t i t y (2.1.20) puts i t into a form that i s e a s i l y approximated or computed exactly i f desired. We 47 should d i s t i n g u i s h here between two d i f f e r e n t approximations: one approximation consists of ignoring the higher-order terms of the i n f i n i t e series (2.3.2) [th i s i s the approximation made in (2.1.19)], whereas the other approximation i s the one made to the terms themselves [this i s the approximation made in going from (2.1.21) to (2.1.24)]. The error in approximating the f i r s t term (2.1.21) by (2.1.24) i s so small for N greater than about 10 b i t s that almost a l l the error may be attributed to the omission of the higher-order terms. If we now desire a better approximation to P f, then the obvious way to proceed i s to compute the higher-order terms in (2.3.2). However, the higher-order c o e f f i c i e n t s are just as d i f f i c u l t to evaluate d i r e c t l y as (2.3.3). One might hope for a general identit y analogous to (2.1.20) which w i l l transform the c o e f f i c i e n t s (2.3.4) into expressions that are more e a s i l y computed or approximated. Unfortunately, there appears to be no such i d e n t i t y , and each c o e f f i c i e n t must be dealt with in an ad hoc manner. It i s possible to get somewhere by attacking the i = 2 term d i r e c t l y , but the computations get more and more d i f f i c u l t as i increases. Using the formulas of Section 2.2 we can largely sidestep the d i f f i c u l t i e s mentioned above. The key here i s that the c o e f f i c i e n t s in the expansion of P are much easier to work with than those in the expansion of P . Let us begin our . N (-1) 1 Z k=1 (i > 2) (2.3.4) 48 analysis with some new notation: define qi(m,x) and q^dr^x) by Q(m,x;r) = (*) r 2 T Blg(m+r, 1 +x-m) = Z qi(m,x) r 1 \\ / i = 0 (2.3.5) Q(m,x;r) = (*) r 2* B(m+r,1+x-m) = I qi(m,x) r 1 . W i = 0 The i n f i n i t e series in (2.3.5) converge for at least |r| < 1. It i s not hard to show that convergence a c t u a l l y holds for |r| < m when m £ 1, but the situ a t i o n i s more d i f f i c u l t for m = 0 (th i s i s one of the few instances where the case m = 0 i s more d i f f i c u l t than m > 0 ) , and the sense in which (2.3.5) holds for m = 0 i s described in Appendix C. We also define M p±(M,x) = Z q±(m,x) , (2.3.6) m=0 and s i m i l a r l y define p i(M,x). Then oo P(M,x;r) = Z p.(M,x) r 1 i = 0 and (2.3.7) 00 P(M,x;r) = Z p.(M,x) r 1 i = 0 for |r| < 1. It i s not hard to derive exact formulas for the c o e f f i c i e n t s q^ ^ and p i when x = N = an integer — for example, using (2.3.2) and the re l a t i o n P = 1 - P f, we have in the special case M = 0 that q O(0,N) = 1 and N /M\\ (~1/2) k q.(0,N) = ( - 1 ) 1 + 1 Z (l) — . ( i > 1) 1 k=1 VK/ k 1 (2.3.8) We have already seen that these c o e f f i c i e n t s are hard to work with, and we expect the situation to be even worse when M > 0 . But we know that P i s an excellent approximation to P, and 49 so i t is natural to see what we can learn from the series expansion of P. Thus we focus on the c o e f f i c i e n t s q± and p±. Before we proceed,.we r e c a l l some previous notation, and introduce some more; much of the notation used here i s the same as in [13]. In Section 2.1 we defined the quantity H n for n = 1, 2, 3, ... by n ^ = Z k\"1 (2.3.9) k=1 (the H stands for \"harmonic\"). We extend t h i s d e f i n i t i o n by writing n H ni> = Z k _ i (2.3.10) k=1 for i = 1, 2, 3, ... Thus H n = H n 1>. We s h a l l also use the convention that H^l' = 0; t h i s convention w i l l allow us to write down several of the expressions that follow without the need to consider special cases. It i s an elementary result of analysis that the harmonic series diverges, i . e . H — ° ° as n —^ oo . However, for i £ 2 the l i m i t of H^1' exists as n oo , and we put S(i) = lim H' ni' = Z k - i (2.3.11) n -> co k= 1 for i £ 2. The function $(i) i s c a l l e d the Riemann Zeta function [28]. We also introduce the Bernoulli numbers B n, which are defined by the i n f i n i t e series z 0 0 = Z B n z n/n! . |z| < 2ir (2.3.12) exp(z) - 1 n=0 50 (The Bernoulli numbers are sometimes defined s l i g h t l y d i f f e r e n t l y , and so one must be careful when consulting various references.) The f i r s t few c o e f f i c i e n t s in (2.3.12) are B 0 =1, B, = -1/2, B 2 = 1/6, B 3 =0, Bfl = -1/30 and i t can be shown that a l l c o e f f i c i e n t s with odd indices except B, are zero. A table of Bernoulli numbers can be found in [1], Another fact which we s h a l l use i s that $(2n) = |B 2 n| (27r) 2 n/2(2n)! for n = 1, 2, 3, ...; in p a r t i c u l a r (2.3.13) $(2) = I k' 2 = T T 2 / 6 k=1 and (2.3.14) OO $(4) = I k-« = 7r«/90. k=1 2.3.2 Extension of formula (2.1.26) We do not start by immediately deriving the expansion for Q given in (2.3.5); instead we f i r s t represent Q in the form Q(m,x;r) = (r/m) exp Z b±(m,x) r 1 (2.3.15) i = 0 for 1 < m < x. (According to our notational convention we should write b-j_(m,x) instead of bi(m,x), but since we s h a l l not be examining the corresponding expansion for Q(m,x;r) i t i s convenient to omit the c a r e t ) . The reason why we derive an expansion of the form (2.3.15) i s because the c o e f f i c i e n t s bi(m,x) can be e a s i l y expressed in terms of known functions, 51 and the q± can in turn be e a s i l y represented in terms of the b.. Note that (2.3.15) holds only for m > 1. It i s shown in Appendix C that 5(0, x;r) = exp I b. (1 ,x) r 1 L i = 0 (2.3.16) and so finding the c o e f f i c i e n t s bi(m,x) for m > 1 w i l l s u f f i c e for the case m = 0 as well. In Appendix C exact formulas for these c o e f f i c i e n t s are obtained; the results are r b0(m,x) = 0 \\ b,(m,x) = log 2 + i//(m) - ^(1+x) (2.3.17) b±(m,x) = [^«i- 1 )(m) - V1'1'(1+x)]/i! . ( i > 2) The function \\p in (2.3.17) i s the the Psi function (also c a l l e d the Digamma function), which is defined by [1,28] r-(z) *(z) = (2.3.18) r(z) and which is tabulated in [1], The Psi function i s analytic in the same region of the complex plane as the Gamma function, i . e . in 10 or so by means of asymptotic expansions; the d e t a i l s of deriving these expressions are given in Appendix C. There i t i s shown that for i = 1 we have 52 (2.3.20) b,(m,x) ~ H - [ l o g ( x / 2 ) + C + 1 / 2 X - 1 / 1 2 X 2 + 1 / 1 2 0 X 4 - . . . ] , m _ 1 (2.3.19) and for i > 2 we have b±(m,x) ~ ( - 1 J 1 ! \" 1 ( $(i) - H ( i> -L ( i - l ) x i _ 1 2 X 1 ( i - 1 ) ! n=1 (2n)! x 2 n + i _ 1 -I / ' Although the preceding formulas may look complicated, they are quite simple to use. For the reader's convenience the asymptotic forms of the f i r s t few c o e f f i c i e n t s are written out e x p l i c i t l y in Table III below. b, (m, x) ~ Hm - 1 \" tlog( x / 2 ) + C + + 1 / 2 X - 1 / 1 2 X 2 + 1 / 1 2 0 X « - 1/252X 6 + ...] b 2 (m,x) ~ ( 1 / 2 ) { $ ( 2 ) _ H < 2 ) _ m-1 [ 1 / x - 1 / 2 X 2 + 1/6X 3 -1/30X 5 + 1/42X 7 - ...]} b 3 (m, x) ~ (-1/3){5(3) - H< 3 > -m-1 [ 1 / 2 X 2 - 1/2x 3 + l/4x't -1 / 1 2 X 6 + 1 / 1 2 X 8 - . . . ] } b. (m, x) ~ ( 1/4) {$(4) - H< • > -m-1 [ 1 / 3 x 3 - 1 / 2 X \" + 1/3X 5 -1/6X 7 + . . . ] } Table I I I : Asymptotic forms of the c o e f f i c i e n t s . From (2.3.14) we have the exact values for $(2) and $(4); there is no such closed form for the Zeta function evaluated at the odd p o s i t i v e integers, and £(3) must be computed numerically. From [1] we fi n d that $(3) = 1.20205. For block sizes greater than about 10 b i t s , the above asymptotic formulas allow easy 53 computation of the c o e f f i c i e n t s b i to considerable accuracy. Consider now the computation of P(0,x;r) = Q(0,x;r) using (2.3.16). Fortunately, the convergence of the i n f i n i t e series in (2.3.16) i s s u f f i c i e n t l y rapid that we may truncate i t after only several terms with l i t t l e error; reference to approximation (2.1.26), developed in [21], shows that i t corresponds to retaining only the f i r s t term b,(1,x) in (2.3.16). At high average SNR's the single term i s s u f f i c i e n t , but at lower SNR's i t is advisable to take several more. The methods here demonstrate how we can extend the approximation (2.1.26) to higher-order terms and thus increase the accuracy. Retention of only the f i r s t four terms, corresponding to the four c o e f f i c i e n t s written out in d e t a i l above, gives good accuracy for a wide range of average SNR's 7 0. The computation of P(M,x;r) for M > 0 by f i r s t computing Q(m,x;r) for m = 0, 1, 2, M using (2.3.15) and (2.3.16), and then substituting these intermediate results into (2.2.14), is not very e f f i c i e n t . A much better approach is to use (2.3.16) to compute P(0,x;r) as described above, and then to use equation (2.2.35) to compute P(M,x;r). 2.3.3 Extension of formula (2.1.24) Based on what we have derived so far, i t i s easy to determine the c o e f f i c i e n t s q^n^x) and p ±(M,x) of equations (2.3.5) and (2.3.7). The result w i l l be an extension of approximation (2.1.24) to higher-order terms, in the same manner as we extended approximation (2.1.26). The method of 54 doing t h i s i s to express the c o e f f i c i e n t s q± and p i in terms of the known c o e f f i c i e n t s b^. We begin by writing Z ai(m,x) r 1 = exp E bi(m,x) r 1 i=0 L i=i (2.3.21) where the b± are known and the a± are to be determined. We have used the fact that b0(m,x) = 0 in writing (2.3.21). From now on we s h a l l usually suppress the parameters m and x in our notation, and simply write L a . r 1 = exp i = 0 L b , r L (2.3.22) L i = 1 In Appendix C i t i s shown that there i s a recurrence formula which holds between the c o e f f i c i e n t s a^ ^ and b i. This formula is a 0 = 1 . a . = I - 1 k=1 k 1 k ( i ^ 1) (2.3.23) We ea s i l y find that a 0 = 1 a, = b, a 2 = b, 2/2 + b 2 a 3 = b , 3/6 + b , b 2 + b 3 a , = b , V 2 4 + b 2b, 2/2 + b 2 2/2 + b , b 3 + b« (2.3.24) and so on. Now that we have expressed the c o e f f i c i e n t s a i in terms of b ^ i t is a simple matter to express p\\ in terms of b.. We f i r s t consider the case M = 0. We have i 55 P(0,x;r) = Q(0,x;r) = Z a.(1,x) r 1 (2.3.25) i = 0 from equations (2.3.16) and (2.3.21), and i t immediately follows that p±(Q,x) = q ±(0,x) = a i ( l , x ) . Since a 0 ( l , x ) = 1, CO CO P f(0,x;r) = - Z a ± ( l , x ) r 1 = - Z p ±(0,x) r 1 . (2.3.26) i=1 i=1 But a , ( l,x) = b,(1,x) [log(x/2) + C + 1/2X - 1/12X2 + ...] (2.3.27) and so taking the f i r s t term in (2.3.26) recovers the approximation (2.1.24) [see also the note after (2.1.26)]. Note that the derivation leading to (2.1.24) depended on the fact that the block size was an integer N; equation (2.3.27) shows that (2.1.24) may be used for non-integral block sizes simply by replacing the integer N by the real number x (although the intermediate steps leading to (2.1.24) no longer make sense). The importance of (2.3.26) is that we now have formulas that enable us to compute as many of the c o e f f i c i e n t s p i(0,x) as we desire, i . e . we have extended the approximation (2.1.24) to ar b i t r a r y order. The computational scheme is s l i g h t l y more complex than i t i s for equation (2.3.16), since we must not only compute the c o e f f i c i e n t s b i ( l , x ) , but also must then f i n d the c o e f f i c i e n t s p i(0,x) = a i ( l , x ) using the recurrence r e l a t i o n (2.3.23). Lastly, we demonstrate how a s l i g h t modification of the f i r s t - o r d e r approximation (2.1.24) allows i t to be used for M > 0 as well. Comparison of equations (2.3.15) and (2.3.21) y i e l d s , for m ^ 1, 56 Hence, when m > 1, we have q0(m,x) = 0 (2.3.28) | qi(m,x) = a±_i(m,x)/m . Since q^O^x) = a i ( l , x ) [see the top of the previous page], we may write M p . (M, x) = Z q . (m, x ) m=0 (2.3.29) M = a . (1 , x ) + (1 - 6. ) Z a. ,(m,x)/m 1 i o 1-1 m=1 where i s the Kronecker del t a . In general we cannot a n a l y t i c a l l y simplify (2.3.29) very much, although we can make some useful s i m p l i f i c a t i o n s when i i s small. We s h a l l examine only the cases i = 0 and i = 1, i . e . we s h a l l consider only a f i r s t - o r d e r approximation. When i = 0, p 0(M,x) = a 0 ( l , x ) = 1. For i = 1, From (2.3.24) we fi n d that a,(1,x) = b,(1,x), and that a0(m,x) = 1. Then where the l a s t equality follows immediately on reference to Table I I I . Hence when r i s small, M p,(M,x) = a,(l,x) + Z a0(m,x)/m . m=1 (2.3.30) p,(M,x) = b,(1,x) + H = b,(M+1,x), (2.3.31) 57 P(M,x;r) = Z p ±(M,x) r 1 i = 0 = p 0(M,x) + p,(M,x) r (2.3.32) = 1 + b,(M+1,x) r and so P f(M,x;r) = 1 - P(M,x;r) = - b,(M+1,x) r = r [-log 2 - ,//(M+1) + 0. 58 2.4 D i v e r s i t y 2.4.1 Introduction We come now to the l a s t topic in our analysis of very slow Rayleigh fading: the computation of the block-error rate when ideal selection d i v e r s i t y i s employed. We assume that there are L branches, where L i s an integer greater than or equal to 1, and l e t t i n g denote the instantaneous signal-to-noise r a t i o on branch i , we further assume that {y^} i s a set of independent random variables, each having d i s t r i b u t i o n (2.1.7). In a receiver using selection d i v e r s i t y , the branch with the highest SNR i s chosen. In [23] i t i s shown that the p r o b a b i l i t y d i s t r i b u t i o n function of the largest SNR 7 * is given by f ~ * < 7 ) = L [1 - e x p ( - 7 / 7 O ) ] L _ 1 7 o - 1 e x p ( - 7 / 7 0 ) ( 7 > 0 ) 7 (2.4.1) Under the condition of very slow fading, the SNR's y± are assumed to remain constant over an entire block, and hence the same branch w i l l be chosen for an entire block. In other words, 7 * remains constant over an entire block, but varies from block to block according to (2.4.1), and so in analogy with equation (2.1.11) we may immediately write down Pd(L,M,x) = / P (M,x;7) f 7 * ( 7 ) d 7 (2.4.2) where Pd(L,M,x) is the p r o b a b i l i t y that there i s more than M errors in a block of x b i t s when L-branch selection d i v e r s i t y 59 is used. We s h a l l usually write simply P d for P d(L,M,x), and sh a l l use the notation P d } c = 1 - P d (the subscript c stands for \"complement\"). Putting (2.4.1) into (2.4.2) gives P d,c = 2 (*) f P ( 7 ) m [1 \" p ( 7 ) ] X _ m m=0 \\ / J c\\ [1 - exp(-7/7 0)] L 1 exp(-7/7 0) 6y. (2.4.3) We consider only NCFSK, for which p(7) = (1/2) exp(~7/2). For the special case M = 0 and x = 1 ( i . e . when we are computing the p r o b a b i l i t y of b i t e r r o r ) , see [14] or [20]; we are interested in the more general case. Making the substitution t = p(7), as we did in equation (2.2.2), we fi n d P d c = L r 2 r Z (*) f\\*+*-1 (1 - t ) X \" m [1 .- ( 2 t ) r ] L \" 1 dt. m=0\\m/^0 (2.4.4) r L -1 Using the-binomial expansion of the term [l - (2t) ] , we can write the previous equation in the form •i. m=0 \\ / (2.4.5) tm+(j + 1 ) r - l (, _ T)X-m d f c # 0If we now take x = N = an integer in (2.4.5) above, and use the binomial expansion of the term (1 - t j , we find P d c = L r i d s ( 7 ) (-1 ) 3 d , c m=( u (2.4.6) (-Dk 1 2 m + k [ m+(j+1)r+k] 60 Equation (2.4.6) i s the same as equation (15) of [25] (with a s l i g h t rearrangement and obvious changes in notation). As noted in [25],. equation (2.4.6) i s an alternating series that may be d i f f i c u l t to evaluate numerically when N or M i s large. In fact, the largest value of N used in [25] for numerical results i s N = 100. 2.4.2 Approximations We now develop some approximations for P d c (and hence for P d ) ; these approximations work well for block sizes greater than 10 or so. We begin by writing equation (2.4.5) in the form P d . = L r 2 r 2 (l) V pT1) ( - l ) J 2 J r BJ,(m+(j + 1)r,1+x-m). m=0 V / j=0 \\ J / 2 (2.4.7) We now approximate P d c in the manner of Section 2.2, i . e . we replace the incomplete Beta function by the Beta function: P, = L r 2 r 2 ( A V (LT1) (-1 ) j 2 j r B(m+( j + 1 )r, 1+x-m) . d ' C m=0 W j = 0\\ 2 / (2.4.8) In Appendix B we show that P d , c \" P d , c I = l Pd \" P d I -(2.4.9) L r L m=0 V\"/ 2 x _ m (1+x-m) s \\ CO m=0 \\ / This error bound i s very similar to those examined in Section 2.2, and i t follows that the error in the approximation i s 61 n e g l i g i b l e for the parameter range in which we are interested. Equation (2.4.8) may be rearranged to give L \" 1 ( - 1 ) J Pd,c = L Z I . I j = 0 \\ 2 ) j + 1 •|\"(j + 1)r 2 ( j + 1 ) r I ( A B(m+( j + 1 )r, 1+x-m) L m=0 W - I (2.4.10) L-1 / T A (-1) J ^ = L Z L , M P(M,x;(j+1)r) . j = 0\\ 3 / j + 1 We now put k = j+1 to get P d ) C = ^ ( L A ) {^il^j ( \" D k + 1 P(M,x;kr) (2.4.11) = Z fLJ ( - 1 ) k + 1 P(M,x;kr) k=l\\ k/ Since we already have an e f f i c i e n t way to compute P(M,x;r), equation (2.4.11) can be used to approximate P d c , and hence P d , when L i s small. If L i s large, the alternating series (2.4.11) may prove unsuitable for numerical computation. In Figure 2.7, P(L,0,100) has been plotted as a function of the average SNR y0 for L = 1, 2, 3, 4. Clearly the ef f e c t of d i v e r s i t y i s to substantially improve the pro b a b i l i t y of block error for a given SNR, although the improvement obtained by adding one more branch decreases as the number of branches increases. We can get more insight into the behavior of P d by deriving i t s i n f i n i t e series expansion. We use (2.3.7) to write 0.0 10.0 20.0 30.0 40.0 50.0 Average signal-to-noise r a t i o r 0 in dB. Figure 2.7: P,(L,0,100) for L • 1, 2, 3, 4. 63 P(M,x;kr) = Z p±(M,x) r 1 k 1 i = 0 when |r| < 1/k ( r e c a l l that the series expansion for P(M,x;r) converges for at least |r| < 1). Since the largest value assumed by the index of summation k in (2.4.11) i s k = L, we may write f C = Z (l) (-Dk+1 Z p.(M,x) r V k=1 W i=0 (2.4.12) = Z p.(M,x) T Z (^(-D k + 1 k1 1 r 1 i=0 1 L k=0 W for |r| < 1/L. Denote the quantity in square brackets by S ( L , i ) , i . e . S(L,i) = j ^ ) (-l)k+1 k 1 = -L (^( -UV. (2.4.13) Let | H denote S t i r l i n g numbers of the second kind [1,13]. On page 67 of [13] we fi n d the r e l a t i o n (-Dnn! = Z k m(-D k (2.4.14) with the convention that 0° = 1. Using t h i s same convention, we can combine equations (2.4.13) and (2.4.14) to give S(L,i) = - Z (-1 j H 1 = 6 i o - Z (-I)** 1 where 6 ±j i s the Kronecker de l t a . Thus 64 P d(L,M,x) = 1 - P d c(L,M,x) CO = 1 - Z p.(M,x) S(L,i) r 1 i = 0 1 = (-1) LL! I p.(M,x) M r 1 . i=1 1 l 1 ' In the preceding calculations we used the result p 0(M,x) = a 0 ( l , x ) = 1 (see page, 56) and the fact that S(L,0) = 1 to cancel the f i r s t term of the serie s . It can be shown that [13] = 0 for 1 < i < L, {I:}-'- ™* { L V \\ • Thus P d = (-1) LL! (p L(M,x) r L + [L(L+D/2] p L + 1 ( M , x ) r L + 1 + ...} or, retaining only the f i r s t term, Pd = (-1) LL! P L ( M , X ) r L = (-2) LL! pT (M,x)/ 7 o L. Thus the eff e c t of d i v e r s i t y i s to make the pr o b a b i l i t y of error proportional to 7 0~ L tor large SNR's, instead of proportional to 7 o \" 1 as in equation (2.1.24). The pr o b a b i l i t y of error therefore drops off much more rapidly as the signal-to-noise r a t i o increases than i t does when d i v e r s i t y i s not employed, as shown in Figure 2.7. 65 Chapter 3 A model for ca l c u l a t i n g block-error rates on slow Rayleigh fading channels In the previous chapter we examined several methods for the computation of Pf(M,N) on a channel subject to very slow Rayleigh fading. The purpose of thi s chapter i s to consider the computation of Pf(M,N) when the assumption of very slow fading is relaxed, i . e . when the signal-to-noise r a t i o does not necessarily remain constant over an entire block. The emphasis w i l l be on the mobile-radio environment. Without the assumption of very slow fading, the a n a l y t i c a l methods of Chapter 2 are no longer applicable, and at present there appears to be no a n a l y t i c a l method for computing the pro b a b i l i t y of block error. Thus we must resort to simulations. In general, there are two types of simulators: hardware and software. Descriptions of hardware simulators for Rayleigh fading can be found, for example, in [2] and [4]. It was decided for the purposes of thi s thesis to use a software simulator based on a computer program given in [24]. The software simulator was chosen over a hardware version because of the ease of i t s implementation. A disadvantage of using a simulator on a d i g i t a l computer i s the long running time (and hence high cost) required to guarantee s t a t i s t i c a l l y v a l i d r e s u l t s . To overcome the expense of computer simulations, an attempt was made to find a simple empirical formula, based on the formulas of Chapter 2, that would allow us to predict the 66 results of the simulations. In Section 3.2.2 we describe a model from which we derive such an empirical formula. This formula turns out to be quite successful in that i t allows easy ca l c u l a t i o n of the p r o b a b i l i t y of block error when very slow fading i s not assumed. 67 3.1 The Simulator 3.1.1 Implementation The simulator was implemented both on the university's Amdahl 470 and on a Nova 840 that i s resident in the department of e l e c t r i c a l engineering. Although i t i s much slower than the Amdahl, the Nova could be run for much longer periods of time because the computer time was free. The simulation programs for both computers were written in FORTRAN, but they d i f f e r e d in many respects due to differences in the machines and their operating systems. For example, the Amdahl has virtual-memory c a p a b i l i t y , i . e . the system automatically performs transfers between primary and secondary storage when necessary, thereby enabling the programmer to manipulate large data structures e a s i l y and r e l i a b l y . On the Nova, however, storage a l l o c a t i o n and transfers between core and disk are largely the r e s p o n s i b i l i t y of the programmer. Furthermore, the Amdahl has a large amount of support software, such as random-number generators and fast Fourier transform (FFT) routines. A l l such programs had to be coded e s p e c i a l l y for the Nova. Thus, although the simulation programs implemented the same algorithm, they d i f f e r e d in many respects. The fact that the simulators gave i d e n t i c a l results in several tests increased the confidence in their correctness. 3.1.2 Description of the algorithm The simulation program uses a Monte Carlo method, i . e . a 68 method based on random-number generators (the numbers should more accurately be c a l l e d pseudo-random, but the term random number i s standard). An outline of the algorithm follows; the d e t a i l s w i l l be described in subsequent sections. The simulation program f i r s t generates and stores a fading sequence with the exponential d i s t r i b u t i o n given in equation (2.1.7), and then normalizes i t to the desired average SNR 7 0 . The sequence i s given an exponential d i s t r i b u t i o n instead of a Rayleigh d i s t r i b u t i o n because i t i s more convenient to work d i r e c t l y with signal-to-noise r a t i o s . \" Samples are taken from the exponentially d i s t r i b u t e d sequence one at a time; each sample represents the SNR that i s associated with each bit in a simulated stream of transmitted b i t s . As a f i r s t step in deciding whether or not a given b i t i s in error, the p r o b a b i l i t y of error for that b i t is calculated. This c a l c u l a t i o n i s done by substituting the associated SNR from the fading sequence into the appropriate formula for the p r o b a b i l i t y of b i t error. That i s , i f 7 i s the k-th SNR value in the fading sequence, then the k-th b i t i s in error with p r o b a b i l i t y p ( 7 ), where i s chosen from (2.1.1) or (2.1.2) in accordance with the modulation scheme being examined. Next, a random number u, i s chosen from the uniform d i s t r i b u t i o n on k \"Of course, we can derive a Rayleigh-distributed sequence from the exponentially d i s t r i b u t e d one by taking the square root of the sample values. A Rayleigh-distributed sequence i s desired for c e r t a i n tests that are used in Section 3.1.3 to v e r i f y the s t a t i s t i c a l properties of the sequence generator, and for these tests the square root i s taken. 0 69 the i n t e r v a l [0,1], and i s compared with p ( 7 k ) . If u k < p(7 k) we say that the b i t i s in error; otherwise we say that the b i t is correct. Note that the signal-to-noise r a t i o i s s t i l l assumed to be constant over the duration of a b i t , although i t may change from b i t to b i t . Thus the simulator should give a bi t - e r r o r rate equal to the the o r e t i c a l results for slow fading given in equations (2.1.9) and (2.1.10). By segmenting the fading sequence into blocks of N samples, we can ea s i l y keep track of the number of errors per block. If a s u f f i c i e n t l y large number of blocks are observed, the block-error rate may then be stated with a high degree of cert a i n t y . To gauge the s t a t i s t i c a l accuracy of the simulations, the following procedure was adopted. A fading sequence i s f i r s t generated, and the block-error rate for t h i s sequence i s computed as a r e l a t i v e frequency. The results for th i s sequence are said to constitute a single t r i a l . Thus i f n t r i a l s are conducted, the result i s n r e l a t i v e frequencies P^MjN), P2(M,N), Pn(M,N) that approximate the true p r o b a b i l i t y of block error. The sample mean Pg (M,N) and the sample variance are then computed. Assuming that the d i s t r i b u t i o n of the sample mean i s approximately Gaussian, and replacing the unknown true variance by the sample variance, we construct a 95% confidence i n t e r v a l about the sample mean using the t - d i s t r i b u t i o n . J u s t i f i c a t i o n for using the t - d i s t r i b u t i o n can be found, for example, in [27]. A 95% confidence i n t e r v a l means that we are 95% confident that the stated i n t e r v a l contains the true mean. F i n a l l y , we note that the algorithm 70 above i m p l i c i t l y assumes a lack of intersymbol interference. 3.1.3 Generation of the fading sequence Before looking at the d e t a i l s of generating the fading sequence, l e t us consider the s t a t i s t i c a l properties that we desire the sequence to have. As stated in the introduction, the emphasis here i s on mobile-radio communication. The following discussion i s based on continuous-time s t a t i s t i c s ; the simulator of course employs their discrete-time counterparts. The s t a t i s t i c a l model that we use for the mobile-radio environment i s the one examined by R.H. Clarke in [7]. It i s assumed that the received signal contains no d i r e c t component, but instead consists e n t i r e l y of indi r e c t components, each of which has an angle of a r r i v a l that i s uniformly d i s t r i b u t e d from 0 to 2n. The phases of the a r r i v i n g waves are assumed to be uniformly d i s t r i b u t e d from 0 to 2w and s t a t i s t i c a l l y independent. Clarke showed that the amplitude of the received signal envelope i s then Rayleigh d i s t r i b u t e d , and that the phase is uniformly d i s t r i b u t e d . Furthermore, when a v e r t i c a l monopole antenna is used the power spectral density of the Rayleigh-fading envelope i s where S 0 i s a constant and f_ i s the Doppler frequency, given S(f) = S 0 [1 - ( f / f D ) 2 ] - i / 2 , 0, D (3.1.1) by 71 f = v/X. (3.1.2) In equation (3.1.2) v i s the vehicle speed and X i s the c a r r i e r wavelength. The use of a d i f f e r e n t antenna leads only to a d i f f e r e n t power spectral density; see [10] for the power spectral densities that result from a variety of antenna conf igurat ions. Several other s t a t i s t i c a l properties of the Rayleigh-fading envelope have been derived in the l i t e r a t u r e . In [12] i t is shown that the average duration of the fades below the l e v e l p i s exp(p 2) - 1 Tip) = , (3.1.3) \\/2T f D p and that the average rate at which the envelope crosses the l e v e l p with a positive slope i s N(p) = V T T T f p exp(-p 2). (3.1.4) The quantity p in equations (3.1.3) and (3.1.4) is the amplitude of the fading envelope measured r e l a t i v e to the RMS value of the envelope, i . e . . envelope amplitude p = . (3.1.5) RMS value of the envelope F i e l d tests described in the l i t e r a t u r e have v e r i f i e d experimentally that the above results hold quite well. It has been v e r i f i e d that the short-term s t a t i s t i c s of the fading envelope are well described by the Rayleigh d i s t r i b u t i o n [7,22], and experimental results in [11] and [22] show that the 72 t h e o r e t i c a l formulas (3.1.3) and (3.1.4) adequately predict the average duration of fades and the rate of l e v e l crossings. Let us now return to the generation of the fading sequence. The section of the simulator that generates t h i s sequence was taken almost verbatim from [24]. The computer program in [24] i s based on the fact that a Rayleigh-d i s t r i b u t e d sequence can be generated by adding two independent Gaussian-distributed sequences in quadrature (see Chapter 7 of [18]). A shaping f i l t e r i s used to give the sequence the desired spectrum (3.1.1). The shaping i s done by m u l t i p l i c a t i o n in the frequency domain followed by a translation into the time domain using an FFT. The number of points in the FFT was set to 4096, resu l t i n g in a simulated b i t rate of R = 4096 bits/sec. Note that the normalization of the fading sequence makes the actual value of S 0 in equation (3.1.1) immaterial: i t was set to unity for convenience. To check the operation of the fading-sequence generator, a sequence was generated that was 500 seconds long, and several s t a t i s t i c a l quantities based on this sequence were computed. F i r s t , the cumulative d i s t r i b u t i o n function (cdf) of the fading sequence was computed and compared with the desired Rayleigh cdf. In Figure 3.1 the s o l i d l i n e i s the t h e o r e t i c a l Rayleigh cdf, and the plotted points are the values computed from the fading sequence. Clearly the d i s t r i b u t i o n of the output of the fading-sequence generator i s very close to the desired Rayleigh d i s t r i b u t i o n . Also computed from the 500-second-long sequence were the average fade duration and the level-crossing rate. The 73 Level p in dB r e l a t i v e to the RMS value. Figure 3.1: Rayleigh cdf 74 th e o r e t i c a l results given by equations (3.1.3) and (3.1.4) are graphed as s o l i d l i n es in Figures 3.2 and 3.3 respectively; the curves in these two figures have been normalized to unity Doppler frequency. The plotted points are the values computed from the fading sequence, also normalized to unity Doppler frequency. As one can see, the agreement between the t h e o r e t i c a l and the measured results is excellent. 3.1.4 Simulation results The simulation program was used to compute the probability of block error, P (M,N), for NCFSK modulation. The program was run for block sizes N = 63, 127, 255, 511, 1023, 2047; for M = 0, 1, 2, 9; for Doppler frequencies f n = 10.5, 15.5, 20.5, 25.5 Hz; and for average SNR's y0 = 5, 10, 15, , 35 dB. In Section 3.1.2 the use of a 95% confidence i n t e r v a l to check the s t a t i s t i c a l accuracy of the simulations was described. Tests were run to determine the number of t r i a l s , n, required to make thi s i n t e r v a l s u f f i c i e n t l y small that meaningful conclusions could be drawn. It was f e l t that a reasonable c r i t e r i o n was to make the 95% confidence i n t e r v a l less than about 10% of the computed sample mean Pg(M,N). This c r i t e r i o n could not be met uniformly with respect to the average SNR 7 0, because for a fixed number of t r i a l s the confidence intervals become larger with increasing SNR. This pattern holds because at low SNR's the p r o b a b i l i t i e s are close to unity, and hence many errors w i l l occur during the simulation. The large number of errors ensures good s t a t i s t i c a l 1 1 1 1 1 1 ~\" -30.0 -2S.0 -20.0 -1S.0 -10.0 -5.0 0. L e v e l p i n dB r e l a t i v e t o the RMS v a l u e F i g u r e 3.2: Average fade time T(p). L e v e l p i n dB r e l a t i v e to the RMS value F i g u r e 3.3: L e v e l - c r o s s i n g r a t e N ( * ) . 76 r e s u l t s . At high SNR's the p r o b a b i l i t i e s are small, i . e . we are examining rare events, and so not enough errors occur during the simulation to obtain s t a t i s t i c s that are as good as those at low SNR's. When sequences 60 to 90 seconds long per t r i a l were used, the tests showed that taking n in the range 10 ^ n < 15 was s u f f i c i e n t to meet the c r i t e r i o n given above at 7o = 25 dB. The bi t - e r r o r p r o b a b i l i t y was also computed, and as anticipated i t agreed well with the th e o r e t i c a l result p = 1/(2 + 7 0) given for NCFSK in equation (2.1.9). Some of the simulation results are presented here in graphical form; the idea i s not to catalog a l l the results produced, but to give representative examples. Figure 3.4 gives P S(0,127) as a function of the average SNR 7 0 for a l l four Doppler frequencies, and with a l l other parameters held fixed. The plotted points are those produced by the simulation, and the curves connecting them are plotted using quadratic interpolation. In addition to these four curves, two other curves are given for reference. The lower curve i s the value of P f(0,127) for very slow fading, computed using the approximate methods of Chapter 2. The upper curve shows the prob a b i l i t y of block error 1 - (1 - p f ) 1 2 7 that would result on an independent-error channel that has a bi t - e r r o r p r o b a b i l i t y p f = 1/(2 + 7 0 ) . From Figure 3.4 we see that the prob a b i l i t y of block error computed by the simulation program i s larger than the value computed under the assumption of very slow fading. I n t u i t i v e l y one anticipates that allowing faster fading should have an P r o b a b i l i t y of block error P g(0,127). LL 78 adverse effect on the performance, and th i s conjecture i s confirmed. It is further supported by the fact that Pg(M,N) increases with the Doppler frequency f D , i . e . the faster the fading the worse the performance. However, the performance appears to be less sensitive to changes in f R for larger values of f Q , e.g. the curves for 20.5 and 25.5 Hz are closer together than are the curves for 10.5 and 15.5 Hz. Also, the pr o b a b i l i t y of block error i s smaller than that on a random-error channel with the same b i t - e r r o r rate. Figure 3.5 gives the error p r o b a b i l i t y P g(0,N) for di f f e r e n t block lengths N. Comparison with Figure 2.3 shows that the deterioration of performance with increasing block length i s worse for the simulation results than i t i s for the case of very slow fading. F i n a l l y , Figure 3.6 shows Pg(M,63) for several values of M at Doppler frequency 15.5 Hz. For M ^ 1, P s does not appear to have a simple dependence on y0 when 7 0 i s large, i . e . the curves for d i f f e r e n t values of M are not straight for large SNR's, as they are in the case of very slow fading (see Figure 2.4). This behavior suggests that i t might be more d i f f i c u l t to describe a n a l y t i c a l l y the curves for M > 1 than i t was when the fading was very slow. Average signal-to-noise r a t i o r 0 in dB. Figure 3.5: P s(0,N) for d i f f e r e n t block sizes at 15.5 Hz. 80 Figure 3.6: PS(M,63) for M = 0, 1 , 2, 3 at 15.5 Hz. 81 3.2 Derivation of the empirical formula 3.2.1 Introduction The purpose of t h i s section i s to develop an empirical formula r e l a t i n g the results of the computer simulations to the equations of Chapter 2. If such a formula could be found, i t s usefulness would be obvious: we could e a s i l y predict the res u l t s that would be obtained by the simulation program without a c t u a l l y running the program. The upshot would be an enormous saving in computer time, while allowing us to compute a more r e a l i s t i c value of the pr o b a b i l i t y of block error than i s provided under the assumption of very slow fading. For s i m p l i c i t y we s h a l l r e s t r i c t ourselves to the case M = 0, i . e . to the approximation of P (0,N). As we s h a l l see, a simple s model allows the derivation of an empirical formula that works quite well. We start by describing t h i s model. 3.2.2 The model Given a block of N b i t s , we divide t h i s block into a number of sub-blocks, each of length x b i t s . The hypothesis i s that by choosing the size of the sub-blocks c o r r e c t l y , we may treat the sub-blocks as though they were independent. Furthermore, i f the sub-blocks are small enough, i t seems reasonable to assume that the fading process i s so slow r e l a t i v e to the sub-block duration that the SNR is approximately constant over the sub-block. Thus we may approximate the probability that each sub-block i s correct by 82 using the results for very slow fading. Then, in the notation of Chapter 2, the p r o b a b i l i t y that each sub-block is correct i s P(0,x;r), where r = 2/y0. Because the sub-blocks are assumed to be independent, the p r o b a b i l i t y P(0,x;r) i s m u l t i p l i e d together to obtain the p r o b a b i l i t y that the o r i g i n a l block of N b i t s i s correct. Since there are N/x sub-blocks we use the formula 1 - P ( 0 , x ; r ) N / x (3.2.1) to approximate the p r o b a b i l i t y of block error, P (0,N). We s h a l l now investigate formula (3.2.1) in d e t a i l . If i t turns out that formula (3.2.1) works well, this i s not necessarily due to the reasons given in our description of the model; however, i f the formula works well, the actual reasoning that led to i t can be ignored. The problem now i s to discover how the sub-block size x must be chosen in order to make (3.2.1) y i e l d the p r o b a b i l i t y P g(0,N) computed by the simulation program. We do not r e s t r i c t x to integer values, i . e . the size of the sub-blocks may be non-integral. The derivations of Chapter 2 allowed for t h i s p o s s i b i l i t y . Recall that, besides the block size N, P s(0,N) w i l l depend on the average signal-to-noise r a t i o 7 0, on the Doppler frequency f D , and on the b i t rate R. To reduce the number of variables we must consider, we define the r a t i o L = R/f D. Note that the units of L are b i t s when R i s in bits/sec and f D i s in Hertz. The dependence of P s(0,N) on R and f D can be s p e c i f i e d e n t i r e l y by the single quantity L because i t i s only the fading rate r e l a t i v e to the b i t rate that 8 3 determines the error p r o b a b i l i t y P s(0,N) when the other parameters are held fixed. Since the fading rate i s proportional to the Doppler frequency f D [see equation (3.1.4)], the error p r o b a b i l i t y P s(0,N) remains constant when R and f D change by the same factor. We think of L as a fundamental block length that helps to characterize the fading channel for a given R and f n . We also introduce a quantity d, which i s defined by the requirement that 1 - P ( 0 , x ; r ) N / x = P s(0,N) (3.2.2) where x = L/d. We s h a l l c a l l d the d i v i s o r : i t i s the number by which we must divide L to obtain the size of the sub-blocks. Suppose we are given the following three parameters: the block size N, the quantity L = R/f D, and the average SNR y0l i . e . we are given enough information to specify a value of P g. The only quantity we must now know in order to apply formula (3.2.1) i s the corresponding value of the d i v i s o r d, as previously determined by equation (3.2.2), for then we can compute the sub-block size x = L/d and substitute t h i s d i r e c t l y into (3.2.1). The d i v i s o r could t h e o r e t i c a l l y change with a l l three parameters N, L, and 7 0• (Since R was held fixed at 4096 bits/sec during the computer simulations performed for t h i s thesis, any change in L i s due solely to a change in the Doppler frequency f D« Hence we s h a l l refer to the change in d with f D , although i t should be remembered that the results we s h a l l derive here do not depend on the p a r t i c u l a r b i t rate used in the simulations.) The usefulness of the formula (3.2.1) 84 depends largely on how d fluctuates with N, f D , and 7 0: the simpler the relationship, the more useful the formula. As we s h a l l see, the d i v i s o r d i s almost independent of N and f n , and has a simple dependence on j 0 . In fact, d changes so l i t t l e with N and f D that we s h a l l assume i t is constant with respect to those two parameters, and focus on characterizing i t s dependence on 7 0 . We s h a l l use curve f i t t i n g to find an empirical relationship between d and 7 0. 3 . 2 . 3 Numerical results The f i r s t step in making our empirical formula quantitative was to compute, for each of the values of P s produced by the simulation program, the d i v i s o r d that makes equation ( 3 . 2 . 2 ) hold. Since simulations were run for 6 block sizes, 4 Doppler frequencies, and 7 average SNR's, P g was computed for 6x4x7 = 168 d i f f e r e n t parameter combinations. The procedure for computing the 1 6 8 corresponding d i v i s o r s was to solve equation ( 3 . 2 . 2 ) for the value of x that makes i t hold for a s p e c i f i c value of P , and then to set d = L/x. Since equation ( 3 . 2 . 2 ) i s a complicated nonlinear equation i t was not possible to solve i t a n a l y t i c a l l y , and the solution had to be found numerically. As a check on the solutions, two d i f f e r e n t numerical methods were used: Newton's method and a simple bisection method. During these numerical computations, the left-hand side of ( 3 . 2 . 2 ) was evaluated using the approximations of Section 2 . 2 . To further c l a r i f y what i s being done here, the expression in ( 3 . 2 . 1 ) has been graphed in Figure 8 5 3.7 as a function of x for N = 255 and for several values of the average signal-to-noise r a t i o . One can find the solution of (3.2.2) for a given P g by drawing a horizontal l i n e across Figure 3.7 at the appropriate l e v e l u n t i l i t intersects the correct curve, and by then extending a l i n e downward to find the corresponding value of x. This procedure has been i l l u s t r a t e d in Figure 3.7 for the value P g(0,255) = 0.246, obtained at f D = 15.5 Hz and y0 = 25 dB using the simulation program. From the figure we find that the sub-block size causing equation (3.2.2) to be s a t i s f i e d i s x = 15 b i t s (the numerical methods, which are of course much more accurate than the graphical method shown here, y i e l d x = 14.96 b i t s ) . The d i v i s o r in t h i s case i s d = L/x = R/(x - f D) = 4096.0/(15.0x15.5) = 17.6. There were several d i f f i c u l t i e s in the numerical computations just described, d i f f i c u l t i e s which w i l l now be discussed. One d i f f i c u l t y occurs when the SNR i s small and the block size large. In this parameter range the pr o b a b i l i t y of block error i s close to unity, and in many cases the simulation program yielded a value P g = 1.0 to single-precision accuracy, i. e . the simulation program did not record a single correct block for the duration of the simulation. A problem arises because for small SNR's the formula of (3.2.1) y i e l d s a value that i s very close to unity for a wide range of x values, i . e . is r e l a t i v e l y insensitive to changes in x (see Figure 3.7). Sub-block size x in b i t s . Figure 3.7: Formula (3.2.1) as a function of x for d i f f e r e n t average SNR's r 0 . CO 87 Hence the value of x computed as a solution of equation (3.2.2) is unreliable when P s = 1.0. On the one hand, th i s problem i s annoying when trying, as we are here, to derive an empirical formula based on (3.2.1), because the values of x for small SNR's w i l l have no consistent trend. On the other hand, t h i s behavior works in our favour when the purpose i s to approximate P s using formula (3.2.1), since even an inaccurate value of x allows a good approximation to the pr o b a b i l i t y of block error when i t i s near unity. Also, we are not generally interested in the case when the block-error rate i s near unity. Another d i f f i c u l t y stems from the behavior of expression (3.2.1) when x i s small. As can be seen from Figure 3.7, the expression in (3.2.1) has a maximum near x = 2 b i t s , and decreases for x below this value (see Figure 3.7). The problem arises because as the average SNR y0 increases the sub-block size x decreases, and for y0 near 35 dB the va'lue of x i s about 5 b i t s or so, i . e . near the peaks of the curves in Figure 3.7. If now 7 0 i s increased further, then the horizontal l i n e corresponding to the p r o b a b i l i t y P g l i e s above the peak in the curve, and equation (3.2.2) no longer has a solution. Consequently, when the SNR becomes large the numerical methods tend to \"lock i n \" at x = 2 b i t s . This behavior suggests that formula (3.2.1) might not work well for large SNR's (or, equivalently, for small sub-block s i z e s ) . Since we s h a l l not be working with SNR's greater than 35 dB we do not need to worry very much about the possible d i f f i c u l t i e s above 35 dB. The method of dealing with the above-mentioned problems 88 was simply to reject those values of x (and hence d) that were obviously wrong. This procedure may seem a r b i t r a r y to the reader, but i t was employed in the absence of any other suitable c r i t e r i o n . (Also, one should not lose sight of the fact that our sole purpose here i s to derive an empirical formula that allows us to predict accurately the outcome of our simulations — i f the formula we end up with does the job well, then the means by which we obtained i t are j u s t i f i e d a p o s t e r i o r i . ) Of the 168 d i v i s o r s computed, corresponding to the 168 data points P , i t was decided to reject 30, leaving 138 d i v i s o r s for subsequent analysis. In Table IV the d i v i s o r s are l i s t e d ; the values that were rejected have been replaced by dashes. The table has been organized to demonstrate c l e a r l y the behavior of d with the changes in the three parameters (N, f , 7 0) on which i t depends. It i s immediately evident from the table that the d i v i s o r changes l i t t l e with either the block size N or the Doppler frequency f , but does change substantially with the average signal-to-noise r a t i o 7 0. For a fixed 7 0 the d i v i s o r seems to decrease s l i g h t l y with increasing N and f , although t h i s trend i s often interrupted by what appear to be s t a t i s t i c a l f l u c t u a t i o n s . There i s a much stronger trend in the change of d with 7o. Since we desire an empirical formula that i s as simple as possible, and since the s t a t i s t i c a l fluctuations just mentioned could make i t hard to characterize corr e c t l y the dependence of d on N and f , i t was decided to regard d as independent of N and f , and to attempt to find an approximate f D (Hz) 7o (dB) N (bits) 10.5 15.5 20.5 25.5 5 63 1 27 255 51 1 1 023 2047 6.887 4.455 4.248 5. 183 4. 1 50 3.513 4.500 3.917 4. 1 55 3.855 1 0 63 1 27 255 51 1 1 023 2047 7.486 5.308 4.923 4.748 6.053 5.080 4.582 4.224 5.440 5.007 4.425 5. 199 4.915 4.588 1 5 63 1 27 255 51 1 1 023 2047 8.893 7.031 6.527 6.472 6.024 8.022 7.041 6.510 6.476 5.855 7.491 7.059 6.666 6.481 5.448 7.208 6.943 6.483 6.306 20 63 1 27 255 51 1 1 023 2047 12.328 10.648 10.150 9.907 9.710 9.206 11.713 10.746 10.444 10.238 9.691 10.891 11.474 11.092 10.609 10.320 9.970 11.200 10.980 10.734 10.172 10.280 10.472 8.520 Table IV: Divisors (cont'd next page) f D (Hz) 7o (dB) N (bits) 10.5 15.5 20.5 25.5 25 63 127 255 51 1 1023 2047 19.208 17.648 17.319 17.090 16.896 17.191 18.305 17.882 17.660 17.558 17.618 18.130 18.973 18.425 18.360 16.629 16.586 16.016 18.726 17.647 17.275 17.276 17.018 16.311 30 63 127 255 51 1 1 023 2047 30.604 30.522 28.904 29.534 28.764 29.225 30.311 31.417 31.279 28.750 32.649 33.382 31.617 32.656 31.560 27.943 30.044 29.126 29.974 30.429 27.628 29.111 27.864 30.094 35 63 1 27 255 51 1 1023 2047 50.701 49.203 50.577 49.548 52.630 47.291 49.959 52.495 51.711 54.840 60.073 61.464 58.729 59.005 57.907 50.266 51.293 50.379 60.655 60.241 51.842 53.802 48.700 Table IV: Divisors 91 relationship between d and 7 0 alone: d = F(A,,A 2,...,A k;7 0)• (3.2.3) In equation (3.2.3), the c o e f f i c i e n t s A± are fixed parameters in the functional r e l a t i o n s h i p F that holds between d and 7 0. The procedure carried out to determine a suitable F and the numerical values of the parameters was as follows. F i r s t , a s p e c i f i c functional form for F was posited on the basis of graphs. Then, the parameters A.^ were chosen to obtain a least squares f i t to the 138 data points. To make the formulation more precise, l e t (701, di) denote the data points for i = 1, 2, 138. We then seek the parameters A^ that minimize the expression 138 138 Z r? = Z [F(A,,...,A k;7 0 i) - d ± ] 2 (3.2.4) i=1 i=1 where r^ = F(A,,...,A k;y 0i) - 6± i s c a l l e d the res i d u a l . Two di f f e r e n t computer programs, both of which were made available by the UBC Computing Centre, were used to carry out the least squares f i t . The f i r s t program, NL2S0L, was best suited for the least squares minimization, as i t required only the coding of F and i t s f i r s t p a r t i a l derivatives with respect to the parameters A-^ . The second program, DGRADX, was a program for maximizing general nonlinear functions, and was not t a i l o r e d s p e c i f i c a l l y to the least squares problem. Thus to minimize the summation appearing in (3.2.4), i t was necessary to code the negative of the summation, along with i t s f i r s t and second p a r t i a l derivatives with respect to the parameters. As a check 92 on the numerical results, both programs were run for each functional form F that was t r i e d . The r e s u l t s were almost i d e n t i c a l in a l l cases (the differences were so small as to be neg l i g i b l e to the accuracy that we were working). To show what the function F must look l i k e , the d i v i s o r has been graphed in Figure 3.8 as a function of y0 for the s p e c i f i c values N = 255 and f D = 10.5 Hz. The shape of the curve, which i s much the same for the other block sizes and Doppler frequencies considered here, suggests a parabola of some sort. Two d i f f e r e n t functional forms were t r i e d : (a) F(A,,A 2,A 3;7 0) = A, + A 2 7 o 3 The units of 7 o were taken to be decibels. The computed values of the parameters were: A, = 5.148 A 2 = 2.237X10\"5 A 3 = 4.102. With th i s choice of parameters, the minimized value of (3.2.4) was 578.0. (b) F(A,,A 2,A 3;7o) = A, + A 2exp(A 37 0) The computed values of the parameters were: A, = 2.850 A 2 = 6.435X10\"1 A 3 = 1.248x10\" 1 . The minimized value of (3.2.4) was 557.9. The exponential curve in (b) provides a s l i g h t l y better f i t than does the power law in (a). Both curves are plotted in Figure 3.9, along with the data shown in Figure 3.8. Clearly F i g u r e 3.8: P l o t of the d i v i s o r as a f u n c t i o n of r 0 a t N = 255 and f D = 10.5 Hz. 94 Figure 3.9: Plots of the curves that have been f i t t e d to the data in table IV. 95 the f i t i s good no matter which one of the two functional forms we use. At t h i s point we have completed the derivation of our empirical formula. A computer program was written to evaluate (3.2.1), using the exponential f i t in (b) above to f i n d the di v i s o r for a spec i f i e d average SNR 7 0. The results produced by the program were compared with the simulation results for a l l 168 combinations of the parameters N, fp, and yQ; the comparison showed that formula (3.2.1) accurately predicts the simulator output P g(0,N). To measure qua n t i t a t i v e l y the accuracy of the empirical formula, the average of the absolute value of the percentage error was taken over the 168 values of P g(0,N) computed by the simulation program. The calculated average was only about 1.7%, indicating the high accuracy of the predicted values. Note that the average was taken over a l l 168 p r o b a b i l i t i e s even though the empirical formula was based on a subset of 138 p r o b a b i l i t i e s . It i s , of course, the purpose of the empirical formula to allow us to predict what the output of the simulation program would be for parameter values d i f f e r e n t from those we have already used. If we make the reasonable assumption that P g depends smoothly on the parameters N, f D , and y0t we can conclude on the basis of the above r e s u l t s that the empirical formula derived here w i l l accurately predict the output of the simulator over a wide range of parameter values. Presented now are some graphical examples. Figures 3.10 and 3.11 are similar to Figures 3.4 and 3.5 respectively, 96 except here the s o l i d l i n es were plotted using formula (3.2.1). The agreement between the simulator results and the values predicted by formula (3.2.1) i s obviously good. L6 Figure 3.11: P s(0,N) for d i f f e r e n t block sizes at 15.5 Hz using the empirical formula. oo 99 Chapter 4 4.1 Conclusions In t h i s thesis, several methods for computing the pro b a b i l i t y of block error on a Rayleigh fading channel in the presence of additive white Gaussian noise were examined. Chapter 2 focussed on the special case of very slow fading; Chapter 3 considered the e f f e c t s of relaxing the assumption of very slow fading. The results of Chapter 2 show that when the fading i s very slow and the modulation technique i s non-coherent FSK, numerical methods exist that allow the accurate approximation of the block-error p r o b a b i l i t y Pf(M,N). An important conclusion is that the computation of Pf(M,N) for M > 0 can be reduced approximately to the computation of P f(0,N) and that of a m u l t i p l i c a t i v e correction factor. Furthermore, rigorous error bounds show that the error incurred by making these approximations i s n e g l i g i b l e over a wide range of parameter values. Also considered in Chapter 2 i s the computation of the block-error rate when L-branch selection d i v e r s i t y is employed; the formulas derived are useful for small values of L. It i s shown that the p r o b a b i l i t y of block error, considered as a function of the average signal-to-noise r a t i o y0, f a l l s off as 1/70-In Chapter 3 a more r e a l i s t i c channel i s assumed, one in which the SNR i s not necessarily constant over an entire block. The block-error rate must now be estimated by simulation; the simulations c a r r i e d out for th i s thesis were performed by 100 d i g i t a l computer. The s t a t i s t i c a l properties of the simulator were chosen to be those of the mobile-radio environment. The resu l t s produced by the simulator had largely the q u a l i t a t i v e properties that one i n t u i t i v e l y expects, e.g. the faster the fading, the worse the system performance. However, the simulation results were not considered to be an end in themselves; the primary function of the simulator was to produce a s u f f i c i e n t amount of data to test a s p e c i f i c model of the fading channel when very slow fading is not assumed. A formula based on t h i s model was shown to be successful in predicting the simulator output. Thus the formula of Chapter 3 provides a simple method of computing a more r e a l i s t i c value of the p r o b a b i l i t y of block error than i s available under the assumption of very slow fading. 101 4. 2 Future work There are several areas in which the work of th i s thesis could be extended. Almost a l l of the formulas derived here are for the case of non-coherent FSK modulation; t h i s modulation technique was considered because i t y i e l d s the most tractable equations and because i t i s the modulation scheme analysed most often in the relevant l i t e r a t u r e (of course, the second reason mentioned i s probably a d i r e c t consequence of the f i r s t ) . Attempts should be made to find useful approximations when other modulation techniques are used, although th i s may be di f f i c u l t . Furthermore, the results of Chapter 3 should be extended to cover the case M > 0 as well. It i s not clear whether this would e n t a i l s i g n i f i c a n t l y more complex equations, or whether th i s extension could be accomplished in a straightforward manner. 1 02 References [1] Abramowitz, M. and Stegun, I.A., eds. Handbook of Mathematical Functions, Dover Publications, New York, 1972. [2] Arredondo, G.A. et a l . \"A multipath fading simulator for mobile radio,\" IEEE Trans, on Commun., v o l . COM-21, no. 11, pp. 1325-1328, November 1973. [3] and Smith, J . I . \"Voice and data transmission in a mobile radio channel at 850 MHz,\" IEEE Trans, on Vehicular Technology, v o l . VT-26, no. 1, pp. 88-93, February 1977. [4] Bodtmann, W.F. and Arnold, H.W. \"Fade-duration s t a t i s t i c s of a Rayleigh-distributed wave,\" IEEE Trans. on Commun., v o l . COM-30, no. 3, pp. 549-553, March 1982. [5] Brent, R.P. \"Algorithm 488: A Gaussian pseudo-random number generator,\" Communications of the ACM, v o l . 17, no. 12, pp. 704-706, December 1974. [6] Burton, H.O. and Sullivan, D.D. \"Errors and error c o n t r o l , \" Proceedings of the IEEE, v o l . 60, no. 11, pp. 1293-1301, November 1972. [7] Clarke, R.H. \"A s t a t i s t i c a l theory of mobile-radio reception,\" B e l l System Technical Journal, v o l . 47, no. 6, pp. 957-1000, July-August 1968. [8] Conway, J.B. Functions of One Complex Variable, Springer-Verlag, New York, 1973. [9] Eaves, R.E. and Levesque, A.H. \"Probability of block error for very slow Rayleigh fading in Gaussian noise,\" IEEE Trans. on Commun., v o l . COM-25, no. 3, pp. 368-374, March 1977. [10] Gans, M.J. \"A power-spectral theory of propagation in the mobile-radio environment,\" IEEE Trans, on Vehicular Technology, v o l . VT-21, no. 1, pp. 27-38, February 1972. [11] Gladstone, K.J. and McGeehan, J.P. \"Computer simulation of multipath fading in the land mobile radio environment,\" IEE P r o c , v o l . 127, Pt. G, no. 6, pp. 323-330, December 1980. [12] Jakes, W.C. \"A comparison of s p e c i f i c space d i v e r s i t y techniques for reduction of fast fading in UHF mobile radio systems,\" IEEE Trans, on Vehicular Technology, v o l . VT-20, no. 4, pp. 81-92, November 1971. 1 03 [13] Knuth, D.E. The Art of Computer Programming, v o l . 1, Addison-Wesley, 1973. [14] Leung, C. \"Bit error rates of selection d i v e r s i t y systems in Rayleigh fading channels,\" Int. Conf. on Commun., Denver CO., June 1981. [15] Mi t r i n o v i c , D.S. Analytic Inequalities, Springer-Verlag, [16] Monro, D.M. \"Complex discrete fast Fourier transform,\" Applied S t a t i s t i c s , v o l . 24, pp. 153-160, 1975. [17] \"Real discrete fast Fourier transform,\" Applied S t a t i s t i c s , v o l . 25, pp. 166-172, 1976. [18] Papoulis, A. Probability, Random Variables, and Stochastic Processes, McGraw-Hill, New York, 1975. [19] Pearson, K., ed. Tables of the Incomplete Beta Function, Cambridge University Press, Cambridge, England, 1948. [20] Pierce, J.N. \"Theoretical d i v e r s i t y improvement in frequency-shift keying,\" Proceedings of the IRE, v o l . 46, no. 5, pp. 903-910, May 1958. [21] Roberts, J.A. and Healy, T.J. \"Packet radio performance over slow Rayleigh fading channels,\" IEEE Trans. on Commun., v o l . COM-28, no. 2, pp. 279-286, February 1980. [22] Reudink, D.O. \"Properties of mobile radio propagation above 400 MHz,\" IEEE Trans, on Vehicular Technology, v o l . VT-23, no. 4, pp. 143-159, November 1974. [23] Schwartz, M. et a l . Communication Systems and Techniques, McGraw-Hill, 1966. [24] Smith, J.I. \"A computer generated multipath fading simulation for mobile radio,\" IEEE Trans, on Vehicular Technology, v o l . VT-24, no. 3, pp. 39-40, August 1975. [25] Sundberg, C.E. \"Block error p r o b a b i l i t y for noncoherent FSK with d i v e r s i t y for very slow Rayleigh fading in Gaussian noise,\" IEEE Trans, on Commun., v o l . COM-29, no. 1, pp. 57-60, January 1981. [26] Sussman, S.M. \"Simplified relations for b i t and character error p r o b a b i l i t i e s for M-ary transmission over Rayleigh fading channels,\" IEEE Trans, on Commun. Tech., v o l . COM-12, no. 4, pp. 207-209, December 1964. 1 0 4 [27] Walpole, R.E. and Myers, R.H. Probability and S t a t i s t i c s for Engineers and S c i e n t i s t s , 2d ed., Macmillan, New York, 1978. [28] Whittaker, E.T. and Watson, G.N. A Course of Modern Analysis, 4th ed., Cambridge University Press, Cambridge, England, 1963. [29] Wozencraft, J.M. and Jacobs, I.M. P r i n c i p l e s of Communication Engineering, John Wiley, New York, 1965. 1 05 Appendix A This appendix d e t a i l s the computation of Pf(M,N) using numerical integration. F i r s t consider the c a l c u l a t i o n of . P f(0,N) = 1 - 7o _ 1 / [1 ~ p(7>] e d 7 J0 (A.1) = 7o- 1 / {1 - [1 - P(7)3 N) e d 7, where p ( 7 ) = (1/2) exp(- 7/2) for non-coherent FSK. Making the substitution y = 7 / 7 o in (A.1) gives P (0,N) = f (1 - [1 - p ( 7 o y ) ] N ) e _y dy. (A.2) Equation (A.2) i s the form of the integral that was used for numerical integration. Note that the range of integration in (A.2) i s i n f i n i t e , making the application of the usual quadrature rules d i f f i c u l t . However, the rapidly decreasing exponential in the integrand suggests that there i s l i t t l e contribution from the \" t a i l \" of the i n t e g r a l , and thi s i s indeed the case. Thus, given a maximum allowable error A, the strategy was to find a number b (depending on A, 7 o , and N) such that j (1 - [1 - p ( 7 o y ) ] N } e _y dy < A, 0 < j {1 - [1 - p ( 7 o y ) ] W } e _y dy < A, (A.3) b and then to compute P f(0,N) = f {1 - [1 - p ( 7 o y ) ] N } e~y dy. (A.4) •'o (We ignore for the moment the error involved in the numerical integration of the f i n i t e integral in (A.4).) The above 106 strategy may appear to be t r i v i a l , because the convergence of the integral (A.2) guarantees that lim / {1 - [1 - p(7 0y)] N} e\" y dy = 0, b -> co J h and so given any A > 0 there always exists a number b such that (1 - [1 - p(7oY)] N} e _ y dy < A. The point here is that the rapid decrease of the integrand ensures that b can be chosen s u f f i c i e n t l y small to make the numerical integration over the f i n i t e i n t e r v a l in (A.4) fe a s i b l e . Just as important i s the fact that there i s a simple procedure for finding b, as we now show. Observing that for fixed N and y0 the function 1 - [1 - p ( 7 0 y ) ] N i s a monotonically decreasing function of y, we have 0 < f {1 $ {1 = {1 Now, given any A > 0, i f we choose b such that {1 - [1 - p( 7ob)] N} e~ b < A, (A.6) then we know that (A.3) holds, and that the error in (A.4) i s less than A. Note that the l a s t l i n e of (A.5) i s just the integrand of (A.4) evaluated at y = b. Thus the formulation (A.4) i s convenient for use on a computer, because once we have coded the integrand for the numerical integration, we can use - [1 - p(7 0y)] N} e - y dy - [1 - p(7ob)] N} / \" \" e - y dy (A.5) •/ b \" [1 \" p(7ob)] N} e _ b . 1 07 th i s same code as part of a , simple search technique to determine a value of b that makes (A.6) true. The actual program used for the numerical integration was a double-precision version of SQUANK, which i s an adaptive quadrature routine based on Simpson's rule. This program was made available by the UBC Computing Centre. SQUANK i s easy to use, because i t adaptively t r i e s to meet an error tolerance supplied by the user. Thus i f the user s p e c i f i e s a maximum error A, SQUANK w i l l come back with an estimate of the integral within A of the true value (the program indicates i f i t cannot meet the error tolerance supplied by the user). Combining a l l the above gives us the following procedure: F i r s t a A > 0 is chosen, and then a value of b i s found such that (A.6) i s s a t i s f i e d . This same A i s then supplied to SQUANK as the maximum error tolerance for the integration of (A.4). If SQUANK i s able to meet the s p e c i f i e d error tolerance, we are then assured that P f(0,N) has been computed with a t o t a l error less than 2A. In the calculations performed for t h i s thesis, the value of A was 1.0X10\"9. Reference to Figure 2.3 shows that the smallest values of P f(0,N) that we have to deal with are on the order of 10\"\". Therefore, in those cases where SQUANK i s able to meet the s p e c i f i e d error tolerance, we are guaranteed that P f(0,N) has been computed c o r r e c t l y within at least two d i g i t s in the f i f t h decimal place. The d e t a i l s of computing Pf(M,N) using numerical integration when M > 0 are much the same as when M = 0, and are not described here. 1 08 Appendix B B.1 No d i v e r s i t y In Section 2.2 we defined the quantities Q(m,x;r) = r 2 r Bj^m+r, 1+x-m) and (B.1 ) Q(m,x;r) = ( x) r 2 r B(m+r,1+x-m), where the incomplete Beta function B y(a,b) i s given by B (a ,b) = / t 3 \" 1 (1 - t ) b _ 1 d t , (B.2) J 0 and B(a,b) = B,(a,b). The purpose of t h i s appendix i s to derive a bound on the difference between Q and Q . For the rest of t h i s appendix we assume that the parameters r, x, and m s a t i s f y the following conditions: (a) r i s r e a l , and 0 < r < 1. Since r = 2/yQ, the r e s t r i c t i o n 0 < r < 1 implies that 2 < y0 < *, . Thus th i s r e s t r i c t i o n s a c r i f i c e s very l i t t l e in a p r a c t i c a l sense, but i t makes the analysis simpler because there are fewer special cases to consider. (b) x i s r e a l , and x > 1. (c) m i s an integer, and 0 ^ m < x. Let e(m,x;r) = Q(m,x;r) - Q(m,x;r). Then using the d e f i n i t i o n s (B.1) and (B.2), we have 109 e(m,x;r) = ( x) r 2 r j t m + r _ 1 (1 - t ) x _ m dt > 0. (B.3) We consider the two cases m = 0 and m > 1 separately. The reason for breaking the problem into these two cases i s because the exponent of t m + r - 1 i s negative for m = 0 and i s positive for m £ 1. CASE 1: m = 0. For m = 0 equation (B.3) reduces to J u e(0,x;r) = r 2 r | t r - 1 (1 - t ) x dt. h Since r - 1 < 0, i t follows that t r _ 1 < ( l / 2 ) r _ 1 = 2 1 _ r for t C [1/2,1], i . e . for t in the range of integration. Then 0 < e(0,x;r) < r 2 r 2 1 _ r / (1 - t ) x dt I d t ) x (B.4) = 2 r / ( 1 - t ) x d t . Making the substitution u = 1 - t in the last i n t e g r a l , we get f (1 - t ) x dt = f u Jh Jo 1 X du = • (B-5) 2 1 + x (1+x) Substitution of (B.5) into (B.4) y i e l d s r 0 < e(0,x;r) < . ( B > 6 ) 2 X (1+x) 1 10 CASE 2: m £ 1. In t h i s case m+r-1 > 0, and so for t C [1/2,1] the inequality t < 1 holds. Then (B.3) becomes 0 < e(m,x;r) = ( x) r 2rJ1 t m + r ~ l (1 - t ) x _ m dt * t) r 2Tfhl (1 \" t)X_I u 3 0 \" m dt x r 2 r / x \" m du (B.7) r 2 r 01+x-m , > 2 (1+x-m) Summarizing i n e q u a l i t i e s (B.6) and (B.7), 0 < e (m, x ; r ) < r 2 X (1+x) m = 0 (B.8a) r 21 [Ij 9 l + x - m r ' m ^ 1 . (fl.Bb) s ' 2 (1+x-m) Of course, i t would be nice to have a single bound for the two cases m = 0 and m > 1. We can obtain such a bound by making the simple observation that the inequality 2 r < 2 holds for 0 < r < 1, and so i t follows from (B.8b) that 0 < e(m,x;r) < fX) (B.9) W 2x-m ( 1 + X _ m ) for m > 1. Note that (B.9) reduces to (B.8a) in the case m = 0. Thus inequality (B.9) holds for m > 0. The price we pay for the convenience of a single formula that holds for m > 0 i s that the bound for m > 1 i s worse. However, the bound in (B.9) is larger by at most a factor of 2, and as the examples in Section 111 2.2 demonstrate, the bound in (B.9) i s usually so small that a factor of 2 w i l l not influence our opinion of whether or not the difference between Q and Q i s n e g l i g i b l e . B.2 D i v e r s i t y We want to obtain a bound on the difference between p a > c and P, „, which are defined by equations (2.4.7) and (2.4.8) respectively. It i s easy to see that replacing the incomplete Beta function in (2.4.7) by the Beta function i s equivalent to extending the upper l i m i t of integration in (2.4.4) from 1/2 to 1. Thus we may write At P d , c ~ P d , c = i (B.10) = L r 2r Z ( A f tm+r~l (1 - t ) x _ m [1 - ( 2 t ) r ] L _ 1 dt, m=0 \\ / J % where r and x are as in Section B.1 above, and L > 1 i s an integer. For L = 1 the integral reduces to that of the non-d i v e r s i t y case, and we can apply the results of Section B.1. r L — 1 For the case L > 1, we can bound the [1 - (2t) ] factor of the integrand in such a way that the results of Section B.1 are s t i l l applicable. We sta r t by noting that the inequality (1 + y ) r < 1 + ry holds for -1 < y * 0 and 0 < r < 1 (see, for example, [15]). Taking y = 1, we have 2 r < 1 + r. Then i f 0 < r < 1 and 1/2 < t < 1, we have ( 2 t ) r < 2 r < 1 + r, and hence |1 - ( 2 t ) r | < r. It now follows that 1 1 2 tm+r-l { 1 _ t )x-m { ] ~ ( 2 t ) r ] L _ 1 dt < L r L 2 r C J k tm+r~l (1 - t ) x _ m dt L r J 2 x _ m (1+x-m) The l a s t inequality above follows from (B.9). Using the preceding result with (B.10) y i e l d s P d , c p d , c * = U) L r1 m=0 % ' 2 x _ m (1+x-m) (B. 1 1 ) 1 1 3 Appendix C The purpose of t h i s appendix i s to present the mathematical derivations of the results given in Section 2.3. We s h a l l without mention use the notation of the thesis proper, with the exception that we s h a l l replace the quantity r = 2/70 by the complex variable z throughout t h i s appendix. C.1 Existence of the expansions We begin by showing that Q(m,x;z) and Q(m,x;z), which are defined by Q(m,x;z) = z 2\" B^dn+z, 1 +x-m) and (C.1) Q(m,x;z) = z 2 Z B(m+z,1+x-m) , have series expansions CO Q(m,x;z) = Z q.(m,x) z i = 0 and (C.2) Q(m,x;z) = Z q.(m,x) z i = 0 that hold for |z| < 1 (the region of convergence may in a c t u a l i t y be larger, but t h i s does not concern us). In equations (C.1) we define 2 Z by 2 Z = exp{z log(2)}, where log(2) i s r e a l ; t h i s same d e f i n i t i o n w i l l be used i f 2 i s replaced by any real number. By the d e f i n i t i o n of the incomplete Beta function, we have 1 1 4 B (m+z, 1+x-m) = C tm+z~l (1 - t ) X _ m dt , (C.3) y J 0 where i t i s assumed that m i s an integer s a t i s f y i n g 0 ^ m < x, and that y i s a real number in the range 0 < y £ 1. The integral (C.3) converges for Re(z) > -m, and defines an analytic function of z there. Thus, since z 2 Z i s entire, i t follows immediately that Q(m,x;z) and Q(m,x;z) are analytic functions of z for Re(z) > -m, and so i f m > 1 these functions are analytic in the unit disk D = {z : |z| < 1}. Since the analytic functions are prec i s e l y those functions that have power series expansions, and vice versa, i t follows that (C.2) holds when m £ 1. When m = 0 the issue i s not so simple, because then Q(m,x;z) and Q(m,x;z) as given by (C.1) are defined and analytic only for Re(z) > 0, a region which obviously does not contain the unit disk. Thus we must look at the cases Q(0,x;z) = z 2 Z Bj s(z, 1+x) Q(0,x;z) = z 2 Z B(z, 1+x) in more d e t a i l . Although we do not prove i t here, i t can be shown that the following expression holds for Re(z) > 0: co y k B v(z,1+x) = y k L (*) (-1) k . (C.4) k=0 \\ k' z + k It can further be shown that the right-hand side of (C.4) defines a function that i s analytic for the entire complex plane, except for the points z = 0, -1, -2, ... Thus the r i g h t -1 1 5 hand side of (C.4) i s the unique analytic extension of the left-hand side. Using (C.4) i t i s easy to see that z 2 B y(z,1+x) has a removable s i n g u l a r i t y at z = 0; to be precise, we may write z 2 Z B y(z,1+x) = (2y) Z [ 1 + L (*j j , ( C. 5) where the right-hand side i s analytic for the entire complex plane, except for the points z = -1, -2, ... Taking y = 1/2 and y = 1, we can use the right-hand side of (C.5) to a n a l y t i c a l l y extend Q(0,x;z) and Q(0,x;z) to thi s same region, i . e . to a region containing D. Thus the expansions in (C.2) exist even for m = 0. C.2 Expressions for the c o e f f i c i e n t s in (2.3.15) We now derive expressions for the c o e f f i c i e n t s bi(m,x) in equation (2.3.15) [the derivation also proves the v a l i d i t y of this expansion]. For 0 ^ m < x, we have from equation (2.2.28) that rd+x) r(m+z) Q(m,x;z) = z 2 . (C.6) Td+x+z) r(1+m) If we omit m = 0 from the range considered, we can write z 2 Z Td+x) T(m+z) Q(m,x;z) = (C.7) m r(1+x+z) r(m) for 1 < m < x. For convenience, we l e t rd+x) r(m+z) f(m,x;z) = 2 (C.8) r(1+x+z) T(m) for 1 < m < x. In (C.8) the complex variable z i s viewed as the 1 16 main independent variable, whereas x and m are considered to be parameters that are held fixed during the discussion. Thus we often write simply f(z) for f(m,x;z), and any d i f f e r e n t i a t i o n that occurs i s understood to take place with respect to z. Comparison of (C.7) and (C.8) shows that Q(m,x;z) = (z/m) f(m,x;z) (C.9) for m £ 1; hence in order to find a representation of the form (2.3.15) we want to write f in the form f(m,x;z) = exp I bi(m,x) z 1 . (C.10) L i = 0 -I If we put m = 0 into (C.6), we find „ ro+x) r(z) rd+x) rd+z) Q(0,x;z) = z 2 = 2 rd+x+z) rd) rd+x+z) = f(1 ,x;z). (C.11) The l a s t equation shows that (2.3.16) holds. We now derive formulas for the c o e f f i c i e n t s bi(m,x) in (C.10). It i s understood that for the duration of the discussion x represents a real number s a t i s f y i n g x > 1 and m represents an integer s a t i s f y i n g 1 < m < x. Since T(m+z) i s analytic in the complex z-plane except at z = -m, -m-1, -m-2, and both 2 and l/r(l+x+z) are entire, f(z) i s analytic except at z = -m, -m-1, -m-2, ... In p a r t i c u l a r , f(z) is analytic in the unit disk D = {z : |z| < 1}, and- i t is th i s region to which we s h a l l r e s t r i c t our attention. Also, f(z) has no zeros in D ( i t s zeros are located at z = -x-1, -x-2, -x-3, . . . ) . We apply the following result (see Corollary 4.16, Ch. IV 1 1 7 of [8]): Let G be a simply connected region of the complex plane C, and l e t f:G —> C be an analytic function such that f(z) * 0 for any z in G. Then there i s an analytic function g:G -» C such that f(z) = exp(g(z)). If z 0 C G and exp(w 0) = f ( z 0 ) , we may choose g such that g (z 0) = w0. Since D i s simply connected, and f s a t i s f i e s the hypotheses of the above theorem, there exists a function g(z) = g(m,x;z), analytic in the unit disk, such that f(z) = exp(g(z)). (C.12) Let z 0 = w0 = 0. Then exp(w 0) = 1 = f ( z 0 ) , and we may choose g(z) such that g(0) = 0. Applying the chain rule to (C.12), we find f'(z) = exp(g(z)) g'(z) = f(z) g'(z) where, of course, the prime indicates d i f f e r e n t i a t i o n . Since f(z) has no zeros in D, we may write f'(z) g' (z) = . (C.13) f (z) Since g i s analytic in D, i t has a Taylor series 00 g(z) = Z bi(m,x) z 1 (C.14) i = 0 v a l i d for |z| < 1. The c o e f f i c i e n t s bi(m,x) are given by b1(m,x) = g ( i ) ( 0 ) / i ! = g ( 1>(m,x;0)/i! (C.15) where g ( i ) ( z ) i s the i - t h derivative of g with respect to z, with the special cases g ( 0 ) ( z ) = g(z) and g ( 1 ) ( z ) = g'(z). Since g(0) = 0 we immediately have that b0(m,x) = 0. To find (C.18) 1 18 the higher-order c o e f f i c i e n t s we substitute (C.8) into (C.13) to get r'(m+z) T'd+x+z) g'(z) = log 2 + - . (C.16) r(m+z) r(1+x+z) Using the Psi function, equation (C.16) may be written g'(z) = log 2 + \\p(m+z) - »//(1+X+Z). (C.17) By induction, we have, for i = 2, 3, 4, ... g ( i ) ( z ) = ^ ( i - l ) ( m + z ) - \\}>{±-1 1 (1+x+z) , and so from (C.15) we f i n d b,(m,x) = log 2 + \\p(m) - \\^(1+X) b±(m,x) = [^«i-l'(m) - t / / 1 1 \" 1 ' (1+x) ] / i ! . ( i > 2) These are the results stated in equation (2.3.17). C.3 The asymptotic expansion of the c o e f f i c i e n t s We show how the asymptotic expansions for the c o e f f i c i e n t s bj_(m,x) are derived. We look at two cases: i = 1 and i £ 2. CASE 1 : i = 1 . When i = 1 , we have from ( C . 1 9 ) that b,(m,x) = log 2 + i|/(m) - (1+x). (Our general approach i s to view the block size x as being so large that asymptotic expansions are c a l l e d for, whereas we view m as being s u f f i c i e n t l y small that i t is feasible to compute d i r e c t l y summations involving m terms.) We f i r s t write *( 1+x) = + 1/x (C.21 ) (this immediately follows from the recurrence formula Z'T(z) = T(1+Z) and the d e f i n i t i o n of >//). In [1] we find the following asymptotic expansion for i//(z): B 2 n \\Kz) ~ log(z) - 1/2z - Z n=1 2n z 2 n (C.22) = log(z) - 1/2z - 1/12z2 + 1/120Z« - 1/252Z6 + ... as z -» oo . Using the resu l t [1] |B 2 n | ~ 2(2n)!/(2») (C.23) which holds for large n, i t i s easy to see that the i n f i n i t e series in (C.22) does not converge; nevertheless, the notation is the standard notation for an asymptotic s e r i e s . Combining (C.21) and (C.22) y i e l d s 1 20 I//(1+X) ~ log(x) + 1/2X - Z — n n=l 2n x 2 n (C.24) = log(x) + 1/2X - 1/12X2 + 1/120x* - 1/252x6 + ... and f i n a l l y b,(m,x) = log 2 - C + Um-\\ - ^(1+x) (C.25) H. m _ x - [log(x/2) + C + 1/2x - 1/12X2 + 1/120X\" - ...] This is the resu l t given in (2.3.19). CASE 2: i > 2. We consider bidiwx) = [^/(i-l»(m) - tf(l+x)]/i! . From entry 6.4.3 of [1] we find )( m) = (-D^i-D! [$(i) - H^>] for m = 1, 2, 3, ... and i S 2. Note that the previous equation does not make any sense for i = 1, since $(1) does not e x i s t . We again find an asymptotic expansion for the term in x, sta r t i n g by repeatedly d i f f e r e n t i a t i n g (C.21) to get ) (1+x) = 0 ( i - l ' ( x ) + ( - 1 ) i + l ( i - D l / x 1 . Entry 6.4.11 of [1] gives the asymptotic expansion 121 ) ( z ) ~ }: r ( i - 2 ) ! ( i - 1 ) ! - B (2n+i-2)! n __ + + 2 _tl _ z 1 1 2 z 1 n=1 (2n)! z 2 n + i _ 1 as z oo . Combining the l a s t three equations gives b±(m,x) ~ ( - 1 ) l i - 1 | $(i) - H m i | -(C.26) 1 1 1 oo B 2 n (2n + i-2) ! -, x (i-Dx 1 1 2x x ( i - 1 ) ! n=1 (2n)! x 2 n + i - l J J This is the formula given in (2.3.20). C.4 Derivation of the recurrence formula We now prove that the recurrence formula (2.3.23) holds. Based on equations (2.3.22) and (C.10) we may write f(z) = Z a i z 1 = exp Z b i Z 1 i = 1 (C.27) i = 0 where the parameters m and x have not been indicated [see the note after (2.3.21)]. Since f(z) in analytic at least in the unit disk D, the leftmost power series in (C.27) converges for at least |z| < 1 (we have already seen that the other power series in (C.27) converges for at least t h i s same region). There are several ways to find formulas for the a± in terms of the known c o e f f i c i e n t s b i f the most obvious of which i s to use the series expansion of exp(0 to rearrange the right-hand side of (C.27) into ascending powers of z and then to equate c o e f f i c i e n t s . The disadvantage of t h i s method i s that i t rapidly becomes tedious. A better method begins by r e c a l l i n g that 1 22 f ' (2) = f(z) g' (z), (C.28) where g(z) has the series expansion given in equation (C.14). Since a power series may be d i f f e r e n t i a t e d term-by-term in i t s disk of convergence, the substitution of the series expansions for f(z) and g(z) into (C.28) y i e l d s L i a±z i = 1 i - 1 Z a^z i = 0 I i bi z L i = 1 i - 1 Multiplying both sides of (C.29) by z, we may write Z i a ^ 1 = Z c^1 i=1 i=1 (C.29) (C.30) where c ± i s given by the Cauchy product formula c. = Z k b, a. , 1 , , k i - k k= 1 i-1 Z (i-k) a kb._ k. k=0 k 1 k (C.31 ) Taking the Cauchy product i s allowed because a power series converges absolutely in i t s region of convergence. Equating c o e f f i c i e n t s in (C.30) and using (C.31), we obtain the following recurrence formula: a i = = i _ 1 . v b k a i - k - ( i * 1 ) k= 1 (C.32) To \" s t a r t \" the recurrence formula we need the value of a 0 , a value which can e a s i l y be obtained by putting z = 0 in (C.27) to find a 0 = 1. "@en ;
edm:hasType "Thesis/Dissertation"@en ;
edm:isShownAt "10.14288/1.0095826"@en ;
dcterms:language "eng"@en ;
ns0:degreeDiscipline "Electrical and Computer Engineering"@en ;
edm:provider "Vancouver : University of British Columbia Library"@en ;
dcterms:publisher "University of British Columbia"@en ;
dcterms: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."@en ;
ns0:scholarLevel "Graduate"@en ;
dcterms:title "The computation of the block-error rate on a Rayleigh-fading channel in the presence of additive white Gaussian noise"@en ;
dcterms:type "Text"@en ;
ns0:identifierURI "http://hdl.handle.net/2429/24089"@en .