BIT ERROR RATE PERFORMANCE ANALYSIS AND OPTIMIZATION OF SUBOPTIMUM DETECTION PROCEDURES By NORMAN CHARLES BEAULIEU B.A.Sc., The University of British Columbia, 1980 M.A.Sc., The University of British Columbia, 1983 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA January 1986 • Norman Charles Beaulieu, 1986 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Electrical Engineering The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date /HI ^ ii ABSTRACT Three suboptimum detection schemes are examined. The deterioration in performance, measured in the probability of error sense, of weighted partial decision, binary partial decision, and sample-and-sum detectors are analyzed. Even though these schemes are inferior to the digital matched filter, they can be used in systems with more modest computational capabilities. Analytic expressions are obtained for the penalties. The effects on the peaalties of the signalling waveform employed, the number of samples processed, and the signal-to-noise ratio are considered in detail. Included are the penalties for the optimum weighted partial decision detector. The effects of dependence among the samples on the detector losses are investigated. It is shown that, in some cases, the losses of the suboptimum procedures can be reduced by processing more, dependent, samples. The amount of the loss that can be recovered depends on the prefilter characteristic and the sampling rate, as well as the detection algorithm. The structure of the optimum detector for hard-limited data signals is presented and its performance is compared with those of some commonly used schemes. Performance in Impulsive as well as Gaussian noise environments is considered. The optimum receiver for M-ary signalling based on received signal samples quantized to an arbitrary number of levels is derived and compared to another common detector. The fundamental loss in signal detectability due to hard-limiting in a sampled system operating in Gaussian noise is investigated. The relation of the loss to the signal-to-noise ratio and the number of samples is analyzed. iv TABLE OF CONTENTS Page ABSTRACT ii TABLE OF CONTENTS iv LIST OF TABLES viiLIST OF FIGURES x ACKNOWLEDGEMENT xii I INTRODUCTION 1.1. Motivation 1 1.2. Scope of the Thesis 2 1.3. Review of Relevant Work 4 1.4. Outline of the Thesis 7 II PERFORMANCE COMPARISON OF THREE SUBOPTIMUM SCHEMES FOR BINARY SIGNALLING 2.1. Introduction 9 2.2. The Sample-and-Sum (SAS) Detector 12 2.3. The Weighted Partial Decision (WPD) Detector 15 2.4. The Binary Partial Decision (BPD) Detector 7 2.5. Generalization to Arbitrary Signalling Waveforms 18 2.6. Discussion lq V Page III EFFECTS OF OVERSAMPLING ON THE PERFORMANCE OF THREE SUBOPTIMUM DETECTION SCHEMES 3.1. Introduction 26 3.2. The Sample-and-Sum Detector with Dependent Samples 9 3.3. The Weighted Partial Decision Detector with Dependent Samples 39 3.A. The Binary Partial Decision Detector with Dependent Samples 47 3.5. Discussion 8 IV OPTIMAL DETECTION OF HARD-LIMITED DATA SIGNALS IN DIFFERENT NOISE ENVIRONMENTS 4.1. Introduction 49 4.2. Derivation of the Optimum Detector for Hard-Limited Samples 49 4.3. Optimum Weights for Low Signal-to-Noise , Ratios 52 4.4. Optimum Weights for High SNR's 53 4.4.1. Gaussian Noise Distribution 4 4.4.2. Laplace Noise Distribution 4.4.3. Cauchy Noise Distribution 55 4.5. Some Numerical Examples 54.6. Generalization to M-ary Signalling and Multilevel Quantization 62 4.7. Conclusions 68 vi Page V PENALTIES OF WEIGHTED PARTIAL DECISION DETECTORS IN GAUSSIAN NOISE 5.1. Introduction 69 5.2. Problem Statement 65.3. Weighted Partial Decision (WPD) Detectors 72 5.4. The WPD Detector for a Piecewise Constant Amplitude Signalling Waveform 7^ 5.5. The Optimum WPD Detector for Arbitrary Signalling Waveforms 78 5.6. The Weights = |s±I and u± = si WPD Detectors 8l 5.7. Discussion 81 VI PENALTIES OF SAMPLE-AND-SUM AND BINARY PARTIAL DECISION DETECTORS IN GAUSSIAN NOISE 6.1. Introduction 88 6.2i The Sample-and-Sum (SAS) Detector Loss ....... 89 6.3. The Binary Partial Decision (BPD) Detector Loss 94 6.4. Discussion of Results 100 VII CONCLUSION 7.1. Summary of Results 102 7.2. Suggestions for Further Research 104 APPENDIX A 105 APPENDIX B 6 vii Page APPENDIX C 107 APPENDIX D 109 APPENDIX E 111 APPENDIX F 113 APPENDIX G 114 APPENDIX H 115 APPENDIX I 118 APPENDIX J 120 APPENDIX K 124 REFERENCES 126 GLOSSARY 130 Vlll LIST OF TABLES Table PaSe I Asymptotic losses for suboptimum schemes 20 ix LIST OF FIGURES Figure Page 2.1 Block diagram of the data receiver 10 2.2 The suboptimum detector penalties for a sinusoid with P(e) = 10"3 21 2.3 The suboptimum detector penalties for a sinusoid with P(e) = 10~7 22 2.A The suboptimum detector penalties for a _3 square-wave with P(e) = 10 23 2.5 The suboptimum detector penalties for a square-wave with P(e) - 10 24 3.1 , Block diagram of the data receiver 27 3.2 The normalized autocorrelation function of white noise filtered by a Butterworth lowpass filter of order N 34 3.3 The normalized autocorrelation function of white noise filtered by a cascade of N identical poles 36 3.4 The additional penalty T^ for the SAS detector with a Butterworth pref liter of order N 37 3.5 The additional penalty for the SAS detector with prefliter consisting of a cascade of N identical poles 38 X Figure Page 3.6 The normalized autocorrelation function of white noise after lowpass filtering by a Butterworth filter of order N and hard-limiting 43 3.7 The normalized autocorrelation function of white noise after lowpass filtering by a cascade of N identical poles and hard-limiting 44 3.8 The additional penalty of the WPD and BPD detectors with a Butterworth prefliter of order N *5 3.9 The additional penalty of the WPD and BPD detectors with prefilter consisting of a cascade of N identical poles 46 4.1 Error probabilities for the DMF detector and four different WPD detectors for a raised cosine pulse 56 4.2 Error probabilities for the DMF detector and four different WPD detectors for a half sinusoid pulse 58 4.3 Error probabilities for the detection of a raised cosine pulse in Laplace noise 60 4.4 Error probabilities for the detection of a raised cosine pulse in Cauchy noise 61 PAM error probabilities for the DMF and the WPD detectors with optimum and unity weights , Block diagram of the data communication system The penalty TyppC if*1."^ ) as a function of the signal-to-nolse ratio it A. The penalty Trrnr. ( s,M,— ) of the optimum WPD WPD O detector for a raised cosine The penalty ( s,M,— ) of the optimum WPD detector for a half sinusoid The penalty ( s,M,£ ) of the - |s±| weights WPD detector for a raised cosine The penalty ( s,M,£-) of the a± - IsJ weights WPD detector for a half sinusoid A 2 The penalty ( s,M,- ) of the «i - e± weights WPD detector for a raised cosine A 2 The penalty ( s,M,— ) of the w± - s± weights WPD detector for a half sinusoid The penalty r_A_( s,M ) for a half sinusoid The penalty rgAS( s,M ) for a sinusoid The penalty rBpD ( s,M,— ) for a raised cosine The penalty rBpD ( s.M.y ) for a half sinusoid ACKNOWLEDGEMENT I wish to thank my advisor Dr. C.S.K. Leung for suggesting the topic and for rendering assistance during the course of the work. I am grateful to the Natural Sciences and Engineering Research Council of Canada for the financial support received under their graduate scholarship program and from Grant A-1731. A special thanks is given to MDI Mobile Data International for the generous assistance received from the MDI Mobile Data International Fellowship in Communications Engineering. I am also indebited to the Science Council of British Columbia for the support provided under the auspices of the Graduate Research and Engineering Technology (GREAT) Award. Thanks are due to the British Columbia Telephone Company for giving me a British Columbia Telephone Company Graduate Scholarship and to the University of British Columbia for providing some funds for conference travel. Finally, I wish to express my appreciation to the office staff for their willing assistance, encouragement and cheerfulness. 1 I INTRODUCTION 1.1. Motivation A fundamental problem In communication theory and design is how to best detect information signals in noise. Optimal detection methods are known but may be expensive or difficult to implement. Suboptimum detection procedures are employed in a number of diverse areas. Data recovery circuits in modems are frequently based on suboptimal procedures where cost-effective implementations trade off complexity against performance. In underwater sound detection systems, arrays of receivers that nay be quite large are used to detect weak signals. For large arrays, the processing required can be reduced significantly by employing suboptimal procedures that have more modest computational requirements than the optimal processing. Digital receivers for systems employing tine or frequency spreading techniques have large time-bandwidth products and oust process a large number of samples. Simplified versions of digital Batched filters offer flexibility, reliability, speed, compactness and cost efficiency. In order to assess, compare and choose alternative detection procedures for • given application, the communications engineer requires knowledge of the performance of the schemes. This is one of the principal objectives of this research. The performances of a number of ad hoc detectors are analysed. The results are useful for performance evaluation of existing designs as veil ss for initiating new designs in data recovery and signal detection systems. 2 Another principal objective is to investigate the optimality of the schemes employed. In particular,, given certain processing constraints, what are the optimum detection schemes? The results of this investigation will provide theoretical limits for the performance that can be achieved by systems operating with particular hardware or processing limitations. The thesis research has industrial as well as academic significance. In the short term, the results will provide answers that will enable product designers to construct improved receiver subsystems. In the long term, the development of theory of suboptimal detection procedures entails dealing with some fundamental issues regarding the properties and the components of the losses incurred by these processes. A better understanding of signal detection will come from the theory developed. 1.2. Scope of the Thesis This thesis considers suboptimum detection procedures. Both theoretical and numerical results are presented. With the exception of section 4.6, the work deals with binary systems. The emphasis is on evaluating the performance of the detectors with the performance measured in the signal detectability sense. That is, the probability of error is used as the performance criterion. The thesis is concerned throughout with the processing of sets of signal samples. The analysis and results are cast in the context of data recovery in digital communication receivers. The mathematical techniques and the results, however, are quite general and apply to a wide range of problems. The signal samples may, for example, be from a diversity digital communication system, or a radar or sonar signal detection system. 3 The effects of hard-limiting on signal detectabillty are investigat ed in detail. The relations of the detector losses to the number of samples processed, the signal-to-noise ratio, and the processing algorithm ere of central Interest. In order to gain insight into the principal mechanisms and relations of the detector losses, some simplifying assumptions have been made. In particular, it has been assumed that there 1B negligible intersymbol interference (ISI) and that bit synchronization is available. ISI is not present in pulse detection systems. Furthermore, many communication systems operate with little or no ISI. Low speed modems for telephone channels and radio modems are two examples. The present results also apply to ISI channels when the received signal has been equalized. The method used to obtain bit synchronization is not of particular interest here. Timing recovery circuits can provide bit synchronization with less than a few percent jitter. The effects of this jitter on the penalties of the detectors Is of minor Importance as consideration of the binary eye Indicates. Some of the results of this thesis have been reported earlier in the journal papers, "On the Performance of Three Suboptimum Detection Schemes for Binary Signalling" 17), •'Optimal Detection of Hard-Limited Data Signals in Different Noise Environments" [6], "Penalties of Sample-and-Sum and Weighted Partial Decision Detectors in Gaussian Noise" [9], and the conference papers, "A Comparison of Three Suboptimum Detectors for Binary Signalling"[32], "On Hard-Limiting in Sampled Binary Data Systems" 133], "The Optimal Hard-Limiting Detector for Data Signals in Different Noise Environments" [10], and "Penalties of Weighted Partial Decision Detectors In Gaussian Noise"[34]. A 1.3. Review of Relevant Work A review of work relevant to this thesis is given in this section. Brief comments on the methods used and the results obtained are given for each reference. The reader may find it helpful to refer to the glossary for explanation of some of the terms. Tozer and Kollerstrom [1] have considered the penalties of hard decision in the detection of binary antipodal signals in additive white Gaussian noise. In this analysis, short subsections of the signal are detected, giving a number of hard binary decisions. The subsections of the signal are constrained to be of equal energy and are detected by appropriate matched filters. The data polarity is recovered by using majority rule on the subsection decisions. This detection scheme is compared to the optimum detection achieved by using an analogue matched filter over the entire signal duration. It is shown that for a large number of independent subsections and small signal-to-noise ratios a penalty of 1.96 dB is incurred. Milutinovic [2,3,35,36] has described a suboptimum detection pro cedure based on weighting partial decisions. This work considers binary signals in additive white Gaussian noise. The detection algorithm is based on two counters, Bo and B^. The received 6ignal is sampled M times in the duration of one signalling element. Each sample is compared with a threshold value and, depending on the outcome, counter B or B, Is incremented by a weight which depends on the sample index, o 1 After M partial decisions, the transmitted signal is determined by a comparison of the two counters. The weights are chosen to be proportional to the distance between the two transmitted signals at the sampling 5 instant. Also considered is an algorithm based on binary partial decisions. In this scheme, all samples are weighted equally. The performance of the two suboptimum detectors is compared to that of a digital matched filter. The penalty is computed for a particular set of antipodal signals for three values of sample size M. The results are example specific. It is found that the penalty of the weighted partial decision detector is about 2 dB for all three values of M and increases slightly with increasing signal-to-noise ratio. The penalty of the binary partial decision detector is about 3 dB for low signal-to-noise ratios and increases sharply as the signal-to-noise ratio becomes large. Lockhart [4] has considered replacing analogue filter and analogue detector circuits in data receivers by digital networks designed from truth table specifications. A method of compiling the truth tables from received signal probabilities is presented. The technique is illustrated by an example. The detection of binary antipodal raised cosine signals in the presence of Gaussian noise is examined. The received 6ignal samples are assumed to be independent. The performance of the digital network is compared to that achieved by using a single sample detector. An error probability versus signal-to-noise ratio curve is presented for each scheme. It is noted that the proposed scheme performs better. It is also noted that the truth table is valid for all values of signal-to-nolse ratio and can be derived more directly by considering a hard-limited received signal filtered by a nonrecursive matched filter. 6 The algorithm presented by Lockhart is an application of the maximum aposteriori probability (MAP) rule to the situation where there are a number of independent hard-limited received signal samples and the transmitter signal set, as well as the noise statistics are known. The independence assumption will require that the noise be white or that appropriate filtering of the received signal be done. The computationally direct method of considering the hard-limited, nonrecursively matched filtered signal samples is the weighted partial decision algorithm described by Milutinovic [2,3]. For the signalling waveform and the number of samples considered the MAP rule and the weighted partial decision algorithm yield the same truth table. In general, however, the MAP rule truth table will depend on the signal-to-noise ratio and the two procedures will not be truth table equivalent. Chie [5] has investigated a simplified digital detector which performs only additions on the noisy signal samples. In this analysis, the signalling waveforms are antipodal nonreturn-to-zero (NRZ) pulses and the additive noise is white and Gaussian. The detector prefilter is assumed to pass the signal without distortion. Hence, all the signal samples have the same magnitude and there is no ISI. It is also assumed that perfect synchronization is available. Numerical results are presented for a typical implementation example configured with sixteen samples and a four bit analogue-to-digital converter (ADC). The sensitivity of the detector performance to the number of samples processed, the number of ADC bits, and the ADC loading is examined^ each Individually. For this example, It appears that four bit quantization performs almost as well as quantization with an infinite number of bits and that very little can be gained in performance by using more than sixteen samples. Chang [6] has also investigated the sample-and-sum detector examin ed by Chle 15]. Again, antipodal NRZ signals in white Gaussian noise are considered. The performance degradation of the detector is related to the bandwidth of the prefilter, the sampling rate, and the number of quantizat ion levels. The distortion of a single pulse resulting from the prefilter is dealt with in the analysis, but the effects of ISI are assumed to be negligible. Perfect synchronization is assumed throughout. It is con cluded that, for the examples investigated, a prefilter bandwidth on the order of twice the bit rate is adequate and that three or four bit quantization is almost as good as infinite quantization. 1.4. Outline of the Thesis In this section, an outline of the thesis is given. The principal results of each chapter are described in turn. Chapter two Introduces three suboptlmum detection procedures: the Sample-and-Sum (SAS), the Weighted Partial Decision (WPD) and the Binary Partial Decision (BPD) algorithms. The bit error rate performances of these detectors are analysed for large time-bandwidth product conditions. This is first done for binary antipodal signals and It is then shown that the results may be generalized to arbitrary binary signals. The relation among the losses of the three schemes is presented. In chapter three, the performances of the three detectors for large time-bandwidth systems with dependent samples are considered. It Is shown that, In some cases, the losses of the auboptimum schemes can 8 be reduced by processing more, dependent, samples. The amount of the loss recoverable is related to the prefliter shape and the sampling rate. The structure of the optimum, minimum probability of error, detector for hard-limited samples is presented in chapter four. Whereas previous chapters have dealt with large time-bandwidth product conditions and Gaussian noise, the results of this chapter are general and apply to an arbitrary number of samples and most common noise environments. The optimum detector for M-ary signalling with each received sample quantized to an arbitrary number of levels is also derived. Again, the result is valid for most noise distributions. In chapter five, the penalty associated with the use of the WPD detector in Gaussian noise is examined in detail. The effects on the penalty of the signalling waveform employed, the number of samples processed, and the signal-to-noise ratio are examined. Two common ad hoc choices of weights are considered as well as the optimum weights. The performance degradations of the SAS and BPD detectors are analysed for arbitrary SNR's in chapter six. The effects on the penalties of the signalling waveform employed and the number of samples processed are also considered in detail. The relationship among the losses of the SAS, BPD and WPD detectors for low SNR and finite sample sizes is derived. Finally, chapter seven gives a more detailed summary of the results of the thesis research and suggests some topics for further research. 9 II PERFORMANCE COMPARISON OF THREE SUBOPTIMUM DETECTION SCHEMES FOR BINARY SIGNALLING 2.1. Introduction In this chapter, the problem of detecting one of two equally likely signals using digital techniques is addressed. The case of antipodal signals is first considered and it is then shown that the results are readily gener alized to arbitrary signals. The model considered is shown in figure 2.1. Depending on the message «c{0,l} to be transmitted, s signal +s(t) or -s(t) Is sent over the additive white Gaussian noise (AWGN) channel. The two-sided power spectral density of the noise process o(t) is assumed to be NQ/2. The signal s(t) Is assumed to be non-zero only In the time Interval I0,T] sec. •nd bandlimited to B Hzt. The received signal r(t) is filtered to remove excess out-of-band noise producing the signal v(t) which is then processed by the detector. The detector samples the signal v(t) at a rate of 2B samples per second, yielding a total of H - 2BT noisy samples of the transmitted signal. A consequence of this sampling rate Is that the (Gaussian) noise samples in v(t) will be Independent 111]. Furthermore, in order to ensure that the transmitted signal s(t) Is essentially undlstorted by the receiver filter, we require that M - 2BT » 1. (2.1) Exactly how large M should be depends in part on the shape of s(t). If »(t) is fairly smooth (e.g. • sinusoidal wave) then a value of 10 would suffice. t Strictly speaking, a time-limited signal cannot be completely bandlimited. Bbwever, for practical purposes, all the signal energy will lie within a frequency range of B » * . LOWPASS FILTER -B B v(t) DETECTOR •Cm) Figure 2.1. Block diagram of the data receiver. 11 On the other hand If s(t) hae 6harp transitions (e.g. a square wave), then a larger value of about 100 is required. These values of M are sufficient to T / |s(t)-s(t)|dt keep p • —~ , where s(t) denotes the output of the filter, to / |a(t)|dt 0 less than 1.52. It Is well-known [11) that the optimum detector for minimizing the A * probability of error P(e) • Pr { m * m) in the above problem is the digital matched filter (DMF). Its operation can be described as follows: Let Vi " Si + ni * 1 ' 1,2M (2'2) IT denote the M samples of v(t), i.e. » V^"~M^ which are to be processed. M IT The values { BI )IM^ denote the samples of s(t), i.e. s^ - and the { n^ }^_^are Independent Gaussian noise random variables with means 0 and 2 variances o • BN . The DMF computes no Don ' lml V, <2-3) A A and decides m - 0 if D^«„ > 0: otherwise it declares m • 1. The resulting OPT probability of error is given by [11] /2E~ P(e) - QC/y-*) o (2.4) 12 T " 2. where E & / s2(t)dt Is the energy of s(t) end Q( a ) & -~ / e~* dx. 8 0 ^5* a Equation (2.4) gives the error probability for an analogue matched filter. It is also valid for the DMF when M is large. We note that the DMF requires M multiplications and (M-l) additions. A number of suboptimal schemes I 1-10,12,13 1 have been proposed which have more modest computational requirements. These include the Sample-and-Sum (SAS), the Weighted Partial Decision (WPD) and the Binary Partial Decision (BPD) detectors. Previous analyses of these suboptimal schemes have been confined to specific signalling waveforms s(t) and specific (small) values of M. In the following sections, an analysis of the penalty incurred by each of these schemes for an arbitrary signalling waveform and large values of M is given. The penalty is defined as the increase in signal energy required by a suboptimum detector in order to achieve the same error probability as a digital matched filter (in the large sample case, this is the same as the error probability of the analogue matched filter). Examples illustrating how the penalties vary with M are also included. Note that the model used implies a small signal-to^noise ratio condition. The results, therefore, are valid for small signal-to-noise ratios. This restriction is removed in chapters 5 and 6. (2.5) 2.2. The Sample-and-Sum (SAS) Detector The SAS detector [5,6,13] computes the quantity DSAS M Yi •«nC*i) (2.5) f+1 if *>0 < 0 if *-0 , L-i if *<o where sgn(x) 0 if «-0 , and declares a - 0 if D^ > 0. Otherwise, * - 1 13 is decided. Comparison of (2.3) and (2.5) shows that the SAS detector avoids multiplication by not weighting the samples of the received signal. The resulting penalty is now analysed. Clven • - 0, I.e. 4«(t) Is transmitted, the nean of is given by wj, Ki (2-6> and the variance of D_._ 16 given by aAs 2 u 2 ou - Mo ^SAS « MBN A° -T^. C2.7) An error will be nade if D„ir. < 0. We note that since De._ is the sum of SAb a<va Gaussian random variables, It is Itself a Gaussian random variable. Thus, M I K r P(efm-O) - Q ) *BAS Q f 1 1 ) . (2.8) • N /2T o By symmetry, P(e) - P(e|»-0) - P(e|«-1). Vote also that 14 M _ T lim I (s J - / js(t)|dt. Therefore, as M< M-M» i-l 0 He) - Q (/p<|s(t>|>) , (2.9) 1 T where <|s(t)|> - / js(t)jdt represents the average magnitude of the T 0 signalling waveform s(t). If we define E o- 5- , (2.10) T{<|s(t)i>r equation (2.9) can be rewritten as '2E 8 ^ (2.11) PC) • 9(/^-} By comparison of (2.11) with (2.4), it can be seen that to achieve the same value of P(e), the SAS detector uses a times the energy required by the DMF detector. For a constant s(t), o - 1 as might be expected. (It can be shown using Schwarz'6 Inequality [11] that the minimum value of a is 1.) However, 2 for a sinusoidal signalling waveform, a" i /8 or 0.912 dB. 15 2.3. The Weighted Partial Decision (WPD) Detector In the WPD detector (2], the necessity for multiplication is avoided by ignoring the magnitudes of the received signal samples and using only their polarities. The decision is based on implementation, two accumulators AQ and A^ could be used. If v^ > 0, A^ is incremented by 8^ and if v^ < 0, then A^ is incremented by s^. In the (unlikely) event that v^ - 0, neither accumulator is incremented. After all N samples have been processed, the contents of A^ and A^ are compared to A determine m. We now proceed to calculate P(e) for the WPD detector. Since by symmetry, P(ejm-O) • P(e|m*l), we assume with no loss of generality that D - 0, i.e. +s(t) is sent. In this case, we can rewrite (2.12) as (2.12) A A If D > 0, m - 0 is declared; otherwise m - 1 is declared. In an actual M (2.13) where the partial decision random variable D. is defined by (2.14) It follows that P(D1»1) - l-p1 and P^ —1) - where -Qiyi1^,!). (2.i5) 2 The mean and variance of D^Js^j are given by (l-2p^)Js^| and 4p^(l-p^) Js^ | respectively. Under certain conditions which are satisfied in this case, it can be shown [14] that as M-^°°, D^^ has the asymptotically Gaussian distribution M M n( I (l-2p )|s |, I 4p (1-p )|s J2). 1-1 1 1 1-1 Using this result, it is shown in Appendix A for small signal-to-noise ratios that the probability of error for the WPD detector as M** is given by 4E 8^ (2.16) o It Is interesting to note that for large values of M, the WPD detector uses y tlaes the energy required by the DMF detector to achieve the sane value of P(e). This penalty of 1.96 dB Is independent of the specific signalling waveform used, in contrast to the SAS detector in which the penalty does depend on the shape of s(t). 17 2.A. The Binary Partial Decision (BPD) Detector The BPD detector can be considered as a special case of the WPD detector in which the Information regarding the magnitude of the sample M values {s^)^m^ is not used. This results In a simple implementation in which a counter (Initially reset to 0) is Incremented or decremented by 1 depending on the polarities of v^ and s^. Specifically, define i"l where Di - sgnCv^ • sgn (s^, as in (2.1A). Then if DBpD > 0, m = 0 is A declared; otherwise m - 1 Is decided. It can easily be seen that the detector will make an error if and only if a majority of the M samples have had their polarities reversed by the channel noise. Proceeding as in section 2.3, it can be shown that as M+«°, ^BPD *ias tne aBYmot-°ticaHy Gaussian distribution M M n( I (l-2p ) , I 4p.(l-Pl)). i-l 1 i-l 1 1 Using this result, it is shown in Appendix B that the probability of error for the BPD detector as M+- is given by p(e> - o ( /nr.) • o (2.18) 18 where a is as defined in (2.10). Compared with the DMF detector, we see that the BPD detector Is 10 log10(-~) - 1.96 + 10 log1()a dB less efficient. We note that the penalty can be interpreted as consisting of 2 components: 1.96 dB Is lost because decisions are based only on the polarities of the received signal samples (not on their magnitudes) and 10 log^a dB is lost because equal weights are being given to received signal samples even though the sample corresponding to a large js^ J is less likely to be in error than the sample corresponding to a small \B^\. These 2 components correspond to the losses resulting from the WPD and the SAS detectors respectively. 2.5. Generalization to Arbitrary Signalling Waveforms The results of the three preceeding sections can be easily generalized to arbitrary signalling waveforms. Let aQ(t) and 8j(t) denote any two finite-energy waveforms defined on [0,T]. This set of signals can be transformed into a set of binary antipodal signals by defining s (t) • a (t) ..(t) - .o(t) - _° and en(t) + a (t) sj(t) - Bj(t) --^ j-^ This transformation subtracts the arithmetic mean of the two signals from each signal. The results derived in the previous sections then apply directly to { *o^t^» }» where EG is to be interpreted as the energy in sl(t) or s!(t). The energy E of (2.4), (2.11), (2.16) and (2.18) can u x s be related (2.19a) (2.19b) 19 to the signals SQCO and s^(t) by noting that T E - / [s'(t)]2 dt s '0 0 i T 4- [ E + Ec - 2 J sn(t) s.(t) dt ], (2.20) 4 i sQ s2 'Q 0 1 where E , i-0,1, is the energy of s.(t). Of course, if s.(t) • -sn(t), 6^ 1 1 U T E - E - E . On the other hand, if E - E and / B-(t) s.(t) dt - 0 s s0 6l s0 Sj 'Q 0 1 E 80 corresponding to binary orthogonal signalling, Eg " leading as expected to a los6 of 3 dB relative to binary antipodal signalling. 2.6. Discussion The asymptotic losses associated with the use of three suboptimum detection schemes have been analysed. Table I gives a summary of the results as applied to three specific signalling waveforms. 20 Losses relative to DMF detector (dB) Waveform SAS WPD BPD Square Sinusoid Raised Cosine 0 0.912 1.76 1.96 1.96 1.96 1.96 2.87 3.72 Table I - Asymptotic losses for suboptimum.schemes. As Indicated below, these asymptotic values are reached quite rapidly. The losses for the SAS, WPD and BPD detectors are plotted against the sample size M in figures 2.2 - 2.5. In figures 2.2 and 2.3, a sinusoidal signalling waveform Is assumed, whereas a square signalling waveform is used in figures 2.4 and 2.5. For each figure, a target value of P(e) is used. In figures -3 -7 2.2 and 2.4, this value Is 10 and in figures 2.3 and 2.5, it is 10 . The losses represent the Increase In E required to achieve the same 8 target value of P(e) using the suboptimum detector and equation (2.4) respectively. The plots in these figures were obtained numerically using a VAX-11/750. Losses were calculated for each suboptimum scheme for different (odd) values of M. It should be noted that the distortion of the signalling waveform which would result for small values of M was taken Into account In these calculations. Details concerning the computation of P(e) are given in Appendix C. Recall that the samples are spaced TT sec. apart. The first Ob i 1 1 10 100 1000 10000 SAMPLE SIZE M Figure 2.2. The penalty as a function of the (odd) sample size M. The signalling waveform is a single sinusoid. Curves. B, D and F (A, C, E) are for the best (worst) choice of sampling starting time for the BPD, WPD and SAS detectors respectively. SAMPLE SIZE M Figure 2.3. The penalty as a function of the (odd) sample size M. The signalling wave is a single sinusoid. Curves B, D and F (A, C, E) are for the best (worst) choice of sampling starting time for the BPD, WPD and SAS detectors respectively. Figure 2.h. The penalty as a function of the (odd) sample size M. The signalling waveform is a square-wave. Curves A and B are for the worst and best choice of sampling starting time respectively for the BPD and WPD detectors. Curves C and D represent the worst and best choice of sampling starting time respectively for the SAS detector. Figure 2.5. The penalty as a function of the (odd) sample size M. The signalling waveform is a square-wave. Curves A and B are for the worst and best choice of sampling starting time respectively for the BPD and WPD detectors. Curves C and D represent the worst and best choice of sampling starting time respectively for the SAS detector. sample can be chosen anywhere In the interval (0 , -g). The difference in losses obtained by selecting the best and the worst times for the first sample is also indicated in the figures. As would be expected, the time of the flr6t sample has little effect on the losses for large values of M. Figure 2.2 shows that with the sinusoidal signalling waveform and P(e)«10 , for M greater than about 15, the SAS, WPD and BPD detector losses are within 0.05, 0.03 and 0.25 dB of their asymptotic values. For P(e)«*10-7, figure 2.3 shows that the corresponding figures are 0.1, 0.2 and 1 dB respectively. For square wave signalling, the WPD and BPD detectors are _3 equivalent. From figure 2.4, it can be seen that for P(e)=10 , and M greater than about 15, the SAS and WPD detector losses are within 0.5 dB of their asymptotic values. For a smaller value of T(.e)B10 \ figure 2.5 indicates roughly the same behaviour. 26 III EFFECTS OF OVERSAMPLING ON THE PERFORMANCE OF THREE SUBOPTIMUM DETECTION SCHEMES 3.1. Introduction In chapter 2, the penalty incurred in the use of three suboptimum detectors was analysed. The filter characteristics and the sampling rates used in the analysis guaranteed the independence of the received signal samples. In this chapter, the effects of sample dependence on the penalties are examined. The effects of oversampling are analysed for Butterworth, Gaussian and ideal lowpass filters as well as for a cascade of N identical poles. The receiver model is shown in figure 3.1. The case of antipodal signals will be analysed but the results can be generalized to arbitrary binary signals by using the transformation of section 2.5. Depending on the message me{0,l} to be transmitted, a signal +s(t) or -s(t) is sent over an additive white Gaussian noise (AWGN) channel. The two-sided power spectral density of the noise process is NQ/2. The signal s(t) Is assumed to be non-zero only in the time Interval [0,T] sec. and bandlimited to B Hz. The received signal r(t) is filtered to remove excess out of band noise to produce the signal v(t) which is then processed by the detector. The lowpass filter has 3dB cutoff frequency B. The detector samples the signal v(t) at a rate of 2cB samples per second yielding a total of M - 2cBT noisy samples « + of the transmitted signal where f - f(lx ~ ^'5^) »nd the ^ni^i-i are Gaussian (not necessarily independent) noise random variables with means 0 and variances a 2. The parameter c may be thought of as the oversampling factor, n Increasing c gives more, dependent, samples for processing. There are a LOWPASS FILTER V. -B B v(t) DETECTOR Figure 3.1. Block diagram of the data receiver. 28 maximum of M • 2BT independent samples available from an ideal lowpass filter corresponding to c • 1 and sampling frequency f • 2B [11]. The normalized sampling rate is c • fg/2B. In order to ensure that the transmitted signal is essentially undistorted by the receiver filter, we require that M = 2BT » 1. (3.1) The ideal lowpass filter admits noise power 0Q2 • NQB. In general, °n2 " W (3-2) where Yn " 2T ^ |H(f)|2df (3.3) is the normalized noise bandwidth of the filter and H(f) is the amplitude response of the filter. One has [18,19] |H(f)|2 - [1 + (f/B)21*]*1 (3.4a) N-th order Butterworth |H(f)l2 - [1 + (f/B)2(21/N - 1)]"N (3.4b) cascade of N identical poles |H(f)|2 - e-(f/B)2ln2 (3 4c) Gaussian for the N-th order Butterworth, the cascade of N identical poles and the Gaussian filter respectively. Using (3.4a) - (3.4c) and (3.3) gives Yn = 2N sln[*/2N] (3*5a) N-th order Butterworth Y - 1'3»5. (2N - 3)u (3>5b) 11 /21/N- iV (H-1) I cascade of N identical poles Gaussian for the N-th order Butterworth, the N-pole cascaded and the Gaussian filter respectively. 3.2. The Sample-and-Sum (SAS) Detector with Dependent Samples The SAS detector with dependent samples computes the quantity M D » £ v sgn(s.) as described previously in section 2.2. The SAS ±ml I I penalty may be determined by proceeding as was done there. Given that m • 0 is transmitted, the mean of DgAS is given by _ M DSAS " ^ '8il and the variance of DSAS 18 8IVEI1 by 30 «VC - E«DSAS " DSAS>21 * v^gnCe^ - j IsJ)2] (3.6) SAS i«l i-1 where E[x] denotes the expected value of x. The square in (3.6) may be expanded and the terms rearranged to give M—1 M a2 -o*M{l+'!E I ign(s . )r (J-i)j (3.7) SAS D i-1 J-i+1 where r (j-i) " E[n .n ]/E[(n )2] is the normalized autocorrelation of the n j I I noise which is assumed stationary. If the signalling waveform s(t) is continuous on 0 < t < T and single-phase, i.e. s(t) > 0 for 0 < t < T, then (3.7) gives SAS i=l j-1 Using the result [20] that . M-l i 11* £ I X rB(J) - I rn(j) M-~» " i-1 j-1 ° J-l whenever the series (3.9) 31 is convergent with (3.8) gives for large values of M SAS - a (3.10) when the series (3.9) converges. Let the term split-phase refer to a signal s(t) which is continuous on the interval 0 < t < T and which satisfies the conditions signum{s(tA)} • signum{s(tB)} - -1 for (0 < t>A < T/2, T/2 < tg < T) and s(T/2) - 0. Then result (3.10) is valid for split-phase signals. This is proven from (3.7) by proceeding as in the single-phase case. The following analysis applies to all signalling waveforms which satisfy (3.10). Gaussian random variables. Therefore, (3.1), (3.2), (3.10) and (2.10) give The random variable D SAS is Gaussian since it is the sum of jointly P(e) - P(e|m-0) - P(e|m-1) } (3.11) 32 Comparison of (3.11) with (2.4) shows that to achieve the same error probability as the optimum detector, the SAS detector with dependent samples requires aT^ more energy where r - Y U + 2 I r (i)}/c . (3.12) The loss represented by is in addition to the o loss described in section 2.2. One observes from (3.12) that T has two components. The factor Y n n . arises because a filter with finite roll-off admits more noise than an CD ideal filter with infinitely sharp cut-off. The sum £ rn(l) results from i-l the dependence of the samples. ( sin(ni/c) this case, Y - 1 and r (i) - —;—. , x . Using the fact that the Fourier * 'n nv (m/c) ° sine series representation for the function f(x) - n - %, 0 < x < it, is [21] It is interesting to consider for the ideal lowpass filter. In 8 in ix f(x) ~ 2 I llf i-l gives for x - K/C with c > 1, . r sin (ttl/c) _ . 2 J1 Oci/c) C 1 ' where convergence is guaranteed by a Fourier Theorem. Hence, T - 1 for all n values of c > 1 for the ideal lowpass filter. That is, processing more than the maximum number of independent samples neither improves nor deteriorates the performance when (3.1) is satisfied. Note also that the loss, a, incurred by not weighting the samples is not retrievable in whole or in part by oversampling. In the general case, the normalized autocorrelation r (t) of filtered n white noise is related to the filter characteristic by the Wiener-Khintchine theorem [22]. That is, rn(t) is the normalized inverse Fourier transform of the squared magnitude frequency response of the filter. Starting from (3.4a) - (3.4c) one may derive N r (T) - sin(n/2N) J exp[-2nB|t|sin ( n A=l 2A-1 2N Tt)] sin{ 2JL-1 2N n + 2itB|x|cos( 2JI-1 2N Nth order Butterworth (3.13a) rn<*> cascade of N identical poles (3.13b) rn(T) -T2*2B2/Jln2 e Gaussian (3.13c) for the N-th order Butterworth, the cascade of N identical poles and the Gaussian filter respectively. Figure 3.2 presents r (T) as a function of 2BT Figure 3.2. The normalized autocorrelation function *n(T) of white noise filtered by Butterworth lowpass filter of order N. The ideal lowpass filter corresponds to N =» «°. 35 BT for the Butterworth (N - 1-4) and Ideal lowpass filters. Figure 3.3 shows rn(t) for the cascaded pole (N • 1, 2, 4, 6) and Gaussian filters. The terms in the sum of (3.12) occur at time instants - l/2cB. Therefore, equations (3.13a)-(3.13c) combined with (3.12) •nd (3.5a)-(3.5c) yield, after some manipulations, - — sin a. N sinfa,+ - cot i.) - e C sin a. n ' 2cNsin(*/2N) ll+Blni2Nj * Z7^~~t ^ r* \ ' ' JM. cosh'^— sin s^j - cos^— cos a^) 21-1 •A • ic N-th order Butterworth (3.14a) r - 1'3»5« ... (2N-3)n ... 2(N-1)1 r -ih n / i/N •» M (2N-2) 1 £ /21/N-1 2N(N-l)!c 11 "r1 (2N-k-2)!(21h)k , h 1 k!(N-k-l)l >» C/2T7T7 (3'14b) cascade of N Identical poles x 1 Gaussian (3.14c) The quantity Is plotted as • function of the normalized sampling rate f /2B - c in figures 3.4 and 3.5 for Butterworth and cascaded pole filters respectively. Also shown In figure 3.5 is the curve for the Gaussian filter Figure 3.3. The normalized autocorrelation function rn(T) of white noise filtered by a cascade of N identical poles. The Gaussian filter corresponds to N = ». 3.0 r (dB) n 2 3 5 10 Normalited Sampling Rate f /2B Figure 3.5. The additional penalty rn for the SAS detector with prefilter consisting of a cascade of H identical poles. The Gaussian prefilter corresponds to N • ». u> OO 39 which corresponds to a cascaded-pole filter with N - ». In all cases, T decreases with c and lim T • 1. Using the Wlener-Khintchine theorem, it n c+" n ° ' can be shown that lim r - 1 for any filter provided that r (T) is c*» n n integrable. 3.3. The Weighted Partial Decision (WPD) Detector with Dependent Samples The WPD detector with dependent samples bases its decision on M M DWPD " I 8gD( Vi ),8i " I Di'8il (3-15) U i-1 1 1 i-1 1 1 as described in section 2.3. The error probability is found by proceeding as previously. That is, the mean and variance of D^^ are derived and a central limit theorem is used to approximate the error probability for large values of M. The partial decision random variables D^ are now permitted to be dependent. In order to proceed, we postulate that a central limit theorem holds for certain sums of dependent random variables. Many central limit theorems for dependent random variables formalise in some sense a heuristic notion that one expects a central limit theorem to hold if the random vari ables behave more like independent random variables the further they are separated [23]. The dependent random variables considered here behave in this fashion. Computer simulations are used to test the validity of the postulate and to illustrate how the penalty varies with M. When a general filter and dependent samples, as described by (3.1) and (3.2), are considered equation (2.15) must be replaced by pi = Pr(ni>lSil) " Q^y/~Yp^ ^i11 ' (3'16) The mean and variance of D^|s^| are again given by (l-2p^)|s^| and Ap^(l-p^)||2 respectively. The mean of D^pp is found from (3.15) DWPD- X CX-2p±>|.±| (3.17) 1=1 and the variance of nypD is M M UWPD i-l i-l M MM I |. |2+ I I |s ||s | {E[DD -DD ]} . (3.18) i-l "i 1 i-l J-l x J i*j It is shown in Appendix D that for large values of M E[DtD ] - - -| arcsin {rn(j-i)} (3.19) where the noise process is assumed to be stationary. Then (3.18) can be rewritten as 41 M 2 M M 1 - I |s±|2 + - I I |s ||s |arcsin{r (j-i)} . (3.20) WPD 1=1 1 1 71 1=1 j*»l n i*j By proceeding as in Appendix A with p^ given by (3.16), it may be shown that for large values of M M ME I-JI-il'-T1 (3-21> i=l i and /4cM \ *VnT D » /_-l£EL- E . (3.22) WPD / IN v T s Furthermore, it is proven in Appendix E that as M-*89 Combining (3.21) and (3.23) with (3.20) and (3.22) gives WPD WPD 4E c 8 1 (3.24) Applying a central limit theorem to the sum of (3.15) and using (3.24) gives the error probability P(e) 4E c 8 ulW1+" I arcsin{rn(i)}) (3.25) 1=1 Comparison of (3.25) with (2.4) shows that the penalty of the WPD detector with dependent samples is it/2 where rn " I I «csln{rn(l)}]/c . (3.26) The loss represented by Tn is in addition to the n/2 or 1.96 dB loss of the WPD detector with independent samples. Note that 2/it arcsin{rn(i)} is the normalized autocorrelation function after hard-limiting of a random variable possessing normalized autocorrelation function rn(i) [24]. Equation (3.26) is, therefore, analagous to equation (3.12). The function 2/ir arcsin{rn(BT)} is shown in figures 3.6 and 3.7 for Butterworth and cascaded pole filters respectively. The additional penalty r is plotted as a function of the normalized sampling rate in figures 3.8 and 3.9 for Butterworth and cascaded pole fil ters respectively. The values r (i) are determined from equations (3.13a) -n (3.13c) with r (i) - r (i/2cB). Observe that for high sampling rates, the n n penalty for a low order filter is less than that for a high order filter. For example, in figure 3.8 at f /2B • 15, T « -1.5 dB for N - 1 while s n T - -0.9 dB for N - °°. A similar observation was made in [25], in the n -0.25 I I I I I 0 1 2 3 4 5 2BT Figure 3.6. The normalized autocorrelation function of white noise after lowpass filtering and hard-limiting. The filter used Is N-th order Butterworth. The ideal lowpass filter corresponds to N • 00. -p-0 0.2 0.4 0.6 0.8 1.0 BT Figure 3.7. The normalized autocorrelation function of white noise after lowpass filtering and hard-limiting. The filter used is a cascade of N identical poles. The Gaussian lowpass filter corresponds to K * •, Figure 3.8. The additional penalty r of the WPD and BPD detectors. The prefliter is H-th order Butterworth lowpass. The ideal lowpass filter corresponds to H • "• 46 r (dB) n Konnallred Sampling Kate fg/2B Figure 3.9. The additional penalty T of the WPD and BPD detectors. The prefilter is a cascade of F identical lowpass poles. The Gaussian lowpass corresponds to N • ". 47 context of polarity coincidence array detectors. 3.4. The Binary Partial Decision (BPD) Detector with Dependent Samples The BPD detector with dependent samples computes A M D„™ -ID.. (3.27) BPD /, i 1=1 The probability of error is determined by proceeding as in section 2.4, For large M, PBPD / 4cT{<ls(t)|>}2 m I 4cEs B?D «csin{rn(i)}] / uNoyna[l+^I arcsin{rn(i)}] i-1 V i-1 (3.28) where a has been previously defined in (2.10). Assuming a central limit theorem holds for the sum in equation (3.27) and using (3.28) gives for the error probability r / *CEB W I PBPD(e)"Q1 / r Ar r n f (3'29) 1/ -,oTnatl+i:X«"lll{rn(1)H J The penalty of the BPD detector with dependent samples Is found by comparing (3.29) with (2.4). It is o w/2 T where T is given by (3.26). That is, the n n additional penalty is the same for the BPD and WPD detectors and is independent of the signalling waveform. 3.5. Conclusions The asymptotic losses of three suboptimum detection schemes with dependent sampling have been analyzed. In order to verify the central limit theorem postulated in section 3.3 and to illustrate how quickly the asymptotic values are reached, we have simulated the WPD detector with dependent samples. Coloured Gaussian noise samples were generated using the method of reference [26], The signal-to-_3 noise ratio required to attain P(e) • 1.00 x 10 is determined from figure 3.8 and equations (3.25) and (2.4). Using a first order Butter worth prefilter, the simulated error probabilities for fs/2B • 1 were 1.13 x 10"3 and 1.01 x IO-3 for M - 9 and M * 31 respectively. For -3 f /2B - 3 and M « 27, 93 and 303 the P(e) values were 1.77 x 10 , s -3 -3 1.14 x 10 and 1.05 x 10 respectively. It was noted earlier that better performance can be achieved by using a first order lowpass filter rather than a fourth order filter. This has also been verified by simulation. Again, the SNR _3 required to achieve P(e) • 1.00 x 10 is determined from the present results and used in the simulator. The analysis indicates that 0.48 dB greater SNR is required for the fourth order filter when both filters are Butterworth and f /2B = 15 for M = 1515. The s -3 -3 simulated error probabilities were 1.09 x 10 and 1.04 x 10 for the first and fourth order filters respectively. Note that an -3 -4 increase of 0.48 dB decreases P(e) from 1.00 x 10 to 5.46 x 10 IV OPTIMAL DETECTION OF HARD-LIMITED DATA SIGNALS IN DIFFERENT NOISE ENVIRONMENTS 4.1. Introduction A number of digital techniques for detecting binary antipodal 6 ig rials are based on examining the polarities of the received signal samples and ignoring their amplitudes. The weighted partial decision (WPD) and binary partial decision (BPD) detectors analyzed in chapters 2 and 3 are two examples. In this chapter, the structure of the optimum detector DQJJ ^ for the hard-limited samples is derived. Its performance is compared with those of some commonly used ad hoc detectors in both impulsive and Gaussian noise environments. For the Gaussian case, the performance is also compared with that of the optimum detector D^p^ which operates directly on the unquantized received samples. The generalization of the D0pT ^ detector to M-ary signal ling with each received sample quantized to an arbitrary number of levels is also examined. The optimum, minimum probability of error, receiver for this case is derived. 4.2. Derivation of the Optimum Detector for Hard-Limited Samples In this section, we derive the optimum processing for a number of hard-limited samples. For ease of discussion, it is assumed that the samples come from one of two antipodal signals that have been corrupted by additive channel noise.* Depending on the message The analysis Is extended to arbitrary signalling schemes in section 50 me{0,l} to be transmitted, a signal +s(t) or -s(t) is sent over a noisy channel. The detector decides which message m, me{0,l} was sent on the basis of the hard-limited samples. The optimum detector D minimizes OPT , HI* the probability of error P(e) * Pr( m ¥ m ). Assume that the transmitted signals ±s(t) are time-limited to the interval 10,T]. If s(t) is sent (corresponding to message m-0), then vi " + + nj • 1 " lf2....»Ne (4.1) N .i~0 5 IT where {v^} 6 denote the Vg samples of v(t), i.e. - v —K* ' ), to be N N N i-1 processed. The values {s.} 6 denote the samples of +s(t) and {n.} s 1 i-1 1 i-1 represent outcomes of independent noise random variables (r.v.'s). The noise is assumed to possess an even probability density function. If the message Is m-1, then -s(t) Is sent, and Vj - -Sj + n^, 1-1,2,...,Ng. Each sample is hard-limited by the detector according to {I if sgn (Vj) - sgn(s1) # 0 if sgn(v1) - 0 or sgn(&1) - 0 (4.2) otherwise if x > 0 where sgn(x) - 0 if x - 0 if x < 0 The probability that sample v± Is of opposite polarity to the transmitted sample +ei or -s1 (s^O, v^O) Is given by Pj - Pr^-llm-0) - Pr^-llm-l) - Pr^ > \B±\) . (4.3) The minimum P(e) detector corresponds to the maximum a posteriori (HAP) decision rule which states that m-0 is chosen if N N Pr({d } 8 |m-0) Pr(m-O) > Pr ({d > 8 |m-l) Pr(m-l) (4.4) 1 1-1 1 1-1 where d^ denotes a particular outcome of the random variable D^. In the case of equally likely messages, Inequality (4.4) reduces to N N Pr({d.) 6 |m-0) > Pr({d,} 8 |m-l) . (4.5) X 1-1 1 i-l Let A1 denote the set of all I's such that d^-1 and A_^ denote the set of all A i's such that d^—1. Then, the optimum decision rule Is to choose m-0 if n (i-p.) n p > n p. n U-P.). (4.6) icAl 1 icA_x 1 icAj 1 IcA_1 From (4.6), the optimum decision rule can be stated as follows: form the statistic DOPT,HL£ j^i * ' (A'7) if d-__ „. > 0, m-0 is declared; otherwise, m-1 Is declared. OFT,HL Various weighted partial decision (WPD) detectors for hard-limited signals have been proposed (2] which have the following general form. The . Ns Ns test statistic i6 d„__ - J d.u., where {u. } are weights assigned to the Wt i-l 1 1-1 different samples. The WPD detector chooses m-0 if & ^ > 0 and m-1 if dwpD < 0. The weights Wj-1, w1"ls1l and wi"8i* are often u8ed» 1* c5n ^e seen 52 from equation (4.7) that the optimum weights are given by " An (-p-i) . (4.8) In the next three sections, the detector DQPJ hl is compared to these schemes and, in the case of Gaussian noise, to the optimum detector based on the N unquantized samples {v.} 1 i-1 4.3. Optimum Weights for Low Slgnal-to-Noise Ratios In this section It Is shown that, for most common noise models, the optimum weights as given by equation (4.8) are well approximated by = |s^| when the signal-to-noise ratio (SNR) is low. Assume that the noise variables N {NjJ 6 have an Identical probability density function (pdf) which Is even. 6 i-1 This holds for most commonly used noise models such as the Gaussian, Laplace or Cauchy pdf s. Let the cumulative distribution function (CDF) be denoted by Fn(*)» Suppose that Fn(•) can be represented by a Maclaurin series expansion, i.e. Fn<"> - j0 Fnk<°> £ <4'9) where Fn (0) denotes the k-th derivstlve of Fn(o) evaluated at a-0. One may combine (4.3), (4.8) and (4.9) to obtain # F(|s.|/o) 53 1 r- k <l»il/">k JUiI — i— 1 (A.10b) Irk (l6il/0>k ' 4- i O(o) 1 2 k-i n - k <i»,iMk 2 I Fn (0) El - An ( 1 4—^ - ) CA.lOc) V i ? r"nn(l''|/o) 2-J/n^-kl-In (4,10b) the fact that the noise pdf is an even function has been used and o is the noise scale parameter. For low signal-to-noise ratios, i.e. |s^|/o << 1, one has w* - AFn1(0) IsJ/c, (A.11) since An(l + x) - x - -| x2 + -| x3 + ..., for -1 < x < 1. In (A.11) it has also been assumed that F A(0)^0, as is the case for a Gaussian, Laplace n or Cauchy pdf. Finally, one notes that scaling of the weights by a * constant does not affect the decision rule. Hence, may be chosen to be approximately equal to |s i'-4.4. Optimum Weights for High SNR's In the case of high SNR's the optimum weights depend on the noise pdf. The Gaussian, Laplace and Cauchy distributions will be considered in turn. 54 4.4.1. Gaussian Noise Distribution For a Gaussian noise r.v. of variance a 2, it follows from equation n j wnere v\«U - • JTh a s 2 1' 1 1 — » 1, p. Is well approximated [31] by r——r exP ( )• From (4.8) ti i^ii 1 i1 2o 2 M\K 1 r" -X2/2 (4.3) that p. - QM- where Q(a) - J e ' dx. When the SNR Is high, 1 °n m a n °n the optimum weights are approximated by s 2 * 1 w. . (4.12) 1 W Since scaling the weights by a constant doe6 not affect the decision rule * 2 defined by (4.7), can be chosen to be approximately equal to s^ . 4.4.2. Laplace Noise Distribution This distribution Is sometimes used as a model for Impulsive noise [11]. The Laplace pdf Is defined by f(o) - -j£ e"'°'/c, < a< with 1 -I8l'/C variance 2c2. In this case, Pj --J « . For high SNR's, from (4.9), the optimum weights can be approximated by i- . (4.13) 1 c Since the decision rule is unchanged by scaling [u.} , u. can be chosen as i-1 4.4.3. Cauchy Noise Distribution The Cauchy distribution defined by the pdf f(o) --£7^^. < a< », Is used to model severe impulsive noise [27] • In this case for high SNR's, * the optimum weights are approximately given by " 1 as shown in Appendix F. 4.5. Some Numerical Examples In thl6 section a number of examples are presented. These examples Illustrate some of the Issues Involved In the selection of the weights and compare the detector performances for different choices. In all of the A A examples the signal-to-noise ratio is defined as 20 logi0 (—), 20 logi0 (-) n and 20 log^Q f^) for the Gaussian, Laplace and Cauchy distributions respectively, where A is the pulse amplitude. As a first example, we consider the detection of a taised cosine pulse, sampled Ng - 11 times according to (4.1), in Gaussian noise. The optimum detector for the unquantlzed samples In Gaussian noise Is the digital —* P(e) - Q(/ I •12/on). matched filter (DMF) for which P(e) - Q(/ I *42/o J. Figure 4.1 shows the i-l probability of error obtained using the DMF and the WPD detector with weights 1-P4 I-P* in( -). |s1|, s42 snd 1. The Inf——) and curves, though indistin-Pi ' ' 1 Vpi gulshable, are not Identical. It can be seen that the use of the s^2 weights Instead of the optimum weights results In little loss. However, the use of Figure U.l . Error probabilities for the DMF detector and four different WPD detectors. A raised cosine pulse in additive white Gaussian noise is sampled 11 times. 57 ti^-1 results in a substantial loss, e.g. a penalty of about 3.7 dB is incurred at P(e)-10~1* relative to nQpT For the same error probability an inherent penalty of about 2 dB results from hard-limiting the samples. It Is Interesting to note that In certain cases, the WPD detectors with weights 1_Pi ln(—-—), Is^l and B^2 are equivalent. Examples Include the case of a raised cosine In Gaussian noise sampled N - 3, 4 or 6 times. 6 For a second example, the detection of a half sinusoid pulse sampled Ng"3 times is investigated. Thl6 example shows that caution should be N 5 exercised when dealing with ties. A tie occurs when d^p^ - £ d^ o^-O. If i-1 the weights || are used, a tie will occur if the first and third samples have opposite polarity to the second sample. One option In this case Is to A choose message m based on the outcome of a fair coin toss. This may, however, lead to poorer performance than that obtained by using the optimum MAP decision rule. This Is Illustrated in figure 4.2 which shows the error probability as a function of the SNR for the WPD detector with weights 1-P4 1-P4 w - Jtnf i), Is. I, and s 2. In this case, the Jtnf " ) and s 2 weights are 1 v p ' - • l' l "i equivalent. The |s^| weights detector with random tie resolution performs poorer at high SNR'6, e.g., an Increase of about 1.5 dB In SNR Is required to maintain a target value of PCe)-!©"1*. In this case If the decisions corresponding to ties are properly chosen, the || weights detector is equivalent to D0PT)HL-Also shown in figure 4.2 are the error performances of the DMF detector Figure U.2. Error probabilities for the DMF detector and four different WPD detectors. A half sinusoid in additive white Gaussian noise is sampled 3 times. oo 59 and the WPD detector with u^-l. It is 6een that the WPD detector with optimum weights (or 6^* weights) performs poorer than the DMF detector by about 1*8 dB (actually a factor of 1.5). It performs, nonetheless, appreciably better than the equal weights detector; e.g., to achieve P(e)-10~\ an additional 2.0 dB is required. An example involving the detection of a raised cosine pulse sampled Ng»7 times in Laplace noise 16 now considered. As discussed in sections 4.3 and 4.4, the weights |s^| are nearly optimum for very low and very high SNR environments. This can be observed in figure 4.3. The only noticeable l"pi difference between the An(~—) *»d |s1| curves occur for SNR's between -3 dB and 21 dB. The weights u -1 detector is significantly poorer, the difference being about 4 dB at P(e)«10~5. The • B^2 detector performs almost as well as the optimum weights detector. The difference is less than 0.6 dB for P(e) < ~10~6. The last example of this section Involves the detection of a raised cosine pulse sampled Ng«3 times In Cauchy noise. The error probabilities for 1-pj , . u>, • inf =•), Is. I and 1 are plotted in figure 4.4. The weights \s. | 1 vp^ ' 1 detector outperforms the equal weights detector when the SNR is less than 15.1 dB. For higher SNR values, the unity weights detector has a signif icantly better performance. In Appendix G it is shown that in this example with Ng » 3 samples the P(e) of the optimum weights detector is equal to the smaller of the P(e)'s for the weights Js^j and 1 detectors. For this example, it can easily be seen that the weights |s.| and s. detectors are equivalent. P(e) -20 -10 0 10 20 SNR (dB) Figure U.3. Error probabilities for the detection of a raised cosine pulse in Laplace noise sampled 7 times. Three different WPD detectors are illustrated. o 61 -20 0 20 40 SNR (dB) Figure k.k. Error probabilities for the detection of a raised cosine pulse in Cauchy noise sampled 3 tines. Three different WPD detectors are illustrated. However, there are signalling waveforms for which the weights Jsj| detector performs much better than the weights s 2 detector. 4.6. Generalization to M-ary Signalling and Multilevel Quantization In this section, the WPD detectors for M-ary signalling with each received sample quantized to an arbitrary number of levels are examined. These detectors can be viewed as generalizations of the binary signalling detectors of section 4.2. Thus, consider that the message m can now take on one of M values, m e{l,...,M}. Corresponding to n • J, the signal s^(t) Is 6ent and the Ng received samples are vj " sj j + n1» 1 * l»2,...Nfi, j e {l,2,...M} where s, - s. ft *~f;: ) and {n } 6 are Independent noise J.* J Ns 1 i-1 samples. Let v-(vj,v2»••«v^ ) denote the vector of received samples. In the _ s case of M equally likely messages, the minimum P(e) detector corresponds to the maximum likelihood decision rule, I.e., choose m-j If Fr(v|m=j) > Pr(v|m-k) for all k # j . (4.14) Let each received sample v , i-l,2,...,N be quantized to one of q regions {R .} q and define the function d -A if v e». On the basis of d-(dltd2 dN ), the WPD detector decides on the transmitted message m. "~ 6 A The minimum P(e) detector will decide m-j if Pr(d|m-j) > Pr(d|m-k) for all k # J . (4.15) Since the samples are Independent, Inequality (4.15) becomes 63 N N 6 S n Pr(d |m-j) > II Pr(d |m-k) , all k * j . (4.16) 1-1 1 i-l 1 Let A^ denote the set of all I's such that d^-I. Then (4.16) can be rewritten as n Pr (di-l|m-j) n Pr(d1-2|m-j)... n Pr (d^q |m«j ) > cA, ieA, leA 1 2 q (4.17) n Pr(d1-l|iu-k) n Pr(dj-2|m«k)... n Pr (dj-q |m«k) all k * j . IEAJ 1EA2 ieAq Defining Pi Jl|n " ^ (d1"AlD"n)» 1 " 1»2»'*«NS» i " l»2,...,q, n - 1,2,...M and taking logarithms, (4.17) becomes l z q ^ L * Pi.l|^ + ,L * P^2ilc + - + I *> Pi,q|k' 811 k * J ' icAx ' 1 leA2 ' 1 iEAq From (4.18) it is seen that one way of implementing the optimum WPD detector is as follows: Associate with each message an accumulator C , n=l,2,...,M. n Step 1. Initialize all M accumulators to zero* Step 2. For each 1, i-l,2,...,Ns increment Cn by In ^n if and only If vi c Ri,r Step 3. Determine the accumulator with the largest value, i.e., C. - max{C }; declare m-j. ^ n It can be verified that the above procedure when M-q-2 and sit±m~B2ti reduces to that of section 4.2. We conclude this section by looking at an example. Figure 4.5 shows the error probabilities for 2, 4 and 8 level pulse amplitude modulation (PAM) for the DMF and the WPD detectors with optimum and unity weights. In this example q=M and the term "unity weights" refers to incrementing accumulator C by 1 if and only if v. c R, • In this 6 n J i,n example, the signalling waveforms are raised cosines and the noise is Gaussian. The M amplitude values are ±B, ±3B,..., ±(M-1)B where B is the amplitude of the smallest energy pulse. The M-l decision thresholds for any sampling Instant are located at the midpoints of the Intervals between adjacent signals. In all cases the receiver processes 5 samples. The SNR Is defined as the average value of 20 log10(A/on) where A Is the amplitude of the pulse and the M messages are assumed equiprobable• The optimum detector for the Ng unquantized samples makes Its decision according to (4.14). Furthermore, Pr(v|m«j) • P^ (y-_sj ) where _6j denotes the vector of signal samples {s. .} and P»(*) denotes the N-fold Gaussian density of the noise samples. Equivalently, the optimum decision is to pick the signal j that lies closest In terms of Euclidean distance to the received vector. By making use of the fact that the signal vectors are collinear the probability of error for the DMF In this case can be shown to be where_£u denotes the signal with amplitude B. One sees in figure 4.5 that the WPD detector with optimum weights suffers some loss relative to the optimum detection of the unquantized P(«) 0 10 20 30 SNR (dB) (•) Figure 4.5. PAM error probabilities for the DMF and the WPD detectorB with optimum and unity weights. The received signals are raised cosines In Gaussian noise sampled 5 times. The number of signalling levels is 2, h and 8 for figures (a), (b) and (c) respectively. 0 10 20 30 SNR (dB) (b) Figure U.5. PAM error probabilities for the DMF and the WPD detectors with optimum and unity weights. The received signals are raised cosines in Gaussian noise sampled 5 times. The number of signalling levels is 2, 1* and 8 for figures (a), (b) and (c) respectively. o ON Figure U.5. PAM error probabilities for the DMF and the WPD detectors with optimum and unity weights. The received signals are raised cosines in .Gaussian noise sampled 5 times. The number of signalling levels is 2, k and 8 for figures (a), (b) and (c) respectively. <JN 68 samples. For P(e)«10~* there Is a penalty of about 2.2 dB for all 3 cases. The performance is, however, significantly better than when equal weights are used. The differences are about 3.2, 3.4 and 3.5 dB for signalling with 2, 4 and 8 levels, respectively, for the same PCe)-!©"4* value. 4.7. Conclusions The problem of detecting binary antipodal data signals based on a number of hard-limited samples has been analyzed and the optimum detector has been derived for an arbitrary nol6e environment. The optimal processing Is characterized by a set of weights. In general, the values of the weights depend on the signal-to-noise ratio as well a6 on the shape of the signals and the probability distribution of the channel noise. The optimal weights are approximately |s^| for low SNR's for most noise environments. For high SNR's the weights *^2» |s^| and 1 are nearly optimum for Gaussian, Laplace and Cauchy noise respectively. In some Instances, a set of weights which Is Independent of the signal-to-noise ratio performs almost as well as the optimum weights for practical ranges of SNR. It Is interesting to note that in these cases, nearly optimum processing of the hard-limited samples can be performed using only threshold decisions and additions. The optimum detector for M-ary data signals based on samples quantized to an arbitrary number of levels has also been derived. The processing requires forming sums of optimized weights, analogous to the binary antipodal case. V PENALTIES OF WEIGHTED PARTIAL DECISION DETECTORS IN GAUSSIAN NOISE 5.1. Introduction The performance of the WPD detector with weights - |s^| has been analyzed for low SNR conditions in chapters 2 and 3. The optimum WPD detector for arbitrary SNR was derived in chapter A. In this chapter, the penalties of WPD detectors are analyzed for arbitrary signal-to-noise ratios. The weights * (s^J and ID • s^^ detectors as well as the optimum weights detector are considered. The effects on the penalties of the signalling waveform employed, the number of samples processed, and the SNR are considered in detail. The optimum WPD detector is the optimum detector for hard-limited samples and the digital matched filter is the optimum detector for the continuous amplitude samples. Hence, the penalty of the optimum WPD detector relative to the DMF detector represents the fundamental loss in signal detectability due to hard-limiting in a sampled system. 5.2. Problem Statement We consider the model of a data communication system shown in figure 5.1. Depending on the message me{0,l) to be transmitted, a signal +A s(t) or -A s(t) is sent over the additive white Gaussian noise (AWGN) channel. The positive constant A is a scaling factor. The received signal r(t) is filtered to remove out of band noise and the resulting signal v(t) is sampled at some appropriate rate. TRANSMITTER NOISY FILTER • t (0, 1} * A 8(t) CHANNEL r(t) m e (0, 1} DETECTOR SAMPLER v(t) Figure 5.1. Block diagram of the data communication system. 71 Assume that the signal 6(t) is time limited to the Interval [0,TJ. If A s(t) is sent (corresponding to m-0), then Vi " +A 8i + °i * i-l»2f-»M (5.1) ^ 11—0 5 IT where {v.} denote the M samples of v(t), i.e. v. - Ei~)» t0 De 1 i-1 n M M processed. The values {s.} denote the samples of + s(t) and {n } 1 i-1 1 i-1 represent outcomes of Independent Gaussian noise random variables, each with variance o2. If m-1, then -A s(t) is sent and v^ - -A s^ + n^, M 1 - 1,2,...,M. The detector bases its decision on {v } 1 i-1 It is veil known [l] that the optimum detector for minimizing the probability of error P(e) - Pr {m * m} in the problem described above is the digital matched filter (DMF). The DMF computes DOPT " X V* 8* (5'2) i-1 and chooses m-0 if DQ^ > 0; otherwise it declares m-1. The resulting probability of error is /M 1 (5.3) 72 where Q(a) • / e X ^ dx. It is convenient to assume that s(t) is /fit a normalized so that its maximum value is equal to 1. We define the A signal-to-noise ratio (SNR) to be 20 log1Q-^ measured in dB. In this chapter, the penalties of the weighted partial decision detect ors are measured relative to the DMF detector. The penalty is defined as the increase in signal-to-noise ratio required by a suboptimum detector in order to achieve the same target value of probability of error as the DMF detector. 5.3. Weighted Partial Decision (WPD) Detectors In the family of WPD detectors, the received signal samples are first A A . . hard-limited. The decision a6 to which message m, BE{0,1J was sent Is based on the hard-limited samples. Let the random variables representing these samples be denoted by if sgn (v4) - sgn (s1) # 0 if sgn (vA) - 0 or sgn (s1) - 0 (5.4) otherwise * Then the general WPD detector forms the test statistic M A D - T D u . (5.5) "WPD *x ul wi ' y 1 M where {u^} are the weights assigned to the different samples. The detector chooses m-C if D^ > 0 snd m-1 if D^ < 0. Some caution should be 73 exercised in choosing m if DypD = 0 as shown in section 4.5. The optimum ( minimum P(e) ) weights to be used in (5.5) are given by (4.8) in(-1 " P. ) . (5.6) where p^ i6 the probability that the 1-th sample has its polarity reversed, i.e. Pj » Q(A|si|/a). The weights « 1, - 16^ | and • 2 have also been previously suggested. Let B denote a subset of U - {l,2 M} and Bc its complement. Then the probability of error for a WPD detector can be written as PWPD(e) " E I(B) 11 pi 11 c (1"pi) " all B ieB 1 ieBc (5.7) where 1(B) ieB leB" ieB ieB-0 , if I itfj < I m1 IeB ieB-In (5.7), it is assumed that if Dypn " 0, m is chosen according to the out come of a fair coin toss. The probability of error P^^e) can be directly computed from equation (5.7). This, however, may Involve considerable computational effort. In some cases, more computationally efficient methods can be used to compute P^pp(e) as described in Appendix C. An expression for the penalty at high SNR values is derived in Appendix H, namely M r„D (.,«,.)- if (5.8) ieB vhere B* C U and B* has the properties that I(B*) > 0 and X s. 2 < X s. * * * 2 "i ieB ieB for all B C U for which 1(B) > 0. The penalty for lov SNR values is given by 22M"2 J 8i2 ^ ( s,M,0 ) ^ . (5.9) [ X KB) { X Kl - X l»ilH all B ieB icBc This result may be derived by applying the procedure of Appendix K to ?ypD(e) as given in (5.7). 5.4. The WPD Detector for a Piecewise Constant Amplitude Signalling Waveform For a piecewise constant amplitude signalling waveform, the weights • 1, • |s4|, - Sj2 and - w* WPD detectors are equivalent. With |s1| « 1, the penalty relative to the DMF detector Is defined implicitly by X (?) P1 d-P)""1 • M odd -l * (5-10) M M X (?) P1 (1-P)M_1 + 4 ( " ) [P(J-P)]2 • M even i» where p - Q(/2»m4 )%4 ) 8nd the notatlon ?m < ±***0 ) is used to explicitly Indicate the dependence of the penalty Typ^ on »• (s itS2> • • • »s^) , M and ^ . Equation (5.10) can be used to compute rwpD( ) as follows. Defining y ^ / IJ^C 2 »M»4 > 4 » one can rewrlte (5.10) as Q( & 7 ) " T(M,y) (5.11) / where M I (?) P1 (I-P)"'1 M+l 1 , M odd T(M,y) - / and p - Q(y). From (5.11), one has W x»M'i > ^—\ - (5-12) [Q"1{T(M,y)}] Figure 5.2 shows a plot of JtM^ ) against ~o for M-1, 2, 3, 4, 10 and M v2 y 11 obtained by plotting 2 as a function of y • It [(TMT(M.y)}]2 0T1{T(M,y)} can be observed that the penalty Is a non-decreasing function of and 16 upperbounded by 2 (3.01 dB). Explicit expressions for the penalty for small and large SNR values are now examined. In Appendix I, it Is shown that 4 M - 2 M - 4 M - 10 M - 11 M M-1 -50 -25 25 50 20 log1() ( A/o ) (dB) Figure 5.2. The penalty ( ) as a function of the signal-to-noise ratio for seven values of sample size M. 77 ,2M-2 M-1 , M odd 2 ,2M M (I) , M even (5.13) U6ing Stirling's formula it follows that lim rWpD( i.»M»° ) " * Equation M-K» (5.13) also shows that r^a.i.o) < rWDQ,3,o) < ... < r^a.4,0) < rHPD(i,2io) . (5.14) By using the approximation Q(a) * shown that -a2/2 e /2~* o , a » 1, in (5.10) it can be rWPD( i'M'" } " 12 , M even \2 " Wl • M odd • (5.15) It 16 also possible to determine the penalty T^^i .i»M»"o- ) for lar8e values UB A of M. The basic approach is to derive an upper bound T^^i ) using the UB A Chernoff bound [28,29] and to show then that J..-*— ) 16 also 8 lower A bound on Iyp^ ±»mrj, ) • The details appear In Appendix J. The curve rWPD( ) 16 Plotted in fig^e 5.2. 5.5. The Optimum WPD Detector for Arbitrary Signalling Waveforms In the case of an arbitrary signalling waveform, the penalty * A *WPD^ —'^'"o ^ *or tne °Pt^num detector can be evaluated numerically by >ting Q(/T~7*A] equatin Q(/ J s.2—) to the right side of (5.7) with i-l ° P4 - Q(/r^pDC )Isjl) and - Jta£-—i). The procedure is ^ 1 analogous to that followed in (5.10) to (5.12). The results for a raised cosine and a half sinusoid signalling waveform are plotted in figures 5.3 and 5.4 respectively. In both figures, for a fixed value of M, the penalty A increases with — even though it is essentially constant for small and large values of —. a It is shown in Appendix J that, for large values of M, the penalty is upper bounded by C< > , ^ <•'<'>> — (5.16) WD ° < in{4Q(y|s(t)|)[l-Q(y|s(t)|)]} > where y - / rj^D( B,»J± j± and < f(t) > &j jj f(t)dt is the average of f(t) f(t) on the Interval te[0,T]. This bound is plotted in figures 5.3 and 5.4. For the examples considered here T^^i. ) close to Iy^D( .£»•»•" ) when M > 10. As sn example, Jrjjp^ mT-A0 ) " r^pD< ^.lO^ )l < 0.14 dB for both -50 -25 1 M-1 25 50 20 log10 ( A/o ) (dB) * A Figure 5.3. The penalty ( J.tM,— ) of the optimum WPD detector as a function of signal-to-noise ratio for a raised cosine signalling waveform. Six values of sample size M are illustrated. The curve for M B • is an upper bound. 4 M - 2 M - 4 M - • M - 5 M - 3 JJLl -50 -25 25 50 20 log1() (A/o ) (dB) Figure 5.H. The penalty T*pD ( j»tM»~ ) of tne optimum WPD detector as a function of signal-to-no ratio for a half sinusoid signalling waveform. Six values of sample size M are illustrated. The curve for M = » is an upper hound. 81 the half sinusoid and raised cosine. For large values of — , (5.16) becomes 5.6. The Weights u± - |s1| and - s±2 WPD Detectors The weights • || and • s^2 WPD detectors have been previously examined for low signal-to-nolse ratio conditions. It has also been shown that the optimum WPD detector 16 equivalent to the || and s^2 weights detectors for low and high SNR conditions respectively. In this section, the performance of these weighting choices for other values of SNR Is investigated. The penalty rwi)( ±»^r^ ) for the (sJ weights and the weights WPD detectors may be evaluated using the technique of the previous section. Figures 5.5 and 5.6 show £,Mr^ ) as a function of signal-to-noise ratio for a raised cosine and a half sinusoid signalling waveform respectively. In both figures the • Js^J weights are used. There are plots for the cases of M - 1, 2, 3, 4, 5, 10 and 11 samples. Figures 5.7 and 5.8 show r,_TX S,M,— ) versus SNR for a raised cosine and a half sinusoid WPD — a respectively, for the same values of sample sire with weights • s^2. In all cases, for fixed M, the penalty Increases with ^ but is approximately constant for small and large values of ~ • _ -y2 < s2(t) > . 2# < -y2s2(t)/2 > 5.7. Discussion The performance losses for WPD detectors in Gaussian noise have been M - 10 •a <\t> m X a -50 -25 0 20 log1Q ( A/o ) (dB) 25 50 Figure 5-5. The penalty ( £.M,^-) of the - IsJ weights WPD detector as a function of signal-to-noise ratio for a raised cosine signalling waveform. Seven values of sample size M are illustrated. 00 NJ 5 r— to o 4 — 2 = 1 — -50 -25 25 20 log1() ( A/o ) (dB) 50 Figure 5.6. The penalty TwpD ( B,H ~ ) of the u± - |8i| weights WPD detector as a function of signal-to-noise ratio for a half sinusoid signalling waveform. Seven values of sample size M are illustrated. oo 4 r— Tj X •I 1 — -50 -25 25 50 20 log1() ( A/o ) (dB) Figure 5.7. The penalty ( £,M,£ ) of the u>1 - e* weights WPD detector as a function of signal-to-noise ratio for a raised cosine signalling waveform. Seven values of sample size M are illustrated. 00 4> 4 a .52 1 — -50 M - 2 M -25 25 50 20 log10 ( A/o ) (dB) Figure 5.8. The penalty ( B_,M,— ) of the - s^ weights WPD detector as a function of signal-to-noise ratio for a half sinusoid signalling waveform. Seven values of sample size M are illustrated. 00 investigated. Three choices of weights have been considered. Previous analyses of these suboptimal schemes have been confined to low signal-to-noise ratio conditions. In general, the penalty depends on the choice of weights, the samples of the signalling waveform (and their number) as well as on the signal-to-noise ratio. In all of the examples considered, the penalties of the WPD detectors are approximately constant for low SNR values, increase in a transition region, and are approximately constant for high SNR values. Since equations (5.8) and (5.9) are independent of the signal-to-noise ratio, the losses for the general WPD detector will be approximately constant for low and high SNR values. Since the u « In —-— weights WPD detector is the optimum detect or for hard-limited samples and the DMF 'detector is the optimum processor for continuous amplitude samples, the penalties of figures 5.2 - 5.4 represent the fundamental losses due to hard-limiting of independent samples. In all cases, this loss Is a non-decreasing function of signal-to-noise ratio and is upper bounded by 2(3.01 dB). The value of w/2 - 1.96 dB is often cited as the loss due to hard-limiting [25,31,37], This result applies to an infinite number of independent samples and a vanishingly small SNR. The work of this chapter has shown that the loss is a function of the signal-to-noise ratio and of the number of samples. Independent samples are assumed in this work and the results are shown to agree with the previous result when the number of samples is infinite and the SNR is vanishingly small. However, the well known result of 1.96 dB as it applies to an infinite number of independent samples does not represent a physically realistic system. The results derived here deal with finite numbers of independent samples. This is representative of real systems. The u)^ = |s^| detector is optimal for low SNR conditions. Figur 5.5 - 5.8 show that the penalty for this detector may exceed 2(3.01 dB) 2 for high SNR values and is greater than the penalty incurred by the s^ 2 weights detector. Similarly, the s^ weights detector which is optimal for high SNR's has greater loss at low SNR values than the |s^| weights detector. VI PENALTIES OF SAMPLE-AND-SUM AND BINARY PARTIAL DECISION DETECTORS IN GAUSSIAN NOISE 6.1. Introduction The performances of the SAS and BPD detectors were analyzed for low signal-to-noise (SNR) conditions in chapters 2 and 3. In this chapter, the performances of SAS and BPD detectors are analyzed for arbitrary signal-to-noi6e ratios. The effects on the penalties of the signalling waveform employed, the number of samples processed, and the SNR are considered in detail. The SAS detector is examined first because its loss constitutes a part of the BPD detector's loss. The losses are compared to those of some WPD detectors and a relationship between the losses of the SAS, BPD and WPD detectors for low SNR and finite sample sizes is derived. The model considered here Is the same as in section 5.2. Antipodal signals are used to communicate a message mt{0, l} over an additive white Gaussian noise (AWGN) channel. The signals 4A s(t) and -A s(t) are aent corresponding to m - 0 and m-1 respectively. The M M receiver processes M samples {•JJJ.J* vj " * A *i * ni where {'ili-i and W^i-1 °"enote the •anP1'» of the signal a(t) (normalised ao that its maxim amplitude Is equal one) and outcomes of Independent Gaussian noise random variables respectively. Signal-to-noise ratio (SNR) la defined to be 20 log 10-^measured In dB. The penalty is defined as the increase in elgnal-to-noise ratio required by the suboptimum detector in order to achieve the same target value of probability of error as the DMF detector. 6.2. The Sample-and-Sum (SAS) Detector Loss In this section, the penalty incurred in using the SAS detector is analyzed. This detector [5,6,13] forms the statistic M DSAS Vi 8*n <Si> (6-A) r+i, if x > o jn(x) - < 0, if x - 0 L-l, if x < 0 where sgn(x 0 • 0 and chooses m-0 if DgAS > 0. Otherwise, m-1 is chosen. Given that m-0, i.e. +A a(t) is transmitted, the mean of DgAS is DSAS-AX |s I (6.2) SAS i-0 1 and its variance is given by t,2 -Mo2. (6.3) DSAS An error occurs if DGAS < 0. To compute the probability of error, PSAg(e)» we observe that D„ _ is a Gaussian random variable(r.v.) since it is SAS the sum 90 of independent^Gaussian r.v.'s. Also, because of the symmetry, PgAg(e|m=l) M A I |.,| 1 r° ~x 2/2 where Q(o) • J e dx . The penalty rcAC incurred by the SAS /2n detector relative to the DMF detector is implicitly defined by comparing PSAS(eJ Wlth PDMF(e) as 8IVEN bv <5-3> namely, /~M N M a/1 8I2 AX Q(-~ ) - Q(-^i— ). (6.5) From (6.5), it follows that M M I s,2 rsAs"~" • (6-6) i-i Note that TSAS is independent of the channel noise power, but does depend on the samples {s } and the number of samples M. Where necessary, we will 1 i-l use r.._ ( s,M ) to indicate this dependence explicitly. For large values of SAS — 91 M, I s * -| / |s(t)| dt (6.7a) i-1 1 1 0 and M T I l«J / l»(0| dt . (6.7b) i-1 1 1 0 Consequently, equation (6.6) can be rewritten as T T / B2(t) dt £ rsAs" -r ; 5 ; (6-8> [/ |s(t)| dt] T[< |B(t)| >] 0 vhere E « J s^t) dt is the energy of the signalling waveform s(t) and 8 0 A 1 T < |s(t)| > / |a(t)| dt is its average magnitude. Equation (6.8) has 1 0 been previously derived (2.10) for a particular filtering scheme with a large number of samples in a low SNR environment. The present derivation shows that it is valid for any SNR. Ve now use equation (6.6) to illustrate how varies with M for a few commonly encountered signalling waveforms. For a constant (or piecewise constant) amplitude signalling waveform, rsAS • 1, i.e. 0 dB as expected. For a half sinusoid signalling waveform, the samples are M s± - 6in-p| (i - 0.5), 1 - 1,2,...,M. In this case, I \e±\ - cosec i-l M fl, M-1 1 M 1-1 1 I |. M > [30,1«341-1] and J, s^2 - ^ M . From (6.6) r i , M -i j y- sin2 gj) , M > 2 , half sii RSAS , n _,_2 f* > „ . „ -1nu80ld. (6.9) The penalty T given by (6.9) is plotted as a function of M in figure 6.1. The asymptotic value of rgAS for large M is -g- or 0.912 dB. The penalties for a full sinusoid (6j - sin [~ (i-0.5)]) and 8 raised cosine (B± - [l-cos-jp (i-0.5)]/2) signalling waveform are given respectively by 1 , M - 1 or 2 i2 lSAS |- sin2 (g) , M - 4,6,8... £ tl fcosU/M))2 • M " 3>5>7- • ful1 BiDUSOld (6'10) ind Jl, M - 1, 2 [•§ , M > 3 , rai SAS I 4 . raised cosine . (6.11) 94 2 The asymptotic values of Tg^g as given by (6.10) and (6.11) are -g— or 3 0.912 dB and -r- or 1.76 dB. A plot of T for a full sinusoid signalling 2 SAS waveform is shown in figure 6.2. In all these examples, the asymptotic value of rgAg is reached rapidly. The magnitude of the difference |rSAS(s»M) - rSAg(6»")| is less than 0.1 dB for M > 11. 6.3. The Binary Partial Decision (BPD) Detector Loss The BPD detector forms the test statistic [ 2,3 ] °™* X b* where the partial decision random vsriable D^ is defined by if •gn(v1) » sgn(s1) # 0 if •gn(v1) - 0 or •gn(s1) - 0 (6.12) otherwise • The BPD detector chooses m - 0 if DBpD > 0 and m « 1 if DBpD < 0. Some caution ahould be exercised (section 4.5) in choosing m if DBpD ™ 0. This detector may be thought of as the special case of the WPD detector for which the weights all equal one (u^ - 1). It can be easily Implemented using a counter which is incremented or decremented by 1 depending on the polarties of v^ and s^. 2.0 rSAS< *M > (dB) 1.0 M (SAMPLES/BIT) Figure 6.2. The penalty T^i s,M ) aa a function of the number of bit samples for a sinusoid. VO The probability of error Is the probability that a majority of the transmitted samples are received vlth their polarities reversed, i.e. (6.13) where P^ - Pr {exactly 1 polarity errors In the M samples}. By equating the right hand side of (6.13) with P~_(e) as in DMF section 5.4 the penalties rBTjr.( a-M^- ) can be numerically evaluated* A Plots of r__n(«,»,0 as a function of for the raised cosine and half sinusoid signalling waveforms are shown in figures 6.3 and 6.4. The values of sample size illustrated are M « 1 - 5, 10 and 11 for both waveforms. For high SNR, it follows from (5.8) that M W > !T <6'U) sum of the I -j I smallest terms in i8^2}^.! where Px"] denotes the smallest integer > x. Equation (6.14) holds for an arbitrary signalling waveform. For large values of M, one has 20 log1() ( A/o ) (dB) Figure 6.3. The penalty rBpo ( J»»M,~ ) as a function of the signal-to-noise ratio for a raised cosine signalling waveform. Seven values of sample size M are illustrated. The solid triangles indicate points for which pBpn(e) • 10~7. -50 -25 0 25 50 20 loglQ ( A/o ) (dB) Figure 6.U. The penalty rBpD ( l.M.j ) as a function of the signal-to-noise ratio for a half sinusoid signalling waveform. Seven values of sample size M are illustrated. Oo T JnB2(t) dt J 82(t) dt V PBPD( £•"»" > " T~: (6.15) T where V Is a union of Intervals In [0,T] with a total width of which minimizes / s2(t) dt. W For a raised cosine signalling waveform, (6.15) becomes ret,, , fffri-co.»)]>dt _ 6, ^(raised cosine,-,-) ^j-2 /0 [jd-cost)] dt or 11.22 dB. (6.16) For a half sinusoid waveform, we have £ 8in2t dt 2, rBpD(half sinusoid,-,-) ^ - % _ 2 or 7.41 dB . (6.17) 2 L sln^ dt In the case of a piecewise constant signalling waveform, (6.14) { 2, M even 2 2_ M in agreement with (5.15) M+l * The asymptotic values for low SNR's will now be considered. In 100 Appendix K, It is shown that for an arbitrary signalling waveform, rBPD( -£'M*° > " rWPD( -i'M»° } * rSAS( 1»M ) (6-18) Equation (6.18) can be interpreted as follows: suppose the penalties are measured in dB; then for low SNR values, the penalty Incurred by the BPD detector Is the sum of the penalty Incurred by the SAS detector and the penalty Incurred by the WPD (or BPD) detector operating with a plecewlse constant signalling waveform ( as given by (5.13) ). Strictly speaking, this relation is only valid for - 0. It is however, nearly exact over a wide range of signal-to-noiBe ratio because of the flat nature of the penalty curves in that range. From (6.18) and the fact that lim rwpD( _1»M»°) " ^2 (section 2.3), it follows that for large M, Wi'"»° > " 1 rSAs<.£»-> • (6-19) This result was previously derived for a particular filtering scheme in section 2.A. 6.4. Discussion of Results The penalties associated with the use of the SAS and BPD detectors have been analyzed. The loss incurred by the SAS detector depends on the samples of the signalling waveform used but is Independent of the signal-to-noise ratio. In contrast, the losses associated with the BPD 101 detector (and the WPD detectors) depend on the signal-to-noise ratio as well as on the 6ignal samples. While the BPD detector is easier to Implement than the WPD detectors analyzed in chapter V, the penalty of the BPD detector was more sensitive to the choice of the signalling waveform and in 6ome cases was much greater than the penalty of the WPD detectors. Also shown in figure 6.3 are the points corresponding to pgpD(e) " 10~7, Jt can be seen from figure 6.3 that for the raised cosine waveform, the penalty using a BPD detector with M - 4 and pBpD(e) " 10~7 is about 14.5 dB. The corresponding penalty for the optimum WPD detector is only ~ 2.8 dB. 102 VII CONCLUSION 7.1. Summary of Results In this section, the highlights of the thesis research are summarized. Three suboptimum detectors which find application In practical digital systems have been described. The penalties of each have been analysed and identified. The relationships between the losses of the systems have been derived. Previous work In this area was mainly numerical and example specific. The present work treats the topic theoretically and gives some results that are fairly general and can be applied to systems other than those examined in the examples. The effects of dependence among the signal samples on the penalties have been examined. It has been shown that, in some cases, the penalties can be reduced by processing more, dependent, samples. It has been found that the amount of loss recoverable depends on the prefilter characteristic and the sampling rate. The optimal detector which bases its decision on a number of hard-limited samples has been presented. This detector is optimal in the sense that it minimizes the bit error probability. The detector is simple and inexpensive since it is essentially a one-bit analog-to-digital converter (ABC) and does not require an automatic gain control (ACC). This result is general in that it applies to arbitrary SNR values, arbitrary numbers of samples, and most practical noise environment models. The generalisation of the optimum hard-limiting detector for binary signals to higher quantisation and signalling levels has also been derived. That is, the minimum bit error probability detector for M-ary signalling with received signal samples quantized to an arbitrary number of levels has been found. Again, these results have been obtained using theoretical analysis whereas previous related work, in many cases, has been numerical and example specific. The fundamental loss due to hard-limiting in Gaussian noise has been investigated in depth. This loss is measured in the signal detectability sense. That is, the loss is expressed as the increase in SNR required to maintain a target value of error probability. Much attention has been paid to the loss due to hard-limiting in the past. The result most often quoted is that the loss is TT/2 = 1.96 dB. This result applies to an infinite number of independent samples and a vanishingly small signal-to-noise ratio. The present work shows that the loss is a function of the signal-to-noise ratio and of the number of samples. Independent samples are assumed in our work and the results agree with the previous result when the number of samples is infinite and the SNR is vanishingly small. The results are important because they apply to real world system conditions. The well known result of 1.96 dB as it applies to an infinite number of Independent samples does not represent a physically realistic system. The work done here which deals with a finite number of independent samples is representative of real systems. In addition to the investigation of the fundamental loss due to hard-limiting, the losses incurred by some ad hoc schemes that hard-limit the received samples have been examined. Some of the results of this work are of considerable interest for practical design. It is shown, for example, that one common ad hoc procedure has very large losses at high SNRs and is therefore unsuitable for application in a strong signal environment. 7.2. Suggestions for Further Research There are a number of issues arising from the thesis work that provide interesting topics for further research. Some of these are presented and briefly discussed in this section. The effects of dependence among the signal samples on the detect or penalties was investigated for large time-bandwidth product conditions and low SNRs. The generalization of these results to arbitrary time-bandwidth products and arbitrary SNRs has not been treated in this thesis The optimum detector for M-ary signalling with an arbitrary, given, quantizer was derived. The optimum quantizer thresholds that minimize the bit error probability were not specified. A related question is the sensitivity of the detector performance to variations in threshold settings. The performance of the optimum detector for M-ary signalling may be evaluated. Hereunder, one can consider different quantization levels and modulation formats. The losses of the suboptimum detectors under bandlimited condition with appreciable ISI are of interest. Performance evaluation in these cases is probably best done by the application of tight bounds for the error probabilities. \ 105 APPENDIX A ID this appendix, we show that as M+», the probability of error for the WPD detector is He) - Q [/TIT)- (A,1) o Recall that Q( o) can be represented by the infinite series 115,16] 3 5 . , .vn 2n+l 2 ^ 6 40 (2n+l)2nn! Thus, from (2.15), for large values of M (small signal-to-noise ratio), o M As M-*-, the mean of D^, i.e J (l-2pi)|si|. Is given by (see page 14) O 0 o M , and the vsriance of D^, i.e. J Ap1(l-p1)|a1| , ia given by § /V(t)dt - ^ (A.5) But P(e) • Q [ • variance of 0 ( /3 )• 106 APPENDIX B It is to be shown that the probability of error for the BPD detector is O Using (A.3), it can be determined that as M-w, the mean of Dgpj}» 1«e-M I (l-2pi), is given by i-1 4"M t i-t^lA. <B-2> /^/o|.(t)|-t and its variance, i.e. J 4p (1-p^. 1B given by M. Hence i-1 mean of DBpp P(e) - Q ( J • variance of DBpD Q ( 107 APPENDIX C In this appendix the calculation of P(e) for the SAS, BPD and WPD detectors for small values of M is briefly described. Let us denote the noiseless received waveform by f(t). Thus f(t) results from passing the transmitted waveform s(t) through the lowpass filter. Then, for the SAS detector, M P(e) - Q ( 1,1 ) (C.l) Mitt /2T o where f , i-l,2,3,...,M denotes the 1th sample of f(t). The calculation of P(e) for the BPD and WPD detector Is computationally more involved. Let p^ denote the probability that the channel causes a reversal In the polarity of f^, I.e., , ,fi' , PA - Q (-7- ) CC2) n where o - / MN /2T . Also define q. • 1 - p.. no 1 > 1 Suppose A is some subset of D - {1,2,3,...,M}. Then the probability that the samples {f.}. . have their polarities reversed by the noise and the 1 X EA remaining samples (f } retain their original polarities is given by 1 ieAc PA" C • 9±)i *c\) • (C'3) * ieA 1 ieAc ^ Hence, P(e) • [ P. where the sum Is taken over all subsets A which would A A lead to a wrong decision. This brute-force method of calculating P(e) is 108 time consuming. A more efficient way of evaluating P(e) for the BPD detector can be obtained by noting that it is just the probability that a majority of the samples have their polarities reversed, i.e., IM/2J P(e) ~ I P (C.4) n-0 n'M where P Pr {exactly n of the M samples are correct}. In (C.4) it is n ,M assumed for simplicity that M is odd. If M is even, then M/2 j P(e) "Jb Pn,M " * ?M/2»M* In any case, P u represents the generalized binomial distribution and n,H can be recursively evaluated [17] using P » q P , . + p P , n,m Tn n-1, m-1 m n,m-l P. . » 1, P. - p, p....p , and P • 0 if n > m. (C.5) 0,0 ' 0,m rlK2 rm* n,m APPENDIX D It is to be shown that as M-**> E[D^DJ] - 5^ - 2/n arcsin {rjj-i)} One has that EtDjDj] » E[sgn(vis1)sgn(vjsj)] - Pr(ni> -\B±\, n^> + Pjn^ -IsJ, -|8j|) - Pr(ni> -IsJ, Dj< -|8jl) - P(nA< -|B1|, NJ> -|SJ|), Let 1 -(x^px^+x.,2) , B-,(C, P. P) - / / —— exp{ ; M*2dxl denote the bivariate Gaussian distribution [15]. Then (D.2) becomes EID^j] - 2[B1(-|si|/on, -l-jl/o^ rn(j-i)) + B1(|.1|/an, l-jl/v rn(j-i))] - 1 MNQY where o 2» ^ _ • and the noise is assumed to be stationary. The two n zcl 110 sional Taylor series, centred at the origin, for f(x,y) is m=0 x=0 y-0 (D.5) Combining (D.5) with (D.3) gives B1(C,8,p) i + ^ arcsin p -2/2i? 2w/l-p2* 4itA-p2* (D.6) where e(C.6)-K) as C3, P3, CP2 and C2B. Using (D.6) in (D.4) gives for large M, ElDjDj] • 2/tt arcsin {rn 2CT(|S I-|S \y< {r (j-i)} 3 (D.7) By proceeding as in Appendix A it may be shown that as M+» 1 J ^n (D.8) Combining (D.8) with (D.7) results In (D.l), Ill APPENDIX E In this appendix it will be shown that as M-»-«> (3.23) vj- I I |s ||s |arcain{r <J-i)} - 2 \ arcsin{r (i)} . s 1=1 j»l 3 j=l (E.l) One has that MM M I I |s ||s |arcsin{r (j-i)} - l{ \ |s | |s |arcsin{r (1)} i-l j=l 1 J n k=2 K K 1 n 3*i M + I l«kl|sk_2|arcsin{rn(2)} + .. k=3 M + I |skl|sk_N+1|arcsin{rn(N-l)} + ... } k=N M M 2{arcsin{rn(l)} \ IsJIs^-J + arcsin{rn(2)} \ |8k||sk_2| + k*2 lce3 M + arcsin{rn(N-l)} J l*kl l»k..N+1l + ••• } • (E-2> k-N Note that, for fixed N, 112 M+» k»N M-w k»N M>» k-1 i laI J |.(I><-°^)|2 ./TB2(t)dt-E • (E.3) M-K» M k-1 M 0 where, without loss of generality, it has been assumed that -s([i-0.5]T/M). Using the result of (E.3) with (E.2) gives (E.l). APPENDIX F It 16 to be shown that when the channel noise has a Cauchy * distribution the optimum weights for high SNR'6 are given by w^-l. In a Cauchy noise environment the probability that a sample has Its polarity CD reversed is p. - Pr (N > |s.|) • / —-2- da. Making use of the series 1 11 IsJ b2+o2 -ji^ » 1-x+x2-... yields |s1| %a* o-|s1 It 6, 1 i1 * r 1 i1 •» For large signal-to-noise ratios,—-— » 1 and • In(—-—J. Assume that s(t) * C s(t) where s(t) is a waveform with unit amplitude and C is a constant. Then, * *|C||sJ to* - M b 1 ) " *»UC|)+ togli-J) . For large values of |C| and hence large SNR's, u>* - JUi(|C|). Since the optimum decision rule is not changed by scaling the weights, one may use * <i>4 « 1 for large SNR's. 114 APPENDIX G In this appendix it is shown that the optimal weights for the case of a raised cosine pulse in Cauchy noise sampled 3 times are 4 r |s1| if SNR < 15.1 dB Ui " 1 1 Ll if SNR > 15.1 dB . Note that there are 8 possible combinations of the 3 received signal * * , 6ample6 and that tii± - u>3. Therefore, the sample vectors _v • [+,+,+), (+,+,-) and (-,+,+) will be assigned message m-0 and the vectors_v - (-,-,-), (-,-,+) and (+,-,-) will be assigned m-1. This is true for any signal-to-nolse ratio and any choice of weights provided that Wj-u^. According to the |s^| weights, the detector chooses m-0 for_v-(-,+,-) and m=l for _v»(+,-,+). But for p^ specified by the Cauchy distribution and < 15.1 1-Pi 1~P3 1-P2 dB, inf 1 + inf J < in[ ]• Thus, the optimum weights are equivalent Pi P3 P2 to the |61| weights in this SNR region. When ^ > 15.1 dB, 1-Pj l-p3 l-p2 A Jtnf ] + Jtnf 1 > Jtn[ 1 and m - 0,1 are chosen corresponding to Pi P3 ?2 v-(+,-,+), (-,•+,-) respectively by both the optimum and unity weights detectors. APPENDIX H In thi6 appendix it is shown that the penalty for the general WPD detector at high SNR values is given by (5-8) From (5.7), for high SNR values, the probability of error becomes We) - r 1 I(B) 11 Pi wru B C {1,2,...M} ieB (H.l) where 1 , if I > I wf ieB ieB 1(B) - / i , if I u>x" I u± ieB ieB 0 , if I u± < I w± . ieB ieB" Also, for large — , /2* rOTn( S.M^)-! l8i' "WPDV (H.2) Hence, nPj -w^M4> lioJ24jB8i2 e n /2W WJ,MA > i |. | ieB (H.3) From (H.3), it can be seen that fypr/e) 86 given by (H.l) will be dominated (for high SNR) by the set (or sets) B for which 1(B) > 0 and £ s 2 is ieB 1 * * A r > minimum. Let B denote one such set, that is, B C U - {1,2,...,M} and I(B*) > 0 and I s 2 < J s 2 for all BC U for which 1(B) > 0. Since * 1 1 ieB IeB rypD( ±t*£a ) > 1, it follows from (H.l) that as incresses ieB Recall that /T i-i -t-0i 1,1 V e /—8—\ , for large - , so that 117 Equating (H.M with (H.5) yields M 2 * IEB APPENDIX I It Is to be 6hovn that the penalty for the WPD detector with a piecewise constant amplitude signalling waveform and low SNR is given by (5.13). We consider first the derivation for odd values of M. A A Differentiating (5.10) with respect t° — and then letting — = 0 yields M 2 2M-2 M I (JK21-M) M+l L1* ~2 , M odd (1.1) One ha6 I M(?) - M2M_1 , M odd . . M+l ±ms — (1.3) 119 Using (1.2) and (1.3) In (I-l) one obtains 2M—2 In a similar way, it can be shown that 22M W i'M'° > " /Mv 2 • M eVCn * U,5) It might be noted from (I.U) and (1.5) that 120 APPENDIX J It is to be shovn that for a large number M of samples the penalty for the optimum WTD detector is upper bounded by (5.16). Let fXj}j.i be M Independent random variables defined by 1-Pj An(—-—) with probability p^ 1 1 i-Pj -Inf-p—-) with probability (l-p1) r A—v A where p± - Q(/ B,H,- ) - |s1|) . Then * M P (e) - Pr{ X X > 0} . (J.l) i-l One can use the Chernoff bound 129: Eq« (5.4.15)] to upperbound the right hand side of (J.l) M XX P* (e) < n E[e *] (J.2) meu i-l where X Is a positive number which can be chosen to optimize the bound. For the present problem, the best value to use Is X - -| • Then (J.2) becomes We) < " 2/'P1<1-P1>S • <J'3) 121 An upper bound T™D( l.M,^ ) Is obtained by equating the right hand side of (J.3) to P_..(e), namely Q("a^Jl Sl2)" i-1 2/pi(l~PiV where pA £ Q (/ O-S'M4 >i I I 5- For large M , 2 M , k -i e|r i «i2 4 / l 8.2 ) >C A*! Q(± M^2 ) i-i * ° Using (J.5) in (J.4) yields for large M, (J.5) £)2 jg s2(t)dt - - /J |*Q(/C^»-4^4 l8(t> l> [I-Q(/0±.--t>4 .•<*>!>]}* • (J-6) Letting /rJ^D( )'4" y. ^ can rewrite (J.6) as -Y2 s2(t)dt JOB ( „ A ^ J° (J.7) WPD i ' * O fT • - ' - .i.r. • - v I * 11.. Ji ln{4Q(y|s(t)|)[l-Q(y|B(t)|)]}dt UB A A Equation (J.7) can be used to plot Tmj){ l.-r^ ) as a function of -122 For a plecevise constant amplitude waveform the upper bound Is also a lower bound* This is now shown. One has (5.10) M I (?) PV-P)*1"1 M+l 2 i -, M odd (J.8) 1 - ' even where p - Q(/1,*,^ ) (-p • Therefore A ^ .A. M I 12 (V )2 (^)[P(1-P)]2 t^f ."odd WPD (e) >< 1(H) [Pd-P>] , M even (J.9) Since (40-M+l M-1 , 2 2 »M . ^ n (2 + "j) > l+i when M 18 °*d and »M (M) "2 (MMX) >-2r when M 18 even (J*9) *leld6 M M+T (T%)1/2 [*P(1-P)? . M ODD W6> > M 2M j; [4p( 1-p >? , M even • (J.10) 123 Using (J.3) (with PA - p for all i), (J.5) and (J.10) one obtains for large M £)2«- Xn { 4Q(/rTO( 1.-4)4 > * (J.ll) [i-Qc/r^c i.-4 )'4>] ^ • Letting / FypjjC ) -5 - y » (J.ll) ««y rewritten as r ( 1 ) rz2. — . (J.12) W-"o> An{4Q(y) [l-Q(y) ]} A A Equation (J.12) is used to plot hm*~a > as a function of • 124 APPENDIX K In this appendix, it is proved that W •6-,M'° } " W ^•M,° } * rSAS( > ' (K.l) From equations (5.3) and (6.13), W B.M,- ) is Implicitly defined by «(/! -J-J i-1 1 M M IU.1 J , M odd M+l 3 " 2 M even (K.2) where PM - Pr {exactly j (polarity) errors in the M samples} M M k^-l k2-kx+l Hp n (l-pk) # Wl*1 Aetkl»k2 V keU-{kl,....kj} •nd P. » Q(/rBpD( B,*£A) |BAI 4 > • Differentiating with respect to - and lBPD then letting ^ - 0 in (K.2), we obtain 125 1-1 M M I I J--^ krl k2=kx+l le{k1(...,k^} keU-jki k^} , M odd M rif-i / r ( . m o f * K^" X ^1 tj-* " ^BPIT -* * ' , M+l 2 J i-l M I (K.3) (K.4) Similarly, for M even, one haB /? *,2- ^f"1 /rBPD(i.M,o)X I {2CJ) - ff)} X i-l 1 * *™ , M+2 3 1 3 i-l 1 (K.5) From (K.4) and (K.5) one ha6 M W > - CM I "i2 i-l M , M—1,2,3,.•. (X IsJ)2 i-l 1 (K.6) for some constant C^. In particular, (K.7) Using (6.6) and (K.7) in (K.6), we have W ±">° 5 " W I»M'° > ' rSAS( ±'* > REFERENCES T.C. Tozer and J. RollerStrom, "Penalties of hard decision in signal detection," Electron. Lett.. vol. 16, pp.199-200, Feb. 1980. V.M. Milutinovic, "Suboptimum detection procedure based on the weighting of partial decisions," Electron. Lett., vol. 16, pp.237-238, Mar. 1980. V.M. Milutinovic, "Comparison of three suboptimum detection procedures," Electron. Lett., vol. 16, pp.681-683, Aug. 1980. G. B. Lockhart, "Implementation of digital matched filters in data receivers," Electron. Lett., vol. 10, pp.311-312, July 1974. CM. Chie, "Performance analysis of digital integrate-and-dump filters," IEEE Trans. Commun., vol. COM-30, pp.1979-1983, Aug. 1982. H. Chang, "Presampling filtering, sampling and quantization effects on the digital matched filter performance," in Proc. International Telemetering Conference, San Diego,CA, USA, Sept. 28-30, 1982, pp.889-915. N.C. Beaulieu and C. Leung, "On the performance of three suboptimum detection schemes for binary signalling," IEEE Trans. Commun.. vol. C0M-33, pp.241-245, Mar. 1985. N.C. Beaulieu and C. Leung, "Optimal detection of hard-limited data signals in different noise environments," IEEE Trans. Commun., vol. C0M-34, pp.619-622, June 1986. 127 [9] N.C. Beaulieu, "Penalties of Sample-and-Sum and Weighted Partial Decision Detectors in Gaussian Noise," under review. [10] N.C. Beaulieu and C. Leung, "The Optimal Hard-Limiting Detector for Data Signals in Different Noise Environments," in Proc. IEEE ICC, Toronto, Canada, June 23-25, 1986, pp.32.6.1-32.6.5. [11] M. Schwartz and L. Shaw, Signal Processing: Discrete Spectral Analysis, Detection and Estimation. New York: McGraw-Hill, 1975. [12] R.W. Stroh, "An experimental microprocessor-implemented 4800 bit/s limited distance voice band PSK modem," IEEE Trans. Commun., vol. COM-26, pp.507-512, May 1978. [13] V.C. Hamacher, "Analysis of a simplified sampled signal detector," Queen's university Research Report 65-1, Mar. 1965. [14] M. Flsz, Probability Theory and Mathematical Statistics. New York: J. Wiley, 1963, pp.202-211. [15] J. Patel and C. Read, Handbook of the Normal Distribution. New York: Marcel Dekker, 1982, p.50. [16] M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions. New York: Dover, 1972, pp.931-932. [17] G.P. Wadsworth and J.G. Bryan, Applications of Probability and Random Variables. New York: McGraw-Hill, 1974, pp.89-91. [18] C. Cherry, Pulses and Transients In Communication Circuits. London: Dover, 1950. [19] A.I. Zverev, Handbook of Filter Synthesis. New York: J. Wiley, 1967, pp.67-71. 128 [20] w. Rudin, Principles of Mathematical Analysis. New York: McGraw-Hill, 1964. [21] R.V. Churchill and J.W. Brown, Fourier Series and Boundary Value Problems. New York: McGraw-Hill, 1978, p.84. [22] R.E. Ziemer and W.H. Tranter, Systems, Modulation, and Noise. Boston: Houghton Mifflin, 1976. [23] M. Rosenblatt, "A Central limit theorem and a strong mixing condition," Proc. Nat. Acad. Sci., vol. 42, pp.42-47, 1956. [24] R. Deutsch, Nonlinear Transformations of Random Processes. Englewood Cliffs, N.J. : Prentice-Hall, 1962. [25] M. Kanefsky, "Detection of weak signals with polarity coincidence arrays," IEEE Trans. Inform. Theory, vol. IT-12, pp.260-268, Apr. 1966. [26] M.J. Levin, "Generation of a sampled gaussian time series having a specified correlation function," IRE Trans. Inform. Theory, vol. IT-6, pp.545-548, Dec. 1960. [27] J.H. Miller and J.B. Thomas, "Detectors for discrete-time signals in non-gaussian noise," IEEE Trans. Inform. Theory, vol. IT-18, pp. 241-250, Mar. 1972. [28] H. Chernoff, "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations," Annals Math. Stat., vol. 23, pp. 493-507, 1952. [29] "R.G. Gallager, Information Theory and Reliable Communication. New York: J. Wiley, 1968. 129 [30] i.s. Gradshteyn and I.M. Ryzhik, Table of Integrals, Series and Products. New York: Academic Press, 1980. [31] J.M. Wozencraft and I.M. Jacobs, Principles of Communication Engineering. New York: J. Wiley, 1968. [32] N.C. Beaulieu and C. Leung, "A comparison of three suboptimum detectors for binary signalling," in Proc. IEEE ICC, Chicago, USA, June 23-26, 1985, pp.18.A.1-18.4.6. [33] N.C. Beaulieu and C. Leung, "On hard-limiting in sampled binary data systems," North American Radio Science Meeting (URSI), Vancouver, Canada, June 17-21, 1985, p.330. [34] N.C. Beaulieu, "Penalties of Weighted Partial Decision Detectors in Gaussian Noise," in Proc. IEEE International Montech Conference on Antennas and Communications, Montreal, Canada, Sept. 29-0ct. 1, 1986. [35] V. Milutinovic, "Performance comparison of two suboptimum detection procedures in real environment," IEE Proc.. vol. 131, Pt. F, pp.341-344, July 1984. [3 6] V.M. Milutinovic, "Generalised WPD procedure for microprocessor-based signal detection," IEE Proc., vol. 132, Pt. F, pp.27-35, Feb. 1985. [37] P.M. Schultheiss and F.B. Tuteur, "Optimum and Suboptimum Detection of Directional Gaussian Signals in an Isotropic Gaussian Noise Field Part II: Degradation of Detectability Due to Clipping," IEEE Trans, on Military Electronics, vol.MIL-9, pp.208-211, July-Oct. 1965. GLOSSARY binary antipodal signals two signals, each of which is the negative of the other binary partial decision a decision based on a single signal sample which has two possible outcomes digital matched filter the optimum detector which bases its decision on a number of independent signal samples hard decision a decision which has two possible outcomes hard-limiting a transformation that assigns one value to all positive arguments and a second value to all negative arguments M-ary signalling the transmitter sends one of M signals depending on the message sequence maximum aposteriori probability (MAP) rule the receiver chooses as its estimate of the transmitted signal that signal which is most likely given the received signal penalty the deterioration in performance of a suboptimum detector measured relative to an optimum detector; the increase in signal-to-noise ratio required by a suboptimum detector in order to maintain the same error probability as an optimum detector sample-and-sum detector the received signal is sampled and the samples are summed signalling element one of the signal waveforms sent by the transmitter weighted partial decision a decision based on a single signal sample which may have one of several outcomes, the larger the outcome the more heavily the decision is weighted PUBLICATIONS N.C. Beaulieu and C. Leung, "Optimal Detection of Hard-Limited Data Signals in Different Noise Environments", IEEE Trans. Commun., vol. COM-34, no.6, pp.619-622, June 1986. N.C. Beaulieu and C. Leung, "On the Performance of Three Suboptimum Detection Schemes for Binary Signalling", IEEE Trans. Commun., vol.COM-33, no.3, pp.241-245, March 1985. N.C. Beaulieu, "Comment on 'Calculating Binomial Probabilities When the Trial Probabilities are Unequal'", J. of Statistical Computation and Simulation, vol.20, no.4, pp.327-328, 1985. E.V. Jull, N.C. Beaulieu and D.C.W. Hui, "Perfectly Blazed Triangular Groove Reflection Gratings", J. of the Optical Society of America, vol.1, no.2, Feb. 1984. N.C. Beaulieu, "Penalties of Sample-and-Sum and Weighted Partial Decision Detectors in Gaussian Noise", submitted. N.C. Beaulieu, "Penalties of Weighted Partial Decision Detectors in Gaussian Noise", IEEE International Montech Conference on Antennas and Communications, Montreal, Sept. 1986. N.C. Beaulieu and C. Leung, "The Optimum Hard-Limiting Detector for Data Signals in Different Noise Environments", IEEE International Conference on Communications, Toronto, pp.32.6.1-32.6.5, June 1986. PUBLICATIONS N.C. Beaulieu and C. Leung, "A Comparison of Three Suboptimum Detector for Binary Signalling", IEEE International Conference on Communication Chicago, pp.18.4.1-18.4.6, June 1985. N.C. Beaulieu and C. Leung, "On Hard-Limiting in Sampled Binary Data Systems", North American Radio Science Meeting (URSI), Vancouver, Canada, June 1985. E.V. Jull, N.C. Beaulieu and D.C.W. Hui, "Dual Blazed Triangular Groove Reflection Gratings", IEEE Antennas and Propagation Society International Symposium, Houston, Texas, May 1983. E.V. Jull and N.C. Beaulieu, "An Unusual Reflection Grating Behaviour Suitable for Efficient Frequency Scanning", IEEE Antennas and Propagation Society International Symposium, Quebec, June 1980.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Bit error rate performance analysis and optimization...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Bit error rate performance analysis and optimization of suboptimum detection procedures Beaulieu, Norman Charles 1986-12-31
pdf
Page Metadata
Item Metadata
Title | Bit error rate performance analysis and optimization of suboptimum detection procedures |
Creator |
Beaulieu, Norman Charles |
Publisher | University of British Columbia |
Date | 1986 |
Date Issued | 2010-07-22T02:47:13Z |
Description | Three suboptimum detection schemes are examined. The deterioration in performance, measured in the probability of error sense, of weighted partial decision, binary partial decision, and sample-and-sum detectors are analyzed. Even though these schemes are inferior to the digital matched filter, they can be used in systems with more modest computational capabilities. Analytic expressions are obtained for the penalties. The effects on the penalties of the signalling waveform employed, the number of samples processed, and the signal-to-noise ratio are considered in detail. Included are the penalties for the optimum weighted partial decision detector. The effects of dependence among the samples on the detector losses are investigated. It is shown that, in some cases, the losses of the suboptimum procedures can be reduced by processing more, dependent, samples. The amount of the loss that can be recovered depends on the prefilter characteristic and the sampling rate, as well as the detection algorithm. The structure of the optimum detector for hard-limited data signals is presented and its performance is compared with those of some commonly used schemes. Performance in Impulsive as well as Gaussian noise environments is considered. The optimum receiver for M-ary signalling based on received signal samples quantized to an arbitrary number of levels is derived and compared to another common detector. The fundamental loss in signal detectability due to hard-limiting in a sampled system operating in Gaussian noise is investigated. The relation of the loss to the signal-to-noise ratio and the number of samples is analyzed. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2010-07-21 |
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.0097037 |
URI | http://hdl.handle.net/2429/26775 |
Degree |
Doctor of Philosophy - PhD |
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
- [if-you-see-this-DO-NOT-CLICK]
- UBC_1986_A1 B42.pdf [ 4.71MB ]
- Metadata
- JSON: 1.0097037.json
- JSON-LD: 1.0097037+ld.json
- RDF/XML (Pretty): 1.0097037.xml
- RDF/JSON: 1.0097037+rdf.json
- Turtle: 1.0097037+rdf-turtle.txt
- N-Triples: 1.0097037+rdf-ntriples.txt
- Original Record: 1.0097037 +original-record.json
- Full Text
- 1.0097037.txt
- Citation
- 1.0097037.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 27 | 0 |
China | 13 | 48 |
Rwanda | 5 | 0 |
France | 2 | 1 |
Canada | 1 | 0 |
City | Views | Downloads |
---|---|---|
Ashburn | 12 | 0 |
Shenzhen | 11 | 48 |
Unknown | 7 | 15 |
San Francisco | 7 | 0 |
Mountain View | 5 | 0 |
Beijing | 2 | 0 |
Hopkinsville | 2 | 0 |
Windsor | 1 | 0 |
Seattle | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0097037/manifest