Poor, H.V., Looney, C.G., Marks Il,RJ, Verdu, S, Thomas, J.A., Cover, TM "Information Theory The electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRc Press llc. 2000
Poor, H.V., Looney, C.G., Marks II, R.J., Verdú, S., Thomas, J.A., Cover, T.M. “Information Theory” The Electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRC Press LLC, 2000
73 Information Theory 73. 1 Signal Detection General Considerations. Detection of Known Signals. Detection of Parametrized Signals. Detection of Random Signals. Deciding Among Multiple Signals. Detection of Signals in More General Noise Processes.Robust and Nonparametric Detection. Distributed and equential Detection. Detection with Continuous-Time Measurements 3.2 Noise Statistics of noise. Noise power Effect of linear transformations on Autocorrelation and Power Spectral Density.White, Gaussian and pink noise models Thermal noise as gaussian white noise Some Examples. Measuring Thermal Noise. Effective Noise and Antenna Noise. Noise Factor and Noise Ratio. Equivalent Input Noise.Other Electrical Noise. Measurement and Quantization Noise. Coping with Noise 73.3 Stochastic Processes Introduction to Random variables Stochastic Processes Classifications of Stochastic Processes. Stationarity of Processes H. Vincent poor Gaussian and Markov Processes. Examples of Stochastic Processes Linear Filtering of Weakly Stationary Processes. Cross-Correlation of Processes. Coherence. Ergodicity Carl G. Looney 3.4 The Sampling Theore niversity of Nevada The Cardinal Series. Proof of the Sampling Theorem. The Time- Bandwidth Product Sources of Error Generalizations of the J. Marks II Sampling Theorem niversity of washington 73.5 Channel Capacity Sergio Verdu Information Rates Communication Channels Reliable Information Transmission: Shannon,s Theorem Bandwidth and Capacity. Channel Coding Theorems Joy A. Thomas 73.6 Data Compression ntropy. The Huffman Algorithm. Entropy Rate. Arithmetic Thomas m. Cover Quantization and Vector Quantization. Kolmogorov Complexity Stanford University Data Compression in Practice 73.1 Signal Detection H. Vincent poe The field of signal detection and estimation is concerned with the processing of information-bearing signals for the purpose of extracting the information they contain. The applications of this methodology are quite broad, ranging from areas of electrical engineering such as automatic control, digital communications, image processing, and remote sensing, into other engineering disciplines and the physical, biological, and social c 2000 by CRC Press LLC
© 2000 by CRC Press LLC 73 Information Theory 73.1 Signal Detection General Considerations • Detection of Known Signals • Detection of Parametrized Signals • Detection of Random Signals • Deciding Among Multiple Signals • Detection of Signals in More General Noise Processes • Robust and Nonparametric Detection • Distributed and Sequential Detection • Detection with Continuous-Time Measurements 73.2 Noise Statistics of Noise • Noise Power • Effect of Linear Transformations on Autocorrelation and Power Spectral Density • White, Gaussian, and Pink Noise Models • Thermal Noise as Gaussian White Noise • Some Examples • Measuring Thermal Noise • Effective Noise and Antenna Noise • Noise Factor and Noise Ratio • Equivalent Input Noise • Other Electrical Noise • Measurement and Quantization Noise • Coping with Noise 73.3 Stochastic Processes Introduction to Random Variables • Stochastic Processes • Classifications of Stochastic Processes • Stationarity of Processes • Gaussian and Markov Processes • Examples of Stochastic Processes • Linear Filtering of Weakly Stationary Processes • Cross-Correlation of Processes • Coherence • Ergodicity 73.4 The Sampling Theorem The Cardinal Series • Proof of the Sampling Theorem • The TimeBandwidth Product • Sources of Error • Generalizations of the Sampling Theorem 73.5 Channel Capacity Information Rates • Communication Channels • Reliable Information Transmission: Shannon’s Theorem • Bandwidth and Capacity • Channel Coding Theorems 73.6 Data Compression Entropy • The Huffman Algorithm • Entropy Rate • Arithmetic Coding • Lempel–Ziv Coding • Rate Distortion Theory • Quantization and Vector Quantization • Kolmogorov Complexity • Data Compression in Practice 73.1 Signal Detection H. Vincent Poor The field of signal detection and estimation is concerned with the processing of information-bearing signals for the purpose of extracting the information they contain. The applications of this methodology are quite broad, ranging from areas of electrical engineering such as automatic control, digital communications, image processing, and remote sensing, into other engineering disciplines and the physical, biological, and social sciences. H. Vincent Poor Princeton University Carl G. Looney University of Nevada R. J. Marks II University of Washington Sergio Verdú Princeton University Joy A. Thomas IBM Thomas M. Cover Stanford University
There are two basic types of problems of interest in this context. Signal detection problems are concerned primarily with situations in which the information to be extracted from a signal is discrete in nature. That is, signal detection procedures are techniques for deciding among a discrete(usually finite) number of possible alternatives. An example of such a problem is the demodulation of a digital communication signal, in which the task of interest is to decide which of several possible transmitted symbols has elicited a given received signal. Estimation problems, on the other hand, deal with the determination of some numerical quantity taking values in a continuum. An example of an estimation problem is that of determining the phase or frequency of the carrier underlying a communication signal. Although signal detection and estimation is an area of considerable current research activity, the fundamental principles are quite well developed. These principles, which are based on the theory of statistical inference. plain and motivate most of the basic signal detection and estimation procedures used in practice. In this ction,we will give a brief overview of the basic principles underlying the field of signal detection. Estimation is treated elsewhere this volume, notably in Section 16. 2. A more complete introduction to these subjects found in Poor[1994] General Considerations The basic principles of signal detection can be conveniently discussed in the context of decision-making between two possible statistical models for a set of real-valued measurements, Y,, Y2,..., Ym. In particular, on observing Y Y,..., Y,, we wish to decide whether these measurements are most consistent with the m Yk=Nk,k=1,2,,,n (73.1) Yk=N+ Sk, k=l, 2,...,n (73.2) where N, N2,..., N is a random sequence representi d where S, S,,...,S, is a sequence In deciding between Eqs. (73. 1)and(73. 2), there are two types of errors possible: a false alarm, in which (73. 2)is falsely chosen, and a miss, in which(73. 1) is falsely chosen. The probabilities of these two types of errors can be used as performance indices in the optimization of rules for deciding between(73. 1)and(73. 2) Obviously, it is desirable to minimize both of these probabilities to the extent possible. However, the minimi- zation of the false-alarm probability and the minimization of the miss probability are opposing criteria. So, it is necessary to effect a trade-off between them in order to design a signal detection procedure. There are several ways of trading off the probabilities of miss and false alarm: the Bayesian detector minimizes an average of the two probabilities taken with respect to prior probabilities of the two conditions(73. 1)and(73. 2), the minimax detector minimizes the maximum of the two error probabilities, and the Neyman-Pearson detector mizes the miss probability under an upper-bound constraint on the false-alarm probabili If the statistics of noise and signal are known, the Bayesian, minimax, and Neyman-Pearson detectors are all of the same form. Namely, they reduce the measurements to a single number by computing the likelihood ratio I(Y,12…,Y)P、Yn (73.3) Px(Y1,Y2,……,Yn) where PsN and px denote the probability density functions of the measurements under signal-plus-noise(73. 2) and noise-only(73. 1)conditions, respectively. The likelihood ratio is then compared to a decision threshold, with the signal-present model(73. 2) being chosen if the threshold is exceeded, and the signal-absent model (73. 1)being chosen otherwise. Choice of the decision threshold determines a trade-off of the two error probabilities, and the optimum procedures for the three criteria mentioned above differ only in this choice e 2000 by CRC Press LLC
© 2000 by CRC Press LLC There are two basic types of problems of interest in this context. Signal detection problems are concerned primarily with situations in which the information to be extracted from a signal is discrete in nature. That is, signal detection procedures are techniques for deciding among a discrete (usually finite) number of possible alternatives. An example of such a problem is the demodulation of a digital communication signal, in which the task of interest is to decide which of several possible transmitted symbols has elicited a given received signal. Estimation problems, on the other hand, deal with the determination of some numerical quantity taking values in a continuum. An example of an estimation problem is that of determining the phase or frequency of the carrier underlying a communication signal. Although signal detection and estimation is an area of considerable current research activity, the fundamental principles are quite well developed. These principles, which are based on the theory of statistical inference, explain and motivate most of the basic signal detection and estimation procedures used in practice. In this section, we will give a brief overview of the basic principles underlying the field of signal detection. Estimation is treated elsewhere this volume, notably in Section 16.2. A more complete introduction to these subjects is found in Poor [1994]. General Considerations The basic principles of signal detection can be conveniently discussed in the context of decision-making between two possible statistical models for a set of real-valued measurements, Y1, Y2, . . ., Yn. In particular, on observing Y1, Y2, . . ., Yn, we wish to decide whether these measurements are most consistent with the model Yk = Nk , k = 1, 2, . . . , n (73.1) or with the model Yk = Nk + Sk , k = 1, 2, . . . , n (73.2) where N1, N2 , . . ., Nn is a random sequence representing noise, and where S1, S2, . . ., Sn is a sequence representing a (possibly random) signal. In deciding between Eqs. (73.1) and (73.2), there are two types of errors possible: a false alarm, in which (73.2) is falsely chosen, and a miss, in which (73.1) is falsely chosen. The probabilities of these two types of errors can be used as performance indices in the optimization of rules for deciding between (73.1) and (73.2). Obviously, it is desirable to minimize both of these probabilities to the extent possible. However, the minimization of the false-alarm probability and the minimization of the miss probability are opposing criteria. So, it is necessary to effect a trade-off between them in order to design a signal detection procedure. There are several ways of trading off the probabilities of miss and false alarm: the Bayesian detector minimizes an average of the two probabilities taken with respect to prior probabilities of the two conditions (73.1) and (73.2), the minimax detector minimizes the maximum of the two error probabilities, and the Neyman-Pearson detector minimizes the miss probability under an upper-bound constraint on the false-alarm probability. If the statistics of noise and signal are known, the Bayesian, minimax, and Neyman-Pearson detectors are all of the same form. Namely, they reduce the measurements to a single number by computing the likelihood ratio (73.3) where pS+N and pN denote the probability density functions of the measurements under signal-plus-noise (73.2) and noise-only (73.1) conditions, respectively. The likelihood ratio is then compared to a decision threshold, with the signal-present model (73.2) being chosen if the threshold is exceeded, and the signal-absent model (73.1) being chosen otherwise. Choice of the decision threshold determines a trade-off of the two error probabilities, and the optimum procedures for the three criteria mentioned above differ only in this choice. L Y Y Y p Y Y Y p Y Y Y n S N n N n ( , , , ) ( , , , ) ( , , , ) 1 2 1 2 1 2 ... ... ... D +
There are several basic signal detection structures that can be derived from Eqs.(73. 1)to(73.3)under the assumption that the noise sequence consists of a set of independent and identically distributed (i.i.d. )Gaussian random variables with zero means Such a sequence is known as discrete-time white Gaussian noise. Thus, until further notice, we will make this assumption about the noise. It should be noted that this assumption is physically justifiable in many applications Detection of Known Signals If the signal sequence S,,S2,..,Sn is known to be given by a specific sequence, say SI, s2,..,s,(a situation known as coherent detection), then the likelihood ratio(73.3)is given in the white Gaussian noise case by exp (73.4 where o is the variance of the noise samples. The only part of (73. 4 )that depends on the measurements is the erm EkalskYk and the likelihood ratio is a monotonically increasing function of this quantity. Thus, optimum detection of a coherent signal can be accomplished via a correlation detector, which operates by comparing the quantity kYk (73.5) to a threshold, announcing signal presence when the threshold is exceeded. Note that this detector works on the principle that the signal will correlate well with itself, yielding a value of (73.5)when present, whereas the random noise will tend to average out in the sum(73.5), yiel relatively small value when the signal is absent. This detector is illustrated in Fig. 73.1 ∑() Comparison k=1 FIGURE 73. 1 Correlation detector for a coherent signal in additive white Gaussian noise. Detection of Parametrized Signals The correlation detector cannot usually be used directly unless the signal is known exactly. If, alternatively, the ignal is known up to a short vector e of random parameters(such as frequencies or phases)that are independent of the noise, then an optimum test can be implemented by threshold comparison of the quantity 5(6)y_1 ∑ (6)|/}p()de where we have written Sk=S(0)to indicate the functional dependence of the signal on the parameters, and where A and p(0)denote the range and probability density function, respectively, of the parameters The most important example of such a parametrized signal is that in which the signal is a modulated sinusoid with random phase; i.e e 2000 by CRC Press LLC
© 2000 by CRC Press LLC There are several basic signal detection structures that can be derived from Eqs. (73.1) to (73.3) under the assumption that the noise sequence consists of a set of independent and identically distributed (i.i.d.) Gaussian random variables with zero means. Such a sequence is known as discrete-time white Gaussian noise. Thus, until further notice, we will make this assumption about the noise. It should be noted that this assumption is physically justifiable in many applications. Detection of Known Signals If the signal sequence S1, S2, . . ., Sn is known to be given by a specific sequence, say s1, s2 , . . ., sn (a situation known as coherent detection), then the likelihood ratio (73.3) is given in the white Gaussian noise case by (73.4) where s2 is the variance of the noise samples. The only part of (73.4) that depends on the measurements is the term S n k =1skYk and the likelihood ratio is a monotonically increasing function of this quantity. Thus, optimum detection of a coherent signal can be accomplished via a correlation detector, which operates by comparing the quantity (73.5) to a threshold, announcing signal presence when the threshold is exceeded. Note that this detector works on the principle that the signal will correlate well with itself, yielding a large value of (73.5) when present, whereas the random noise will tend to average out in the sum (73.5), yielding a relatively small value when the signal is absent. This detector is illustrated in Fig. 73.1. Detection of Parametrized Signals The correlation detector cannot usually be used directly unless the signal is known exactly. If, alternatively, the signal is known up to a short vector u of random parameters (such as frequencies or phases) that are independent of the noise, then an optimum test can be implemented by threshold comparison of the quantity (73.6) where we have written Sk = sk (u) to indicate the functional dependence of the signal on the parameters, and where L and p(u) denote the range and probability density function, respectively, of the parameters. The most important example of such a parametrized signal is that in which the signal is a modulated sinusoid with random phase; i.e., FIGURE 73.1 Correlation detector for a coherent signal in additive white Gaussian noise. exp s Y s / k k k k n k n - Ê Ë Á ˆ ¯ ˜ Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ = = Ô Â Â 1 2 2 1 1 2 s s Yk k k n = Â 1 exp s Y ( ) s ( ) / p( )d k k k k n k n q - [ ] q q q Ê Ë Á ˆ ¯ ˜ Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ Â= Â= Ô Ú 1 2 2 1 1 2 s L
Sk= ak cos(o k +0), k=l, 2,...,n where a is a known amplitude modulation sequence, o is a known(discrete-time) carrier frequency, and the random phase 0 is uniformly distributed in the interval [, In this case, the likelihood ratio is a monotonically increasing function of the quantity ∑吗 cos(o k)Yk+∑ ap sin(o.k)x (738) Thus, optimum detection can be implemented via comparison of(73. 8)with a threshold, a structure known as an envelope detector. Note that this detector correlates the measurements with two orthogonal components of the signal, ak cos(o k)and a, sin(o k). These two correlations, known as the in-phase and quadrature components of the measurements, respectively, capture all of the energy in the signal, regardless of the value of 0. Since 0 is unknown, however, these two correlations cannot be combined coherently, and thus they are combined noncoherently via(73. 8)before the result is compared with a threshold. This detector is illustrated in Fig. 73.2. Parametrized signals also arise in situations in which it is not appropriate to model the unknown parameters as random variables with a known distribution. In such cases, it is not possible to compute the likelihood ratio (73.6)so an alternative to the likelihood ratio detector must then be used. (An exception is that in which the likelihood ratio detector is invariant to the unknown parameters-a case known as uniformly most powerful detection. Several alternatives to the likelihood ratio detector exist for these cases. One useful such procedure is to test for the signals presence by threshold comparison of the generalized likelihood ratio, given by maxL(Y1,Y2,……,Y) (73.9 where Le denotes the likelihood ratio for Eqs. (73. 1)and(73. 2)for the known-signal problem with the parameter vector fixed at 0. In the case of white gaussian noise we have L(Y,Y2,……,Yn) (73.10) It should be noted that this formulation is also valid if the statistics of the noise have unknown parameters, e.g.,the noise variance in the white Gaussian case in which the generalized likelihood ratio detector is useful is that of detect signal that is known except for its time of arrival. That is, we interested in ized where (al is a known finite-duration signal sequence and where 0 ranges over the integers. Assuming white Gaussian noise and an observation interval much longer than the duration of tab, the generalized likelihood ratio detector in this case announces the presence of the signal if the quantity (73.12) exceeds a fixed threshold. This type of detector is known as a matched filter, since it can be implemented by filtering the measurements with a digital filter whose pulse response is a time-reversed version of the known e 2000 by CRC Press LLC
© 2000 by CRC Press LLC Sk = ak cos(vc k + u), k = 1, 2, . . ., n (73.7) where a1, a2, . . ., an is a known amplitude modulation sequence, vc is a known (discrete-time) carrier frequency, and the random phase u is uniformly distributed in the interval [–p,p]. In this case, the likelihood ratio is a monotonically increasing function of the quantity (73.8) Thus, optimum detection can be implemented via comparison of (73.8) with a threshold, a structure known as an envelope detector. Note that this detector correlates the measurements with two orthogonal components of the signal, ak cos(vck) and ak sin(vck). These two correlations, known as the in-phase and quadrature components of the measurements, respectively, capture all of the energy in the signal, regardless of the value of u. Since u is unknown, however, these two correlations cannot be combined coherently, and thus they are combined noncoherently via (73.8) before the result is compared with a threshold. This detector is illustrated in Fig. 73.2. Parametrized signals also arise in situations in which it is not appropriate to model the unknown parameters as random variables with a known distribution. In such cases, it is not possible to compute the likelihood ratio (73.6) so an alternative to the likelihood ratio detector must then be used. (An exception is that in which the likelihood ratio detector is invariant to the unknown parameters—a case known as uniformly most powerful detection.) Several alternatives to the likelihood ratio detector exist for these cases. One useful such procedure is to test for the signal’s presence by threshold comparison of the generalized likelihood ratio, given by (73.9) where Lu denotes the likelihood ratio for Eqs. (73.1) and (73.2) for the known-signal problem with the parameter vector fixed at u. In the case of white Gaussian noise, we have (73.10) It should be noted that this formulation is also valid if the statistics of the noise have unknown parameters, e.g., the noise variance in the white Gaussian case. One common application in which the generalized likelihood ratio detector is useful is that of detecting a signal that is known except for its time of arrival. That is, we are often interested in signals parametrized as sk(u) = ak–u (73.11) where {ak} is a known finite-duration signal sequence and where u ranges over the integers. Assuming white Gaussian noise and an observation interval much longer than the duration of {ak}, the generalized likelihood ratio detector in this case announces the presence of the signal if the quantity (73.12) exceeds a fixed threshold. This type of detector is known as a matched filter, since it can be implemented by filtering the measurements with a digital filter whose pulse response is a time-reversed version of the known ak ck Yk a k Y k n k c k k n cos(w w ) sin( ) = = Â Â È Î Í Í ˘ ˚ ˙ ˙ + È Î Í Í ˘ ˚ ˙ 1 ˙ 2 1 2 max ( , , , ) u u ŒL L Y1 2 Y Yn ... L Y Y Y s Y s n k k k k n k n u( , , ) exp ( ) u (u) / 1 2 2 1 1 1 2 2 . . . , = - [ ] Ê Ë Á ˆ ¯ ˜ Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ = = Ô Â Â s max q q a Y k k k  -