Week 4-Lecture 23

Summary

This lecture explores the optimal map detector for AWGN channels, focusing on decision regions in signal space that minimize error probability. It explains how detectors partition the space and use correlation and match filters for implementation. The discussion includes the impact of equiprobable and non-equiprobable messages on decision regions, with examples illustrating the geometrical representation of signals in vector space. The lecture concludes with calculating the probability of error for both equiprobable and non-equiprobable cases, highlighting the challenges of high-dimensional signal spaces.

Takeaways

• 📡 The optimum map detector for AWGN channels is derived and its implementation is based on correlation and match filters.
• 🔍 To determine the error probability of the optimum receiver, decision regions in the signal space must be established.
• 📏 The N-dimensional signal space is partitioned into M regions, each corresponding to a message signal, aiming to minimize the error probability.
• 📶 The decision region R_k includes all points in the N-dimensional space where the probability of message m_k given observed vector x is greater than for any other message.
• 📉 For equiprobable messages, the decision regions are determined by the perpendicular bisectors of the lines joining signal points, reflecting the spherical symmetry of Gaussian noise.
• 📊 The decision function for an AWGN channel can be expressed as the argument minimum of a norm of the difference between the received vector and signal vectors.
• 📈 Non-equiprobable messages lead to weighted decision regions, favoring messages with higher probabilities, which is reflected in the decision function by the log of the message probabilities.
• 📐 In higher-dimensional signal spaces, visualizing decision regions becomes difficult, and the calculation of error probabilities is more complex.
• 🔢 The probability of correct detection is calculated based on the region where the received vector falls, which is easier with defined decision regions.
• 📉 The probability of error is found by subtracting the probability of correct detection from 1, and can be simplified for specific cases such as equiprobable messages.

Q & A

What is the purpose of decision regions in signal space?

Decision regions in signal space are used to partition the N-dimensional signal space into M regions, where M is the number of message signals. This partitioning is done to minimize the probability of error by assigning received signals to the most likely transmitted message based on their proximity in signal space.

How does the optimum receiver determine the decision regions?

The optimum receiver determines the decision regions by choosing them to minimize the probability of error. For a MAP (Maximum A Posteriori) detector, the decision region R_k includes all points in the N-dimensional space for which the probability of message m_k given the observed vector x is greater than the probability of any other message m_j given x, for all j not equal to k.

What is the significance of equiprobable messages in decision region formation?

When messages are equiprobable, the decision regions are formed by the perpendicular bisectors of the lines joining the signal points. This is because the decision is made in favor of the signal that is closest to the received vector x, and for Gaussian noise, which has spherical symmetry, the boundary between decision regions will be equidistant from the signal points.

How does the presence of non-equiprobable messages affect decision regions?

In the case of non-equiprobable messages, the decision regions are biased in favor of the message with a higher probability. This is reflected in the decision function by the inclusion of the log of the probability of the message, which results in weighted decision regions that favor the more probable messages.

What is the role of the Q function in calculating the probability of correct decision?

The Q function plays a crucial role in calculating the probability of correct decision in the presence of Gaussian noise. It is used to determine the probability that the noise component will not cause the received vector x to fall into the wrong decision region, thus ensuring a correct decision is made.

How is the probability of error calculated given the decision regions?

The probability of error is calculated by considering the complement of the probability of correct detection. The probability of correct detection is the probability that the received vector x belongs to the correct decision region R_j, given that message m_j was transmitted. The unconditional probability of correct detection is the sum of these conditional probabilities, and the probability of error is 1 minus this sum.

What is the significance of the perpendicular bisector in the context of decision regions?

The perpendicular bisector of the line joining two signal points is significant because it forms the boundary between two decision regions. This boundary is the set of points equidistant from the two signal vectors, which is a straight line perpendicular to the line joining the signal points and passing through the midpoint at a distance determined by the probabilities of the messages.

How does the dimensionality of the signal space affect the visualization and calculation of decision regions?

As the dimensionality of the signal space increases, the visualization of decision regions becomes more complex and potentially impossible beyond two dimensions. Similarly, the calculation of the probability of error becomes more challenging and may require more advanced mathematical techniques or computational methods.

What is the impact of the noise power spectral density on the decision regions and the probability of error?

The noise power spectral density affects the decision regions and the probability of error by influencing the distribution of the noise in the signal space. Higher noise power spectral density leads to a larger spread of the noise, which can cause the received signal to be more likely to fall into the wrong decision region, thus increasing the probability of error.

Can you provide an example of how decision regions are calculated for non-equiprobable messages?

For non-equiprobable messages, the decision regions are calculated by considering the log of the probability of each message in the decision function. For example, if the probability of message m_2 is higher than m_1, the decision region R_2 will be biased towards S_2, making it larger. The boundary is determined by the condition where the squared distance from the received vector x to S_1 is equal to a constant c, which is derived from the probabilities of m_1 and m_2.

Outlines

00:00

📡 Understanding Optimum Map Detector and Decision Regions

The paragraph introduces the concept of the optimum map detector for an Additive White Gaussian Noise (AWGN) channel, emphasizing the need to determine the probability of error for this detector. It explains that the detector partitions the N-dimensional signal space into M regions, each corresponding to a message signal. The decision region for a message is defined as the set of all channel outputs that map to that message. The partitioning aims to minimize the error probability, and the optimum receiver sets these regions to achieve the lowest possible error rate. The decision rule for the map detector is discussed, which is based on the probability of a message given the observed vector x, compared to the probabilities for all other messages.

05:23

📊 Decision Regions and Error Probability in Signal Space

This paragraph delves into how decision regions are determined in the presence of Gaussian noise, which has spherical symmetry. It explains that for equiprobable messages, decision boundaries are the perpendicular bisectors of the lines joining signal points. The discussion then extends to higher dimensions and non-equiprobable messages, where decision regions are biased towards messages with higher probabilities. An example with two signals is used to illustrate how decision regions are affected by unequal probabilities, showing that the region for the more probable message expands at the expense of the less probable one.

11:06

🔍 Analyzing Decision Boundaries in Signal Space

The paragraph provides a mathematical analysis of decision boundaries, using the decision function to partition the signal space into regions. It introduces a constant 'c' to represent the condition under which a decision is made, and it is shown that the boundary is a straight line perpendicular to the line joining two signal points. The proof involves geometric relationships and algebraic manipulation to establish that the boundary line passes through a specific distance from one of the signal points, derived from the decision function.

16:14

📚 Calculating Error Probability with Decision Regions

This section discusses the calculation of error probability using the decision regions. It explains that the probability of a correct decision is the probability that the received vector x belongs to the correct region Rj. The unconditional probability of correct detection is the sum of conditional probabilities, and the error probability is the complement of this. An example with an AWGN channel and two messages is used to illustrate the calculation, where the signals are antipodal and non-equiprobable. The implementation of the optimum receiver using a match filter and the geometric representation of signals in the vector space are also discussed.

21:16

📉 Probability Calculations for Optimum Receiver

The paragraph focuses on calculating the probability of correct decision and error for the optimum receiver in a 1-dimensional signal space with two messages. It describes the geometric representation of signals and decision regions, and how the probability of correct decision is calculated given the Gaussian distribution of noise. The Q-function is introduced to express the probability of the noise being less than a certain value, which determines the correct decision region. The probability of correct detection for both messages is derived, and the overall probability of error is calculated by considering the probabilities of each message and the conditional probabilities of correct detection.

26:17

🔗 Conclusion on Optimum Receiver and Error Probability

The final paragraph summarizes the process of finding the optimum receiver and calculating the probability of error. It highlights the partitioning of the signal space into decision regions as a key step in visualizing and calculating the probability of correct detection. The paragraph concludes by acknowledging the complexity of these tasks in high-dimensional signal spaces and non-trivial probability calculations, suggesting that further discussion will be needed in subsequent classes.

Keywords

💡Optimum Map Detector

The optimum map detector is a theoretical construct used in signal processing to detect signals optimally in the presence of noise. It is designed to minimize the probability of error in signal detection. In the context of the video, the optimum map detector is derived for an AWGN (Additive White Gaussian Noise) channel, which is a fundamental concept in digital communication systems. The script discusses how this detector partitions the signal space into decision regions to make the best possible decision on which signal was transmitted.

💡Correlation and Match Filter

Correlation and match filtering are signal processing techniques used to detect known signals in the presence of noise. A match filter is a specific type of filter designed to maximize the signal-to-noise ratio of a specific input signal. In the video, these techniques are mentioned as the basis for implementing the optimum map detector, suggesting that they play a crucial role in the detection process by aligning the received signal with a template or expected signal.

💡Decision Regions

Decision regions are partitions of the signal space that are used to make decisions about which signal was transmitted. Each region corresponds to a possible transmitted message, and the detector decides which message was sent based on which region the received signal falls into. The script explains that these regions are critical in minimizing the error probability and are determined based on the probabilities of the transmitted signals.

💡Additive White Gaussian Noise (AWGN)

AWGN is a type of noise commonly encountered in communication systems, characterized by a Gaussian probability distribution with a mean of zero and a constant power spectral density. It is a fundamental concept in the video as it represents the type of noise over which the optimum map detector operates. The script discusses how the properties of AWGN, such as its spherical symmetry, influence the shape of decision regions.

💡Equiprobable Messages

Equiprobable messages refer to a scenario where all possible messages have the same probability of being transmitted. This assumption simplifies the analysis of communication systems, as it allows for symmetric decision regions. The script mentions that when messages are equiprobable, the decision regions are defined by the perpendicular bisectors of the lines joining signal points, which simplifies the calculation of error probabilities.

💡Non-equiprobable Messages

Non-equiprobable messages are those where the probabilities of transmission are not equal. This concept is important in the video as it introduces a layer of complexity in the decision-making process of the detector. When messages are not equiprobable, the decision regions are no longer symmetric, and the script discusses how this affects the partitioning of the signal space and the calculation of error probabilities.

💡Perpendicular Bisector

The perpendicular bisector is a line that divides a line segment into two equal parts at a 90-degree angle. In the context of the video, the perpendicular bisector is used to define the boundary between decision regions when messages are equiprobable. The script uses the perpendicular bisector to illustrate how decision regions are formed in a two-dimensional signal space.

💡Probability of Error

The probability of error is a measure of how often the detector makes incorrect decisions about which signal was transmitted. It is a key performance metric in communication systems. The script discusses how to calculate the probability of error for the optimum map detector by considering the decision regions and the properties of the noise.

💡Conditional Probability

Conditional probability is the probability of an event occurring, given that another event has occurred. In the video, conditional probability is used to calculate the probability of correct detection given that a specific message was transmitted. The script explains how these probabilities are used to determine the overall probability of correct detection and, consequently, the probability of error.

💡Q Function

The Q function is a mathematical function used in probability theory and statistics, particularly in the analysis of Gaussian processes. In the video, the Q function is used to express the probability of the noise causing a decision error, which is integral to calculating the probability of correct detection and, by extension, the probability of error.

💡Signal Space

Signal space is a multidimensional space used to represent signals, where each dimension corresponds to a different aspect of the signal, such as time or frequency. The script discusses how the optimum map detector partitions the N-dimensional signal space into decision regions based on the properties of the transmitted signals and the noise. Understanding signal space is crucial for visualizing and analyzing the detection process.

Highlights

Optimum map detector for AWGN channel derived and its implementation based on correlation and match filter studied.

Task is to determine the probability of error for the optimum receiver.

Decision regions in signal space are crucial for any detector, including MAP and ML detectors.

The N-dimensional signal space is partitioned into M regions, each corresponding to a message signal.

Decision regions are chosen to minimize the probability of error.

For a MAP detector, the optimal decision regions result in the minimum probability of error.

In the case of additive white Gaussian noise, the decision is made in favor of the signal closest to the received vector.

For equiprobable messages, decision region boundaries are the perpendicular bisectors of the lines joining signal points.

Visualization of decision regions becomes difficult with dimensionality larger than 2.

Non-equiprobable messages lead to weighted decision regions favoring messages with higher probabilities.

The term log of probability of m j in the decision function reflects the bias towards more likely messages.

A simple example with two signals shows how decision regions are determined by the bisector of the line joining the signals.

In non-equiprobable cases, the decision region for the more probable message is biased towards it.

The decision boundary is a straight line perpendicular to the line joining two signal points.

The probability of correct detection and error can be calculated given the decision regions.

An example with an AWGN channel and two messages shows how to find the optimum receiver and corresponding probability of error.

For high-dimensional signal spaces, visualization and calculation of probability of error may be challenging.

The lecture concludes with a discussion on how to calculate the probability of error for a simple case with partitioned signal space.

Transcripts

We have derived the optimum map detector for AWGN  channel and also studied its implementation based  

on correlation and match filter. The next task  is basically is to determine the probability of  

error of this optimum receiver. And in order  to do this we need to determine what is known  

as decision regions in the signal space. So, any detector including the map and ML  

detector; what it does basically it partitions  the N dimensional signal space into M regions  

which we indicate by R 1, R 2, R m; capital  M denotes the number of message signals.

This partition is done in such a way that  the vector x which is the projection of  

the signal x t receive signal onto the N  dimensional space belongs to R k. If this  

condition is satisfied then we take the  decision that m k was transmitted. Now,  

this R j for j equal to 1 to M is called the  decision region for message m j and R j is the  

set of all outputs of the channel that are mapped  into message m j by the detector. This R js are  

chosen to minimize the probability of error. So, how is this how does the optimum receiver  

set this R js. So, if you are using a map detector  then R js constitute the optimal decision regions  

resulting in the minimum probability of error  and for a map detector this region R k would  

consist of all the points in N dimensional space  such that probability of the message m k given. 

We have observed the vector x is greater  than probability of the message m j,  

given we have observed the vector x for all  j from 1 to m, but j not equal to k correct.

So, for the case of additive white Gaussian  noise channel map decision function is given  

by the following expression and this can be  re-written as argument minimum of this quantity.  

So, for the case where the message  signals are equiprobable this will  

reduce to argument minimum of the norm of the  difference of the vector between x and S j. 

Now, this is the distance of the vector  x from the signal vector S j. So,  

the decision is made in favor of that signal which  is closest to the vector x correct. So, in the  

case of Gaussian noise this is qualitatively  expected because it has a spherical symmetry. 

So, for equiprobable messages the boundary  of say the region R j and R k will be the  

set of points that are equidistance  from two vectors S j and S k which  

implies that it will be the perpendicular  bisector of the line joining the two signal  

points S j and S k right ok. (Refer Slide Time: 06:31)

So, taking a simple case for n equal to 2 and m  equal to 4; If you have equiprobable messages S 1,  

S 2, S 3, S 4 then the decision regions  would be obtained by taking the bisectors  

of the lines joining the signal points. So S 1, S 4 you take the bisector S 1,  

S 2 you take the bisector correct and this  is how you obtain the regions for decision  

region for equiprobable message for n equal  to 2 and m equal to 4. Now, this kind of a  

visualization would become difficult if we have  the dimensionality to be larger than 2 correct  

and this kind of reasoning also will not hold  good when you have non-equiprobable messages. 

So, in that case we can draw some broad  conclusions in the sense that, if a particular  

message m j is more likely than the others it will  be safer in deciding more often in favor of m j. 

So, what will happen that there will be some  kind of a bias of weighted decision regions in  

favor of a particular message signal m j which  has a higher probability correct and this is  

also reflected by the appearance  of the term log of probability of  

m j in the decision function for the AWGN  channel. Now, let us take a simple case to

So, here I show a simple example where I have two  signals S 1 and S 2 and assume that probability  

of message m 1 is same as probability of message  m 2. In this case the decision region basically  

can be found out very easily and it is a line  which is a bisector of the line joining S 1, S 2. 

So, all the points on this side of this line  are region R 1 and all the points of this  

side of the line is R 2. This will not hold  good if the probabilities are unequal. So,  

here I have shown a case where the  probability of message m 2 is higher. So,  

the decision region for R 2 is biased in  the favor of S 2. So, you see that this  

line has got shifted away from the center of  the line joining S 1 and S 2 towards S 1. So,  

this region has become larger; that  is R 2 region has become larger ok. 

So, let us try to formally analyze this example  and see where this line perpendicular line will  

prove that this a perpendicular line  located in the signal space. Now,  

we will use this relation sorry. (Refer Slide Time: 10:12)

We will use this decision function  to partition the signal space in  

two regions R 1 and R 2 and  this will be done as follows.

So, without loss of generality our decision will  be equal to m 1 if this condition is satisfied.  

Now, this basically is nothing, but the  distance of vector x from S 1 square of it. 

So, let me denote this as a d 1 square  and this is d 2 squared correct. So,  

if this condition is not satisfied if  it is greater than you will it will  

be m hat will be m 2 ok. Therefore,  from this we get this relationship. 

So, we can say that the decision rule is equal to  m 1; if this is less than this quantity for given  

P m 1 and P m 2 is a constant and let me call that  constant to be equal to c. This is equal to m 2;  

if d 1 square minus d 2 square is greater  than c and if it is equal we will toss  

a coin and randomly decide the decision. . So, the boundary of the decision is given  

by this equation d 1 squared minus d 2 squared is  equal to c and we will now show that this boundary  

is given by a straight line perpendicular to  the line joining the two points S 1 and S 2  

and passing through this line at a distance from  point S 1; where mu is given by c plus d squared  

by 2 d which is equal to this expression; where  your d is the distance between point S 1 and S 2.

So, the proof for this follows. So, I have  just redrawn S 1 and S 2 in this figure out  

here. This point S 1 and S 2 and now if you  take any line perpendicular to this line S 1,  

S 2 joining it correct, any point on it  and let me indicate this is a point and  

let the distance be alpha from this line. Then, I can write the relationship between d  

1 alpha mu d minus mu correct as follows. So,  from this it is very clear that d 1 squared  

is equal to alpha squared plus mu squared  and d 2 squared is equal to alpha squared  

plus d minus mu whole squared. So, if you take the difference  

between the two I get it as 2 d mu minus d  squared; which is a constant correct. So,  

it implies that this constant is equal to your  c correct because this is the constant which I  

get from my decision function correct. So, and  from this I get my value of mu to be equal to  

c plus d square by 2 d and plugging in the  value of c; I get it as this quantity which  

was the desired result to be proved correct. So the boundary, boundary is a straight line  

perpendicular to the line joining S 1 and  S 2 and passing through the line joining S  

1 and S 2 at a distance which is this is  a distance mu from S 1 and that mu which  

I have indicated here correct; same is  equal to given by this quantity fine. So,  

now, if you have N dimensional signal space  then your R js will be also N dimensional,  

but corresponding to m messages  you will have m regions correct.

So, if you were to calculate the  probability of error then what  

we would be required is to calculate the  probability of correct decision given that  

I have transmitted the message m j correct. So, this is the probability that your vector  

x belongs to the region R j correct. So,  the unconditional probability of correct  

detection would be equal to the summation of the  conditional probabilities and the probability of  

error would be equal to 1 minus probability  of correct detection. So, given the decision  

regions it would be easier for us to calculate  this kind of probability of errors correct. 

So, let us take another example to show you  how to calculate this probability of error.

Let us consider that I have an AWGN channel  and the noise is zero mean with power spectral  

given by italic N by 2. We assume that  we have two messages to be transmitted  

m 1 and m 2 and we use the message signal  as S 1 t and S 2 t for this messages m 1  

and m 2 and the message signals are related  like this; that means, they are basically  

antipodal and this a non-equiprobable case. The goal is to find the optimum receiver  

and for that optimum receiver find the  corresponding probability of error fine.

So, the solution follows. It is simple to realize  that in this case it is a 1-dimensional signal  

space. So, I need only 1 basis signal let  that basis signal be phi 1 t equal to S 2  

t normalized by the energy of S 2 t which I  call it E. In this case the energy for both  

the signal S 1 t and S 2 t is same which is  equal to E. So, for the implementation point  

of view I can just use this block schematic.  Let me implement using it match filter. 

So, I will have a match filter corresponding  to the basis signal; this is my signal received  

x t then I need to sample it because I am  using a match filter sample it exactly at  

t equal to capital T and then I can put it  to a threshold device and get the output. 

And here basically we have this problem basically  is very similar to what we have discussed earlier.  

So, let me just show you the how the two signals  will look geometrically in the vector space.

So I have S 1, I have S 2; let me in indicate  this as a origin so, this is located. So,  

I require only 1 basis signal phi 1 t. So, this  will be root E this point will be minus root E.  

Let me indicate this distance to be mu this  is the partition which I am going to form. 

We have just studied that because the  probabilities are unequal and I have drawn this  

assuming that probability of m 2 is larger than  probability of m 1. So, let me indicate this mu  

this distance is d between the two signal points.  So, this is equal to d minus mu distance correct. 

Now, this problem is very similar to what we  did earlier. So, we can calculate quickly what  

is the value of mu; So, in d in this case is  going to be 2 root E, mu is going to be italic  

N by 2 log of P m 1 by P m 2. (Refer Slide Time: 22:30)

So, now, probability of correct decision is the  probability the vector x lies in region R 1. So,  

remember this is our all this  side is region R 1 and this  

side it is going to be region R 2 correct. So, now, we assume the noise to be Gaussian. So,  

we are without loss of generality let us assume  that we have transmitted message m 1. So,  

this being your center the noise is going to be  distributed in a Gaussian shape around this. So,  

what you should do is basically, if  you want correct decision the noise  

should not be that large that point  lands up here; vector x correct. So,  

your vector x should be lying only in  this region R 1 correct. So, this can be  

easily calculate I want to find out what is the  probability of my vector x lying in this region. 

So, assuming Gaussian distribution for  the noise I have to calculate this so,  

this means basically what is the probability  of my noise being less than mu. Here when I am  

writing this is assume that noise origin is at S 1  fine. So, this I can write it as assuming Gaussian  

distribution to be pdf of my noise 2 pi there is  a sigma n squared is a variance of the noise e  

raised to minus say x sorry. I will write it as a  beta squared 2; I have to integrate this quantity.

Now, this quantity I can rewrite it as  

now, if I define a Q function of this form then  probability of correct decision given m 1 is equal  

to 1 minus Q times mu by sigma n correct. Let  us just change your variables we can show this. 

Now, this is the square root of the  variance. So, variance for the noise  

in our case is going to be it is projected  on the basis signal with unit energy. So,  

this will be equal to italic N by 2 because  the energy in the impulse response which is  

equivalent to the basis signal is equal  to 1 fine. So, I get this quantity.

So, from this using this I get my probability  of correct detection given message m 1 is equal  

to 1 minus Q times mu root of italic N  by 2 correct. So, this is what I get. 

Now, so similarly you can find out what is the  probability of correct detection given m 2;  

there the only the distance will  change. It will become d minus mu  

rest of the things will remain the same;  I will get this quantity and then I can  

write what is the probability  of correct detection right.

So, if I do this basically I get this probability  of correct detection it is a unconditional  

probability. I just plug in the values which  I have just recently calculated and I expand  

it I get and then knowing that probability  of m 1 and probability of m 2 is equal to  

1. I get equal to this quantity and this  can be simplified and rewritten like this. 

Now, if you assume that both the probabilities  are equal then in that case your mu will  

be equal to d by 2 and the probability of  error will turn out to be this expression;  

just plug in these values out there  and it is not very difficult to show  

that this is what I am going to get correct. So, for the simple case I have shown you what  

is the optimum receiver and that is done by  partitioning the signal space in two regions.  

Once I have done that it becomes easier for  me to visualize and write the probability  

of correct detection and from there I can  find out what is the probability of error. 

But if the dimension of the signal space is  very high then this kind of visualization  

may be very difficult and calculating the  probability of error may be non-trivial task. 

We will discuss this in the next class. Thank you.