Bounds on Probability of Error

# Introduction

Proability of Error Pe is not easy to compute in many cases.In such situations we resort to bounds.In this topic we will discuss in detail various few naive bounds and fairly good approximation of the probability of error. In all the discussions in this topic, we determine the probability of error assuming a single symbol being transmitted.

(1)
\begin{align} P_e=\sum_{m} P_{e|m}P_m \end{align}

Caluculating Pe|m is a tedious task in many cases, as the decision regions may not be easy to integrate over. In such cases Probability of error is either approximated or bounds are determined. we approximate the probability using some standard functions. The most widely used function in AWGN channel for approximation is the Q-function.

For a gaussian random variable X, The tail probability by, P(X>x0) is given by Q-function as,

(2)
\begin{eqnarray} P(X>x_0)=Q \left( \frac{x_0-\mu}{\sigma} \right) \\ Q(x)=1-Q(-x) \end{eqnarray}

# Probability of Error for Binary Antipodal Signalling

Consider two signals, s1(t), s2(t), such that

(3)
\begin{eqnarray} s_1(t)=-s_2(t) &=& \sqrt{\frac{2E_s}{T}}\sin(2\pi f_0 t ) \hspace{4mm}0\leqt<T\\ &=& \hspace{5mm}0 \hspace{20mm} \mbox{otherwise} \end{eqnarray}

The received signal r(t) = sm(t) + n(t), the vector recieved at the receivor is therefore,

(4)
\begin{align} r=\int_{0}^{T} r(t) \sqrt{\frac{2}{T}}sin(2\pi f_0 t) dt = \underline{+}\sqrt{E_s} + n \end{align}

The probability of error Pe is derived from Pe|1 and Pe|2 ,where

(5)
\begin{eqnarray} P_{e|1} &=& \int_{-\infty}^{0} P_r(r|1)dr_1 = \int_{-\infty}^{0} N(1, \sigma^2) dr_1 \\ &=& P(r<0) \hspace{5mm} \mbox{when } r\sim N(\sqrt{E_s},\sigma^2) \\ &=& P(-r>0) \hspace{5mm} \mbox{when } -r\sim N(-\sqrt{E_s},\sigma^2) \end{eqnarray}

Hence

(6)
\begin{align} P_{e|1}= Q \left( \sqrt{\frac{E_s}{\sigma^2}} \right)=Q \left( \sqrt{\frac{2E_s}{N_0}} \right) \end{align}

By symmetry we have, Pe|2 = Pe|1. Therefore, $P_e = Q \left( \sqrt{\frac{2E_s}{N_0}} \right)$

# Invariance of Probability of error to Translation

In a vector channel, r = sm + n.

(7)
\begin{align} P(\underline{r}|\underline{s}_m)= P_{\underline{n}}(\underline{r} -\underline{s}_m) \end{align}

Consider translation of the constalletion such that r' = r - ro = sm- ro + n. Let sm' = sm- ro.

(8)
\begin{eqnarray} P(\underline{r}'|\underline{s}_m')&=& P_{\underline{n}}(\underline{r}' -\underline{s}_m') \\ &=& P(\underline{r}|\underline{s}_m) \end{eqnarray}

# Inavriance of Probability of error to Rotation

Suppose T is a rotation matrix and r = sm + n.

(9)
\begin{eqnarray} \underline{r}'&=& T\underline{r}=T\underline{s}_m + T\underline{n}\\ &=& \underline{s}_m' + \underline{n}' \end{eqnarray}

We know that T is an orthogonal matrix, Therefore Cn= Cn' = I. Hence, we conclude that the probability of error is invariant to rotation.

# Error probability for any two Equiprobable Signals

(10)
\begin{align} P_{e|1}= P\left[ \frac{\underline{n}.(\underline{s}_1 - \underline{s}_2)}{d_{12}}> \frac{d_{12}}{2} \right]= P \left[ \underline{n}.(\underline{s}_1 - \underline{s}_2) > \frac{d_{12}^2}{2} \right] \end{align}

Fact: $\underline{n}.(\underline{s}_1 - \underline{s}_2) \sim N(0,\sigma^2 \|\underline{s}_1 - \underline{s}_2)\|^2)$

(11)
\begin{align} p_{e|1}= Q \left(\sqrt{\frac{d_{12}^2}{4\sigma^2} \right) ,\hspace{5mm} \sigma^2 = \frac{N_0}{2} \end{align}
(12)
\begin{align} P(\mbox{ error }) = Q \left( \sqrt{\frac{d_{12}^2}{2N_0} \right) \end{align}

Notice that the above derived expression also works when s1 and s2 are complex and $\sigma^2$ is the noise variance in each real and comlex dimension.

Example: Binary orthogonal Signals

# Bounds on the Probability of error

In the above figure, integrating over the decision regions for computing Probability of error is not easy. Therefore, we determine bounds on Pe. In the following discussion we compute upper bound and later determine lower bound on the probability of error. Consider the figure depicted above. We make use of the union bound of probability in obtaining the upper bound of the Probability of error. Let Dm' denote the decision region for the mth signal.

(13)
\begin{align} D_{m'}= \{\underline{r} | P(\underline{r}|\underline{s}_{m'}) > P (\underline{r}|\underline{s}_{k}) \} \hspace{3mm} \forall \mbox{ } k \not= m'\} \end{align}

Let Dmm' be the region such that detector makes a decision in favour of sm' when sm is transmitted.

(14)
\begin{align} D_{mm'}= \{\underline{r} | P(\underline{r}|\underline{s}_{m'}) > P (\underline{r}|\underline{s}_{m}) \} \end{align}
(15)
\begin{align} P_{mm'}= P(\underline{r} \in D_{mm'} | \underline{s}_m \mbox{ is transmitted}) \end{align}
(16)
\begin{align} P_{e|m} = P \left( r\in \bigcup_{m' \not= m} D_{mm'} \right) \leq \sum_{m'} P(r\in D_{mm'}) = \sum_{m'}P_{mm'} \end{align}

Pmm' is called Pairwise error probability.

(17)
\begin{align} P_{mm'}= Q \left( \sqrt{\frac{d_{mm'}^2}{2N_0}} \right) \end{align}

For equally likely signals,

(18)
\begin{eqnarray} P_e &\leq& \frac{1}{M} \sum _{m}\sum_{m'\not=m} Q\left( \sqrt{\frac{d_{mm'}^2}{2N_0}} \right) \\ &\leq& \frac{1}{2M}\sum _{m}\sum_{m'\not=m} e^{\frac{d_{mm'}^2}{4N_0}} \end{eqnarray}

Let T(x) be the distance enumerator for the constellation,

(19)
\begin{align} T(x)= \sum a_{d}x^{d^2} \end{align}

where ad denotes the number of ordered pairs such that m' not equal to m and dmm'=d

(20)
\begin{align} P_e \leq \frac{1}{2M} \left T(x) \right|_{x= e^{\frac{1}{-4N_0}}} \end{align}

we compute a loose upper bound interms of the minimum distance of the constellation,

(21)
\begin{eqnarray} d_{min}^m &=& \min_{m'}\|\underline{s}_m - \underline{s}_m' \| \\ d_{min} &=& \min_{m} d_{min}^m} \end{eqnarray}

Therefore the Inequality in equation (19) can be modified as,

(22)
\begin{eqnarray} P_e &\leq& \frac{1}{M}\sum_{m} (M-1) Q \left( \sqrt{\frac{d_{min}^{m 2}}{2N_0}} \right)\\ P_e &\leq& (M-1)Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right) \end{eqnarray}

This is known as a Naive Union bound.
Now we compute the lower bound.

(23)
\begin{align} P_{e|m}= p \left( \underline{r} \in \bigcup_{m'} D_{mm'} \right) &\geq& \max_{m'} P(\underline(r) \in D_{mm'}) &=& Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right) \end{align}

Therefore,

(24)
\begin{align} P_e \geq \frac{1}{M} \sum Q\left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right) \end{align}

We can further weaken the lower bound by considering only those signals for which there is aleast one other signal at a distance of dmin. Suppose there are Nmin of them,

(25)
\begin{align} P_e \geq \frac{N_{min}}{M} \sum Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right) \end{align}

The following table summarizes the entire discussion in the above section.

 Union bound $P_e \leq \frac{1}{2M} \left T(x) \right|_{x= e^{\frac{1}{-4N_0}}$ Naive union bound $P_e &\leq& (M-1) Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right)$ Lower bound $P_e \geq \frac{1}{M} \sum Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right)$ Weak lower bound $P_e \geq \frac{N_{min}}{M} \sum Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right)$

# probability of error for Amplitude shift Keying

In the above figure dmin= d. For inner points,

(26)
\begin{align} P_{ei}= P \left[ |n|>\frac{1}{2}d_{min} \right] = Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right) \end{align}

Probabililty of error for the outer points is equal to half of the probability of errror for any of the inner points. Therefore,

(27)
\begin{align} P_{eo}=\frac{1}{2}P_{ei} = Q \left( \sqrt{\frac{d_{min}^{2}}{2N_0}} \right) \end{align}

From the previous topics we have $d_{min}^2= \left( \frac{12\log_{2}M}{M^2 -1} \right) E_{bavg}$

(28)
\begin{align} P_e = 2 \left(1-\frac{1}{M} \right) Q \left( \sqrt{\frac{6\log_{2}M}{M^2 -1}\frac{E_{bavg}}{N_0}} \right) \end{align}

# Probability of error for M-ary PSK

(29)
\begin{align} P(\mbox{ error }|s_1)= Q \left( \sqrt{\frac{E_s}{\sigma^2}} \right) + 2\frac{1}{\sqrt{2\pi}} \int_{0}^{\infty} Q \left (z\tan\beta \right) e^ {\frac {-(z-\sqrt{\frac{E_s}{\sigma^2}})^2}{2}}dz \end{align}

Where $\beta = \frac{\pi}{M}$.

(30)
\begin{align} P_e \approx N_m Q \left( \sqrt{\frac{2E_b}{N_0}\log_2 M \sin^2 \left( \frac{\pi}{M}}\right) \right) \end{align}

Where Nm =1 when M=2 and Nm=2 for M>2.

# Probability of error for M-QAM

(31)
\begin{eqnarray} P_{c,M-QAM} &=& P_{c,\sqrt{M}-PAM} = \left( 1-P_{e,{\sqrt{M}-PAM} \right)^2 \\ P_{e,M-QAM} &=& 1-\left[1-2 \left(1-\frac{1}{\sqrt{M}} \right) Q \left( \sqrt{\frac{3\log_{2}M}{M -1}\frac{E_{bavg}}{N_0}}\right) \right] \\ &\leq& 4Q\left( \sqrt{\frac{3\log_{2}M}{M -1}\frac{E_{bavg}}{N_0}} \right) \end{eqnarray}

page revision: 17, last edited: 07 Jun 2010 17:24