3
$\begingroup$

How do you draw decision boundaries given this type of 16-qam constellation diagram16-QAM, I know that there should be no vacant decision boundary but I can't seem to get it.Also, assuming that the correct decision boundary is drawn, how do you derive its total probability of error, if we let the SNR ratios of all symbols are equal?

$\endgroup$
  • $\begingroup$ In practice you would compute an approximation to the symbol error probability using the union bound. This bound becomes tight at large SNRs. $\endgroup$ – Matt L. Apr 5 '17 at 7:28
7
$\begingroup$

The optimal decision regions are the Voronoi Regions. I dont know, if this is what you are looking after.

import numpy as np

points = np.array([(1,1), (1,-1), (-1,1), (-1,-1), (3,3), (3,0), (3,-3), (0,-3), (-3,-3), (-3,0), (-3,3), (0,3), (5,0), (0,5), (-5,0), (0,-5)])
from scipy.spatial import Voronoi, voronoi_plot_2d
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.axis('equal'); plt.xlim((-7,7)); plt.ylim((-7,7));

enter image description here

I actually, consider analytically calculating the error probability of this constellation a very hard task, since the regions are not very regular.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ @MarcusMüller me too, but a quick search for "python voronoi" gives you this example, which you just need to adapt. I agree, doing it numerically is doable, but it might be actually out of scope of a lecture on digital communications (it's more about numeric math I guess). So, maybe the OP is missing something in the description. I actually doubt that there would be a closed-form solution to this problem, since you'd need to integrate over error functions (dont know, if they can be solved in closed form). $\endgroup$ – Maximilian Matthé Apr 5 '17 at 6:41
  • 1
    $\begingroup$ Let's wait for the OP to clarify :-) $\endgroup$ – Maximilian Matthé Apr 5 '17 at 6:45
  • 2
    $\begingroup$ @MarcusMüller: It's the 30 year old ITU-T V.29 modem standard for data transmission at 9600 b/s: link $\endgroup$ – Matt L. Apr 5 '17 at 7:14
  • 1
    $\begingroup$ @MattL. :) please tell me you found that by reverse image search or some other trick rather than knowing that by heart! Awesome! $\endgroup$ – Marcus Müller Apr 5 '17 at 7:16
  • 1
    $\begingroup$ ah, yeah, makes a lot of sense, this is really more of a Phase/amplitude than a QAM. So, ease of impl based on phase discriminators, with little care about optimum decision lines was probably more important during design $\endgroup$ – Marcus Müller Apr 5 '17 at 7:18
7
$\begingroup$

As explained in Maximilian Matthé's answer, the exact computation of the symbol error probability of this constellation (ITU-T V.29 modem standard) is quite complex. However, you can quite easily compute an approximation which becomes very good for relatively large signal to noise ratios (SNRs). This approximation is based on the union bound.

The symbol error probability is given by

$$P_S=\sum_{i=1}^MP[a_i]P[\text{error}|a_i]\tag{1}$$

where $M$ is the number of symbols, $P[a_i]$ is the probability that symbol $a_i$ is sent, and $P[\text{error}|a_i]$ is the error probability given that symbol $a_i$ was sent. This latter probability can be bound by the union bound:

$$P[\text{error}|a_i]\le\sum_{j=1\\j\neq i}^MQ\left(\frac{d_{ij}}{2\sigma}\right)\tag{2}$$

where $Q(\cdot)$ is the Q-function (assuming Gaussian noise), $d_{ij}$ is the distance between symbols $a_i$ and $a_j$, and $\sigma^2$ is the noise variance.

For large SNRs, the sum in $(2)$ is dominated by the term with the smallest value of $d_{ij}=d_{i,\text{min}}$, so we can write

$$P[\text{error}|a_i]\approx k_iQ\left(\frac{d_{i,\text{min}}}{2\sigma}\right)\tag{3}$$

where $k_i$ is the number of symbols with minimum distance $d_{i,\text{min}}$ from symbol $a_i$. Using this approximation in $(1)$, and assuming equally likely symbols (i.e., $P[a_i]=1/M$), we obtain the approximation

$$P_S\approx\frac{1}{M}\sum_{i=1}^{M}k_iQ\left(\frac{d_{i,\text{min}}}{2\sigma}\right)\tag{4}$$

Applying this formula to the given constellation works as follows. There are four groups of symbols with increasing distance from the origin. The first group (the one closest to the origin) has two nearest neighbors with distance $2$. The second group has one nearest neighbor with distance $2$. The third group has one nearest neighbor with distance $2\sqrt{3}-\sqrt{2}$, and the last group (furthest from the origin) has one nearest neighbor with distance $2$. This results in

$$\begin{align}P_S&\approx \frac14 2Q\left(\frac{1}{\sigma}\right)+\frac14 Q\left(\frac{1}{\sigma}\right)+\frac14 Q\left(\frac{2\sqrt{3}-\sqrt{2}}{2\sigma}\right)+\frac14 Q\left(\frac{1}{\sigma}\right)\\&=Q\left(\frac{1}{\sigma}\right)+\frac14 Q\left(\frac{2\sqrt{3}-\sqrt{2}}{2\sigma}\right)\tag{5}\end{align}$$

$\endgroup$
  • $\begingroup$ Thank you for the answer guys! This attracted new ideas, Im impressed. IM basing the probability of error based on (1-X), where X is the Q function of the sqrt of the SNR. If we take the probability of correct region of the very left symbol from origin, its probability of error is (1-X) since if its gonna move in the x-axis region, it will only affect one symbol (to the right of it). How do I compute the other symbols, given that they are enclosed in a pentagon like boundary? $\endgroup$ – LeBlanc Lord Apr 5 '17 at 10:40
  • $\begingroup$ Nice! Also, $\frac{2\sqrt 3-\sqrt2}2$ is "pretty close" to $1$, so $Q\left(\frac1\sigma\right)\approx Q\left(\frac{2\sqrt 3-\sqrt2}{2\sigma}\right)$, and we can, even more roughly estimate $P_S\approx\frac54Q\left(\frac1\sigma\right)$. $\endgroup$ – Marcus Müller Apr 5 '17 at 10:41
  • $\begingroup$ What should be noted is that if my head-computing skills don't fail me, this constellations has average power of $$\frac{5^2+(2\sqrt3)^2+3^2+\sqrt2^2}{4}=13.25\text.$$ A "usual" orthogonal 16QAM with the same average energy would have its "outermost" (read: peak power) constellation points on a circle with radius ummm 3.1something, I think? It would be worth comparing the symbol error probability of that one with this 16ary phase/amplitude modulation from V.29. $\endgroup$ – Marcus Müller Apr 5 '17 at 10:50
  • $\begingroup$ @LeBlancLord to cite Matt and Maximilian: "it's very hard". It's really very hard to find analytic terms for Q function integrated over non-rectangular/-circular shapes. You usually simply can't, and need to resort to good bounds (which is what Matt explained in breadth) or to numerical integration (which really demands a good understanding on the error bounds of that). So: sorry, I doubt we'll be able to help you finding the exact probabilities for the non-trivial constellation points, as we've all been pointing out. $\endgroup$ – Marcus Müller Apr 5 '17 at 10:54
  • $\begingroup$ Is the average symbol energy of this 16-qam the same as the usual orthogonal 16 qam? Also, if that is very hard, is there any way to derive its general formula for the total probability of error, i mean not the exact value, just the formula? for the symbols enclosed in a pentagon, can I estimate its probability of error by looking at the symbols at its adjacent sides? (5 sides) $\endgroup$ – LeBlanc Lord Apr 5 '17 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.