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, U n i v e r s i t y 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 We accept this Engineering t h e s i s as conforming to the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA November © 1982 B r i a n Howard Maranda, 1982 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of requirements f o r an advanced degree at the the University o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make it f r e e l y a v a i l a b l e f o r reference and study. I further agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying o f t h i s f o r s c h o l a r l y purposes may department or by h i s or her be granted by the head o f representatives. understood t h a t copying or p u b l i c a t i o n of t h i s f o r f i n a n c i a l gain Electrical Engineering The U n i v e r s i t y of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date DE-6 (3/81) December 2, 1982 my It is thesis s h a l l not be allowed without my permission. Department of thesis written ii Abstract The problem of computing than M bit the p r o b a b i l i t y considered. In the formulas literature, but case for these numerical computation. special of white very P (M,N) f formulas slow have well the included error are diversity in this approximations in the suited for approximations M > 0. In this f approximation for is P (M,N) f given. when Also selection i s employed. analytical methods probability. this for the computation S i m u l a t i o n s are performed case. Furthermore, on of a no digital an e m p i r i c a l known the b l o c k - e r r o r computer formula i s d e r i v e d that can be used to estimate e a s i l y and a c c u r a t e l y the output of the s i m u l a t o r . The consequence i s a great s a v i n g of time effort in realistic fading. the f o r P (M,N) i s d e r i v e d , and a If very slow f a d i n g i s not assumed, there e x i s t for for i n the l i t e r a t u r e , but f an a c c u r a t e approximation is fading, derived not case P (0,N) have a l s o appeared bound on more noise Rayleigh been are S e v e r a l simple Gaussian a p p a r e n t l y no work has been done f o r the case thesis of f e r r o r s i n a block of N b i t s f o r a R a y l e i g h - f a d i n g channel i n the presence of a d d i t i v e analytical P (M,N) the computation and of a value of P (M,N) that i s more f than that p r o v i d e d under the assumption of very slow iii Table of Contents Abstract i i T a b l e of Contents i i i List of Tables v List of F i g u r e s List of Main Symbols vi vii Acknowledgement x 1. Introduction 1 2. Very Slow R a y l e i g h Fading 6 2. 1 7 Background 2.1.1 2.1.2 2.1.3 2.1.4 2.1.5 The AWGN channel The f a d i n g channel The computation of P (M,N): Series expressions The computation of P (M,N): Numerical i n t e g r a t i o n Approximate methods f o r the computation of P (0,N) 7 9 f 11 f 15 17 f 2.2 A new 2.2.1 2.2.2 2.2.3 2.2.4 2.3 Introduction Error analysis The approximation to P ( 0 , x ; r ) The approximation to P (M,x;r) 24 28 36 40 f f s e r i e s expansions 45 I n t r o d u c t i o n and n o t a t i o n E x t e n s i o n of formula (2.1.26) E x t e n s i o n of formula (2.1.24) Diversity 2.4.1 2.4.2 3. 24 f Infinite 2.3.1 2.3.2 2.3.3 2.4 approach to approximating P (M,N;r) 58 Introduction Approximations A model f o r c a l c u l a t i n g b l o c k - e r r o r on slow R a y l e i g h f a d i n g channels 45 50 53 58 60 rates 65 iv 3.1 The simulator 3.1.1 3.1.2 3.1.3 3.1.4 3.2 D e r i v a t i o n of the e m p i r i c a l formula 3.2.1 3.2.2 3.2.3 4. Implementation D e s c r i p t i o n of the a l g o r i t h m Generation of the f a d i n g sequence Simulation r e s u l t s Introduction The model Numerical r e s u l t s Conclusions 67 67 67 70 74 81 81 81 84 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 Diversity 111 Appendix C C. 1 C.2 C.3 C.4 E x i s t e n c e of the expansions E x p r e s s i o n s f o r the c o e f f i c i e n t s in (2.3.15) The asymptotic expansion of the c o e f f i c i e n t s D e r i v a t i o n of the recurrence formula 113 113 115 118 121 V L i s t of Tables I II Upper bounds f o r parameter v a l u e s x = 100, 7o = 20 dB (r = 0.02) Upper bounds f o r parameter v a l u e s x = 10, 7 0 III Asymptotic IV 34 Divisors = 5 dB (r = 0.6325) 34 forms of the c o e f f i c i e n t s 52 89 vi List of F i g u r e s 2.1 The AWGN channel 7 2.2 The f a d i n g channel 9 2.3 P (0,N) f o r d i f f e r e n t block 2.4 P (M,10) f o r M = 0, 1, 2, 3 2.5 Pf(0,l00) f sizes 18 19 £ and computed using (2.1.24) numerical i n t e g r a t i o n 22 2.6 The r e l a t i v e e r r o r i n the approximation 31 2.7 P (L,0,100) f o r L = 1, 2, 3, 4 62 3.1 Rayleigh cdf 73 3.2 Average fade time Tip) 75 3.3 Level-crossing 3.4 P (0,127) at d i f f e r e n t Doppler f r e q u e n c i e s 77 3.5 P (0,N) f o r d i f f e r e n t block 79 3.6 P (M,63) f o r M = 0, 1, 2, 3 at 15.5 Hz 80 3.7 Formula (3.2.1) as a f u n c t i o n of x f o r d i f f e r e n t average SNR's 7 86 d r a t e Hip) 75 S s i z e s at 15.5 Hz S 0 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 y at N = 255 and f = 10.5 Hz P l o t s of the curves that have been f i t t e d to the data i n Table IV 0 D 3.9 3.10 3.11 P (0,127) at d i f f e r e n t Doppler using the e m p i r i c a l formula s 93 94 frequencies P (0,N) f o r d i f f e r e n t block s i z e s at 15.5 Hz using the e m p i r i c a l formula 97 s 98 vii L i s t of Main Symbols Symbol Meaning Definition o t y p i c a l use a^nifX) c o e f f i c i e n t s i n expansion a(t) Rayleigh fading A mean square of a ( t ) = E [ a ( t ) ] A (2.3.21) 54 process 9 9 2 parameters ± i n curve f i t t i n g b (m,x) c o e f f i c i e n t s i n expansion B Bernoulli i 91 (2.3.15) 50 numbers 49 n C Euler's constant = 0.57721 20 <C the complex plane 25 d divisor 83 D u n i t disk erfc complementary e r r o r E(m,x;r) error E s energy per s i g n a l s ( t ) f D the Doppler frequency i n the complex plane function 8 term 29 7 i £y(±)(7} f(7) = F(A,,A ,A ;7o) 2 3 71 p r o b a b i l i t y d i s t r i b u t i o n function functional p a r t i a l sum of the harmonic n series H^ ' p a r t i a l sum of Riemann Zeta f u n c t i o n L ( i ) i n Chapter 2, the number of branches i n a d i v e r s i t y system ( i i ) i n Chapter 3, the fundamental block s i z e given by R/fjj 1 ... 10 r e l a t i o n s h i p between the d i v i s o r d and the average SNR 7 H 114 0 .... 91 20 ..... 49 58 82 m the number of e r r o r s i n a block 8 M the number of e r r o r s i n a block 8 n(t) white Gaussian n o i s e process 7 vi i i N number of b i t s per block (integer) 8 N /2 power s p e c t r a l d e n s i t y of n ( t ) 7 N(p) level-crossing r a t e at l e v e l p 71 p, p(7) bit-error probability on AWGN channel p bit-error probability on fading 0 f p (M,x) coefficients P(M,N;r) 1 - P (M,N;r) ± 0 P (M,N;r) f P (L,M,N) d P, (L,M,N) (M,N) (2.3.7) .. 10 48 24 p r o b a b i l i t y of more, than M e r r o r s i n a block of N b i t s on an AWGN channel 8 p r o b a b i l i t y of more than M e r r o r s i n a block of N b i t s on a very slow R a y l e i g h f a d i n g channel 11 same as the p r e v i o u s e n t r y , except L-branch s e l e c t i o n d i v e r s i t y i s used 58 1 - P(L,M,N) 59 d ,c P channel f P (M,N;7 ) b i n expansion .... 7 d p r o b a b i l i t y of more than M e r r o r s i n a block of N b i t s as determined by computer s i m u l a t i o n s 69 q (m,x) c o e f f i c i e n t s i n expansion 48 Q(m,x;r) p r o b a b i l i t y that there are e x a c t l y m e r r o r s i n a block of x b i t s 27 2/ 12 i r (r) (2.3.5) 7 o Pochhammer's symbol 41 b i t rate 72 m R s (t) transmitted signal 7 T signal duration 7 Tip) average fade d u r a t i o n below the l e v e l p .. 71 x a r e a l number that r e p r e s e n t s : (i) i n Chapter 2, the block s i z e i (ii) ( b i t time) i n Chapter 3, the sub-block s i z e v vehicle velocity B(a,b) Beta f u n c t i o n (mobile r a d i o ) 24 .... 81 71 26 ix B (a,b) incomplete Beta f u n c t i o n 7, 7 ( t ) signal-to-noise 7 average s i g n a l - t o - n o i s e y 0 26 ratio 7 r a t i o of the R a y l e i g h f a d i n g process 10 T Gamma f u n c t i o n 25 8^ Kronecker d e l t a e(m,x;r) e r r o r term 28 $ Riemann Zeta f u n c t i o n 49 X c a r r i e r wavelength 71 £ M/2(x-M) 33 p normalized amplitude of the envelope 71 \p Psi function 51 (=0 i f i * j ; =1 i f i = j ) ... 56 (mobile r a d i o ) Note: See page 28 f o r the s i g n i f i c a n c e of a c a r e t * x Acknowledgement I should suggesting direction also l i k e to thank my s u p e r v i s o r , Dr. C y r i l Leung, f o r the Research of this throughout my work. greatly financial topic appreciated. support Council of by the thesis, and His constant I gratefully Natural Science for providing availability was acknowledge the and Engineering means of a Postgraduate S c h o l a r s h i p , and a l s o under Grants A1052 and Al731. 1 Chapter 1 Introduction In a binary usually two d i g i t a l communication system, transmitted main i n blocks, techniques (ARQ). To f o r combatting evaluate is or packets, of N b i t s . There a r e e r r o r s : forward e r r o r c o r r e c t i o n request information the e f f e c t s of channel (FEC) and automatic repeat- the performance of an FEC scheme that employs an e r r o r - c o r r e c t i o n code capable of correcting or to fewer b i t errors per block, one wishes p r o b a b i l i t y P (M,N) of more than M b i t e r r o r s b know the i n a block, where 0 ^ M < N. In p r a c t i c e , we are concerned with the case The overall performance upon the d e t e c t i o n request for p r o b a b i l i t y of probability of of retransmission, an error, M << N. the ARQ systems, which are based of e r r o r s at the r e c e i v e r and block M depends P (0,N). undetected e r r o r the p r o b a b i l i t y of a d e t e c t e d e r r o r a subsequent primarily (For most i s very s m a l l ; on the codes the therefore, i s very c l o s e to the b l o c k - error p r o b a b i l i t y ) . For most b i n a r y Gaussian noise s i g n a l l i n g schemes on (AWGN) channel, an additive the p r o b a b i l i t y white P (M,N) i s b e a s i l y c a l c u l a b l e from the b i t - e r r o r p r o b a b i l i t y p: (1.1.1) N with the s p e c i a l case P (0,N) = 1 - (1 - p) . Thus f o r the AGWN b channel under s t e a d y - s i g n a l conditions, the p r o b a b i l i t y of b i t 2 error i s a u s e f u l f i g u r e of However, radio merit. transmission in an environment i n which there are m u l t i p l e changing propagation subject to random time v a r i a t i o n , or f a d i n g , of the s i g n a l s t r e n g t h at the receiver. Such multipath paths interference is occurs in many s i t u a t i o n s . Examples a r e : (i) long-distance reflection (ii) communication (used mainly in the HF trans-horizon (used at (iii) communication on ionospheric band). via tropospheric scatter UHF). mobile-radio there based transmission i n urban areas, where often i s no l i n e - o f - s i g h t path between the r e c e i v e r and transmitter — the r e c e i v e d s i g n a l i s due totally to the s c a t t e r i n g of the t r a n s m i t t e d s i g n a l from b u i l d i n g s (used at The UHF). e f f e c t of f a d i n g on d i g i t a l t r a n s m i s s i o n i s to cause a time v a r i a t i o n of the e r r o r p r o b a b i l i t y at the r e c e i v e r , in turn r e s u l t s i n a " c l u s t e r i n g " of e r r o r s . There are s e v e r a l techniques to which that are used, u s u a l l y i n c o n j u n c t i o n counteract interleave the clustering of with the adverse e f f e c t s of f a d i n g . One codewords errors in [ 6 ] . We an attempt to coding, method i s to break up the s h a l l not c o n s i d e r i n t e r l e a v i n g here. Another method to h e l p overcome the e f f e c t s of f a d i n g is 3 to use diversity transmission. transmission i s to send independent paths, or signals w i l l be subject suitably error combining the The same the deep behind message branches. to idea The hope fades, received on a number i s that and signals diversity hence not a l l that by the p r o b a b i l i t y of w i l l be reduced. Denote the average b i t - e r r o r case by p , and f similarly probability denote by in P (M,N) f the fading the fading c o u n t e r p a r t of P (M,N). The average b i t - e r r o r p r o b a b i l i t y i s no b longer a good f i g u r e of m e r i t , because the p r o b a b i l i t y is of not r e l a t e d to p f through the simple equation f fading in the presence of a d d i t i v e t h e o r e t i c a l basis variety of case conditions model expression f o r P (M,N) which i n the keying f special 1 (NCFSK) can i n turn of and a two c a s e s : an i n terms of i n t e g r a l s , non-coherent frequency-shift be expanded i n t o f i n i t e U n f o r t u n a t e l y , these s e r i e s a r e not computation, under very slow R a y l e i g h f a d i n g , can be w r i t t e n case Rayleigh can be found i n [ 7 ] , [23], and [29]. We s u b d i v i d e the problem i n t o the f o l l o w i n g ( 1 ) In the case of n o n s e l e c t i v e of thesis, white Gaussian n o i s e . The f o r the use of the R a y l e i g h fading f ( 1 . 1 . 1 ) . The q u e s t i o n of how t o compute P (M,N) thus a r i s e s . In t h i s t h i s problem i s c o n s i d e r e d f o r the s p e c i f i c P (M,N) convenient series [9], f o r numerical i n [9] the c a l c u l a t i o n of P (0,N) i s done by numerical i n t e g r a t i o n . f S e v e r a l approximations f o r P (0,N) 'That i s , f l a t a c r o s s the spectrum bandwidth. f have 4 been made i n the l i t e r a t u r e are d e r i v e d i n an ad manipulated and hoc [21,26], but these manner, ignored the terms are n e g l e c t e d u n t i l t a b l e s can be e a s i l y a p p l i e d . largely i.e. Also, the approximations expressions are results culled from case for M > 0 i n the l i t e r a t u r e . In t h i s t h e s i s a method of approximation that a l l o w s a simple treatment of the case is presented; is this new method yields a approximation to P (0,N) as w e l l . Furthermore, f better an approximation f i s given f o r P (M,N) i n the more d i f f i c u l t much M > 0 case of selection d i v e r s i t y [25], (2) If the requirement of very slow f a d i n g i s r e l a x e d the a n a l y t i c a l methods of (1) are no longer a p p l i c a b l e , and P (M,N) f must be computed by done performing simulations. f o r t h i s t h e s i s were performed were t a i l o r e d to the here mobile-radio simulations on a d i g i t a l computer, and environment. The emphasis i s on mobile r a d i o f o r the simple reasons that there i s a l a r g e amount of l i t e r a t u r e on mobile the statistical large properties of r a d i o and that some software has a l r e a d y been p u b l i s h e d in t h i s area [24], The main drawback of t h i s approach is amount of computer time r e q u i r e d and the consequent c o s t . To o b v i a t e the need f o r such formula is derived simulations, easy assumed. computation an the high empirical that a l l o w s an accurate p r e d i c t i o n of the s i m u l a t i o n r e s u l t s when M = 0; t h i s e m p i r i c a l the The formula permits of P (0,N) when very slow f a d i n g i s not f 5 The deal t h e s i s has with conclusions two cases (1) and short a future i n v e s t i g a t i o n . main c h a p t e r s , and (2) Chapters 2 and 3, which above. Chapter 4 p r e s e n t s discussion of possible topics the for 6 Chapter 2 Very Slow R a y l e i g h Fading In t h i s chapter we examine methods f o r the computation of P (M,N) f o r a channel s u b j e c t t o very slow R a y l e i g h fading f the presence of additive white Gaussian n o i s e . S e c t i o n 2.1 i n t r o d u c e s the b a s i c concepts and n o t a t i o n , and review of what has is largely date special 2.2 we the results of P (0,N). In f approximation to P (0,N), and extended error Section show how deal with the d e r i v e a new can be t o P (M,N) f o r M > 0. Moreover, an upper bound on the i n the approximation formulas a been done i n the l i t e r a t u r e . As we s h a l l see, almost a l l the r e s u l t s p u b l i s h e d to case in i s provided. In Section 2.3, the of S e c t i o n 2.2 are expanded i n t o i n f i n i t e s e r i e s (the approximations i n the l i t e r a t u r e expansions). Finally, in d e r i v e d f o r the computation i s employed. are Section essentially 2.4, first-order approximations of P (M,N) when s e l e c t i o n are diversity 7 2.1 Background 2.1.1 The AWGN channel We begin by transmission reviewing several useful of one of two e q u a l l y l i k e l y results for the s i g n a l s on the AWGN channel with s t e a d y - s i g n a l r e c e p t i o n . The AWGN channel can be represented by n(t) 4 Sj(t) Figure where n ( t ) i s white spectral density r-(t) 2.1: The AWGN channel, Gaussian N /2. Consider 0 noise with two-sided power two s i g n a l s s , ( t ) and s ( t ) 2 which are zero o u t s i d e the i n t e r v a l 0 £ t £ T and which s a t i s f y •T (t) (For the modulation s (t) i i s of probability receiver important this we 2 ( i = 1, 2) dt. schemes mentioned below, we may assume that form.) send Assume either that s ^ t ) or with equal s (t), 2 a priori and that the i s optimum. Then the p r o b a b i l i t i e s of e r r o r f o r some b i n a r y s i g n a l l i n g schemes are given by the f o l l o w i n g well-known e x p r e s s i o n s [23,29] a = 1/2, noncoherent FSK (NCFSK) p(y) = (1/2) exp(-d7) a = 1, d i f f e r e n t i a l PSK (DPSK) (2.1.1) 8 and a = 1/2, p(7> = erfc(Va^) (1/2) where 7 = E / N 0 Suppose that s now CFSK, and PSK is a = 1, the we coherent FSK (CFSK) signal-to-noise transmit modulations elements are independent, and power ratio (SNR). a block of N b i t s . For NCFSK, the e r r o r s f o r 2 (2.1.2) PSK hence different the signalling probability of m e r r o r s i n a block of N b i t s i s (2.1.3) where p = p ( 7 ) not apply f o r a s p e c i f i c SNR 7 . The result (2.1.3) to DPSK modulation, s i n c e the d i f f e r e n t i a l does encoding causes dependence between e r r o r s at the r e c e i v e r . However, those modulation techniques for f o r which (2.1.3) does apply, we can immediately w r i t e down the p r o b a b i l i t y that more than M b i t s i n a block are i n e r r o r : P (M,N) = b N Z (2.1.4) 2 If S i ( t ) i s zero o u t s i d e the range 0 ^ t ^ T i t must have i n f i n i t e bandwidth — a s i g n a l cannot be both t i m e - l i m i t e d and band-limited (see Appendix 5B of [29]). Intersymbol i n t e r f e r e n c e , which causes some dependence between s u c c e s s i v e bits, may i n p r a c t i c e be ignored on channels with s u f f i c i e n t l y l a r g e bandwidth. 9 The dependence of P (M,N) on the SNR 7 i s i m p l i c i t b (2.1.4); in dependence those clear instances we shall where write we wish i n equation to P (M,N;7). make this 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 P (M,N) a r e the b fe quantities of most interest, the probability r e t a i n s i t s s t a t u s as a fundamental u n i t f o r the of b i t e r r o r measure of system performance. 2.1.2 The f a d i n g channel Let Rayleigh us now consider f a d i n g i n the n o i s e . As d i s c u s s e d can be the case of n o n s e l e c t i v e , very presence of additive white Gaussian i n S e c t i o n 9.2 of [23], n o n s e l e c t i v e represented as a slow fading p u r e l y m u l t i p l i c a t i v e p r o c e s s . The s p e c i f i c model we use i s shown i n F i g u r e 2.2. a(t) n(t) > S:(t) Figure Here a(t) i s a density stationary Rayleigh channel. process with first-order function f.,,.(a) = and 2.2: The f a d i n g r:(t) (2a/A) exp(-a /A) 2 (a > 0) s ( t ) and n ( t ) a r e as b e f o r e . The instantaneous i random process which we d e f i n e by (2.1.5) SNR is a 10 (2.1.6) Then from equations (2.1.5) and (2.1.6) i t f o l l o w s N — exp(-N /AE ) AE 0 ZyiJ^ = o7 T ( t ) (7 * s that 0) S To - 1 = where 7 write 0 A = AE /N S simply f(7) Let us now slowly with considered we mean "slow of probability the to the on we shall i t may be r a t e that of each b i t ; t h i s i s what Under this for on of the the p ( 7 ) to be the p r o b a b i l i t y SNR 7 of b i t e r r o r under model considered f ( 7 ) given that fading m u l t i p l i e r . p ( 7 ) over bit the Thus consider particular assumption, p ( 7 ) of a b i t e r r o r on the AWGN channel. case we a so the average for varies just value distribution signalling fading". error average p r o b a b i l i t y particular From now f a d i n g process a ( t ) over the d u r a t i o n a b i t error conditioned then SNR. 0) is slow-fading particular average assume that the constant probability the * (7 0 for ^ y ^ f ) • respect by exp(~7/7 ), is 0 (2.1.7) results from To compute p , f fading of a the conditions, we s t r e n g t h s . For the here, the average i s taken over the a l l fading signal i n (2.1.7). Then 0 (2.1.8) 0 Note that equation (2.1.8) resembles a Laplace transform. To be 11 precise, p = 7 ~ f P ( 7 o " ) , where P i s the Laplace transform of 1 1 0 p ( 7 ) . For p(7) as i n (2.1.1), the i n t e g r a l evaluate a n a l y t i c a l l y ; bit more Pf = 2 Pf 1 + L 1 r ~ = 2 2.1.3 L f a = 1/2, come now l r \ \ • a = 1/2, a = 1, (2.1.9) PSK coherent FSK (CFSK) (2.1.10) to our main topic: the computation of the f conditions. Since bit errors are no d i s t r i b u t e d as i n ( 2 . 1 . 3 ) , P (M,N) i s not f (2.1.4). One to extend PSK of Pf(M,N): S e r i e s e x p r e s s i o n s the p r o b a b i l i t y of b i t e r r o r process FSK P (M,N) of more than M e r r o r s i n a block of N b i t s fading through noncoherent (NCFSK) a = 1, d i f f e r e n t i a l (DPSK) computation binomially to p , [23] 0 (1 + 1/a7 ) probability under is a 0 The We \ 1 1 - r e s u l t s are i a7 the is above so under fading approach to the computation analysis slow by that the SNR assuming longer connected conditions, of P (M,N) i s that f the fading 7 remains constant not only over a s i n g l e b i t , but a l s o over an e n t i r e block of N b i t s , that the s i g n a l - t o - n o i s e ratio a c c o r d i n g to the d i s t r i b u t i o n thesis we assumption to i t i s e a s i e s t j u s t to c o n s u l t a t a b l e of Laplace transforms. The 1 easy f o r p(7) as i n (2.1.2) the i n t e g r a l d i f f i c u l t , and 1 r (2.1.8) i s shall term such varies t(y) from of equation block to block (2.1.7). In t h i s f a d i n g "very slow". Although of very slow f a d i n g becomes l e s s and and less the realistic 12 as the block length becomes l a r g e r , we s h a l l see that based on t h i s assumption we can d e r i v e r e s u l t s that particularly i n Chapter p f useful, 3, where the assumption of very f a d i n g i s r e l a x e d . An expression to the expression are q u i t e f o r P (M,N) that slow i s analogous f (2.1.8) f o r the average b i t - e r r o r p r o b a b i l i t y can be w r i t t e n down: (2.1.11) 0 where P (M,N;7) i s the p r o b a b i l i t y of e r r o r under b conditions given i n equation (2.1.4). d i s p l a y s the dependence of P (M,N) on Equation the average f noise steady-signal (2.1.11) signal-to- r a t i o 7 . I f we were to f o l l o w the n o t a t i o n a l convention 0 established for P (M,N) = P (M,N;7), b b we should write P (M,N) = P (M,N;7 ) i n those cases where we d e s i r e to make the f f dependence 0 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 i n d i c a t e the dependence on y quantity f greater and r = 2/y 0t and to 0 f r i s i n the range small p o s i t i v e values 0 0 < r < 1, (2.1.4) does not apply of r . to DPSK modulation the t r i v i a l case N = 1), from now on we r e s t r i c t our to the >> 1, r s a t i s f i e s 0 < r << 1. Thus we a r e p r i m a r i l y concerned with Since through w r i t e P (M,N) = P (M,N;r). For 7 than 2 ( i . e . about 3 dB), for 7 0 (except i n attention NCFSK, CFSK, and PSK. S u b s t i t u t i o n of (2.1.4) i n t o (2.1.11) gives 13 P (M,N) = f Z (|f) f =M+ 1 \ / JQ p(7) [l " p(7)] m f(7> d N _ m 7 m \U m=0 ?o m Using m = us f i r s t P(7) [l 0 f o r [1 - p ( 7 ) ] k 0 f(7) d m - p(7)] m V(-1) ( U : ) 1 f Let / the binomial expansion P (M,N) = 1 - 7 o - 2 N (2.1.12) 7 0 ( )f 1 1 m (")m " 7o- Z 1 ~ P(7)3 p(7) fl m k=0 N N m 7 k 7 we o b t a i n m /*p(7) m + k exp(- /7o) d . 7 7 / J \ /\ m N exp(- /7o) d . N _ m (2.1.13) 0 look at the s i m p l e s t case, when M = 0 . We have N 7 o - .Z 2 _ ( - D ^ ) y * 1 P (0,N) = 1 f p(7) k k=0 exp(- /7o) d k 7 7 ° = 7 0 ' 1 Z ("D k=1 k + 1 fyj^ (2.1.14) p( ) 7 k cancelled p f f out. = P ( 0 , 1 ) given in For N = 1, we equations 7 7 where i n the l a s t step the k = 0 term (which been d , exp(- /7o) i s equal obtain (2.1.9) to 1) has the r e s u l t s f o r and (2.1.10). For N > 1, we must evaluate the i n t e g r a l 7o for - 1 / p ( 7 ) exp(-7/7 ) d7 J 0 (2.1.15) k 0 k > 1. U n f o r t u n a t e l y , because of the complex form f o r CFSK and PSK modulations, result for the integral NCFSK, p ( 7 ) has the simple easily be e v a l u a t e d : of p ( 7 ) there appears to be no a n a l y t i c a l when k > 1. However, i n the case of form (l/2)exp(-7/2) and ( 2 . 1 . 1 5 ) can 1 4 To - 1 y -'(W2) I K 0 (!/2) r = 2/y . where 0 exp[- (k/2 + 1 / 7 (!/2) k Substitution 0 7 o )] d 7 (2.1.16) k into (2.1.14) of the last e x p r e s s i o n appearing i n (2.1.16) y i e l d s P (0,N;r)=-r f This equation differences compute appears N L k=1 in both [21] i n n o t a t i o n ) . Equation P (0,N;r) for f small block lengths these main problem with using and [26] (with obvious (2.1.17) block d i f f i c u l t i e s begin to a r i s e as N i s large (2.1.17) k + r can be used to lengths, but numerical increased, and for very d i f f i c u l t i e s are s u b s t a n t i a l . The the alternating series. (2.1.17) to compute P (0,N;r) f o r l a r g e N i s the severe l o s s of s i g n i f i c a n t f figures caused the terms may N = 100 and formulas by c a n c e l l a t i o n between terms. Note a l s o become very l a r g e y = 100 = 20 which are 0 P (0,100;0.02) f dB i n magnitude. For example', take (then derived = 8.57X10" . 2 that r = 2/7 in However, 0 Section the = 0.02). Using 2.2, we find magnitude of the k = 50 term i n (2.1.17) i s about 3 . 5 8 X 1 0 . Then f o r the sum to 10 yield 8.57X10" , 2 it c a n c e l l a t i o n between evaluate (2.1.17) on is obvious terms must that take an enormous amount of place, and hence to a computer t o even one or two d i g i t s of accuracy r e q u i r e s m u l t i p l e - p r e c i s i o n a r i t h m e t i c . T e s t s were run on the Amdahl 470 computer here at UBC t o f i n d the v a l u e s of N 15 for which the direct practical. The c a l c u l a t i o n s , were precision of N evaluation arithmetic, was steadily P (0,N;0.02) and y of the s e r i e s (2.1.17) i s performed using double- was taken to be 20 dB. The value 0 increased and the computed values were compared with the c o r r e c t v a l u e s , which were f computed using the methods of S e c t i o n 2.2. For small values N, (2.1.17) gave e x c e l l e n t r e s u l t s , but the accuracy deteriorated as significant N increased, figures were and for obtained. N = 80 was useless only the sometimes n e g a t i v e ) . I f we now c o n s i d e r (2.1.13) leads to P (M,N) M E d/2) m= = 1 - r (") /\ m =0 N-m Z / \ V computed value 0 < M < N, then, / k + m + r k via was for (-1/2) (V) k=0 Y7 two For N > 90, the e f f e c t of ( f o r example, NCFSK, equation of steadily c a n c e l l a t i o n was so dominant that the value of Pf computed (2.1.17) of (2.1 .18) k ™ /xA M = P (0,N) - r f The numerical 2 d/2) m=1 m AT \ (-1/2) ( J L ( 7™ J \ / k=0 \ / k + m + r m . k runs as b e f o r e . The computation of Pf(M,N): Numerical i n t e g r a t i o n One way summations integrating for _ e v a l u a t i o n of (2.1.18) on a computer c l e a r l y i n t o the same d i f f i c u l t i e s 2.1.4 m N to above avoid is the to difficulties compute in P (M,N) f (2.1.12). (In the case of CFSK or which the i n t e g r a l s cannot be evaluated evaluating the by numerically PSK modulation, analytically, this 16 approach must be taken.) T h i s procedure for N = 1, 10, 2 3 d e r i v e d there [see equations 2 the only thesis, we shall n a t u r a l l y we shall approximations integration. numerical our 3 with 3 considered. be to the In later However, compare exact there performed The main reason given are the we d e r i v e . The r e s u l t s i n figures, but only f o r 7 0 [21] are numerical why the insufficient for integration i s simplest case M = 0, given to approximations 4 significant i n steps of 10 dB. For these reasons, (2.1.12) was n u m e r i c a l l y i n t e g r a t e d on the Amdahl [ r e c a l l that f o r N = 1 there are the 1, 2, 3; and 7 0 470 N = 10, 10 , 10 , 10" exact 2 results 3 (2.1.9)]; ranging from 0 to 50 dB i n steps of 1 dB. The r e s u l t s f o r M = 0 and y 0 3 by these i n the form of graphs that are not a more s u i t a b l e range of parameters: M = 0, of reasons a c c u r a t e enough f o r adequate comparison with the for this f results several of we are i n t e r e s t e d i n the case M > 0 as w e l l . A l s o , the r e s u l t s i n [9] are presented equation (2.1.26)]; to P (M,N), and i s that numerical i n [9] and [21] only f o r f sections the results are P (0,N) 10", and the case M = 0 i s d e r i v i n g approximations want to (2.1.24) and r e s u l t s given i n [9] and [21] purposes. whereas one i n t e g r a t i o n of (2.1.12) approximations the v a l u e s of N are 1, 10, 10 , 10 , still [9] s i s a l s o done i n [21] as a check on are in 10 , 10 , 10", 10 , although only the s p e c i a l case M = 0 i s c o n s i d e r e d . The numerical that i s c a r r i e d out = 0, 10, 20, 30, 40, 50 dB The r e s u l t s of the numerical i n t e g r a t i o n are exact i n the sense that a specified number of s i g n i f i c a n t figures can be guaranteed i n the computation of P (M,N). See Appendix A. f 17 were compared with those given i n [21], and were found t o agree to 4 s i g n i f i c a n t P f = 5.814X10 figures at _1 i n a l l but one case ( i n [21] they g i v e N = 100 and 7 = 10 0 dB, whereas c a l c u l a t e d Pf = 5 . 8 0 6 x l 0 ~ ) . Some of the numerical r e s u l t s 1 graphed in f o r high SNR's, suggests t h a t on M, N, and r simple manner. The d e t a i l s of described 2.1.5 i n Appendix Approximate Another approximate problems the dependence can be c h a r a c t e r i z e d the numerical of in a fairly integration are A. methods f o r the computation approach to the the sum (2.1.18) in of P (0,N) f calculation such a of way P (M,N) i s t o f that numerical are avoided. I t appears that approximations have been made i n the l i t e r a t u r e only (2.1.17) (2.1.18). instead (2.1.17) i s d e r i v e d in are F i g u r e s 2.3 and 2.4. The r e g u l a r i t y of the c u r v e s , particularly Pf(M,N;r) we [21] i n approximation almost of f o r the A case simple M = 0, i.e. approximation i n [26]; t h i s approximation is for to re-derived p r e c i s e l y the same way. The b a s i s f o r the i s t o note that for7 0 >> 1 we have r << 1, and so (2.1.19) k We now use the i d e n t i t y 18 o 0.0 10.0 20.0 30.0 40.0 50.0 Average s i g n a l - t o - n o i s e r a t i o r F i g u r e 2.3: P (0,N) for d i f f e r e n t f 0 0 in block 60.0 dB. sizes. 0.0 10.0 20.0 30.0 Average s i g n a l - t o - n o i s e F i g u r e 2.4: ratio P (M,lO) f o r M = 0 f 20 Z (l) k=1 W where H A = (y " D A = k Z y /k - H k=1 , k N (2.1.20) N Z k~ (see e x e r c i s e 13 of [13], S e c t i o n 1.2.7). k=1 S u b s t i t u t i o n of (2.1.20) i n t o (2.1.19) with y = 1/2 g i v e s N 1 r P (0,N;r) = r H f k N N L i r 2 - Z (l/k2 ) = — k=1 J L 7 o The quantity in brackets in k N H N i - I (l/k2 ) . k=1 J (2.1.21) (2.1.21) is well suited for numerical computation, even when N i s l a r g e . However, f o r l a r g e N the amount of computation r e q u i r e d to sufficiently large would be convenient summations From in that a computer i s s t i l l i f we c o u l d (2.1.21); find + 1/120N" with an e r r o r l e s s than 1/252N . The logarithm 6 have no need to (logarithm use common denote the n a t u r a l l o g a r i t h m . constant, avoid the expansion ~ l o g N + C + 1/2N - 1/12N the n a t u r a l l o g a r i t h m is r e q u i r e d . Thus i t some method to 2 N (2.1.21) f o r t u n a t e l y i t i s not hard to do so. [13] we have the asymptotic H evaluate (2.1.22) in (2.1.22) to the base e ) . Since logarithms, The letter we is shall l o g ( ' ) w i l l always C denotes Euler's which i s d e f i n e d by and which N Z (l/k2 ) k=1 increases, k has in and C = l i m {H - l o g N} a numerical value (2.1.21) for converges N £ 10 (2.1.23) C = 0.57721. The extremely summation rapidly as N i s w e l l approximated by i t s l i m i t 21 I 0 / k 2 ) = l o g 2 ( f o r N = 10 k=1 the K approximation error i s about 0.012%, relative and error in this f o r N = 15 the r e l a t i v e i s about 0.00026%). We then have P (0,N;r) = r [log(N/2) + C + 1/2N - 1/12N + 2 f 1/120N ]. 4 (2.1.24) Approximations This s i m i l a r t o (2.1.24) are given i n [21] and [ 2 6 ] . approximation i s good f o r a f a i r l y wide range of block s i z e s N and s i g n a l - t o - n o i s e r a t i o s 7 . For 0 approximation grows a r b i t r a r i l y good as y shown by graphed fixed —=>• °° 0 approximation a the . However, the i s poor f o r small signal-to-n.oise r a t i o s , as i s Figure 2.5, where the approximation f o r N = 100, along with the numerical i n t e g r a t i o n . I f we now h o l d y behavior of (2.1.24) as N -> » results (2.1.24) is obtained by f i x e d and c o n s i d e r the 0 , we see that the approximation breaks down: the r i g h t - h a n d s i d e of (2.1.24) goes t o although N, P (0,N;r) i s of f infinity, course l e s s than u n i t y . A s l i g h t l y d i f f e r e n t approximation that behaves b e t t e r f o r l a r g e N i s a l s o d e r i v e d i n [ 2 1 ] . Although we do here, the authors use approximation t o w r i t e P (0,N;r) = 1 - exp f Note what r N go through they call M (-1/2) i ' - r k=1 L ^ yJ k a the step details function k (2.1.25) k that the argument of the e x p o n e n t i a l f u n c t i o n i n (2.1.25) i s j u s t the l a s t argument of the expression (2.1.19). in (2.1.19). In fact, i f the e x p o n e n t i a l i n (2.1.25) i s s m a l l , t a k i n g the f i r s t - o r d e r term i n the s e r i e s yields not Using the expansion asymptotic of the e x p o n e n t i a l approximations just 22 10.0 0.0 Average Figure 20.0 30.0 40.0 signal-to-noise ratio 50.0 r 2.5: P ( 0 , l 0 0 ) computed u s i n g numerical i n t e g r a t i o n . f 0 60.0 i n dB. (2.1.24) and 23 developed, we may write' P (0,N;r) = 1 - exp{-r f [log(N/2) + C + 1/2N - 1/12N + 2 ...]} (2.1.26) As shown by numerical examples i n [21], approximation is better and (2.1.24) f a i l s . 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 l a r g e Let us now which way that P (0,N). f the consider the more d i f f i c u l t apparently From (2.1.18) we a has summation case M > 0, a not yet been t a c k l e d i n the we can employ in the the reduces equation to of approximating (2.1.18). It i s however, to work d i r e c t l y with the summation, and i t turns out that r e s u l t s can more e a s i l y be d e r i v e d using a different such results already derived for for M > 0 second case literature. see that the problem can be broken up i n Thus the problem difficult, (2.1.26) method, which we c o n s i d e r much i n the next s e c t i o n . As a by-product of our i n v e s t i g a t i o n of the case M > 0 we shall find a b e t t e r approximation f o r the case M = 0 as w e l l . Furthermore, whereas there above i s no a n a l y t i c a l estimate of approximations, we shall be able the error to obtain bounds on the e r r o r i n the approximations d e r i v e d i n sect i o n . in the explicit the next 24 2.2 A new 2.2.1 approach to approximating P (M,N;r) f Introduction We shall find i t most convenient 1 - P (M,N;r) = the p r o b a b i l i t y that f errors to work with P(M,N;r) = there i n a block of N b i t s . From equation are M or fewer (2.1.12) i t f o l l o w s that / N \ /*°° m N-m () / p ( ) [1 " P(7>] \ /Jo M P(M,N;r) = T O " T h i s equation reasons I m=0 1 holds 7 f o r NCFSK, CFSK, and = (1/2) generalization of P(M,x;r) = 7o" Z 1 exp(~7/2). (2.2.1), r e a l number x £ (*) / m but PSK d . 7 (2.2.1) modulations. For not be c l e a r why in Chapter sub-blocks, Furthermore, we consider a in which the block l e n g t h N may be 1: m=0\ /7 It may -7/TO e s t a t e d i n the p r e v i o u s s e c t i o n we c o n s i d e r only NCFSK, for which p(7) any m 3, P(7> [1 ~ P(7>] e d . 7 (2.2.2) 0 we c o n s i d e r non-integer where we block s i z e s d i v i d e the o r i g i n a l block the block s i z e as an a r b i t r a r y r e a l number. A l s o , i t t u r n s out that analysis i n v o l v e d than block s i z e s The for the i t would be extension extended i f we case is to think into of the i t w i l l be a n a t u r a l x, only s l i g h t l y more r e s t r i c t e d o u r s e l v e s to i n t e g e r N. binomial coefficient d e f i n e d f o r r e a l x by in equation (2.2.2) is 25 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 f u n c t i o n . The Gamma f u n c t i o n occurs so f r e q u e n t l y summarizing some i n what of follows i t s properties function i s often defined that i t i s worthwhile here [28]. The Gamma f o r complex z i n the r i g h t h a l f plane by the i n t e g r a l oo T(z) = / t z _ 1 exp(-t) d t , Re(z) > 0 (2.2.4) and l o g ( t ) i s r e a l . I t can be Jo where t shown z _ 1 = exp{(z-1)log(t)} that r ( z ) as d e f i n e d by the i n t e g r a l (2.2.4) i s a n a l y t i c for Re(z) > 0, and that i t can be a n a l y t i c a l l y continued whole complex plane <E, except f o r the n o n - p o s i t i v e -1, -2, where i t has simple p o l e s . Another t o the integers 0, representation f o r the Gamma f u n c t i o n i s oo l / r ( z ) = z exp(Cz) TT (1 z/n) exp(-z/n) , + (2.2.5) n=1 where C converges i s Euler's constant. f o r a l l complex (whence i t f o l l o w s that r ( z ) z The infinite product above and d e f i n e s an e n t i r e f u n c t i o n has no zeros). The recurrence relation z-T(z) = T(1+z) holds f o r z * 0, -1, -2, (2.2.6) and using the f a c t that r(1) = 1, we f i n d that r(1+n) = n! f o r non-negative i n t e g e r s n. 26 Making integral the s u b s t i t u t i o n t = p(-y) = (1/2) exp(~7/2) i n the (2.2.2), we get P(M,x;r) = where r = 2/7 (2.2.7) as 0 b e f o r e . Equation (2.2.7) can be w r i t t e n i n the form P(M,x;r) = r 2 r /\ ( ) B (m+r,1+x-m), \ / * (2.2.8) x t m y where B ( a , b ) = j t y function. M Z m=0 r a _ 1 (1 - t ) b _ dt i s the 1 incomplete I f we take y = 1 i n the d e f i n i t i o n of the incomplete Beta f u n c t i o n , the result B(a,b) = B,(a,b). From computation i s the (complete) equation (2.2.8) we Beta see [19], but the parameter insufficient the tabulated f o r our purposes. For example, c o n s i d e r r B.(r,1+x). (2.2.9) the t a b l e s [19], the s m a l l e s t value l i s t e d a, b that ranges presented i n these t a b l e s are P(0,x;r) = r 2 In function of P(M,x;r) can be b o i l e d down t o the e v a l u a t i o n of the incomplete Beta f u n c t i o n . T h i s f u n c t i o n has been in Beta of B ( a , b ) i s 0.5. But f o r y y > 4 = 6 dB we have r < 0.5, and so these t a b l e s cannot interest. We t r y s u b s t i t u t i n g the b i n o m i a l expansion of the f a c t o r (1 - t ) to (2.1.18), evaluating expression might and into xm be 0 f o r the arguments in the range of most (2.2.7), but t h i s j u s t leads us back i t was (2.1.18) used that the difficulties l e d us to seek in numerically an alternative i n the f i r s t p l a c e . There are some other problems with the e x p r e s s i o n s above. 27 Since P(0,x;r) —> 1 as 7 —> 0 [this is intuitively 00 obvious from the p h y s i c a l meaning of P ( 0 , x ; r ) ] , i t f o l l o w s from that r 2 B (r,1+x) -» r 1 as r —> 0, x B (r,1+x) —>• <x> as x r —> and + 0. This + means so there c o u l d be problems f o r l a r g e s i g n a l - t o - n o i s e r a t i o s . (2.2.9) Consider that numerical also the block-error probability P.(0,x;r) = 1 - r 2 r r When 7o >> right-hand -i> 1 and s i d e of r 2 the r B^rjl+x) (2.2.10) i s equal q u a n t i t i e s . The From foregoing point case expression M = 0), c l o s e to u n i t y , subtraction discussion but i t may see excellent that (2.2.8). For in [21] then (2.2.8) observation to make, and, the for the example, We first (2.1.18) can to an serve as the foundation P (M,x;r). The most i n f a c t , the o b s e r v a t i o n to in (2.2.8) can introduce i t follows only (2.1.24). But some new that follow, is be r e p l a c e d notation, of we for important forms that by the the Beta parameter 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 e x a c t l y m b i t e r r o r s in a block bits; the equation (the authors c o n s i d e r f u n c t i o n with n e g l i g i b l e e r r o r over a wide range values. figures. (2.1.17) i s used as the s t a r t i n g approximations incomplete Beta f u n c t i o n nearly f approximations basis two appear that f o r d e r i v i n g an approximation s i m i l a r to shall of the f o r approximating P (M,x;r) than s i m i l a r to (2.2.10) i s given the a i s very r e s u l t i s a l o s s of s i g n i f i c a n t i s a better s t a r t i n g point alternative (2.2.10) B,(r,1+x). of x that (2.2.11) 28 We a l s o introduce the q u a n t i t y 5(m ,x;r) = (^j r 2 The definition r B(m+r,1+x-m). i n (2.2.12) introduces to which we w i l l adhere f o r the r e s t with a c a r e t quantity indicates A that has an been (2.2.12) a notational convention of t h i s t h e s i s : a quantity approximation to the original obtained by r e p l a c i n g the incomplete Beta f u n c t i o n by the Beta f u n c t i o n . Then (2.2.8) becomes P(M,x;r) = and, using M L Q(m,x;r), m=0 (2.2.13) the n o t a t i o n a l convention d e s c r i b e d above, M P(M,x;r) = I Q(m,x;r). m=0 (2.2.14) At We s h a l l use advantages P to approximate (and disadvantages) the e r r o r i n c u r r e d 2.2.2 E r r o r P . Before we consider of doing so, we f i r s t the examine i n making t h i s approximation. analysis If we write Q(m,x;r) = Q (m, x; r ) - e(m,x;r) then i t f o l l o w s from equation (2.2.15) (B.9) of Appendix B that e(m,x;r) satisf ies 0 < e(m,x;r) < (*) . V / 2 ~ x The upper bound Appendix B f o r a l l in (2.2.16) the m (2.2.16) (1+x-m) holds only when 0 < r < 1 (see restrictions under which the above 29 result holds). We approximating Q we think of e(m,x;r) as the e r r o r i n c u r r e d by with Q. S u b s t i t u t i n g (2.2.15) i n t o (2.2.13), find M P(M,x;r) = M E m=0 Q(m,x;r) - E e (m, x; r ) m=0 (2.2.17) = P(M,x;r) - E(M,x;r), where from (2.2.16) i t f o l l o w s A 0 < E(M,x;r) = M E e(m,x;r) m=0 h— M <- 5 ( 2 . 2 . 1 8 ) ' (1+x-m) m=0 W 2 " represents the e r r o r that r e s u l t s when we r e p l a c e the x E(M,x;r) that m r incomplete Beta f u n c t i o n i n (2.2.8) when we approximate We upon now P examine by examples in order the upper bound i n (2.2.18) depends and to then get numbers i n v o l v e d . As u s u a l , i.e. P . how i t s parameters, by the Beta f u n c t i o n , look an we idea first at several numerical of the magnitude of the 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 ( l + x ) . The e r r o r bound x r 1 (2.2.19) 2 X (1+x) goes to zero e x p o n e n t i a l l y 2 X _ 1 (l+x) 7 o with i n c r e a s i n g block s i z e x, and so the e r r o r i n the approximation r a p i d l y becomes n e g l i g i b l e as x 30 increases. average Also, the error signal-to-noise ratio approximation decreases as y refer here to the bound varies y and 0l increases. 0 i s the r e l a t i v e to P , the q u a n t i t y equation (2.1.23) we that f 0 little e f f e c t on error bound reader may the the see i n v e r s e l y with 7 . inversely on the may 7, 0 However, that quite a tests is (i) The and the though P f [see As 7 bound this and has and the orders of magnitude. conclusion, a bounding functional The because but on technique dependence in Figure drawn 2.6, the above does on 7. 0 hold. An i n which both the r e l a t i v e error bound (2.2.19), P ( 0 , x ; r ) , have been graphed f o r x = 10. dB also f error on the a c t u a l e r r o r E ( 0 , x ; r ) , conclusion also There are to be made. upper bound on 0 0 several the e r r o r e r r o r , although i t does not (ii) wish to compute. From while l e a v i n g x f i x e d different f several points case, of Appendix B might y i e l d a t i g h t e r bound the given by this changing 7 e r r o r E ( 0 , x ; r ) / P ( 0 , x ; r ) and divided we have shown that the e r r o r bound in (2.2.19) i s t i g h t , and example we in f by i s based not on E(0,x;r) with Note, however, that r e l a t i v e e r r o r , even change from in Since both P upper bound given i n (2.2.19), different error to a f i r s t approximation P question the v a l i d i t y of analysis the r e l a t i v e error — the e r r o r depend so the a b s o l u t e e r r o r , whereas a more meaningful i n d i c a t o r of the e r r o r varies i n v e r s e l y with the remark f o l l o w i n g increases the i s q u i t e c l o s e to the hold for 7 o actual l e s s than about 3 (2.2.16)]. r e l a t i v e error rapidly approaches a 31 F i g u r e 2.6: The relative error i n the approximation. 32 constant, and constant. for y changes f by the same range of SNR 7o < that (2.1.21) holds only f o r the the dB. i n graphs From in 10 or 15 dB used reader straight-line F i g u r e 2.3, i . e . for y (depending on the block with y , f y, does 0 not should bear in mind that although w i l l have the general 0 a l l block sizes,.the exponential x so t o t a l l y dominates the behavior sizes greater than 10 r e g a r d l e s s of the value of y , block i n c r e a s e d e r r o r for y 0 restrict we see 0 g r e a t e r than 0 s i z e ) . Thus the hold that was constant for small or sizes shape of F i g u r e dependence of (2.2.19) on for so the e r r o r i s n e g l i g i b l e It is (x l e s s than about 10) that the the average SNR above. 15 dB becomes and i f we dB, the than 1% r e l a t i v e e r r o r ) for x as small as 4 q u i t e small or 5. expect the e r r o r to be SNR important, to be g r e a t e r than about e r r o r i n the approximation i s s t i l l i s when both the block s i z e and 2.6 of the e r r o r term that l e s s than 10 or parameter range f o r which we the e r r o r , viewed i . e . f o r 0 dB and 0 small y, portions a dependence 0 of SNR. as a f u n c t i o n of y , for values the example in F i g u r e 2.5 with respect to the SNR only contrast to p r e d i c t a r e l a t i v e e r r o r that i s almost values of the almost values, i n v e r s e dependence of P block shows that i n r e l a t i v e e r r o r i s g r e a t e s t f o r small about for be c o n s i d e r e d s e v e r a l orders of magnitude over say of The dB may Reference to F i g u r e 2.3 P (0,l0;r) ( i i i ) The > 10 0 are small. The 10 (less only appreciable 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 the error term upper bound although to compute than i t i s f o r M = 0. However, E i s u s u a l l y so small in (2.2.18) weaker than with a that we may much simpler r e p l a c e the bound (2.2.18), i s more than s u f f i c i e n t that, f o r our purposes. In a d d i t i o n to the r e s t r i c t i o n s on r , x, and m in Appendix B, we assume that M 0 ^ m < M < x. I t can then be shown i s an i n t e g e r using given satisfying definition (2.2.3) that M-m M x-M We a l s o have that 1/d+x-m) < 1/(1+X-M), and so (A z m-0\7 2"" Y7 (1+x-m) m where we have put i- = M / 2 ( x - M ) . the sum of a ' (A < 1 2 " X £ < 1+x-M> M m-0 Using the well-known r e s u l t f o r geometric s e r i e s , we conclude, on the b a s i s of (2.2.18) and the above i n e q u a l i t y , that 0 < E(M,x;r) < If £ = 1 Note that the if) quantity r1-S 2 x-M ( 1 + X _ ) M i n brackets i n the important case M + 1 ^ (2.2.20) L should M = 0 the be r e p l a c e d upper by bounds M+1. in (2.2.18) and (2.2.20) are i d e n t i c a l . We now look below, the values are given at some numerical examples. In the t a b l e s of the upper bounds i n (2.2.18) and f o r two d i f f e r e n t block (2.2.20) s i z e s and average s i g n a l - t o - 34 n o i s e r a t i o s , and f o r M = 0, 1,2, Table I, x = 100 and y 3. The parameters chosen f o r = 20 dB, represent 0 typical values of the block s i z e and average SNR. The parameters chosen f o r Table II, x = 10 and 7 the e r r o r 0 = 5 dB, f a l l i n the approximation i n t o the region where we t o s t a r t t o become large. expect Also p r o v i d e d are the values of P ( M , x ; r ) , which were computed using f numerical integration as d e s c r i b e d i n Appendix A. The numbers in the t a b l e s are rounded o f f to the number of decimal places presented. Bound i n (2.2.18) M 0 1 2 3 1.562x10" 3. 171x10" 3. 1 8 7 X 1 0 " 14X10" f 1.562X103.171x10" 3. 188X10" 2. 115x10- 8.567X10" 34 3a 2.1 P (M,x;r) Bound i n (2.2.20) 6.738x10- 3 2 32 3 0 2 8 5.805X10" 30 5.177X10" 28 2 2 2 2 Table I : Upper bounds f o r parameter v a l u e s x = 100, TO = 20 dB (r = 0.02). M 0 1 2 3 P (M,x;r) Bound i n (2.2.20) Bound i n (2.2.18) 5.615x10" 1.291x10" f 5 5.615X10" 3 1 .304X10" 1.364X10" 8.776X10- 1.409X10" 9.413x10* 2 6.915x10" 4.969x103.412x10" 2.139x10- 1 5 3 2 2 2 1 1 1 Table I I : Upper bounds f o r parameter values x = 10, 7o = 5 dB (r = 0.6325). Comparing the values of the two upper bounds given i n the preceding t a b l e s , we see that the upper bound very tight. It is obvious, though, in (2.2.20) is that f o r the c h o i c e of 35 parameters tight, i n Table I above the bound does not have to be since the Beta f u n c t i o n error i n c u r r e d by r e p l a c i n g the i n (2.2.8) by the Beta f u n c t i o n i s P (M,100;0.02) f by at least a factor of very incomplete smaller 10 . The 2 5 small magnitude of the e r r o r term demonstrates the exponential block I t i s c l e a r that the dependence e r r o r term w i l l effect on be n e g l i g i b l e size. increasing parameters expect chosen the the error in that this particularly conclude case the e r r o r from x is the the r e l a t i v e e r r o r work region where table we the interested: see that bound (2.2.18), i n the approximation f o r M = 2. we However, an integer block size, x = N). entire parameter range in which one Of will is i t i s always a bother to have to c o n s i d e r separate approximation (2.2.17) is shown that we can that P values. approximate n e g l i g i b l e e r r o r over the parameter have yet to demonstrate the q u i t e robust, i n the sense that i t works w e l l over a wide range of parameter only can i s less c a s e s . I t i s e v i d e n t from the examples p r o v i d e d above that have we average one u s u a l l y d e s i r e s to f i n d a s i n g l e formula that over The very small we are a b l e t o compute P (M,N;r) d i r e c t l y (2.1.17) (assuming course, f f than 0.0082% f o r M = 0, and l e s s than 4.0% if P (M,x;r). i s small r e l a t i v e to P ( M , l O ; r ) , f o r small M. Using that the estimate r e s u l t s : both the block s i z e and the s i g n a l - t o - n o i s e r a t i o are s m a l l . From the in error probability f o r Table II are worst of f o r l a r g e r block s i z e s , s i n c e the of i n c r e a s i n g x w i l l be to decrease the while even effect than range of P So far by P interest we with — we i s e a s i e r to compute than P . 36 2.2.3 The approximation t o P F ( 0 , x ; r ) The advantage of working with P instead there i s an equation r e l a t i n g the Beta f u n c t i o n of P i s that to the Gamma f u n c t i o n [28]: T(a) T(b) B(a,b) = Re(a) > 0 . Re(b) > 0 T(a+b) Putting this result (2.2.21) into (2.2.12) we f i n d rO+x-m) T(m+r) r 2 , r (2.2.22) T(1+x+r) and, substituting (2.2.22) i n t o P(M,x;r) = r 2 M Z r m=0 We begin our a n a l y s i s consider case (2.2.14), we o b t a i n / \ T(1+x-m) r(m+r) ( ) . (2.2.23) x Y 7 T( 1+x+r) with the s p e c i a l case M = 0, which we i n d e t a i l because, as w i l l be shown l a t e r , the general M > 0 equation reduced t o t h i s s p e c i a l case. With M = 0 , can be (2.2.23) becomes P(0,x;r) = r 2 T(1+x) T ( r ) (2.2.24) r r(1+x+r) with an error i n approximation l e s s than r / 2 ( 1 + x ) . Using the recurrence r e l a t i o n x (2.2.6) we can w r i t e P(0,x;r) = 2 T(1+X) r d + r ) . r (2.2.25) r( 1+x+r) Moving from (2.2.24) to (2.2.25) i s n u m e r i c a l l y b e n e f i c i a l , because a s i n g u l a r i t y a t r = 0 i s removed. T h i s s i n g u l a r i t y (2.2.24) of a t r = 0 occurs because T ( r ) has a pole there (and at r ( r ) goes r = -1, -2, -3, . . . ) , and hence r -» 0 —> °° ). However, the poles of the Gamma + ( i . e . as y 0 to infinity as 37 f u n c t i o n are simple, and so r ' T ( r ) has a removable singularity at r = 0; i n f a c t lim r-T(r) = r->0 + (In other l i m r(1+r) = T O ) r->0 = 1. + words, the r e s i d u e of the T f u n c t i o n a t zero i s 1.) Of course, we should have a n t i c i p a t e d such behavior when near was z e r o : while examining noted that when B^(r,1+x) goes to the behavior of equation r —> 0 infinity the incomplete + i n such r is (2.2.9) Beta it function a way that the product r ' B i ( r , 1 + x ) approaches u n i t y . Since the bound r / 2 ( l + x ) x s on the d i f f e r e n c e between (2.2.9) and (2.2.24) goes t o zero as r —> 0* for a f i x e d x, the behavior of the two expressions must be the same near r = 0. Let us now c o n s i d e r some of evaluating (2.2.25). the d e t a i l s The most obvious of numerically f e a t u r e of (2.2.25) i s that the Gamma f u n c t i o n must be e v a l u a t e d . T h i s makes inconvenient f o r use on a hand (2.2.25) c a l c u l a t o r , but i s no r e a l drawback i f a computer i s a v a i l a b l e — the Gamma f u n c t i o n i s a standard function so packaged program installation of analysis available (at UBC at and may and as i s usually a any well-equipped just blindly exceed evaluate i t stands, because the terms T(1+x) and T(l+x+r) become very l a r g e . For example, T(101) = 100! = r(1001) computer f o r example). However, even i f a Gamma f u n c t i o n program i s a v a i l a b l e we cannot (2.2.25) there = 1000! = 4.02X10 2 5 6 7 , 9.33X10 and both these numbers the l a r g e s t number that i s e a s i l y r e p r e s e n t a b l e on computers. Thus t o a v o i d overflow 157 most i t i s best t o work with the l o g a r i t h m of the Gamma f u n c t i o n , and t o write 38 rd+x) T d + x ) - l o g r(1+x + r ) ] . = exp[log (2.2.26) r(1+x+r) Fortunately l o g r(-) has been analyzed the Gamma f u n c t i o n i t s e l f are (see, f o r example, [ 2 8 ] ) , and the double-precision evaluation (2.2.26) will particularly of result (2.2.25). in a f o r l a r g e block approximation of P f ( 0 , x ; r ) arithmetic First, loss of should there the used s u b t r a c t i o n in significant s i z e s . A l s o , our be figures, f i n a l goal i s the by P (0,x;r) = 1 - P(0,x;r), (2.2.27) f and as programs a v a i l a b l e f o r e v a l u a t i n g t h i s f u n c t i o n . There are s e v e r a l reasons why in almost as e x t e n s i v e l y the s u b t r a c t i o n in t h i s equation w i l l also result in a l o s s of s i g n i f i c a n t f i g u r e s . If a pre-written program for r(«) or log r(•) a v a i l a b l e , there are s e v e r a l programs l i s t e d Algorithms may from the on either expansions, and so). Thus, these Chebyshev if be done on Collected These approximations short programs or are asymptotic (20 l i n e s or a packaged program i s not a v a i l a b l e , the e v a l u a t i o n of T(•) or l o g r(«) easily functions. are s u r p r i s i n g l y simple and even the A s s o c i a t i o n f o r Computing Machinery that be used to evaluate based in i s not poses no r e a l problem, and can a programmable c a l c u l a t o r , or can even be done manually on a hand c a l c u l a t o r i n a matter of minutes. Equation DLGAMA, (2.2.25) was which i s a UBC to d o u b l e - p r e c i s i o n programmed f o r the Amdahl 470 l i b r a r y routine for evaluating accuracy. Values of P f were using log T(•) computed for 39 N = 1 0, 10 ., (2.2.27), of P f 3 sources the two for y from 0 to 50 dB using equation 0 and were then compared with the c o r r e s p o n d i n g o b t a i n e d by numerical three (i) 1 0 , 1 0" and 2 integration. source of e r r o r f o r N = 10 , 10 , 2 3 approximating i s o n l y important 10" the e r r o r in P least by f approximate P f significant figures approaches a numerical f approximation is f on the constant f i g u r e s from (16 Amdahl). For N = 10 we that the r e l a t i v e e r r o r value of in see approximation about 4x10" , and so, 5 we expect (2.2.27) when N = so would t o at l e a s t d o u b l e - p r e c i s i o n accuracy i g n o r i n g other sources of e r r o r , significant P. f o r N = 10, s i n c e t h a t , b a r r i n g a l l other sources of e r r o r , P from F i g u r e 2.6 (ii) at results: the e r r o r that r e s u l t s from small are of e r r o r that c o u l d cause d i s c r e p a n c i e s between s e t s of This There values about four 10. e r r o r i n the e v a l u a t i o n of (2.2.27), caused by the e f f e c t s of performing a r i t h m e t i c using a f i n i t e wordl e n g t h . An example of t h i s type of e r r o r significant i s the loss of f i g u r e s d i s c u s s e d at the top of the p r e v i o u s page. (iii) i n a c c u r a c y i n the numerical Appendix A, the values i n t e g r a t i o n are a c c u r a t e to i n t e g r a t i o n . As d e s c r i b e d of P at f in computed v i a numerical least five significant f igures. According to (i) and (iii), for N = 10 we can expect the 40 r e s u l t s t o agree to about four s i g n i f i c a n t f i g u r e s i f the e r r o r d e s c r i b e d i n ( i i ) can be ignored. Comparison showed t h i s t o the case. For N = 10 , 10 , 10", the only r e l e v a n t sources of 2 e r r o r a r e those values of P f numerical 3 i n ( i i ) and ( i i i ) . Comparison showed computed u s i n g (2.2.27) agreed f i g u r e s f o r almost a l l v a l u e s of y integration. Thus double-precision numerical much more integration check on the numerical accurate the approximation by examined very (and thus, in l i e on those the severe. (2.2.27) obtained by the end, were a b e t t e r i n t e g r a t i o n than v i c e v e r s a ) . G e n e r a l l y , 10 b i t s the e r r o r in i s so small that i f we graph both the r e s u l t s numerical on the same graph, lines range than when the block s i z e i s g r e a t e r than about obtained significant i n most cases the v a l u e s of Pf computed u s i n g probably the a r i t h m e t i c was of e r r o r d e s c r i b e d i n ( i i ) above was never In f a c t , were to f i v e that with those c a l c u l a t e d using 0 e n t i r e l y adequate, and over the parameter source be i n t e g r a t i o n and the approximate results the s c a l e of which i s as i n F i g u r e 2.3, top of one another the f o r the e n t i r e range 0 t o 50 dB. 2.2.4 The approximation to P (M,x;r) f We s t a r t by approximating bit errors Q(m,x;r), the p r o b a b i l i t y i n a block of x b i t s , binomial c o e f f i c i e n t i n equation f u n c t i o n s a c c o r d i n g to equation of m f o r m ^ 0. I f we express the (2.2.22) in (2.2.3), we get terms of Gamma 41 T(1+X) T(m+r) Q(m,x;D = r 2 r(1+x+r) r(1+m) . (2.2.28) For m = 1, 2, ... we can use (2.2.6) t o w r i t e r(m+r) = r(r+1) • • • (r+m-1) T ( r ) . Using Pochhammer's symbol, (2.2.29) which i s d e f i n e d by (Do = 1 (r) m (2.2.30) = r ( r + l ) • • • (r+m-1) f o r m = 1, 2, ... (see e n t r y 6.1.22 of [ 1 ] ) , we can extend m = 0 and w r i t e T(m+r) (2.2.29) t o the case = ( r ) r ( r ) f o r m = 0, 1, 2, ... Then m (2.2.28) becomes Q(m,x;r) = r 2 _ = 2 rd+x) r ( r ) (r) /m! m T( 1+x+r) (2.2.31) rd+x) rd+r) (D /m! . ra T( 1+x+r) Note that the e x p r e s s i o n i n f r o n t of the term (r) /m! i s j u s t ra the approximation to P(0,x;r) given i n equation (2.2.25). Thus Q(m,x;r) = P(0,x;r) ( r ) / m ! , (2.2.32) Q(m,x;r) = P(0,x;r) (D /m! , (2.2.33) m and hence m where a bound on the e r r o r i n the approximation (2.2.16). If r « can be shown from if 1 ( i . e . i f the average SNR y (2.2.30) that r << 1 and m > 1 we have that i s given i n 0 ( r ) / m ! = r/m f o r m i s large), i t m £ 1. Then 42 Q(m,x;r) = P(0,x;r) r/m . Equation (2.2.34) shows that p r o b a b i l i t y that there are m when (2.2.34) the b i t errors SNR in is a l a r g e , the block varies approximately i n v e r s e l y w i t h m. It i s now easy to w r i t e down an approximation f o r P(M,x;r) when M > 0: p u t t i n g (2.2.32) i n t o (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 w r i t e M P(M,x;r) = P(0,x;r) Z ( r ) / m ! - E(M,x;r), m (2.2.36) m=0 where E(M,x;r) satisfies (2.2.20). From (2.2.17) we a l s o have that P(0,x;r) = P(0,x;r) + E ( 0 , x ; r ) , and s u b s t i t u t i o n equation i n t o of this (2.2.36) y i e l d s M P(M,x;r) = P(0,x;r) Z ( r ) / m ! + m=0 m M + E ( 0 , x ; r j Z ( r ) / m ! - E(M,x;r). m=0 Let us get a bound on the a b s o l u t e value of the term M E(0,x;r) Z ( r ) / m ! " E(M,x;r). m=0 (2.2.37) m m We use the numbers, then are p o s i t i v e , following fact: if a and (2.2.38) b are p o s i t i v e real |a - b| ^ max{a, b}. Since both terms i n (2.2.38) 43 M E(0,x;r) Z ( r ) / m ! - E(M,x;r) m=0 m M < max{ E ( O x ; r ) Z ( r ) / m ! , E(M,x;r) } f m m=0 It is easy to see that for 0 < r < 1 the inequality 0 < ( r ) / m ! < 1 h o l d s , and hence, u s i n g the bound i n (2.2.20), m we have M max{ E(0,x;r) Z (r) /m!, m=0 E(M,x;r) } < max{ (M+1)E(0,x;r), E(M,x;r) } /\ (M+Dr < max » (1+x) ' V W7 2* 2 ~" x •G) M where 2 M / r 2 " X M £ = M/2(x-M). (1+x-M) The > M+1 f o r M £ 0, that and the quantity KX 1-£ L i- last .M+1 r M + l n M (1+x-M) L\ - ~ n { step f o l l o w s upon n o t i n g that 1/(1+x-M) > 1 / ( 1 + X ) , in \ square and that both b r a c k e t s a r e g r e a t e r than u n i t y . Summarizing, we have M P(M,x;r) = P(0,x;r) Z ( r ) / m ! m=0 (2.2.39) m with an e r r o r bound in i n approximation that is less the upper (2.2.20) when 0 < r < 1 and 0 £ M < x. Thus from our p r e v i o u s i n v e s t i g a t i o n we know that the e r r o r in than (2.2.39) is negliglible in approximation f o r almost a l l cases of i n t e r e s t . 44 Equation (2.2.39) i s one of the major r e s u l t s of t h i s because i t demonstrates that the computation reduced (approximately, at least) to of P(M,x;r) can be computation of the P(0,x:r): given at a l l , need only compute the " c o r r e c t i o n thesis, the value of P ( 0 , x ; r ) , computed by any method M we factor" M in order to o b t a i n P(M,x;r). The factor L (r) /m! m m=0 Z (r) /m! m poses no m=0 numerical pocket problems, and c a l c u l a t o r . Equation theoretical point compute P(0,x;r) was f o r small M can e a s i l y be handled programmed compared with The agreement of view; (2.2.39) is interesting Amdahl (2.2.35). T h i s l a t t e r for the the r e s u l t s obtained by numerical the from a i n p r a c t i c e , having no method to e x a c t l y , we use between on a 470, results and was the very p r e v i o u s e r r o r a n a l y s i s would lead us to expect. equation results were integration. good, as our 45 2.3 Infinite 2.3.1 this again f s e c t i o n we d e r i v e i n f i n i t e considering approximations wonder about These expansions I n t r o d u c t i o n and n o t a t i o n In P , series of only Section non-coherent 2.2 the need to develop expansions are useful approximations developed how FSK. With i n mind, one might infinite series the reasonably expansions. i n that they show the connection between the approximations developed the s e r i e s expansions f o r discussed in in the Section literature ( i . e . 2.1) and those i n the previous s e c t i o n . In p a r t i c u l a r , we s h a l l approximations (2.1.24) and (2.1.26) formulas of S e c t i o n 2.2, and how these follow see from approximations the can be made more a c c u r a t e with l i t t l e added computational e f f o r t . Thus the formulas derive in this section computational a l t e r n a t i v e to the formulas although in the we we provide of a simple Section 2.2, s h a l l no longer have r i g o r o u s bounds on the e r r o r approximation. approximations We (2.1.24) shall and also (2.1.26) how to modify f o r the case M > 0. F i n a l l y , the formulas we derive discussion ( S e c t i o n 2.4). Since the mathematical of diversity here see will be used i n our d e t a i l s are somewhat t e d i o u s , many of them have been p l a c e d Appendix C: our primary o b j e c t i v e i s to g i v e those in results'that the reader may f i n d u s e f u l or i n t e r e s t i n g . Note that we order expansion of P show i n what may t h i n k of equation (2.1.21) as a f i r s t f sense h i g h e r - o r d e r terms of i n terms of this the the quantity r = 2/y . 0 To i s t r u e , and how we can d e r i v e the expansion, we first go back to 46 equation (2.1.17): N / \ (-1/2) Li?) k=1 \ / k + r P (0,N;r) = - r f (2.3.1) k For | r | < k, we may w r i t e 1 1 = k + r Since for kd+r/k) the s m a l l e s t equation CO = k- (2.3.1) value is f = J j=0 assumed by the index of summation k in k = 1, the f o l l o w i n g equations are v a l i d The interchange clearly N I k=1 (-1/2) k N j+ 1 Z (-1 ) j-0 L Z i=1 in (-1) 1 k Z (-r/k) j=0 w / X (-1/2) N =i J (2.3.2) , 1 J R N / \ (-1/2) Z k k=1 / N 1 the order of summations in (2.3.2) is 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 (2.1.19) i s equivalent k=1 W approximation or of term of the s e r i e s (2.3.3) k 2.1 that the use of i d e n t i t y approximated the coefficient not easy to compute d i r e c t l y easily making t o t a k i n g the f i r s t (2.3.2). Although the f i r s t is (-r/k) . IrI < 1: P (0,N;r) = - r is Z 1 f o r l a r g e N, we saw i n S e c t i o n (2.1.20) puts i t i n t o a form computed exactly that i f d e s i r e d . We 47 should distinguish here between two d i f f e r e n t one approximation c o n s i s t s of i g n o r i n g the of in the i n f i n i t e series the terms going from the first to the themselves term [this (2.1.21) by compute the higher-order (-1) just error in approximating higher-order terms be I f we then the obvious way attributed now desire a to proceed is i n (2.3.2). However, the coefficients . N Z k=1 ( i > 2) 1 as difficult to (2.3.4) e v a l u a t e d i r e c t l y as hope f o r a g e n e r a l i d e n t i t y analogous will transform the c o e f f i c i e n t s be to (2.3.3). (2.1.20) One which (2.3.4) i n t o e x p r e s s i o n s that more e a s i l y computed or approximated. to made (2.1.24) i s so s m a l l f o r N g r e a t e r might appears one i s the approximation made i n omission of the h i g h e r - o r d e r terms. f are i s the 10 b i t s that almost a l l the e r r o r may b e t t e r approximation to P , to terms (2.3.2) [ t h i s i s the approximation made (2.1.21) to (2.1.24)]. The than about are higher-order (2.1.19)], whereas the other approximation to approximations: Unfortunately, there 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 d e a l t with i n an ad hoc manner. I t i s p o s s i b l e to get somewhere by a t t a c k i n g 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 i n c r e a s e s . Using the formulas of S e c t i o n 2.2 the d i f f i c u l t i e s coefficients in mentioned the above. The expansion of with than those i n the expansion of we can l a r g e l y key P here is sidestep that the are much e a s i e r to work P . Let us begin our 48 a n a l y s i s with some new n o t a t i o n : d e f i n e q (m,x) and q^dr^x) by i Q(m,x;r) = (*) r 2 \ / B (m+r, 1 +x-m) T = lg Z i =0 qi(m,x) r 1 (2.3.5) Q(m,x;r) = (*) r 2* B(m+r,1+x-m) = W The It infinite when 1 s e r i e s i n (2.3.5) converge f o r a t l e a s t i s not hard to show |r| < m I qi(m,x) r . i =0 that m £ 1, but convergence the s i t u a t i o n actually | r | < 1. holds for i s more d i f f i c u l t f o r m = 0 ( t h i s i s one of the few i n s t a n c e s 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) h o l d s f o r m = 0 i s d e s c r i b e d i n Appendix C. We a l s o d e f i n e M Z p (M,x) = ± q (m,x) , ± (2.3.6) m=0 and s i m i l a r l y d e f i n e p ( M , x ) . Then i oo P(M,x;r) = and Z p.(M,x) r i =0 1 (2.3.7) 00 P(M,x;r) = for | r | < 1. It (2.3.2) 1 i s not hard t o d e r i v e exact formulas f o r the c o e f f i c i e n t s q^^ and p using Z p.(M,x) r i =0 and i when x = N = an integer — the relation P = 1 - P , f for example, we have i n the s p e c i a l case M = 0 that q ( 0 , N ) = 1 and O /M\ (~1/2) Z (l) — . N q.(0,N) = ( - 1 ) 1 + 1 k=1 V / K 1 We have k k ( i > 1) 1 (2.3.8) a l r e a d y seen that these c o e f f i c i e n t s are hard to work with, and we expect the s i t u a t i o n t o be even worse when M > 0. But P, and we know that P i s an e x c e l l e n t approximation to 49 so i t i s n a t u r a l to see what introduce can learn from the P. Thus we focus on the c o e f f i c i e n t s q expansion of Before we we proceed,.we r e c a l l 2.1 we p. and ± ± some p r e v i o u s n o t a t i o n , and some more; much of the n o t a t i o n as i n [ 1 3 ] . In S e c t i o n series defined used here i s the same the quantity H for n n = 1, 2, 3, ... by n = Z k" k=1 ^ (2.3.9) 1 (the H stands f o r "harmonic"). We extend this definition by writing H i> for i = 1, 2, 3, ... Thus H convention that n Z k k=1 = n (2.3.10) _ i = H >. 1 n n H ^ l ' = 0; this We shall convention write down s e v e r a l of the e x p r e s s i o n s that need to consider n without us to the s p e c i a l cases. I t i s an elementary r e s u l t of However, for i £ 2 the limit i.e. H of H^ ' 1 —°° as e x i s t s as , and we put oo S(i) = for use the w i l l allow follow a n a l y s i s that the harmonic s e r i e s d i v e r g e s , n —^ oo . also i £ 2. The l i m H' i' = Z k n -> co k= 1 (2.3.11) - i n function $(i) i s called the Riemann Zeta which are function [28]. We a l s o introduce defined the by the i n f i n i t e z numbers B , n series 00 = exp(z) - 1 Bernoulli Z B n=0 z /n! . n n |z| < 2ir (2.3.12) 50 (The Bernoulli numbers are sometimes defined slightly d i f f e r e n t l y , and so one must be c a r e f u l when c o n s u l t i n g v a r i o u s r e f e r e n c e s . ) The B 0 and =1, it first few c o e f f i c i e n t s B, = -1/2, can be B shown = 1/6, 2 B i n (2.3.12) are =0, 3 B = fl -1/30 that a l l c o e f f i c i e n t s with odd except B, are z e r o . A t a b l e of B e r n o u l l i numbers can in [ 1 ] , Another f a c t which we indices be found s h a l l use i s that $(2n) = | B | ( 2 7 r ) / 2 ( 2 n ) ! 2n 2n (2.3.13) for n = 1, 2, 3, ...; in p a r t i c u l a r $(2) = and I k=1 k' 2 = TT /6 2 (2.3.14) OO $(4) 2.3.2 = I k-« k=1 E x t e n s i o n of formula We (2.1.26) do not s t a r t by immediately d e r i v i n g the expansion f o r Q given i n (2.3.5); i n s t e a d we Q(m,x;r) = (r/m) for 7r«/90. = 1 < m < x. (According exp to first represent Q i n the form Z b (m,x) r i =0 (2.3.15) 1 ± our notational convention should w r i t e b-j_(m,x) i n s t e a d of bi(m,x), but s i n c e we be examining the corresponding expansion reason expansion i s because the form (2.3.15) bi(m,x) can be e a s i l y expressed i n terms why of s h a l l not f o r Q(m,x;r) i t i s convenient to omit the c a r e t ) . The of we we derive an the c o e f f i c i e n t s known functions, 51 and the q can i n turn be e a s i l y represented i n terms of the ± b.. Note that (2.3.15) holds only f o r m > 1. It is shown in Appendix C that 5(0, x;r) = exp I L i =0 b. (1 ,x) r (2.3.16) 1 and so f i n d i n g the c o e f f i c i e n t s b (m,x) f o r m > 1 w i l l suffice i for the case m = 0 as w e l l . In Appendix C exact formulas f o r these c o e f f i c i e n t s are obtained; the r e s u l t s are r b (m,x) = 0 0 \ b,(m,x) = l o g 2 + i//(m) - ^(1+x) (2.3.17) b (m,x) = [^«i- (m) - V ' '(1+x)]/i! 1) 1 . 1 ± ( i > 2) The f u n c t i o n \p i n (2.3.17) i s the the P s i f u n c t i o n the Digamma f u n c t i o n ) , which i s d e f i n e d *(z) = (also c a l l e d by [1,28] r-(z) (2.3.18) r(z) and which i s t a b u l a t e d i n [ 1 ] , The P s i f u n c t i o n the same region of the complex plane i.e. in <E\{0, -1, -2, ...}. We as the f o r computational purposes, coefficients i n equation means of asymptotic (2.3.15) can (2.3.15) i n terms of known now expansions; functions. f o r x > 10 or so the d e t a i l s of d e r i v i n g these e x p r e s s i o n s are given i n Appendix C. There that f o r i = 1 we have function, s i n c e we have expressed the These c o e f f i c i e n t s can be a c c u r a t e l y computed by Gamma use (//'J' to denote the j - t h d e r i v a t i v e of the P s i f u n c t i o n . The expansion be used i s analytic in it is shown 52 - [log(x/2) b,(m,x) ~ H m _ + C + 1/2X 1/12X - 1/120X + 2 - 4 ...], (2.3.19) 1 f o r i > 2 we have and ( - 1 J ! " ( $(i) - H > b (m,x) ~ 1 ± 1 L (i-l)x Although quite to 2 X i _ 1 the preceding simple - (i formulas may use. For forms of the f i r s t explicitly i n Table I I I below. H (i-1)! 1 asymptotic b, (m, x) ~ m - 1 (2.3.20) " tlog( reader's 2 ~ ( 1 / 2 ) {$(2) _ H < + 1/2X 2 ) m-1 _ [1/x (-1/3){5(3) - H<m-1> 3 3 ( 1 / 4 ) {$(4) - H< • > - [ 1 / 3 x m-1 1/6X Table I I I : Asymptotic From is i _ 1 convenience the 2 3 + 6 + ...] 1/6X + - 1/2x - 7 3 - ...]} + l/4x' 3 out + 2 1/252X 2 -I / ' + 1/12X - 1 / 2 X " + 1/3X 8 - t - . . . ] } 5 - ...]} forms of the c o e f f i c i e n t s . (2.3.14) we have the exact values f o r $(2) and $(4); there no such c l o s e d form odd p o s i t i v e From + are + 1/42X 6 7 - 1/2X 5 [ 1/2X 1/12X b . (m, x) ~ n they 1/12X - - 1/30X b (m, x) ~ 2 few c o e f f i c i e n t s are w r i t t e n + 1/120X« b (m,x) (2n)! x look complicated, the + C x/2) n=1 [1] than about f o r the Zeta f u n c t i o n e v a l u a t e d at the i n t e g e r s , and £(3) must be computed numerically. we f i n d t h a t $(3) = 1.20205. For block s i z e s g r e a t e r 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 Consider now (2.3.16). in the computation Fortunately, several terms approximation corresponds (2.3.16). of the i n f i n i t e r a p i d that we may with (2.1.26), to of P(0,x;r) = Q(0,x;r) the convergence (2.3.16) i s s u f f i c i e n t l y only to c o n s i d e r a b l e accuracy. i little retaining only in the reference [21], first shows term to that it b,(1,x) in At high average SNR's the s i n g l e term i s s u f f i c i e n t , but at lower SNR's i t i s a d v i s a b l e to take methods series truncate i t after error; developed using here demonstrate how several more. we can extend the approximation (2.1.26) to h i g h e r - o r d e r terms and thus i n c r e a s e the Retention of only the f i r s t four c o e f f i c i e n t s w r i t t e n out computation accuracy. four terms, c o r r e s p o n d i n g to the in detail above, accuracy f o r a wide range of average SNR's The gives good 7 . 0 of P(M,x;r) f o r M > 0 by f i r s t Q(m,x;r) f o r m = 0, 1, 2, The M u s i n g (2.3.15) and computing (2.3.16), and then s u b s t i t u t i n g these i n t e r m e d i a t e r e s u l t s i n t o (2.2.14), is i s to use not very efficient. A much better approach (2.3.16) to compute P(0,x;r) as d e s c r i b e d above, and then to use equation (2.2.35) to compute P(M,x;r). 2.3.3 E x t e n s i o n of formula (2.1.24) Based on what we have derived determine the c o e f f i c i e n t s q ^ n ^ x ) (2.3.5) and approximation manner as we (2.3.7). The (2.1.24) to extended result and will higher-order so f a r , i t i s easy to p (M,x) ± be an terms, of equations e x t e n s i o n of in the same approximation (2.1.26). The method of 54 doing t h i s i s t o express the c o e f f i c i e n t s q± and p i i n terms of the known c o e f f i c i e n t s b^. We begin by w r i t i n g Z a (m,x) r i=0 = 1 i where the b ± exp E bi(m,x) r L i=i are known and the a ± a r e t o be determined. We have used the f a c t that b (m,x) = 0 i n w r i t i n g 0 we s h a l l u s u a l l y suppress (2.3.21) 1 (2.3.21). From now on the parameters m and x i n our n o t a t i o n , and simply w r i t e L a . r = exp L b,r i =0 L i = 1 1 (2.3.22) L 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 . T h i s formula i s i a 0 =1 . a .= We e a s i l y a 0 I -1 k=1 k 1 ( i ^ 1) k (2.3.23) f i n d that =1 a, = b, a a 2 = b, /2 + b 3 = b, /6 + b , b 2 2 3 a, = b,V24 2 + b (2.3.24) 3 + b b, /2 + b / 2 + b , b 2 2 2 2 3 + b« and so on. Now that we have expressed the c o e f f i c i e n t s terms of b^ b.. We f i r s t i a i in i t i s a simple matter t o express p\ i n terms of c o n s i d e r the case M = 0. We have 55 P(0,x;r) = Q(0,x;r) = Z a.(1,x) r (2.3.25) 1 i=0 from equations f o l l o w s that (2.3.16) p (Q,x) and (2.3.21), i ± immediately 0 CO CO = - Z a (l,x) r i=1 1 ± f it = q ( 0 , x ) = a ( l , x ) . Since a ( l , x ) = 1, ± P (0,x;r) and = - Z p (0,x) r i=1 1 ± . (2.3.26) But a , ( l , x ) = b,(1,x) [log(x/2) + C + 1/2X - 1/12X + 2 ...] (2.3.27) and so taking approximation the that by the term in (2.3.26) (2.1.24) [see a l s o the note a f t e r that the d e r i v a t i o n that first l e a d i n g t o (2.1.24) depended block s i z e was an i n t e g e r N; equation (2.1.24) may be used f o r n o n - i n t e g r a l block replacing importance of enable us t o compute desire, i . e . we than only compute the have extended the fact (2.3.27) shows sizes simply make sense). that i we the approximation (2.1.24) t o computational f o r equation scheme is (2.3.16), slightly i p (0,x) = a ( l , x ) i using i more s i n c e we must not the c o e f f i c i e n t s b ( l , x ) , but a l s o must the then find recurrence (2.3.23). L a s t l y , we demonstrate first-order approximation how a s l i g h t (2.1.24) M > 0 as w e l l . Comparison of equations yields, on as many of the c o e f f i c i e n t s p ( 0 , x ) as i t is coefficients relation (2.1.26)]. Note (2.3.26) i s t h a t we now have formulas a r b i t r a r y o r d e r . The complex the the i n t e g e r N by the r e a l number x (although the i n t e r m e d i a t e s t e p s l e a d i n g t o (2.1.24) no longer The recovers f o r m ^ 1, modification allows of the i t t o be used f o r (2.3.15) and (2.3.21) 56 Hence, when m > 1, we have q (m,x) = 0 0 (2.3.28) | q (m,x) = a _i(m,x)/m i . ± Since q^O^x) = a ( l , x ) [see the top of the p r e v i o u s page], i we may w r i t e p . (M, x) = M Z m=0 q . (m, x ) (2.3.29) M = a . (1 , x ) + (1 - 6. ) Z 1 i o m=1 where is analytically some delta. 1-1 In general (2.3.29) very much, although we cannot we can s i m p l i f i c a t i o n s when i i s s m a l l . We s h a l l only the cases For Kronecker simplify useful first-order the a. ,(m,x)/m i = 0 and i = 1, i . e . we s h a l l c o n s i d e r approximation. make examine only a When i = 0, p (M,x) = a ( l , x ) = 1. 0 0 i = 1, p,(M,x) = a , ( l , x ) + From (2.3.24) we find M Z m=1 that a (m,x)/m . 0 a,(1,x) = b , ( 1 , x ) , (2.3.30) and that a (m,x) = 1. Then 0 p,(M,x) = b,(1,x) + H where Table the last equality = b,(M+1,x), (2.3.31) f o l l o w s immediately on r e f e r e n c e to I I I . Hence when r i s s m a l l , 57 P(M,x;r) = Z p (M,x) r i =0 1 ± = p (M,x) + p,(M,x) r (2.3.32) 0 = 1 + b,(M+1,x) r and so P (M,x;r) = 1 - P(M,x;r) = - b,(M+1,x) r f = r [-log 2 - ,//(M+1) + <Ml+x)] = r [-H M + log(x/2) + C + 1/2X - 1/12x The l a s t equation shows the simple m o d i f i c a t i o n made t o the f i r s t - o r d e r the case M > 0. (2.3.33) approximation 2 that + ...]. must be (2.1.24) to extend i t to 58 2.4 Diversity 2.4.1 Introduction We come now Rayleigh to the l a s t t o p i c fading: i n our a n a l y s i s of very slow the computation of the b l o c k - e r r o r r a t e when ideal selection diversity i s employed. We L branches, i n t e g e r g r e a t e r than or equal and on where L i s an letting branch assume that there are denote the instantaneous i , we further assume a receiver h i g h e s t SNR that {y^} is a set f~*<7) = L f u n c t i o n of the l a r g e s t SNR [1 - exp(-7/ 7 O )] L _ 1 7 o - 1 0 the by ( 7 > 0) (2.4.1) 7 Under the c o n d i t i o n of very assumed slow fading, the SNR's y ± are to remain constant over an e n t i r e block, and hence the same branch 7* with probability 7 * i s given exp(-7/7 ) of (2.1.7). using s e l e c t i o n d i v e r s i t y , the branch i s chosen. In [23] i t i s shown that the distribution 1, signal-to-noise ratio independent random v a r i a b l e s , each having d i s t r i b u t i o n In to w i l l be chosen f o r an e n t i r e b l o c k . In other words, remains constant over an e n t i r e b l o c k , but v a r i e s from block to block a c c o r d i n g to (2.4.1), and (2.1.11) we may P (L,M,x) = / d immediately with equation w r i t e down P (M,x; ) f * ( ) 7 so i n analogy 7 7 d 7 (2.4.2) where P (L,M,x) errors i n a block of x b i t s when L-branch d is the p r o b a b i l i t y that there i s more than M selection diversity 59 i s used. We s h a l l u s u a l l y w r i t e simply P shall for P ,c d use the notation P "complement"). P u t t i n g = <L/7o> = 1 - P d }c d (2.4.1) i n t o 2 (*) f P ( 7 ) m=0 \ / J c\ f o r P (L,M,x), d (the s u b s c r i p t c stands (2.4.2) g i v e s [1 " p ( 7 ) ] m and d X _ m (2.4.3) [1 - exp(-7/7 )] L exp(-7/7 ) 6y. 1 0 0 We c o n s i d e r only NCFSK, f o r which the special the case in b i t error), the d c = L r 2 r see [14] or [ 2 0 ] ; we are more g e n e r a l case. Making the s u b s t i t u t i o n t = p ( 7 ) , as we d i d i n equation P For M = 0 and x = 1 ( i . e . when we are computing p r o b a b i l i t y of interested p(7) = (1/2) exp(~7/2). (2.2.2), we (*) f\*+*- Z m=0\ /^0 1 (1 - t ) " X find m m [1 .- ( 2 t ) ] " d t . (2.4.4) r r 1 L -1 Using t h e - b i n o m i a l expansion of the term [ l - (2t) ] w r i t e the p r e v i o u s equation L , we can i n the form m=0 \ / (2.4.5) •i.0 t m+(j + 1 ) r - l (, _ ) X - m T If we now take x = N = an i n t e g e r i n (2.4.5) above, and use the binomial expansion of the term (1 - t j P d c d , c = L r i d s ( 7 ) (-1 ) m=( d f c # , we 3 u (-D 2 m+k find (2.4.6) k 1 [ +(j+1)r+k] m 60 Equation slight in (2.4.6) i s the same as equation (15) of [25] rearrangement (with a and obvious changes i n n o t a t i o n ) . As noted [25],. equation (2.4.6) i s an a l t e r n a t i n g s e r i e s that may be difficult t o e v a l u a t e n u m e r i c a l l y when N f a c t , the l a r g e s t value of N used or M is large. i n [25] f o r numerical In results i s N = 100. 2.4.2 Approximations We now develop some approximations f o r P P ); d than P these approximations c (l) V 2 r w e l l f o r block s i z e s g r e a t e r pT ) (-l)J2J 1 r V / j=0 \ J / m=0 We now approximate P d c B ,(m+(j + 1)r,1+x-m). J d = L r 2 C In Appendix r 2 m=0 (2.4.7) 2 i n the manner of S e c t i o n 2.2, r e p l a c e the incomplete Beta f u n c t i o n by the Beta P, ' (and hence f o r 10 or so. We begin by w r i t i n g equation (2.4.5) i n the form . = L r 2 d work d ( A V ( T ) (-1 ) 2 W j = 0\ / L 1 j j r 2 i . e . we function: B(m+( j + 1 ) r , 1+x-m) . (2.4.8) B we show that P d,c " d,c P s m I = \ CO l d " d P P I (2.4.9) L r =0 V"/ 2 x _ m L (1+x-m) m=0 \ / T h i s e r r o r bound i s very s i m i l a r t o those examined 2.2, and i t follows that the e r r o r in Section i n the approximation i s 61 negligible Equation f o r the parameter range i n which we are interested. (2.4.8) may be rearranged to give " Pd,c = L Z I j=0 \ L 1 ( - 1 ) J . I 2 ) j + 1 •|"(j + 1)r 2 ( j + 1 ) I ( A B(m+( j + 1 ) r , 1+x-m) m=0 W r -I L L-1 / A (-1) = L Z ,M j = 0\ / j + 1 (2.4.10) ^ P(M,x;(j+1)r) . J T L 3 We now put k = j+1 to get P d ) C {^il^j = ^ ( L A ) ("D P(M,x;kr) k + 1 (2.4.11) = Z fJ k=l\ / (-1) L k + 1 P(M,x;kr) k Since we equation P d , already have an e f f i c i e n t (2.4.11) can be used to approximate P when L is small. If L i s large, (2.4.11) may prove u n s u i t a b l e Figure 2.7, average SNR diversity error for y 0 f o r L = 1, 2, 3, i s to s u b s t a n t i a l l y one d , c and hence the a l t e r n a t i n g numerical series computation. In P ( L , 0 , 1 0 0 ) has been p l o t t e d as a f u n c t i o n of the f o r a given SNR, adding way to compute P(M,x;r), more Clearly the effect of improve the p r o b a b i l i t y of block although branch 4. the decreases improvement obtained by as the number of branches increases. We can get more i n s i g h t deriving i t s infinite into the behavior of P d by s e r i e s expansion. We use (2.3.7) to w r i t e 0.0 10.0 20.0 30.0 40.0 Average s i g n a l - t o - n o i s e r a t i o r 0 50.0 i n dB. F i g u r e 2.7: P,(L,0,100) f o r L • 1, 2, 3, 4. 63 P(M,x;kr) = when | r | < 1/k converges f o r assumed may by (recall at the Z p (M,x) r k i =0 1 1 ± t h a t the s e r i e s expansion least | r | < 1). Since index of summation the f o r P(M,x;r) largest value k i n (2.4.11) i s k = L, we write f C = = for Z (l) k=1 W Z (-D p.(M,x) i=0 1 | r | < 1/L. k+1 TZ (^(-D k=0 W L Denote rV Z p.(M,x) i=0 the k + 1 quantity k 1 in 1 (2.4.12) r 1 square b r a c k e t s by (^(-UV. (2.4.13) S(L,i), i.e. S(L,i) = Let |H j^) (-l) k+1 denote S t i r l i n g k 1 -L = numbers of the second kind [1,13]. On page 67 of [13] we f i n d the r e l a t i o n (-D n! n = k (-D m Z k (2.4.14) with the convention t h a t 0° = 1. Using t h i s same convention, can combine equations S(L,i) = - Z where (2.4.13) and (2.4.14) to g i v e (-1 j H 1 6 j i s the Kronecker ± = 6 io - Z d e l t a . Thus (-I)** 1 we 64 P (L,M,x) = 1 - P d d c (L,M,x) CO = 1 - Z p.(M,x) S ( L , i ) r i =0 1 1 = (-1) L! I L i=1 1 0 cancel = 1 (see the f i r s t = 0 page, 56) ' l 1 In the p r e c e d i n g c a l c u l a t i o n s a (l,x) Mr1. p.(M,x) we used and the the result p (M,x) = 0 f a c t that S(L,0) = 1 t o term of the s e r i e s . I t can be shown that [13] f o r 1 < i < L, {I:}-'- ™* { V\ • L Thus P or, = (-1) L! (p (M,x) L d r L + [L(L+D/2] p L r e t a i n i n g only the f i r s t P = (-1) L! L d PL(M,X) r T Thus the e f f e c t of d i v e r s i t y i s proportional of error to " 1 7 ~ to ratio drops L 7 o L + 1 + ...} off increases . make tor L 0 as i n equation therefore signal-to-noise not 7 o to r L L proportional (M,x) term, = (-2) L! p ( M , x ) / error L + 1 the large SNR's, (2.1.24). much probability more The instead of probability rapidly as than i t does when d i v e r s i t y employed, as shown i n F i g u r e 2.7. of the is 65 Chapter 3 A model f o r c a l c u l a t i n g b l o c k - e r r o r r a t e s on slow R a y l e i g h In the previous the computation Rayleigh chapter of f a d i n g channels we examined several methods f o r P (M,N) on a channel s u b j e c t to very f a d i n g . The purpose of t h i s chapter i s to c o n s i d e r the computation of P (M,N) when the assumption of very slow f is relaxed, necessarily will i . e . when the remain constant be on the m o b i l e - r a d i o signal-to-noise of ratio fading does not over an e n t i r e b l o c k . The emphasis environment. Without the assumption of very methods slow f slow f a d i n g , the a n a l y t i c a l Chapter 2 are no longer a p p l i c a b l e , and a t present there appears to be no analytical method f o r computing the p r o b a b i l i t y of block e r r o r . Thus we must r e s o r t t o s i m u l a t i o n s . In general, software. there are Descriptions of fading can decided f o r the purposes of simulator be two types found, based on of s i m u l a t o r s : hardware and hardware simulators f o r example, a this in thesis computer program to of ease hence a software i n [24]. The version because of i t s implementation. A disadvantage of using a on a d i g i t a l high use given simulator was chosen over a hardware simulator Rayleigh [2] and [ 4 ] . I t was software the for cost) computer i s the long running required to time guarantee s t a t i s t i c a l l y (and valid results. To attempt overcome was the expense of made t o f i n d a simple computer simulations, e m p i r i c a l formula, the formulas of Chapter 2, that would allow us to an based on predict the 66 results of the simulations. model from which we derive such In Section an 3.2.2 empirical we describe formula. a This formula t u r n s out t o be q u i t e s u c c e s s f u l i n that i t allows easy calculation slow fading i s not of the assumed. p r o b a b i l i t y of block e r r o r when very 67 3.1 The Simulator 3.1.1 Implementation The s i m u l a t o r was implemented both on the u n i v e r s i t y ' s Amdahl 470 and on a Nova 840 that i s r e s i d e n t i n the department of e l e c t r i c a l e n g i n e e r i n g . Although i t i s much slower than the Amdahl, the Nova could be run f o r much longer p e r i o d s of time because the computer time was f r e e . The s i m u l a t i o n programs f o r both computers were w r i t t e n i n FORTRAN, but they d i f f e r e d i n many r e s p e c t s due to d i f f e r e n c e s operating systems. capability, between and and machines automatically performs manipulate large data r e l i a b l y . On the Nova, however, storage transfers and their transfers and secondary storage when necessary, e n a b l i n g the programmer to easily the For example, the Amdahl has virtual-memory i . e . the system primary in between core and disk are thereby structures allocation 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 generators of support and f a s t F o u r i e r transform programs had to although the simulation algorithm, software, they be coded differed s i m u l a t o r s gave i d e n t i c a l the confidence in their such random-number (FFT) r o u t i n e s . A l l especially programs as f o r the implemented such Nova. Thus, the same i n many r e s p e c t s . The f a c t that the results in several tests increased correctness. 3.1.2 D e s c r i p t i o n of the a l g o r i t h m The simulation program uses a Monte C a r l o method, i . e . a 68 method based on random-number generators more accurately be The sequence with (2.1.7), and The An i n subsequent program f i r s t the exponential more sample represents the SNR fading transmitted whether or not of error a for one at a 7 . 0 to work As a bit is in that bit sequence into the appropriate of b i t e r r o r . That i s , i f 7 f a d i n g sequence, then the k-th bit is first the calculated. This formula i s the is SNR from k-th SNR in the for the value error i s chosen from (2.1.1) or i s chosen from the uniform step in error, accordance with the modulation scheme being a random number u, each with each b i t i n a bits. given time; i s done by s u b s t i t u t i n g the a s s o c i a t e d p r o b a b i l i t y p ( 7 ), where in convenient i s associated of probability in the that stream calculation in equation s i g n a l - t o - n o i s e r a t i o s . " Samples are taken from d i s t r i b u t e d sequence probability fading d i s t r i b u t i o n i n s t e a d of a the e x p o n e n t i a l l y deciding the then normalizes i t to the d e s i r e d average SNR with simulated stores a d i s t r i b u t i o n given d i s t r i b u t i o n because i t i s directly follows; sections. generates and sequence i s given an e x p o n e n t i a l Rayleigh should the term random o u t l i n e of the a l g o r i t h m be d e s c r i b e d simulation numbers c a l l e d pseudo-random, but number i s standard). details will (the with (2.1.2) examined. Next, distribution on k "Of course, we can d e r i v e a R a y l e i g h - d i s t r i b u t e d sequence from the e x p o n e n t i a l l y d i s t r i b u t e d one by t a k i n g the square root of the sample v a l u e s . A R a y l e i g h - d i s t r i b u t e d sequence i s d e s i r e d f o r c e r t a i n t e s t s that are used i n S e c t i o n 3.1.3 to v e r i f y the s t a t i s t i c a l p r o p e r t i e s of the sequence generator, and f o r these t e s t s the square root i s taken. 0 69 the interval [0,1], and i s compared with p ( 7 ) . If u k < p(7 ) k k we say that the b i t i s i n e r r o r ; otherwise we say t h a t the b i t is correct. Note that assumed t o be constant may change bit-error given signal-to-noise over the d u r a t i o n ratio is still of a b i t , although i t b i t t o b i t . Thus the simulator should r a t e equal to the t h e o r e t i c a l r e s u l t s f o r slow give a fading i n equations (2.1.9) and (2.1.10). By segmenting samples, block. the from the we the fading block-error To simulations, blocks of N l a r g e number of blocks are observed, rate may then be s t a t e d with a high degree of gauge the sequence i s f i r s t sequence into can e a s i l y keep t r a c k of the number of e r r o r s per If a s u f f i c i e n t l y certainty. sequence the following statistical procedure accuracy was the adopted. A fading generated, and the b l o c k - e r r o r i s computed as a r e l a t i v e of rate for this frequency. The r e s u l t s f o r t h i s sequence are s a i d to c o n s t i t u t e a s i n g l e t r i a l . Thus i f n trials frequencies are P^MjN), the P (M,N), of block variance are distribution result P (M,N) 2 probability sample conducted, n error. then that the can approximate computed. that by the sample v a r i a n c e , the we are 95% we i n t e r v a l about the sample mean using f o r using be found, f o r example, i n [27]. A 95% contains Assuming of the sample mean i s approximately Gaussian, and a 95% confidence that true g t-distribution. Justification means the The sample mean P (M,N) and the r e p l a c i n g the unknown true v a r i a n c e construct i s n relative confident the true mean. F i n a l l y , we that note the t - d i s t r i b u t i o n confidence the s t a t e d that the interval interval algorithm 70 above i m p l i c i t l y assumes a lack of intersymbol 3.1.3 of the Generation Before looking f a d i n g sequence at sequence, l e t us c o n s i d e r the d e t a i l s of generating the s t a t i s t i c a l d e s i r e the sequence to have. As emphasis here discussion simulator based on statistical environment i s the one assumed but that we use examined by R.H. statistics; has an from 0 to 2n. angle The uniformly in mobile-radio [7]. no d i r e c t signal distributed envelope from 0 to 2w then Rayleigh d i s t r i b u t e d . Furthermore, monopole is used the each assumed the when a received that the vertical 0 [1 - (f/f )2]-i/2, D D 0, by to the envelope i s S 0 of statistically power s p e c t r a l d e n s i t y of S(f) = where S is component, d i s t r i b u t e d , and phase i s u n i f o r m l y Rayleigh-fading and showed that the amplitude of is antenna It of a r r i v a l t h a t i s u n i f o r m l y d i s t r i b u t e d phases of the a r r i v i n g waves are independent. C l a r k e the counterparts. f o r the Clarke that the r e c e i v e d s i g n a l c o n t a i n s we following i n s t e a d c o n s i s t s e n t i r e l y of i n d i r e c t components, which be that communication. The continuous-time model fading i n t r o d u c t i o n , the of course employs t h e i r d i s c r e t e - t i m e The the properties s t a t e d in the i s on m o b i l e - r a d i o is interference. i s a constant and f_ i s the Doppler frequency, (3.1.1) given 71 f In equation (3.1.2) (3.1.2) v i s the v e h i c l e speed and wavelength. The use d i f f e r e n t power spectral = v/X. of a spectral densities carrier d i f f e r e n t antenna leads only density; that X i s the result see from [10] a for the variety to a power of antenna conf i g u r a t i o n s . Several other statistical properties f a d i n g envelope have been d e r i v e d i n the i s shown that the average d u r a t i o n of the of the Rayleigh- l i t e r a t u r e . In [12] i t fades below the level p is exp(p ) - 1 2 Tip) = , \/2T and that level N(p) The quantity amplitude p of value of the in the D V T T T envelope crosses the is f p exp(-p ). (3.1.4) 2 equations (3.1.3) and (3.1.4) is fading envelope measured r e l a t i v e to the . = the RMS envelope amplitude . RMS Field = the envelope, i . e . p tests experimentally been f p the average r a t e at which p with a p o s i t i v e slope (3.1.3) verified value of the described in (3.1.5) envelope the l i t e r a t u r e have v e r i f i e d that the above r e s u l t s hold q u i t e w e l l . that the short-term s t a t i s t i c s of the envelope are well described by the Rayleigh [ 7 , 2 2 ] , and experimental r e s u l t s i n [11] and [22] It has fading distribution show that the 72 theoretical formulas (3.1.3) and average d u r a t i o n Let us sequence. The sequence program was in of fades and now return s e c t i o n of taken [24] to the the verbatim on 4096, is The used value 0 that a this computer Rayleigh- independent give the sequence the shaping i s done by m u l t i p l i c a t i o n by a t r a n s l a t i o n i n t o the i n a simulated of S to number of p o i n t s Note that the n o r m a l i z a t i o n actual fact fading generates from [24]. The the frequency domain followed resulting the be generated by adding two d e s i r e d spectrum (3.1.1). The domain u s i n g an FFT. crossings. of that the sequences i n quadrature (see Chapter 7 of [ 1 8 ] ) . A shaping f i l t e r in the generation simulator based d i s t r i b u t e d sequence can Gaussian-distributed the r a t e of l e v e l almost is (3.1.4) adequately p r e d i c t i n the FFT was time set to b i t rate of R = 4096 b i t s / s e c . of the i n equation fading sequence makes the (3.1.1) immaterial: i t was set to u n i t y f o r convenience. To check the o p e r a t i o n of the fading-sequence generator, a sequence was generated that was 500 statistical quantities on First, In c d f , and fading computed and Figure 3.1 and several t h i s sequence were computed. the cumulative d i s t r i b u t i o n f u n c t i o n sequence was cdf. based seconds long, compared with the (cdf) of the desired fading Rayleigh the s o l i d l i n e i s the t h e o r e t i c a l R a y l e i g h the p l o t t e d p o i n t s are the values computed from sequence. C l e a r l y the d i s t r i b u t i o n of the output of fading-sequence generator i s very c l o s e to the d e s i r e d d i s t r i b u t i o n . A l s o computed from the were the average fade d u r a t i o n and 500-second-long the the Rayleigh sequence the l e v e l - c r o s s i n g r a t e . The 73 Level p i n dB r e l a t i v e to the RMS Figure 3.1: Rayleigh cdf value. 74 theoretical r e s u l t s given by equations graphed as s o l i d l i n e s i n F i g u r e s 3.2 curves i n these Doppler two figures frequency. The As one t h e o r e t i c a l and 3.1.4 The 3.3 been also r e s p e c t i v e l y ; the normalized can normalized see, the the measured r e s u l t s Simulation and to agreement block M = 0, 1, 2, 20.5, 25.5 dB. sizes 9; Hz; the computed Doppler between the is excellent. used to compute the N = 63, 127, 255, 511, f o r Doppler f r e q u e n c i e s and In S e c t i o n 3.1.2 check unity results s i m u l a t i o n program was for to unity of block e r r o r , P (M,N), f o r NCFSK modulation. The run (3.1.4) are p l o t t e d p o i n t s are the values from the f a d i n g sequence, frequency. have (3.1.3) and f o r average SNR's y the use statistical of a 95% accuracy 0 f 10, was 2047; f o r = 10.5, n = 5, the program 1023, confidence of probability 15.5, 15, , 35 interval to simulations was d e s c r i b e d . T e s t s were run to determine the number of t r i a l s , required to make this meaningful conclusions reasonable c r i t e r i o n was less than about SNR confidence pattern to 7, 0 could to make the drawn. 95% be met because uniformly for a s i m u l a t i o n . The that felt that a was confidence hence many with fixed i n t e r v a l s become l a r g e r with and It small interval g holds because at low unity, be sufficiently 10% of the computed sample mean P (M,N). T h i s c r i t e r i o n c o u l d not average interval n, respect to number of t r i a l s increasing SNR. the the This SNR's the p r o b a b i l i t i e s are c l o s e errors will occur l a r g e number of e r r o r s ensures good during the statistical ~" -30.0 Level 1 -2S.0 p Figure Level p Figure 1 -20.0 i n dB 3.2: i n dB 3.3: 1 -1S.0 1 -10.0 relative Average t o the fade relative 1 -5.0 RMS time t o t h e RMS Level-crossing rate 1 0. value T(p). value 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 a r e s m a l l , examining rare events, the s i m u l a t i o n at low were used, and so not enough e r r o r s occur to obtain SNR's. the i . e . we are s t a t i s t i c s that are as good during as those When sequences 60 t o 90 seconds long per t r i a l tests showed 10 ^ n < 15 was s u f f i c i e n t that taking n in the t o meet the c r i t e r i o n given range above at 7o = 25 dB. The b i t - e r r o r p r o b a b i l i t y was a l s o computed, and as anticipated p agreed = 1/(2 + 7 ) given simulation well with results Figure SNR 7 0 3.4 theoretical (2.1.9). result Some a r e presented here i n g r a p h i c a l idea i s not t o c a t a l o g a l l the give r e p r e s e n t a t i v e the f o r NCFSK i n equation 0 the the it results produced, of form; but to examples. gives P (0,127) as a f u n c t i o n of the average S f o r a l l four Doppler f r e q u e n c i e s , and with a l l other parameters h e l d f i x e d . The p l o t t e d p o i n t s a r e those produced by the simulation, using and quadratic curves, two interpolation. other curve i s the value using the curves curves connecting In addition are given f methods shows the p r o b a b i l i t y of block f by error The lower slow f a d i n g , computed 1 - (1 - p ) 1 2 7 f that has a that would bit-error 0 3.4 we see that the p r o b a b i l i t y of block the simulation anticipates that error program i s l a r g e r than the value computed under the assumption of very one four = 1/(2 + 7 ) . From F i g u r e computed these of Chapter 2. The upper curve r e s u l t on an independent-error channel probability p to for reference. of P (0,127) f o r very the approximate them a r e p l o t t e d allowing slow f a d i n g . faster Intuitively f a d i n g should have an P r o b a b i l i t y of block e r r o r P ( 0 , 1 2 7 ) . g LL 78 adverse e f f e c t on confirmed. It is the performance, further i n c r e a s e s with the Doppler worse the and supported frequency performance. this conjecture is by the f a c t that P (M,N) g f , i.e. the D fading the appears to be l e s s s e n s i t i v e to changes i n f faster the However, the performance R for larger of f , e.g. the curves f o r 20.5 and 25.5 Hz are c l o s e r Q values together than are the curves f o r 10.5 and 15.5 Hz. A l s o , the p r o b a b i l i t y of block e r r o r i s s m a l l e r than that on a with the same b i t - e r r o r Figure different that 3.5 channel rate. gives the error block lengths N. Comparison the random-error deterioration of probability with P (0,N) f o r g Figure 2.3 shows performance with i n c r e a s i n g block l e n g t h i s worse f o r the s i m u l a t i o n r e s u l t s than i t is f o r the case of very slow f a d i n g . F i n a l l y , F i g u r e 3.6 shows P (M,63) f o r s e v e r a l v a l u e s of M g at Doppler frequency 15.5 Hz. For M ^ 1, P have a simple dependence on y curves for different 0 values when 7 0 s is does not appear t o large, of M are not s t r a i g h t i . e . the for large SNR's, as they are i n the case of very slow f a d i n g (see Figure 2.4). T h i s behavior suggests that i t might be more d i f f i c u l t to d e s c r i b e a n a l y t i c a l l y the curves f o r M > 1 than i t was when the f a d i n g was very slow. Average s i g n a l - t o - n o i s e F i g u r e 3.5: ratio r 0 in dB. P (0,N) for d i f f e r e n t block s i z e s at s 15.5 Hz. 80 F i g u r e 3.6: P (M,63) f o r M = 0, 1 , 2, 3 at S 15.5 Hz. 81 3.2 D e r i v a t i o n of the e m p i r i c a l 3.2.1 formula Introduction The purpose of this section i s to develop an empirical formula r e l a t i n g the r e s u l t s of the computer s i m u l a t i o n s to the equations of Chapter usefulness would r e s u l t s that without be would actually 2. I f such a formula c o u l d be obvious: be we obtained running could by easily the found, its predict the simulation the program. The upshot would be an enormous saving i n computer time, while a l l o w i n g us to a more realistic we compute value of the p r o b a b i l i t y of block e r r o r i s p r o v i d e d under the simplicity program shall to the approximation assumption restrict of very slow than fading. For o u r s e l v e s to the case M = 0, i . e . of P (0,N). As we shall see, a simple s model allows the d e r i v a t i o n of an e m p i r i c a l q u i t e w e l l . We 3.2.2 formula that works s t a r t by d e s c r i b i n g t h i s model. The model Given a b l o c k of N b i t s , number we divide this block the sub-blocks Furthermore, reasonable relative a of sub-blocks, each of l e n g t h x b i t s . The h y p o t h e s i s i s that by choosing the s i z e of the sub-blocks c o r r e c t l y , treat into i f the to to approximately approximate though they are small sub-blocks assume the as that the sub-block constant over fading duration the were process sub-block. the p r o b a b i l i t y that each sub-block may independent. enough, that we it is the Thus is seems so slow SNR is we may correct by 82 using the r e s u l t s f o r very slow f a d i n g . Then, i n the notation of Chapter 2, the p r o b a b i l i t y that each sub-block i s c o r r e c t i s P(0,x;r), be where r = 2/y . Because the sub-blocks are assumed to 0 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 to o b t a i n the p r o b a b i l i t y that the o r i g i n a l block c o r r e c t . Since there are N/x sub-blocks we 1 - P(0,x;r) to approximate s h a l l now out that due the formula however, if the l e d to i t can The must be chosen i n order integer our how the Recall i . e . the that, f , Note b i t s / s e c and f D it can is be f D that must the on necessarily of the 2 model; that fading size The rate do not x restrict allowed the block consider, units i s in Hertz. the sub-block ratio of we L for s i z e N, the b i t r a t e R. 7, 0 To define P (0,N) s on the reduce the the ratio are b i t s when R i s in s single quantity relative be this dependence of P (0,N) on R s p e c i f i e d e n t i r e l y by the only turns s i z e of the sub-blocks may besides and D number of v a r i a b l e s we D it i s not program. We d e r i v a t i o n s of Chapter frequency L = R/f . If We to make (3.2.1) y i e l d the p r o b a b i l i t y w i l l depend on the average s i g n a l - t o - n o i s e Doppler e r r o r , P (0,N). description simulation values, n o n - i n t e g r a l . The possibility. block (3.2.1) in d e t a i l . i s to d i s c o v e r g to of ignored. P (0,N) computed by the x formula formula works w e l l , the a c t u a l reasoning problem now be in the is (3.2.1) (3.2.1) works w e l l , t h i s to the reasons given of N b i t s N / x probability i n v e s t i g a t e formula use together L and because to the b i t r a t e that 83 determines the parameters error are proportional probability held to the fixed. Doppler P (0,N) when s Since the the fading f [see frequency D other rate equation (3.1.4)], the e r r o r p r o b a b i l i t y P (0,N) remains constant when R s and f change D by fundamental block channel for the same factor. We think of L l e n g t h that helps to c h a r a c t e r i z e the a given R and f . We n is as a fading a l s o introduce a q u a n t i t y d, which i s d e f i n e d by the requirement that 1 - P(0,x;r) where x = L/d. We N / x = P (0,N) (3.2.2) s 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 d i v i d e L to o b t a i n the s i z e of the Suppose we block size i . e . we The are given the f o l l o w i n g three N, the q u a n t i t y L = R / f , only quantity we must now the previously determined corresponding by value of equation (3.2.1). The parameters N, L, and thesis, any change Doppler frequency f , D the (3.2.2), to apply y 7• 0 in f« although D L simulations is Hence we due shall P. g d, as f o r then we can substitute this (Since R was 0l formula divisor d i v i s o r c o u l d t h e o r e t i c a l l y change b i t s / s e c d u r i n g the computer with the the average SNR know in order compute the sub-block s i z e x = L/d and three parameters: are given enough i n f o r m a t i o n to s p e c i f y a value of (3.2.1) i s into and D sub-blocks. directly with all h e l d f i x e d at 4096 performed for this s o l e l y to a change i n the r e f e r to the change in d i t should be remembered that the r e s u l t s we s h a l l d e r i v e here do not depend on the p a r t i c u l a r b i t r a t e used in the s i m u l a t i o n s . ) The usefulness of the formula (3.2.1) 84 depends largely on how d f l u c t u a t e s with N, f , and 7 : D simpler the r e l a t i o n s h i p , the more u s e f u l the formula. s h a l l see, the d i v i s o r d i s almost of N and has a simple with N and f to two those D on j . dependence that we and shall use focus curve e m p i r i c a l r e l a t i o n s h i p between d and 3 . 2 . 3 Numerical The step q u a n t i t a t i v e was by equation sizes, in little respect characterizing i t s fitting to find an 7 . 0 making to compute, f o r the ( 3 . 2 . 2 ) 4 n results first produced on we f , and s h a l l assume i t i s constant with We 0 As In f a c t , d changes so 0 parameters, dependence on 7 . independent the 0 our each of empirical the formula values of P s i m u l a t i o n program, the d i v i s o r d that makes h o l d . Since s i m u l a t i o n s were run f o r Doppler frequencies, and 7 average block 6 SNR's, P was g computed f o r 6x4x7 = 168 d i f f e r e n t parameter combinations. procedure for s o l v e equation for a ( 3 . 2 . 2 ) ( 3 . 2 . 2 ) value f o r the value of x that of makes it P , and then to set d = L/x. i s a complicated n o n l i n e a r equation numerically. As a check on the s o l u t i o n s , two numerical methods were bisection method. left-hand side approximations used: During of Newton's these ( 3 . 2 . 2 ) method numerical was ( 3 . 2 . 1 ) Since to evaluated not be different a simple computations, of S e c t i o n 2 . 2 . To f u r t h e r c l a r i f y done here, the e x p r e s s i o n i n and to hold i t was p o s s i b l e to solve i t a n a l y t i c a l l y , and the s o l u t i o n had found The computing the 1 6 8 corresponding d i v i s o r s was specific equation s using the the what i s being has been graphed i n F i g u r e 85 3.7 as a f u n c t i o n of x f o r N = 255 and the average s i g n a l - t o - n o i s e r a t i o . One (3.2.2) f o r a given P Figure 3.7 at by g the drawing f o r s e v e r a l v a l u e s of can a f i n d the s o l u t i o n of horizontal appropriate l e v e l u n t i l c o r r e c t curve, and by then extending a l i n e the corresponding illustrated obtained value of 3.7 for in Figure at f = 15.5 D y we find figure causing (3.2.2) This the Hz and program. From the equation x. line i t intersects downward procedure value across to find has been P (0,255) = 0.246, g = 25 dB using the s i m u l a t i o n 0 that the to be s a t i s f i e d sub-block size i s x = 15 b i t s (the numerical methods, which are of course much more a c c u r a t e the graphical divisor method shown the here, y i e l d x = 14.96 than bits). The i n t h i s case i s d = L/x = R/(x - f ) D = 4096.0/(15.0x15.5) = 17.6. There were s e v e r a l d i f f i c u l t i e s i n the numerical j u s t d e s c r i b e d , d i f f i c u l t i e s which w i l l now One d i f f i c u l t y occurs when the SNR s i z e l a r g e . In t h i s parameter range the error is close to unity, program y i e l d e d a value P i.e. the simulation g that is for = 1.0 program block f o r the d u r a t i o n of because and the computations be d i s c u s s e d . i s small and the block probability of block in many cases the s i m u l a t i o n to s i n g l e - p r e c i s i o n accuracy, d i d not r e c o r d a s i n g l e simulation. small SNR's the formula of A correct problem (3.2.1) y i e l d s a value i s very c l o s e to u n i t y f o r a wide range of x v a l u e s , relatively insensitive to arises changes i n x (see F i g u r e i.e. 3.7). Sub-block s i z e x i n b i t s . F i g u r e 3.7: Formula (3.2.1) as a f u n c t i o n 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 s o l u t i o n of equation i s u n r e l i a b l e when P annoying when formula based SNR's will s = 1.0. On the one hand, t h i s trying, problem is as we are here, to d e r i v e an e m p i r i c a l on (3.2.1), because the v a l u e s have (3.2.2) of x f o r small no c o n s i s t e n t t r e n d . On the other hand, t h i s behavior works i n our favour when the purpose i s to approximate P s u s i n g formula allows a (3.2.1), s i n c e even an i n a c c u r a t e value good approximation of x t o the p r o b a b i l i t y of block e r r o r when i t i s near u n i t y . A l s o , we a r e not g e n e r a l l y i n t e r e s t e d i n the case when the b l o c k - e r r o r r a t e i s near u n i t y . Another d i f f i c u l t y (3.2.1) when x i s s m a l l . As can be seen e x p r e s s i o n i n (3.2.1) decreases stems from the behavior has a maximum f o r x below t h i s value a r i s e s because as the average s i z e x decreases, and f o r y 0 5 of expression from F i g u r e 3.7, the near x = 2 bits, and (see F i g u r e 3.7). The problem SNR y increases 0 near the sub-block 35 dB the va'lue of x i s about b i t s or so, i . e . near the peaks of the curves i n F i g u r e 3.7. If now 7 is 0 corresponding curve, and Consequently, increased further, then t o the p r o b a b i l i t y P equation (3.2.2) no horizontal line l i e s above the peak i n the g longer has a solution. when the SNR becomes l a r g e the numerical methods tend to "lock i n " at x = 2 b i t s . T h i s formula the (3.2.1) might not work e q u i v a l e n t l y , f o r small sub-block behavior well suggests that f o r l a r g e SNR's ( o r , s i z e s ) . Since we s h a l l not be working with SNR's g r e a t e r than 35 dB we do not need to worry very much about the p o s s i b l e d i f f i c u l t i e s above 35 dB. The method of d e a l i n g with the above-mentioned problems 88 was simply to r e j e c t those values of x (and hence d) that obviously wrong. reader, but suitable it This was procedure employed criterion. in (Also, f a c t that our s o l e purpose may seem the one were a r b i t r a r y to the absence of any other should not l o s e s i g h t of the here is to derive an empirical formula t h a t a l l o w s us t o p r e d i c t a c c u r a t e l y the outcome of our simulations — then the i f the formula we end up with does the job w e l l , means by p o s t e r i o r i . ) Of the which listed; decided to r e j e c t the values that were r e j e c t e d behavior are justified 30, a to the leaving 138 replaced by t a b l e has been organized to demonstrate c l e a r l y the of (N, f , 7 ) 0 d with the little frequency with in been the parameters divisor either Doppler the block s i z e N or the ratio 7 . For a f i x e d 7 0 s l i g h t l y with i n c r e a s i n g N and often three e v i d e n t from the t a b l e that the f , but does change s u b s t a n t i a l l y signal-to-noise decrease changes have on which i t depends. i s immediately changes is it f o r subsequent a n a l y s i s . In Table IV the d i v i s o r s are dashes. The It obtained 168 d i v i s o r s computed, c o r r e s p o n d i n g 168 data p o i n t s P , i t was divisors we interrupted by what appear 0 with the average the d i v i s o r seems to f , although t h i s trend to be statistical f l u c t u a t i o n s . There i s a much stronger t r e n d i n the change of d with 7o. Since we d e s i r e an e m p i r i c a l formula that i s as as possible, and since mentioned c o u l d make i t dependence of d on independent of N and N the hard and f , and statistical to fluctuations characterize f , i t was to attempt simple correctly just the decided to regard d as to f i n d an approximate f 7o (dB) 5 10 15 20 D (Hz) N (bits) 10.5 15.5 20.5 25.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 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 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 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: D i v i s o r s (cont'd next page) f N 7o (dB) ( b i t s ) 25 30 35 D (Hz) 10.5 15.5 20.5 25.5 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 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 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 Table IV: D i v i s o r s 60.241 51.842 53.802 48.700 91 r e l a t i o n s h i p between d and 7 0 alone: d = F(A,,A ,...,A ;7 )• 2 In in equation k (3.2.3), the c o e f f i c i e n t s the f u n c t i o n a l r e l a t i o n s h i p The procedure numerical F values of the graphs. Then, the parameters 2, 0 a suitable was p o s i t e d on F and the the basis of A.^ were chosen t o o b t a i n a l e a s t f i t to the 138 data p o i n t s . precise, are f i x e d parameters ± parameters was as f o l l o w s . F i r s t , a f u n c t i o n a l form f o r F more A that holds between d and 7 . c a r r i e d out to determine specific squares (3.2.3) 0 To make the formulation l e t (701, d i ) denote the data p o i n t s f o r i = 1, 138. We then seek the parameters A^ that minimize the expression 138 138 Z r? = Z [ F ( A , , . . . , A ; 7 ) - d ] k i=1 0i i=1 where r ^ = F ( A , , . . . , A ; y i ) - 6± i s c a l l e d k different 0 least F f i t . The f i r s t squares parameters maximizing A-^. to c a r r y out Two the least program, NL2S0L, was best s u i t e d f o r the partial derivatives with respect to the The second program, DGRADX, was a program f o r g e n e r a l n o n l i n e a r f u n c t i o n s , and specifically was not tailored t o the l e a s t squares problem. Thus to minimize the appearing in (3.2.4), negative of the summation, along partial residual. m i n i m i z a t i o n , as i t r e q u i r e d only the coding of and i t s f i r s t summation the computer programs, both of which were made a v a i l a b l e by the UBC Computing Centre, were used squares (3.2.4) 2 ± i t was necessary with i t s first d e r i v a t i v e s with respect t o the parameters. t o code the and second As a check 92 on the numerical r e s u l t s , functional identical form F both that i n a l l cases programs F N = 255 and f frequencies = 10.5 D considered some s o r t . Two d i f f e r e n t (a) 2 The of u n i t s of 7 o 3 0 = A, of y f o r the 0 Hz. The shape of the other here, functional F(A,,A ,A ;7 ) be working). function curve, which i s much the same f o r the Doppler each must look l i k e , the d i v i s o r has been graphed i n F i g u r e 3.8 as a values for (the d i f f e r e n c e s were so small as to show what the f u n c t i o n specific run was t r i e d . The r e s u l t s were almost n e g l i g i b l e to the accuracy t h a t we were To were block sizes and suggests a parabola of forms were t r i e d : +A 3 2 7 o were taken t o be d e c i b e l s . The computed values the parameters were: A, = 5.148 A = 2.237X10" A = 4.102. 5 2 3 With t h i s c h o i c e of parameters, the minimized value of (3.2.4) was 578.0. (b) F(A,,A ,A ;7o) 2 3 = A, + A e x p ( A 7 ) 2 3 0 The computed values of the parameters were: A, = 2.850 A = 6.435X10" A = 1.248x10" . 1 2 1 3 The minimized The fit value of (3.2.4) was 557.9. e x p o n e n t i a l curve i n (b) p r o v i d e s a slightly better than does the power law i n ( a ) . Both curves a r e p l o t t e d i n F i g u r e 3.9, along with the data shown i n Figure 3.8. Clearly F i g u r e 3.8: P l o t of t h e d i v i s o r as a f u n c t i o n r 0 a t N = 255 and f = 10.5 Hz. D of 94 F i g u r e 3.9: P l o t s of the c u r v e s that have been f i t t e d to the data i n t a b l e IV. 95 the f i t i s good no matter which one of the two f u n c t i o n a l forms we use. At this point we have empirical formula. A computer (3.2.1), using divisor exponential to evaluate f i t i n (b) above t o f i n d the 0 were compared with the s i m u l a t i o n r e s u l t s combinations of comparison showed that simulator output the parameters formula (3.2.1) a c c u r a t e l y p r e d i c t s the To g measure f p , and all the P (0,N). N, for y; accuracy of the e m p i r i c a l value program was w r i t t e n f o r a s p e c i f i e d average SNR 7 . The r e s u l t s produced by the program 168 the completed the d e r i v a t i o n of our Q quantitatively formula, the average of the the absolute of the percentage e r r o r was taken over the 168 v a l u e s of P (0,N) computed by g average was only the simulation about program. The calculated 1.7%, i n d i c a t i n g the high accuracy of the p r e d i c t e d v a l u e s . Note that the average was taken over a l l 168 probabilities even though the e m p i r i c a l formula was based on a subset of 138 p r o b a b i l i t i e s . I t i s , of course, the purpose of the e m p i r i c a l of the formula to allow us to p r e d i c t what the output simulation different from program those reasonable assumption parameters N, have that P g be D predict range of parameter already depends 3.11 are values used. I f we make the smoothly on the 0 empirical the output formula of derived here will the s i m u l a t o r over a wide values. Presented now are some g r a p h i c a l and f o r parameter f , and y t we can conclude on the b a s i s of the above r e s u l t s that the accurately we would similar to Figures examples. Figures 3.10 3.4 and 3.5 r e s p e c t i v e l y , 96 except here the s o l i d l i n e s were p l o t t e d u s i n g formula The agreement between the p r e d i c t e d by formula simulator results (3.2.1) i s o b v i o u s l y good. and the (3.2.1). values L6 F i g u r e 3.11: P (0,N) f o r d i f f e r e n t block s i z e s at using the e m p i r i c a l formula. s 15.5 Hz oo 99 Chapter 4 4.1 Conclusions In this thesis, p r o b a b i l i t y of block presence of Chapter very computing Gaussian noise of were very the numerical slow modulation methods technique e x i s t that allow is the accurate i s that the computation of P (M,N) f o r f approximately to the computation M > 0 of P (0,N) that the error approximations i s n e g l i g i b l e over a Also considered block-error wide that be reduced rigorous error making these by range of parameter i n Chapter 2 i s the computation of the r a t e when L-branch s e l e c t i o n d i v e r s i t y i s employed; formulas d e r i v e d are u s e f u l f o r small values shown conclusion and that of a f incurred FSK, approximation can m u l t i p l i c a t i v e c o r r e c t i o n f a c t o r . Furthermore, show i s very non-coherent f the fading; the e f f e c t s of r e l a x i n g the assumption of of the b l o c k - e r r o r p r o b a b i l i t y P (M,N). An important values. the examined. r e s u l t s of Chapter 2 show that when the f a d i n g and bounds the fading. The slow white for f a d i n g channel i n on the s p e c i a l case 3 considered slow methods e r r o r on a R a y l e i g h additive Chapter 2 focussed several the probability of block of L. It i s e r r o r , considered f u n c t i o n of the average s i g n a l - t o - n o i s e r a t i o y , 0 as a f a l l s o f f as 1/70In Chapter 3 a more r e a l i s t i c channel i s assumed, one i n which the SNR i s not n e c e s s a r i l y constant The block-error simulations over an e n t i r e r a t e must now be estimated by carried out for this thesis block. simulation; the were performed by 100 digital were computer. The s t a t i s t i c a l p r o p e r t i e s of chosen to r e s u l t s produced properties fading, that the the simulator be those of the m o b i l e - r a d i o environment. The by the s i m u l a t o r had l a r g e l y one worse simulation results themselves; the the qualitative i n t u i t i v e l y expects, e.g. the f a s t e r the the system were not primary performance. considered function of to the However, be the an end in simulator was to produce a s u f f i c i e n t amount of data t o t e s t a s p e c i f i c model of the fading channel formula based predicting when on t h i s model very was slow f a d i n g i s not assumed. A shown to be successful in the s i m u l a t o r output. Thus the formula of Chapter p r o v i d e s a simple method of computing a more r e a l i s t i c the p r o b a b i l i t y of block e r r o r assumption of very slow f a d i n g . than is available 3 value of under the 101 4. 2 Future work There are s e v e r a l areas i n which the work of t h i s thesis c o u l d be extended. Almost a l l of the formulas d e r i v e d here for the case of non-coherent FSK modulation; t h i s modulation technique was c o n s i d e r e d because equations and because often i t y i e l d s the i s probably Attempts should be most tractable i t i s the modulation scheme a n a l y s e d most i n the r e l e v a n t l i t e r a t u r e mentioned are a direct made to other modulation techniques are (of course, the second reason consequence of the first). f i n d u s e f u l approximations when used, although this may be di f f i c u l t . Furthermore, the r e s u l t s of Chapter 3 should be to cover the case M > 0 as w e l l . I t i s not c l e a r would entail t h i s extension manner. extended whether this s i g n i f i c a n t l y more complex equations, or whether could be accomplished in a straightforward 1 02 References [1] Abramowitz, M. and Stegun, I.A., eds. Handbook of Mathematical F u n c t i o n s , Dover P u b l i c a t i o n s , New York, 1972. [2] Arredondo, G.A. e t a l . "A m u l t i p a t h f a d i n g s i m u l a t o r f o r mobile r a d i o , " IEEE Trans, on Commun., v o l . COM-21, no. 11, pp. 1325-1328, November 1973. [3] and Smith, J . I . "Voice and data t r a n s m i s s i o n i n a mobile r a d i o channel a t 850 MHz," IEEE Trans, on V e h i c u l a r Technology, v o l . VT-26, no. 1, pp. 88-93, February 1977. [4] Bodtmann, W.F. and A r n o l d , 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 S u l l i v a n , D.D. " E r r o r s 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 m o b i l e - r a d i o r e c e p t i o n , " B e l l System T e c h n i c a l J o u r n a l , v o l . 47, no. 6, pp. 957-1000, July-August 1968. [8] Conway, J.B. F u n c t i o n s of One Complex V a r i a b l e , S p r i n g e r V e r l a g , New York, 1973. [9] Eaves, R.E. and Levesque, A.H. " P r o b a b i l i t y of block e r r o r f o r very slow R a y l e i g h f a d i n g i n Gaussian n o i s e , " IEEE Trans. on Commun., v o l . COM-25, no. 3, pp. 368374, March 1977. [10] Gans, M.J. "A power-spectral theory of propagation i n the m o b i l e - r a d i o environment," IEEE Trans, on V e h i c u l a r Technology, v o l . VT-21, no. 1, pp. 27-38, February 1972. [11] Gladstone, K.J. and McGeehan, J.P. "Computer s i m u l a t i o n of multipath fading in the land mobile radio environment," IEE P r o c , v o l . 127, P t . 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 f o r r e d u c t i o n of f a s t f a d i n g i n UHF mobile radio systems," IEEE Trans, on V e h i c u l a r Technology, v o l . VT-20, no. 4, pp. 81-92, November 1971. 1 03 [13] Knuth, D.E. The A r t of Computer Programming, Addison-Wesley, 1973. [14] Leung, C. " B i t e r r o r r a t e s of s e l e c t i o n d i v e r s i t y systems in Rayleigh fading channels," I n t . Conf. on Commun., Denver CO., June 1981. [15] M i t r i n o v i c , D.S. A n a l y t i c I n e q u a l i t i e s , [16] Monro, D.M. "Complex d i s c r e t e f a s t F o u r i e r t r a n s f o r m , " A p p l i e d S t a t i s t i c s , v o l . 24, pp. 153-160, 1975. [17] v o l . 1, Springer-Verlag, "Real d i s c r e t e f a s t F o u r i e r t r a n s f o r m , " S t a t i s t i c s , v o l . 25, pp. 166-172, 1976. Applied [18] Papoulis, A. Probability, Random V a r i a b l e s , and S t o c h a s t i c Processes, McGraw-Hill, New York, 1975. [19] Pearson, K., ed. Tables of the Incomplete Beta F u n c t i o n , Cambridge U n i v e r s i t y P r e s s , Cambridge, England, 1948. [20] Pierce, J.N. "Theoretical diversity improvement i n f r e q u e n c y - s h i f t keying," Proceedings of the IRE, vol. 46, no. 5, pp. 903-910, May 1958. [21] Roberts, J.A. and Healy, T . J . "Packet r a d i o performance over slow R a y l e i g h f a d i n g channels," IEEE Trans. on Commun., v o l . COM-28, no. 2, pp. 279-286, February 1980. [22] Reudink, D.O. " P r o p e r t i e s of mobile r a d i o propagation above 400 MHz," IEEE Trans, on V e h i c u l a r 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 m u l t i p a t h fading simulation f o r mobile r a d i o , " IEEE Trans, on V e h i c u l a r Technology, v o l . VT-24, no. 3, pp. 39-40, August 1975. [25] Sundberg, C.E. "Block e r r o r p r o b a b i l i t y f o r noncoherent FSK with d i v e r s i t y f o r very slow R a y l e i g h f a d i n g i n Gaussian n o i s e , " IEEE Trans, on Commun., v o l . COM-29, no. 1, pp. 57-60, January 1981. [26] Sussman, S.M. " S i m p l i f i e d r e l a t i o n s f o r b i t and c h a r a c t e r error probabilities f o r M-ary t r a n s m i s s i o n over Rayleigh fading channels," IEEE Trans, on Commun. Tech., v o l . COM-12, no. 4, pp. 207-209, December 1964. 1 04 [27] Walpole, R.E. and Myers, R.H. P r o b a b i l i t y and S t a t i s t i c s f o r Engineers and S c i e n t i s t s , 2d ed., Macmillan, New York, 1978. [28] Whittaker, Analysis, Cambridge, [29] Wozencraft, J.M. and Jacobs, I.M. P r i n c i p l e s of Communication E n g i n e e r i n g , John Wiley, New York, 1965. E.T. and Watson, G.N. 4th ed., Cambridge England, 1963. A Course of Modern University Press, 1 05 Appendix A T h i s appendix d e t a i l s the computation numerical integration. First . P (0,N) = 1 - 7 o _ 1 f J = 7o- / 1 where p( ) 7 (0,N) = f / [1 ~ p(7>] 0 e d 7 (A.1) {1 - [1 - P ( 7 ) 3 ) e d , N 7 o 7 i n (A.1) g i v e s (1 - [1 - p ( numerical integration. (A.2) infinite, y ) ] ) e y dy. N 7 o Note making quadrature rules exponential i n the integrand contribution indeed (A.2) _ the used f o r t h a t the range of i n t e g r a t i o n i n the difficult. from was application However, suggests "tail" of of the the r a p i d l y that the there was to find usual decreasing is little i n t e g r a l , and t h i s i s the case. Thus, given a maximum a l l o w a b l e e r r o r strategy using c o n s i d e r the c a l c u l a t i o n of (A.2) i s the form of the i n t e g r a l that is f 7 substitution y = / Equation P (M,N) = (1/2) e x p ( - / 2 ) f o r non-coherent FSK. Making the 7 P of a number b (depending on A, 7 o A, the , and N) such that 0 <jj (1 {1 - [1 [1 - pp (( yy )) ]] }} 7 o 7 o N W e e y y dy dy < < A, A, _ _ (A.3) b and then t o compute P (0,N) = f •'o f {1 - [1 - p ( y)] } N 7 o (We ignore f o r the moment the e r r o r integration of the finite e~y dy. involved i n integral in (A.4) the (A.4).) numerical The above 106 s t r a t e g y may appear t o be t r i v i a l , the convergence of i n t e g r a l (A.2) guarantees that lim b -> and because the / {1 - [1 - p ( 7 y ) ] } e " N co J so given h any A > 0 there always e x i s t s a number b such that (1 - [1 - p ( 7 o Y ) ] } e N The point dy = 0, y 0 here is that dy < A. _ y the r a p i d decrease of the integrand ensures that b can be chosen s u f f i c i e n t l y numerical integration over f e a s i b l e . Just as important procedure fixed N for and monotonically finding y the 0 decreasing 0 < f b, the finite to make interval i s the f a c t that there the i n (A.4) is a simple as we now show. Observing that f o r function 1 - [1 - p ( 7 y ) ] 0 N is a f u n c t i o n of y, we have {1 - [1 - p ( 7 y ) ] } e N dy - y 0 $ {1 - small [1 - p ( 7 o b ) ] } / " " e N y dy (A.5) • b / = {1 " Now, given [1 " p ( 7 o b ) ] } e N N b 7 we . any A > 0, i f we choose b such that {1 - [1 - p ( o b ) ] } e ~ then _ b know that (A.3) h o l d s , < A, (A.6) and that the e r r o r i n (A.4) l e s s than A. Note that the l a s t line integrand at y = b. Thus the formulation (A.4) of (A.4) i s convenient coded the integrand evaluated of (A.5) is just is the f o r use on a computer, because once we have f o r the numerical i n t e g r a t i o n , we can use 1 07 this same code as determine a value The a part of a , simple of b that makes (A.6) search true. a c t u a l program used f o r the numerical i n t e g r a t i o n double-precision version of SQUANK, which i s an quadrature r o u t i n e based on Simpson's r u l e . made use, available by the UBC supplied by e r r o r A, the user. t r i e s to Thus meet the e r r o r t o l e r a n c e Combining (A.6) meet an error is the value the then a value f o l l o w i n g procedure: of b is f 2A. f o r the i n t e g r a t i o n of such values 10"". 1.0X10" . Reference to F i g u r e 9 of P (0,N) that we f able meet the s p e c i f i e d e r r o r t o l e r a n c e , we i n the Therefore, i n those cases where been computed c o r r e c t l y w i t h i n f i f t h decimal details of 2.3 shows that SQUANK described here. on is are guaranteed at least two place. computing P (M,N) f using numerical i n t e g r a t i o n when M > 0 are much the same as when M = 0, and not are error have to d e a l with are of f If In the c a l c u l a t i o n s performed f o r t h i s t h e s i s , of A was that P (0,N) has (A.4). been computed with a t o t a l the order The found to meet the s p e c i f i e d e r r o r t o l e r a n c e , we that P (0,N) has smallest digits cannot user). a l l the above g i v e s us the able than to tolerance i s s a t i s f i e d . T h i s same A i s then s u p p l i e d to SQUANK then assured the was i f the user s p e c i f i e s a maximum s u p p l i e d by as the maximum e r r o r t o l e r a n c e less program (the program i n d i c a t e s i f i t a A > 0 i s chosen, and SQUANK adaptive SQUANK w i l l come back with an estimate of the i n t e g r a l w i t h i n A of the true value that This was Computing Centre. SQUANK i s easy to because i t a d a p t i v e l y First technique to are 1 08 Appendix B B.1 No diversity In S e c t i o n 2.2 we defined Q(m,x;r) = r 2 r the q u a n t i t i e s Bj^m+r, 1+x-m) and (B.1 ) Q(m,x;r) = where the a r 2 x r B(m+r,1+x-m), incomplete Beta f u n c t i o n B ( a , b ) i s given y B (a,b) and () = J / t " 3 0 (1 - t ) 1 B(a,b) = B,(a,b). The _ 1 the following (a) (B.2) Q and Q . For sacrifices 0 < r < 1. Since very little the a n a l y s i s simpler satisfy 0 r = 2/y , < *, Q the . Thus t h i s in a p r a c t i c a l because there are restriction restriction sense, but i t makes fewer s p e c i a l cases consider. (b) x i s r e a l , and (c) m i s an x > i n t e g e r , and 1. 0 ^ m < x. e(m,x;r) = Q(m,x;r) - Q(m,x;r). Then using and of conditions: 0 < r < 1 i m p l i e s that 2 < y (B.1) the r e s t assume that the parameters r , x, and m r i s r e a l , and to dt, purpose of t h i s appendix i s to d e r i v e bound on the d i f f e r e n c e between t h i s appendix we Let b by (B.2), we have the definitions 109 e(m,x;r) = ( ) r 2 x We consider the j r t two m + r _ cases (1 - t ) 1 m = 0 reason f o r breaking the problem the exponent of t m + r - x _ m dt > 0. and m > 1 s e p a r a t e l y . The i n t o these two cases i s because i s negative f o r m = 0 and 1 (B.3) is positive for m £ 1. CASE 1: m = 0. For m = 0 equation (B.3) e(0,x;r) = r 2 Since r - 1 < 0, it reduces to r | J hu t follows r - (1 - t ) 1 that t r _ 1 x dt. < (l/2) r _ 1 = 2 for 1 _ r t C [1/2,1], i . e . f o r t i n the range of i n t e g r a t i o n . Then 0 < e(0,x;r) < r 2 r I/ 2 _r 1 _ r d(1 - tt )) xx dt (B.4) =2r/ (1-t) dt. x Making the s u b s t i t u t i o n u = 1 - t i n the l a s t fh (1 - t ) x dt = J Substitution of (B.5) f Jo u X du = into (B.4) 1 2 1 + x • (1+x) i n t e g r a l , we get - (B 5) yields r 0 < e(0,x;r) < . 2 X (1+x) ( B > 6 ) 1 10 CASE 2: m £ 1. In t h i s case m+r-1 > 0, and so f o r t C [1/2,1] t < 1 h o l d s . Then inequality (B.3) becomes 0 < e(m,x;r) = ( ) r 2 J x r t 1 * t) r f 2T x the r 2 h r m + r " l (1 / ~ (1 - t ) l t)X_I " m x _ m dt dt (B.7) u " du u 3 x m 0 r 2 1+x-m 2 , > (1+x-m) 0 Summarizing r i n e q u a l i t i e s (B.6) and (B.7), r 2 0 < e (m, x ; r ) < (1+x) X m = 0 (B.8a) m ^ 1 . (fl.Bb) r 2 1 [Ij s Of l+x-m ' 2 r ' (1+x-m) 9 course, i t would be n i c e to have a s i n g l e bound f o r the two cases m = 0 and m > 1. We can o b t a i n simple observation that the such a bound by making the inequality 2 r < 2 holds for 0 < r < 1, and so i t f o l l o w s from (B.8b) that 0 < e(m,x;r) < f) W f o r m > 1. Note that (B.9) X 2 x-m ( 1 + X _ f o r m > 0. The p r i c e we pay f o r the convenience of a s i n g l e formula that holds bound ) (B.9) reduces t o (B.8a) i n the case m = 0. Thus i n e q u a l i t y (B.9) holds the m for m > 0 is that f o r m > 1 i s worse. However, the bound i n (B.9) is l a r g e r by a t most a f a c t o r of 2, and as the examples i n S e c t i o n 111 2.2 demonstrate, the bound i n (B.9) i s u s u a l l y so small that factor of 2 w i l l not i n f l u e n c e our o p i n i o n the d i f f e r e n c e between Q and Q a of whether or not i s negligible. B.2 D i v e r s i t y We want to o b t a i n a bound on the d i f f e r e n c e and P, „, which are d e f i n e d by equations (2.4.7) and r e s p e c t i v e l y . I t i s easy to see that Beta function between replacing the i n (2.4.7) by the Beta f u n c t i o n p a > c (2.4.8) incomplete i s equivalent to extending the upper l i m i t of i n t e g r a t i o n i n (2.4.4) from 1/2 to 1. Thus we may write At P ~ d,c d,c P = (B.10) i = L r 2 r Z ( A f m=0 \ / J %t m+r ~ (1 - t ) l where r and x are as i n S e c t i o n integer. For L = 1 the B.1 x _ m [1 - ( 2 t ) ] r above, and For the case L > 1, we can bound the the integrand (1 + y ) r example, < 1 + ry and an Section B.1. L—1 [1 - (2t) ] f a c t o r of that the r e s u l t s of S e c t i o n B.1 are start by y = 1, 1/2 < t < 1, |1 - ( 2 t ) | < r . I t now r is noting that the i n e q u a l i t y holds f o r -1 < y * 0 and 0 < r < 1 (see, f o r [ 1 5 ] ) . Taking 0 < r < 1 hence i n such a way We L > 1 of r applicable. dt, i n t e g r a l reduces to that of the non- d i v e r s i t y case, and we can apply the r e s u l t s still L _ 1 we we have have follows 2 r < 1 + r. (2t) < 2 r that r Then if < 1 + r , and 11 2 t m+r-l < L r 2 L r The last x _ m _ JC k L r 2 { 1 t ~ m+r { ~ (2t) ] ] r (1 - t ) l x _ m L _ 1 dt dt (1+x-m) preceding r e s u l t d ,c x-m J inequality P t) with p d,c above (B.10) follows (B.9). Using the yields * =0 = 'U)2 % m from L r x _ m 1 (1+x-m) (B. 1 1 ) 3 11 Appendix C The purpose mathematical of this appendix derivations is of the r e s u l t s to given present the i n S e c t i o n 2.3. We s h a l l without mention use the n o t a t i o n of the t h e s i s proper, with the exception that we s h a l l r e p l a c e the q u a n t i t y r = 2/7 0 by the complex v a r i a b l e z throughout t h i s appendix. C.1 E x i s t e n c e We of the expansions begin by showing that Q(m,x;z) and Q(m,x;z), which are d e f i n e d by Q(m,x;z) = z 2" B^dn+z, 1 +x-m) and (C.1) Q(m,x;z) = z 2 B(m+z,1+x-m) , Z have s e r i e s expansions CO Q(m,x;z) = Z q.(m,x) z i =0 and (C.2) Q(m,x;z) = that h o l d for actuality be equations log(2) replaced |z| < 1 larger, (the region but (C.1) we d e f i n e i s real; by any Z q.(m,x) z i =0 2 this Z by this same real number. of does 2 Z not = definition incomplete Beta f u n c t i o n , we have By convergence concern may i n u s ) . In exp{z l o g ( 2 ) } , where w i l l be used i f 2 i s the d e f i n i t i o n of the 11 4 B (m+z, 1+x-m) = y J where and C 0 ~ m+z t l (1 - t ) X _ m dt , (C.3) i t i s assumed that m i s an i n t e g e r s a t i s f y i n g 0 ^ m < x, that y i s integral a (C.3) real number converges in the range f o r Re(z) > -m, analytic f u n c t i o n of z t h e r e . Thus, s i n c e z 2 follows immediately that Q(m,x;z) 0 < y £ 1. and defines analytic analytic power in the unit f u n c t i o n s are and Q(m,x;z) are a n a l y t i c then defined and obviously the those functions s e r i e s expansions, and v i c e v e r s a , because m = 0 Q(m,x;z) the and analytic issue Q(m,x;z) only does not c o n t a i n functions d i s k D = {z : |z| < 1}. Since the precisely holds when m £ 1. When an i s entire, i t Z f u n c t i o n s of z f o r Re(z) > -m, and so i f m > 1 these are The as that have i t f o l l o w s that (C.2) is not given f o r Re(z) > 0, a so simple, by (C.1) are region which the u n i t d i s k . Thus we must look at cases Q(0,x;z) = z 2 Z Q(0,x;z) = z 2 Z Bj (z, 1+x) s B(z, 1+x) in more d e t a i l . Although we do not prove i t here, shown that the f o l l o w i n g e x p r e s s i o n v y yk L k (*) ( - 1 ) k=0 \ ' k It can f u r t h e r be shown defines plane, a function that that be holds f o r Re(z) > 0: co B (z,1+x) = i t can the k . (C.4) z + k right-hand side of (C.4) i s a n a l y t i c f o r the e n t i r e complex except f o r the p o i n t s z = 0, -1, -2, ... Thus the r i g h t - 11 hand s i d e of (C.4) i s the left-hand side. unique Using z 2 B (z,1+x) has a (C.4) removable y analytic extension i t i s easy singularity at to 5 of the see z = 0; that to be p r e c i s e , we may w r i t e z 2 Z B (z,1+x) = ( 2 y ) [ 1 + Z y L (*j where the r i g h t - h a n d s i d e i s a n a l y t i c plane, except y = 1, f o r the ( . ) C entire 5 complex f o r the p o i n t s z = -1, -2, ... Taking y = 1/2 and we can use the r i g h t - h a n d s i d e of (C.5) t o a n a l y t i c a l l y extend Q(0,x;z) and Q(0,x;z) t o t h i s same region j , containing D. Thus the expansions region, i . e . to a i n (C.2) e x i s t even f o r m = 0. C.2 E x p r e s s i o n s f o r the c o e f f i c i e n t s i n (2.3.15) We now d e r i v e e x p r e s s i o n s f o r the c o e f f i c i e n t s b (m,x) i equation (2.3.15) in [the d e r i v a t i o n a l s o proves the v a l i d i t y of t h i s expansion]. For 0 ^ m < x, we have from equation (2.2.28) that r d + x ) r(m+z) Q(m,x;z) = z 2 Td+x+z) r(1+m) . (C.6) If we omit m = 0 from the range c o n s i d e r e d , we can w r i t e Q(m,x;z) = for z 2 m T d + x ) T(m+z) r(1+x+z) r(m) 1 < m < x. For convenience, f(m,x;z) = 2 for Z (C.7) we l e t r d + x ) r(m+z) r(1+x+z) T(m) (C.8) 1 < m < x. In (C.8) the complex v a r i a b l e z i s viewed as the 1 16 main independent v a r i a b l e , whereas x and m are considered parameters that are h e l d f i x e d during often write the d i s c u s s i o n . to be Thus we simply f ( z ) f o r 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) for m £ 1; hence i n order (2.3.15) we want to w r i t e f(m,x;z) = exp to f i n d a r e p r e s e n t a t i o n of the form f i n the form I bi(m,x) z L i =0 If we put m = 0 i n t o (C.6), „ (C.9) we 1 -I . (C.10) find ro+x) r(z) rd+x) rd+z) Q(0,x;z) = z 2 = 2 rd+x+z) r d ) rd+x+z) = f(1 , x ; z ) . (C.11) The l a s t equation shows that We now (C.10). It discussion represents analytic no x at formulas understood represents f o r the c o e f f i c i e n t s b (m,x) i n that i for the duration 1 < m < x. Since the complex z-plane except at z = -m, 2 z = -m, of T(m+z) -m-1, and l/r(l+x+z) are e n t i r e , f ( z ) i s -m-1, -m-2, ... In i n the u n i t d i s k D = {z : |z| < 1}, is -m-2, analytic particular, f(z) and- i t to which we s h a l l r e s t r i c t our a t t e n t i o n . A l s o , zeros the a r e a l number s a t i s f y i n g x > 1 and m an i n t e g e r s a t i s f y i n g both analytic region is in and except derive (2.3.16) h o l d s . is is this f ( z ) has i n D ( i t s zeros are l o c a t e d at z = -x-1, -x-2, -x-3, . . . ) . We apply the f o l l o w i n g r e s u l t (see C o r o l l a r y 4.16, Ch. IV 11 7 of [ 8 ] ) : L e t G be a simply plane f(z) C, and connected region l e t f:G —> C be an a n a l y t i c * 0 f o r any z i n G. Then t h e r e g:G -» C f(z ), such that is 0 Since D is simply connected, the complex f u n c t i o n such that an analytic f ( z ) = exp(g(z)). If z we may choose g such that g ( z ) = 0 of 0 function C G and exp(w ) = 0 w. 0 and f satisfies the hypotheses of the above theorem, there e x i s t s a f u n c t i o n g ( z ) = g(m,x;z), a n a l y t i c i n the u n i t d i s k , such that f(z) = exp(g(z)). Let z 0 = w = 0. 0 Then (C.12) exp(w ) = 1 = f ( z ) , 0 and we may choose 0 g(z) such that g(0) = 0. Applying the chain r u l e t o (C.12), we find f'(z) where, f(z) of = exp(g(z)) g'(z) = f ( z ) g'(z) course, the prime i n d i c a t e s d i f f e r e n t i a t i o n . Since has no zeros i n D, we may w r i t e f'(z) g' (z) = . (C.13) f (z) Since g i s a n a l y t i c i n D, i t has a T a y l o r s e r i e s 00 g(z) = valid Z b (m,x) z i =0 (C.14) 1 i f o r |z| < 1. The c o e f f i c i e n t s b (m,x) are given by i b (m,x) = g 1 ( i ) (0)/i! = g >(m,x;0)/i! (1 (C.15) where g ( i ) (z) is the i - t h d e r i v a t i v e of g with respect to z, with the s p e c i a l cases g Since g(0) = ( 0 ) (z) = 0 we immediately g(z) and g ( 1 ) (z) = g'(z). have that b (m,x) = 0. To f i n d 0 1 18 the h i g h e r - o r d e r c o e f f i c i e n t s we s u b s t i t u t e (C.8) into (C.13) to get g'(z) = log 2 + r'(m+z) T'd+x+z) - r(m+z) Using the P s i f u n c t i o n , equation (C.16) (C.16) may be w r i t t e n = l o g 2 + \p(m+z) g'(z) . r(1+x+z) - (C.17) »//(1+X+Z). By i n d u c t i o n , we have, f o r i = 2, 3, 4, ... g and ( i ) ( ) z ^ ( i - l ) ( + ) - \}> - (1+x+z) , {± = m so from (C.15) we 11 z (C.18) find b,(m,x) = l o g 2 + \p(m) - \^(1+X) b (m,x) = [^«i-l'(m) ± These a r e the r e s u l t s C.3 The asymptotic - stated t// 1 1 " 1 (C.19) ' (1+x) ] / i ! . i n equation ( i > 2) (2.3.17). expansion of the c o e f f i c i e n t s We show how the asymptotic expansions f o r the c o e f f i c i e n t s bj_(m,x) a r e d e r i v e d . We look at two c a s e s : i = 1 and i £ 2. CASE 1 : i = 1. When i = 1 , we have from (C.19) that b,(m,x) = l o g 2 + i|/(m) From e n t r y 6.3.2 of [ 1 ] we f i n d that <//(1+X). 1 19 •Mm) for (C.20) m m = 1, 2, 3, ... We c o u l d use t h i s same I//(1+N) = -C + H our intention arbitrary and = -C + H _! of developing sufficiently directly that are expansion that for (Our f o r , whereas we view m as it = is feasible to write 1/x + compute (C.21 ) f o l l o w s from the r e c u r r e n c e formula Z ' T ( z ) = T(1+Z) and the d e f i n i t i o n asymptotic with approach f o r \/>(1+x). summations i n v o l v i n g m terms.) We f i r s t immediately valid take a d i f f e r e n t are c a l l e d small *( 1+x) (this write i s to view the block s i z e x as being so l a r g e that asymptotic expansions being formulas i n s t e a d use an asymptotic approach to x = N = an i n t e g e r , but i n keeping r e a l block s i z e s , we s h a l l shall general when N formula expansion of >//). In [1] we f i n d the following f o r i//(z): B \Kz) ~ l o g ( z ) - 1/2z - Z n=1 2n 2n z 2 n (C.22) = l o g ( z ) - 1/2z - 1/12z 2 + 1/120Z« - 1/252Z 6 + ... as z -» oo . Using the r e s u l t [1] |B 2n | ~ 2(2n)!/(2») which holds series i n (C.22) does not converge; is the (C.23) f o r l a r g e n, i t i s easy t o see that the i n f i n i t e standard n e v e r t h e l e s s , the n o t a t i o n n o t a t i o n f o r an asymptotic (C.21) and (C.22) y i e l d s s e r i e s . Combining 1 20 I//(1+X) ~ l o g ( x ) + 1/2X - Z n=l — 2n x n 2 n (C.24) = l o g ( x ) + 1/2X - 1/12X and 2 + 1/120x* - 1/252x 6 + ... finally b,(m,x) = l o g 2 - C + U -\ m - ^(1+x) (C.25) H. _ m x - [log(x/2) + C + 1/2x - 1/12X T h i s i s the r e s u l t CASE 2: We given 2 + 1/120X" - . . . ] i n (2.3.19). i > 2. consider bidiwx) = [^/ i-l»(m) - tf<i-l > ( l + x ) ] / i ! . ( From entry 6.4.3 of [1] we f i n d )( ) = ( - D ^ i - D ! m [$(i)- H^>] for m = 1, 2, 3, ... and i S 2. Note that the p r e v i o u s does not make any sense f o r i = 1, s i n c e $(1) does We again starting find an asymptotic expansion by r e p e a t e d l y d i f f e r e n t i a t i n g ) (1+x) = 0 i - l ' ( x ) + ( - 1 ) ( Entry 6.4.11 of [1] g i v e s the asymptotic for not exist. the term i n x, (C.21) to get i + l equation (i-Dl/x . 1 expansion 121 )( ~ z ) } : (i-2)! __ r z as z 1 (i-1)! + 2 z 1 oo . Combining the l a s t b (m,x) ~ (-1) il ± 1 - + _tl B 2 n=1 1 (2n+i-2)! _ (2n)! z 2 n + i _ n 1 three equations g i v e s | $(i) - H i | m (C.26) 1 1 (i-Dx 1 2x 1 (i-1)! x T h i s i s the formula given i n C.4 n=1 B (2n + i-2) ! -, x 2 n (2n)! x 2n+i-lJJ (2.3.20). D e r i v a t i o n of the recurrence formula We now prove that the recurrence formula Based on equations f(z) = where the note a f t e r unit series (2.3.22) and Z a z i =0 = 1 i parameters exp Z biZ i =1 (C.27) the l e f t m o s t power s e r i e s i n (C.27) converges for (C.27) converges i f coefficients. ascending The for that the at l e a s t formulas least other power t h i s same r e g i o n ) . f o r the a i n terms ± of the most obvious of which i s to use the s e r i e s expansion of e x p ( 0 (C.27) i n t o [see the the known c o e f f i c i e n t s b to rearrange the r i g h t - h a n d s i d e powers disadvantage of of z this r a p i d l y becomes t e d i o u s . A b e t t e r method that 1 in |z| < 1 (we have a l r e a d y seen in write m and x have not been i n d i c a t e d There are s e v e r a l ways to f i n d the (C.10) we may (2.3.23) h o l d s . (2.3.21)]. Since f ( z ) i n a n a l y t i c at d i s k D, at l e a s t of oo 1 and then method begins to is by equate that i t recalling 1 22 f ' ( 2 ) = f ( z ) g' ( z ) , where g(z) has the s e r i e s expansion S i n c e a power s e r i e s may disk (C.28) given be d i f f e r e n t i a t e d i n equation term-by-term i n i t s of convergence, the s u b s t i t u t i o n of the s e r i e s f o r f ( z ) and g(z) i n t o L i az i-1 Z a^z i =0 L I i bi z i=1 i-1 M u l t i p l y i n g both s i d e s of (C.29) by z, we may Z i a ^ i=1 where c c. = absolutely coefficients in i 1 (C.30) = = i _ 1 formula k 1 i s allowed in (C.30) f o l l o w i n g recurrence write c^ k the Cauchy product converges a Z i=1 (C.29) i-1 Z (i-k) a b._ . k=0 Z k b, a. , , , k i-k k= 1 1 Taking = 1 i s given by the Cauchy product ± expansions (C.28) y i e l d s ± i=1 (C.14). (C.31 ) k k because a power i t s region of convergence. and using (C.31), we series Equating obtain the formula: . v b k i-ka ( i * 1 (C.32) ) k= 1 To "start" the recurrence formula value which can e a s i l y to f i n d a 0 = 1. we need the value of a , a be obtained by p u t t i n g z = 0 0 in (C.27)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The computation of the block-error rate on a Rayleigh-fading...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The computation of the block-error rate on a Rayleigh-fading channel in the presence of additive white… Maranda, Brian Howard 1982
pdf
Page Metadata
Item Metadata
Title | The computation of the block-error rate on a Rayleigh-fading channel in the presence of additive white Gaussian noise |
Creator |
Maranda, Brian Howard |
Date Issued | 1982 |
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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-04-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0095826 |
URI | http://hdl.handle.net/2429/24089 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1983_A7 M37.pdf [ 5.06MB ]
- Metadata
- JSON: 831-1.0095826.json
- JSON-LD: 831-1.0095826-ld.json
- RDF/XML (Pretty): 831-1.0095826-rdf.xml
- RDF/JSON: 831-1.0095826-rdf.json
- Turtle: 831-1.0095826-turtle.txt
- N-Triples: 831-1.0095826-rdf-ntriples.txt
- Original Record: 831-1.0095826-source.json
- Full Text
- 831-1.0095826-fulltext.txt
- Citation
- 831-1.0095826.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0095826/manifest