Topic 1. Detection

1.1 Probability review

Randomness is everywhere in digital communication. The transmitted symbol X is random because the data are, and the received symbol Y is random because of the noise. Everything we will say about a receiver, from what it should do to how often it errs, is a statement about the joint behavior of X and Y. It is therefore worth reviewing the few rules of probability that we will use again and again. There are only three of them, and they all appear in Table 1.1.

We describe the transmitter by the input distribution \Pr(x), the probability that the symbol x of the constellation \mathcal X is sent, and the channel by its channel law W(y|x), the probability that y is received when x was sent. When the output alphabet is continuous, as it will be for most of the course, W(y|x) is a probability density in y. Neither \Pr(x) nor W(y|x) alone says anything about the pair (X,Y). The object that does is the joint distribution, and this is where the rules come in.

The product rule is the most important of the three. It says that the joint distribution of two random variables is always a product of two factors, the marginal of one and the conditional of the other. If X and Y were independent, the second factor would be just the marginal of Y. In general, it is the marginal of Y corrected for the dependence on X. For the pair (X,Y), this dependence is precisely the channel. Applied n times to a sequence of channel uses, the product rule gives the last line of the table whenever the noise in one use is independent of the noise in the others. We call such a channel memoryless, and all the channels in this course are memoryless.

The sum rule does the opposite. To eliminate a variable we are not interested in, we sum the joint over all its values. We will use it constantly, because the probability of an event is simply the joint summed over the outcomes that form the event, and the expectation of a function is the same sum with the function inside. For continuous alphabets both become integrals, and the manipulations are otherwise identical. Note that a probability is itself an expectation, that of the indicator function of the event, so the fourth and fifth lines of the table are really one line. We keep both because we will compute both.

Bayes’ rule, finally, is the product rule read twice: \Pr(x)W(y|x) and \Pr(y)\Pr(x|y) are the same joint, so dividing by \Pr(y) turns the channel law, which conditions on the input, into the distribution of the input given the output. That last distribution is what a receiver would like to know, and in Section 1.4 we will see that the optimal detector is built on it.

1.2 Channel models

Table 1.2 collects the channel laws that we will meet. The first two were introduced in the information theory course. Recall that everything about them can be computed with sums over two or three values, which makes them very convenient. The two Gaussian channels are the ones most often used in digital communications: the real one describes baseband transmission and the complex one passband transmission, as we will see in Topic 5. For now they are just two channel laws, and \sigma^2 is in both cases the total variance of the noise. In the complex case, the real and imaginary parts of the noise are independent Gaussians with variance \sigma^2/2 each.

The last channel, the additive exponential noise channel, models transmission by energy: the input is a nonnegative quantity, and the channel adds to it a random energy with exponential distribution of mean \mu. It is less common than the Gaussian ones, but it will be useful in this course, namely to remind us that what is true for Gaussian noise need not be true in general.

The three continuous channels share a common structure. In all of them the output is the input plus a noise term that does not depend on the input, Y=X+Z, so the channel law is the density of the noise evaluated at the difference, W(y|x)=f_Z(y-x). This is why the three densities in the table depend on x and y only through y-x. It also suggests the right measure of the quality of the channel, namely how large the symbols are compared with the noise. With \Es=\EE(|X|^2)=\sum_{x\in\mathcal X} \Pr(x)|x|^2 the average symbol energy, we define the signal-to-noise ratio of the Gaussian channels as \snr=\Es/\sigma^2. On the exponential channel the inputs are themselves energies, so the natural quantities are their mean \Es=\EE(X) and the ratio \Es/\mu, and we will use that ratio as its SNR.

1.3 Detectors and error probability

A detector is any function g from the output alphabet to the constellation: it looks at y and returns a guess \hat x=g(y). The natural measure of how well it does is the probability that the guess is wrong, and there are two such probabilities, depending on whether we condition on what was sent or not.

Both formulas are applications of the rules of Table 1.1. The event \{g(Y)\neq X\} is a set of pairs (x,y), so its probability is the joint summed over it, \sum_{(x,y):\,g(y)\neq x}\Pr(x)W(y|x). Grouping the terms by the value of x gives the second formula, and the inner sum is the first. This is the fourth line of the table. For a continuous channel, the sum over y is an integral of W(y|x) over the set of outputs that lead to a wrong decision. This is all the computation in this topic: identify that set, then sum or integrate. On the bit-flipping channel with the obvious detector g(y)=y, the set of wrong outputs for x=0 is \{1\}, so P_{\rm e}(0)=W(1|0)=p, and likewise P_{\rm e}(1)=p and P_{\rm e}=p: the computation of Example 1.1 again, now in the vocabulary of detectors.

1.4 Optimal detection

Which detector should we use? The question has a simple answer, and we state it before looking at any particular channel, because the answer does not depend on the channel. Among all functions g, two deserve a name of their own.

The name of the first detector comes from Bayes’ rule: \Pr(x)W(y|x)=\Pr(y)\Pr(x|y), and \Pr(y) does not depend on x, so maximizing the joint over x is the same as maximizing the a posteriori probability \Pr(x|y). In other words, the MAP detector picks the symbol that is most probable given what was received. This seems a sensible choice, and the following result shows that it is indeed the best one.

On the bit-flipping channel with g(y)=y, for instance, the four pairs of Example 1.1 reduce to the two with x=y, and the sum in (1.10) is \Pr(0,0)+\Pr(1,1)=1-p, in agreement with P_{\rm e}=p.

When the symbols are equiprobable, \Pr(x) is the same constant for every x and cancels in the maximization, so the MAP and ML detectors coincide. This is the usual situation, since data bits are well modeled as independent and equiprobable, and it is the reason why the ML detector has its own name. On the bit-flipping channel with p<\tfrac12, for instance, W(y|x) equals 1-p for x=y and p otherwise, so the ML detector is g_{\rm ML}(y)=y, the obvious detector of Section 1.3. For p>\tfrac12 the two likelihoods exchange their roles, and the ML detector flips every received bit. On the Gaussian channels, the ML rule takes a form with a simple geometric interpretation.

Note what the proof used: the noise density is a function of the difference y-x, and it decreases symmetrically with the distance |y-x|. The first property is shared by every additive channel. The second is not, as we will see shortly with the exponential channel, whose density is not symmetric around the transmitted symbol.

Figure 1.1. Decision regions of the ML detector for 2-PAM in Gaussian noise.

1.5 Decision regions

A detector assigns every possible output to a symbol. Conversely, every symbol x is assigned the set of outputs that lead to it, \begin{equation*} \mathcal D_x=\{y:\ g(y)=x\},\tag{1.18} \end{equation*} its decision region. The regions of different symbols do not overlap, and together they cover the whole output alphabet: they form a partition of it. Describing a detector by its regions is often clearer than describing it by a formula. Figure 1.2 shows the regions of three detectors: the ML detectors of 4-PAM and of QPSK in Gaussian noise, which we analyze below, and the detector of Example 1.8.

For the nearest-point detector, the region of x is the set of points closer to x than to any other constellation point. Such regions have a name, Voronoi regions, and a simple geometry: the boundary between the regions of two neighboring points is the perpendicular bisector of the segment that joins them, as Figure 1.3 shows for a constellation of three points. The same construction applies to the constellations of Topic 5.

Figure 1.2. Decision regions of the ML detector: (a) 4-PAM in real Gaussian noise, with thresholds halfway between neighbors, (b) QPSK in complex Gaussian noise, with the four quadrants, and (c) binary transmission in exponential noise, where the threshold is at the larger symbol.

Figure 1.3. Voronoi regions of a three-point constellation in the plane. Each boundary is the perpendicular bisector of the dotted segment between two points, and the three bisectors meet at the point equidistant from all three.

With the decision regions, the computation of the error probability becomes a geometric problem. The conditional error probability of Definition 1.2 is the probability that the output falls outside the region of the symbol that was sent, \begin{equation*} P_{\rm e}(x)=\Pr(Y\notin\mathcal D_x\,|\,X=x)=\int_{y\notin\mathcal D_x} W(y|x)\drm y = 1-\int_{y\in\mathcal D_x} W(y|x)\drm y,\tag{1.19} \end{equation*} where the second form, one minus the probability of a correct decision, is sometimes the easier one to compute. Let us do it for our running example.

The same computation, with A replaced by any threshold a>0, gives a result that we will use repeatedly: for a real Gaussian Z of variance \sigma^2, \begin{equation*} \Pr(Z<-a)=\Pr(Z>a)=\tfrac12\erfc\Bigl(\frac{a}{\sqrt2\,\sigma}\Bigr).\tag{1.23} \end{equation*} The function \erfc will appear repeatedly in the rest of the course, and it is worth having an idea of its size, see Table 1.3: \erfc(1)\approx 0.16, \erfc(2)\approx 4.7\cdot10^{-3}, \erfc(3)\approx 2.2\cdot10^{-5}, and for large u it behaves as e^{-u^2}/(u\sqrt\pi). In other words, the error probability falls very fast with the SNR, roughly like e^{-\snr/2}, as Figure 1.4 and Table 1.4 show.

The SNR is usually quoted in decibels, \snr_{\rm dB}=10\log_{10}\snr, so that 10 dB is a ratio of 10 and 3 dB a ratio of about 2. The vertical axis of the figure is logarithmic too. Going from 10 to 15 dB, a factor of about three in SNR, takes the error probability of 2-PAM from about one error in a thousand symbols to one in a hundred million.

Figure 1.4. Error probability of the ML detector as a function of the SNR for four of the cases of this section (for the exponential channel the SNR is \Es/\mu).

1.6 Bit errors and sequences

Two remarks close the topic. The first is that symbol errors and bit errors are different things. When a symbol carries several bits, a symbol error need not flip all of them: if the detector confuses x with a neighbor, only the bits in which the labels of x and of its neighbor differ are wrong. The bit error probability P_{\rm b} is the average fraction of wrong bits, and it is always between P_{\rm e}/\log_2 M and P_{\rm e}. If neighboring points differ in one bit only, a labeling called Gray, and almost all errors go to a neighbor, as they do at high SNR, then the bit error probability is close to the lower end, P_{\rm e}/\log_2 M. For QPSK the Gray labeling makes the two bits independent decisions on the real and imaginary parts, and P_{\rm b}=p exactly, as Exercise 1.37 shows. We will return to labelings in Topic 5.

The second remark is that a message is a sequence of symbols, and that even small error probabilities accumulate along it. If each of n independent symbols sent over a memoryless channel is detected on its own with error probability P_{\rm e}, the product rule of Table 1.1 gives the probability that the whole message is detected correctly, \begin{equation*} \Pr(\text{no error in } n \text{ symbols})=(1-P_{\rm e})^n\approx e^{-nP_{\rm e}},\tag{1.31} \end{equation*} because the n decisions are independent. A symbol error probability of one in a thousand, which looks small, leaves only a probability e^{-1}\approx 0.37 of receiving a message of a thousand symbols without any error. Detecting each symbol on its own is therefore not enough for reliable communication. The remedy, adding redundancy to the sequence and deciding on the whole message at once, is the subject of Topic 2. Exercise 1.38 works out the numbers.