Detection of Signals in Noise

By Robert N. McDonough and A. D. Whalen

The Second Edition is an updated revision to the authors highly successful and widely used introduction to the principles and application of the statistical theory of signal detection. This book emphasizes those theories that have been found to be particularly useful in practice including principles applied to detection problems encountered in digital communications, radar, and sonar.

• Detection processing based upon the fast Fourier transform

• Language: English
• Publisher: Academic Press
• Release date: May 2, 1995
• ISBN: 9780080504087

Book preview

satisfaction.

Preface

The cordial reception given to the first edition of this work encouraged the publisher and the original author (A.D.W.) to plan a second edition. The extent of developments in the practice of signal detection since the appearance of the first edition dictated a thorough revision. A new author (R.N.M.) was therefore invited to participate in the project, and the present volume is the result. Much new material has been added, although the scope of the topics considered and the philosophy of their treatment have not changed. The additions are intended to add background and, in some cases, generality to the treatments of the first edition.

Our aim is unchanged and can be summarized in a quote from the Preface to the first edition:

This book is intended to serve as an introduction to the principles and applications of the statistical theory of signal detection. Emphasis is placed on those principles which have been found to be particularly useful in practice. These principles are applied to detection problems encountered in digital communications, radar, and sonar. In large part the book has drawn upon the open literature: texts, technical journals, and industrial and university reports. The author[s’] intention was to digest this material and present a readable and pedagogically useful treatment of the subject.

The topics covered are delineated in the Table of Contents. In comparison with the first edition, they are treated in more cases using discrete formulations, in addition to the formulations in terms of continuous time signals that characterized the first edition. Because of the wide application of the fast Fourier transform as a system element, a significant part of the development considers Fourier coefficients as the observables to be processed. Because of this, and because of the convenient calculation of the complex envelope of a signal that is now possible, much of the present development is phrased specifically for the processing of complex observables. However, the treatment of real discrete observables, such as samples of real time functions, is not neglected.

In our treatments of hypothesis testing in Chapter 5 and of estimation theory in Chapter 10, we have made the developments somewhat more general than in the first edition. This is intended to make clear the limitations of the methods discussed, as well as to point out extensions.

Since the publication of the first edition, essentially all of the material that we discuss has migrated from the original journal articles and reports into texts and monographs. We have therefore made fewer citations to the original literature than earlier. Rather, we have appended a bibliography of standard works and have occasionally made specific citations where needed in the text.

The first edition grew out of a Bell Telephone Laboratories in-house course presented by A.D.W. Thus, the book should be suitable for a course in signal detection, at either the graduate or the advanced undergraduate level. Beyond that, we have strongly aimed the book at practicing engineers who need a text for either self-study or reference. Throughout the text, equations of particular importance have been indicated with an asterisk before the equation number.

The preparation of this second edition was supported in part by The Johns Hopkins University Applied Physics Laboratory, through the granting of a Stuart S. Janney Fellowship to R.N.M. In addition, both authors are indebted to their respective organizations for sustained opportunities over the years to work and learn in ways that made it possible for us to produce this book. The friendly help of Jacob Elbaz in preparing the illustrations is gratefully acknowledged.

1

Probability

Engineering is often regarded as a discipline which deals in precision. A well-ordered nature evolves in ways which are in principle perfectly measurable and completely predictable. On the contrary, in the problems that will concern us in this book, nature presents us with situations which are only partially knowable through our measurements, which evolve in ways that are not predictable with certainty, and which require us to take actions based on an imperfect perception of their consequences. The branch of applied mathematics called probability theory provides a framework for the analysis of such problems. In this chapter we will give a brief summary of the main ideas of probability theory which will be of use throughout the remainder of the book.

1.1

PROBABILITY IN BRIEF

Probability can be discussed at the intuitive level that deals with the events observed in everyday life. If a coin is tossed many times, it is noted that heads and tails appear about equally. We assign a probability of 0.5 to the appearance of a head on any particular toss and proceed to calculate the probability of, say, 3 heads in 5 tosses. Generality and clarity of thought follow if we introduce a more mathematical framework for the subject of probability. This was developed in the 1930s. We will summarize that view here, in order to introduce the main elements of the theory and some terminology.

of the elementary outcomes of the experiment. These are defined such that exactly one of them occurs each time the experiment is performed. The second element is a set σ of events, each of which can be said to have occurred or not to have occurred depending on which elementary outcome occurs in a performance of the experiment. The third element, P, is a rule of assignment of a number (its probability) to each event of the set σ.

The construction of an abstract experiment begins by specifying all its elementary outcomes. For example, the rolling of one of a pair of idealized perfect dice (a die) is an abstract experiment. The elementary outcomes could be that the die lands with one of the numbers 1 through 6 on top. Regardless of the experiment, in a case such as this, in which the elementary outcomes are countable, we will label them by the symbols ζi, i = 1, 2, …. On the other hand, if the abstract experiment is such that its elementary outcomes are not countable, we will label them by a continuous variable ω, as ζ(ω). Such an experiment might be, for example, the measurement (with infinite precision) of a voltage which can have any real number for its value. The definition of the elementary outcomes of an experiment is entirely arbitrary, except that they must be complete and mutually exclusive; that is, exactly one of them must occur at each performance of the experiment.

can be considered as a collection of points in a point set space, the sample space can be abstractly defined without reference to points, the language of point sets provides a convenient way to visualize the outcomes ζ as points in a geometric space. In the case of a countable set of outcomes ζi, the points are discrete, whereas with a continuum of outcomes ζ(ω) the points are visualized as being in completely filled regions of the space.

of an experiment we can then construct events, which are defined as sets of elementary outcomes. Events are generally denoted by script letters. For example, in the idealized die-throwing experiment, some events are:

: Either the number 2 or the number 5 shows uppermost.

: The uppermost number is even.

: The number 5 shows uppermost.

: A number less than 5 shows uppermost.

: Some number shows uppermost.

These events can also be described by the set of index numbers of the elementary outcomes they comprise:

(1.1)

Note that we formally distinguish between the single elementary outcome (point), say ζ5, and the event (set) {ζ5} comprising that single outcome.

of all outcomes, the sample space, is also called the certain event, because by definition it must occur in any trial of the experiment.

New events can be defined from old events by introducing rules of combination. These are exactly the rules of point set theory. The sum (union, logical OR) and product (intersection, logical AND) of two events are introduced:

or to both (as a member of any set of events we discuss. Then we can introduce the complement (negation) of an event as

(Fig. 1.1d). It is then necessary also to include the null event , which is the event consisting of no elementary outcomes. Finally, we will mention the symmetric difference of two sets (Fig. 1.1e), defined as

, σ, PI ∈ σ, we require that

FIGURE 1.1 Combinations of events (a) Union .

where the summation is in the sense of the union operation. These two postulates about σ are sufficient to guarantee that σ also contains all the (possibly infinite) products (intersections) of its members and all symmetric differences of its members.

In algebra, any set of elements with the properties assumed above for the set σ of events is called a σ-algebra. In an older terminology, specific to probability theory, the term field of probability or σ-field is used. That invites confusion, however, because a field is a collection whose elements have properties different from those of an algebra. The term is still in use, however.

is such that any events constructed by set operations on events of σ will also be members of σ. The specification of such a set σ is a technical matter, however, because in applications the events of interest are always clear and can always be imbedded in a σ-algebra. It is enough to know that the possibility exists, because we are interested only in the events themselves and usually do not need to characterize the σ-algebra explicitly.

of the set σ. It assigns a probability would occur. For example, for the events Eq. (1.1) of the die-rolling experiment, we might assign:

These assignments would indicate we believe the die to be fair.

Such an assignment of probabilities cannot be made arbitrarily. For example, we feel that something is wrong if we assign probability 1/6 to each face of a fair die and probability 2/3 to rolling an even number. In general, the assignment of probabilities P of σ must be such that the following axioms are fulfilled:

(1.2)

(In this last, the summation of events is the union, and infinite sums are allowed. The events are to be disjoint, with no elementary outcomes in common.)

From the axioms does not occur) satisfy

we have from Eq. (1.2) that

so that

, and the probability of the null event is

The axioms . That latter assignment, however, can be done in many ways. The specifics depend on the aspects of the physical situation being modeled. For example, in the case of a fair die, we take P ({ζi}) = 1/6, i = 1,6. There then follow, for example,

All the various manipulations of set algebra are useful. For example, from the identities

(1.3)

In particular, in the fair die experiment,

With the final axioms relates to a specific engineering question at hand is not part of the study of probability theory. Rather, it is a crucial aspect of the application of probability theory to real problems. In this chapter, and indeed in much of the book, we will be concerned only with idealized experiments and with the use of probability theory to make statements about them.

1.2 CONDITIONAL PROBABILITY AND STATISTICAL INDEPENDENCE

has occurred. This is called the conditional probability and is defined as

*(1.4)

of data.

EXAMPLE 1.1

. Then, from .

in the same set σ of events are called independent provided

(1.5)

occur and is often written P be respectively the events that a fair die comes up odd and that the die comes up less than 4, we have

We conclude that the events are not independent, in the sense of the definition. The word also corresponds to our usual usage, in that knowing the die shows a number less than 4 changes our degree of belief that it has come up odd.

An equivalent definition of independence follows from introducing the conditional probability Eq. (1.4) of the two events into the definition Eq. (1.5). From Eq. (1.5), two events are independent provided

so that

(1.6)

has occurred. This is in accord with the everyday meaning of the term independence.

Combined Experiments

2 be the corresponding sample spaces of elementary outcomes ζ1i, ζ2j. Aggregate together the two sets of outcomes by defining new elementary outcomes ζij = (ζ1i, ζ2j) consisting of all ordered pairs of outcomes from the two sets of elementary outcomes. These points ζij , called the Cartesian product .

2 are ζ1i and ζ2j2 = ∑ ζ2j, where the sum is over all j and is in the sense of the union of events. By the definition of Cartesian product we have

Because the events ζ1i × ζ2j ∈ σ are disjoint (their pairwise intersections are the null event φ), the probabilities of the events in σ are properly defined provided we have

Because the joint space probability on the left is the probability that ζ1i occurs in the first experiment and anything occurs in the second, we reasonably assign to it the value P1(ζ1i). The result is the formula for computing the probabilities in the first experiment (the marginal probabilities) from those in the joint experiment:

(1.7)

EXAMPLE 1.2

= {H1, H2, …, T6}, which we label as ζi, i = 1, 12. Suppose that these elementary outcomes have probabilities respectively of (1/12, 1/12, 1/12, 1/12, 1/12, 1/12, 1/24, 1/8, 1/24, 1/8, 1/24, 1/8). (The only restriction in assigning these is that they be nonnegative and add to unity.) From Eq. (1.7) the marginal probability of heads is

and that of an even number on the die is

where the index set is I = (2, 4, 6, 8, 10, 12). Clearly, this is not a fair die; our assignment of probabilities models a different kind of die.

For this die and coin, the conditional probabilities of rolling an even number, given that we know the coin has come up heads or tails, from Eq. (1.4) are

Since then, for example,

we conclude from Eq. (1.6) that the two constitutent experiments of tossing the coin and rolling the die are not independent. That is, the outcome of the coin toss affects the properties of the die that is rolled. That might come about, for example, if we were to choose one of two dies, depending on the outcome of the coin toss.

The definition of independence given in ii is said to be (mutually) independent provided the events are pairwise independent:

and in addition if, for trios of events,

with similar relations for the events taken by fours, by fives, etc.

1.3 PROBABILLITY DISTRIBUTION FUNCTIONS

, σ, Pand all unions, intersections, differences, and negations of its elements. The probability 0 ≤ P ) ≤ P ) = 1 is a real-valued function whose domain is the events in the σ-algebra. Now we need to introduce the idea of a random variable.

A random variable is any real finite-valued function X corresponding to an abstract experiment. In any particular performance of the experiment underlying a random variable, some elementary outcome ζ0 will occur. This will in turn indicate a specific value X (ζ0) for the random variable.

for which the random variable X (ζ) has the requested property. For example, in the die-rolling experiment, we can take as elementary outcomes the 6 numbers which could appear uppermost. A random variable X (ζ) is then defined by specifying the 6 values Xi = X (ζi) it should take for the 6 possible elementary outcomes of the experiment. These might be specified by a relation such as Xi = 2i − 5, i = 1, 6. Then the requirement 1.5 ≤ X ≤ 8 induces the event

(1.8)

where the notation {ζ: 1.5 ≤ X ≤ 8} means "the set of points ζ for which the value X (ζ) satisfies 1.5 ≤ X ≤ 8."

With such associations of requirements on a random variable X (ζ) with events in the σ-algebra of an experiment, we can then speak of the event that the random variable satisfies the requirement. That is, for example, in the particular case of the assignment X = 2i − 5 relative to the fair die experiment, we speak of the event that 1.5 ≤ X ≤ 8. Furthermore, we can speak of the probability of the event 1.5 ≤ X ≤ 8 as the probability of the corresponding event Eq. (1.8) in the σ-algebra based on the experiment. That is,

In engineering, it is the values of random variables which are central to applications. That is because our measurements are real numbers produced by an instrument observing some system. The state of operation of the system has been determined by the particular outcome of a performance of some abstract experiment by some entity (nature, for example, or the sender of a message). In the study of the values of a random variable corresponding to an experiment, the distribution function of the random variable is central. By definition, that is a function

(1.9)

It is worth reiterating carefully the meaning of the symbols in this definition. On the right, X is a real-valued function X , σ, P}. The inequality is in the usual sense, and x is some real number. The requirement X ≤ x = {ζ: X (ζ) ≤ x} ∈ σ, and the number PX(x) is the probability assigned to that event by the function P: PX(x) = P ).

In the fair die example above, the random variable X = 2i − 5 has values X = (-3, -1, 1, 3, 5, 7). With the particular assignment P (ζi) = 1/6 the distribution function PX(x) is as shown in Fig. 1.2a. A different assignment of values X to the outcomes i, or different probabilities P (ζi), would result in a different distribution function for X.

FIGURE 1.2 (a) Distribution function PX(x) of the random variable X = 2i − 5 in the experiment of casting a fair die. (b) Density function as a sequence of Dirac impulses.

Because the values of a distribution function are the probabilities of various events, from the axioms Eq. (1.2) satisfied by any probability function P we must have

(1.10)

The last follows because the events {ζ: X ≤ x} and {ζ: x < X ≤ x + dx} have no elementary outcomes in common. We conclude from Eq. (1.10) that any distribution function PX(x) is monotonically nondecreasing between the values 0 at x = –∞ and 1 at x = +∞. Rewriting the last equation of Eq. (1.10) yields another important property of a distribution function:

*(1.11)

From this, letting x2 = x and x1 = x ⇒ 0, there follows

(1.12)

This is illustrated for example in Fig. 1.2a.

It is often useful to consider two different sets of measurements relative to the same experiment. We then define random variables, say X (ζ), Y(ζ), and consider the bivariate (joint) distribution function

where the last form is an abbreviation of the second form. From the probabilities of the various events involved it is easy to see that

(1.13)

with the obvious generalizations for multivariate distribution functions PXY…(x, y, …).

1.4 CONTINUOUS RANDOM VARIABLES

A continuous random variable is defined as one with a continuous distribution function, such as in Fig. 1.3a. A discrete random variable is one with a piecewise constant distribution function, as in Fig. 1.2a. A mixed random variable combines the two types and has a distribution function as in Fig. 1.4a. Because a continuous random variable has a continuous distribution function PX(x), the derivative dPX/dx exists everywhere. It is called the (probability) density function of the random variable X:

*(1.14)

An example is shown in Fig. 1.3b. As any PX(x) is monotone nondecreasing, pX(x) ≥ 0 everywhere.

FIGURE 1.3 Probability functions of a continuous random variable. (a) The cumulative distribution function. (b) The density function.

FIGURE 1.4 Probability functions of a mixed random variable. (a) The cumulative distribution function. (b) The density function.

A discrete or mixed random variable by definition has a distribution function which is not everywhere continuous. Formally, we still define the corresponding density function as the derivative of the distribution function, but we allow impulses (Dirac δ functions) in the density. Thus, we write

indicates the continuous part of the distribution, and at (isolated) points xi of discontinuity Pi = PX(xi) − PX(xi−). Figure 1.2b shows an example of a density function for a discrete random variable, and Fig. 1.4b shows the same for a mixed random variable.

In most of our work, the random variables of interest will be of the continuous type. By the definition Eq. (1.14), the density function is related to the distribution function as

so that

(1.15)

That is,

(1.16)

In the case of a multivariate distribution function, we define a multivariate density, for example,

(1.17)

Then

(1.18)

In particular,

From these follow the marginal densities

(1.19)

(1.20)

in the same σ-algebra. We now introduce the conditional probability distribution function of a random variable X (ζ). This is

(1.21)

= {ζ: a < Y ≤ b}, in which case we have

Letting a = y, b = y + dy, as dy ⇒ 0 this becomes

The conditional probability density corresponding to this conditional distribution function is

*(1.22)

or, in a common notation,

This last causes the same symbol (p) to do heavy duty as three different functions in the same equation.

Two random variables X, Y, are said to be independent provided the events x < X ≤ x + dx, y < Y ≤ y + dy are independent for all values x, y. That is,

That is,

(1.23)

so that

(1.24)

As we will often do hereafter, we can write a multidimensional random variable as a (column) vector Z of random variables Zi. The corresponding multidimensional distribution function is PZ(z) = P (Z1 ≤ z1, …, Zn ≤ zn), with density pZ(z) = ∂nPZ(z)/∂z1 … ∂zn. [This latter, scalar, nth order partial derivative is different from the vector ∂PZ(z)/∂z, which is defined as the row vector of the n first-order partial derivatives ∂PZ(z)/∂zi.] If the variables Z are divided into two groups, X and Y, it is easy to see