A formula for computing low symbol error rates

This paper considers the error probability when $M$ mutually orthogonal signals are transmitted with equal likelihood and equal power, and received by a bank of $M$ correlators at the receiver. The analysis requires that the channel be memoryless and have the property that the maximum likelihood symbol decision is the result of identifying the highest correlator output. We are motivated by the desire to calculate the performance of $M$-ary Pulse Position Modulation (PPM) on a Poisson channel, which is a good model for some free space optical communications links [3]. We present an easily computed formula that works at low bit error rates that some applications require.

When the channel has continuous-valued outputs, the probability of incorrectly deciding which of the $M$ signals was sent is well known (see, e.g., [1,2] for the AWGN channel) to be: $P_e = 1 - \int_{-\infty}^\infty p_1(x) \left[ \int_{-\infty}^x p_0(y) dy\right]^{M-1} dx,$ where $p_1(\cdot)$ and $p_0(\cdot)$ are the conditional probability density functions for a correlator output for the transmitted signal or one of the $M-1$ other signals, respectively.

The remainder of the paper considers a discrete-output channel. The probability of symbol error for $M$-ary orthogonal signaling on the Poisson channel is derived in [3,4], and the straightforward generalization of that result to a discrete memoryless channel whose outputs take values from the nonnegative integers is:

$$P_e = 1 -\frac{1}{M}p_0(0)^{M-1}p_1(0) - \sum_{k=1}^\infty p_1(k) P_0(k-1)^{M-1}$$

$$\times\frac{1}{M\frac{p_0(k)}{P_0(k-1)}} \left[\left(1+\frac{p_0(k)}{P_0(k-1)}\right)^M-1\right]$$ (1)

where $p_1(\cdot)$ and $p_0(\cdot)$ are now probability mass functions, and where $P_0(k) = \sum_{m=0}^{k} p_0(m)$ is a cumulative distribution function. (We use the notational convention that if $p_0(k) = 0$, there is no contribution to the sum.) This may be written more simply as

$$P_e = 1-\sum_{k=0}^\infty \frac{p_1(k)}{p_0(k)M} \left(P_0(k)^M-P_0(k-1)^M\right).$$ (2)

Unfortunately, a direct numerical evaluation of either (1) or (2) is difficult when $P_e$ is small, because it involves differences that can be many orders of magnitude smaller than either term. This is problematic when numbers are stored with finite precision, such as with the IEEE 754 floating point standard [5]--a typical program would incorrectly evaluate $1 - (1 - 10^{-30})$ as zero, for example.

Thus, it is helpful to derive a formula for the symbol error rate $P_e$ that does not involve the type of difference present in (1) and (2). This would provide an alternative to the union bound or other upper bound [6] which is typically used when $P_e$ is small . Using $\sum_{k=0}^\infty p_1(k) = 1$, we may rewrite (2) as

$$P_e = \sum_{k=0}^\infty \frac{p_1(k)}{p_0(k)M} \left(p_0(k)M - P_0(k)^M+P_0(k-1)^M\right).$$ (3)

When $P_0(k)$ nearly equals $P_0(k-1)$, or equivalently, $p_0(k)/P_0(k-1)$ is very small, the $k$th term is difficult to calculate in a numerically precise way. We let $f_k = 1-P_0(k-1) = \sum_{m=k}^\infty p_0(m)$ and rewrite the $k$th term as

$$a_k = \frac{p_1(k)}{p_0(k)M} \left[p_0(k)M \right.$$

$$\quad - \left. (P_0(k-1)+p_0(k))^M + P_0(k-1)^M\right]$$

$$= \frac{p_1(k)}{p_0(k)M} \Bigg\{p_0(k)M$$

$$\quad - \left.P_0(k-1)^M\left[\left(1+\frac{p_0(k)}{P_0(k-1)}\right)^M - 1\right]\right\}$$

$$= \frac{p_1(k)}{p_0(k)M} \Bigg(p_0(k)M - P_0(k-1)^M$$

$$\times \left.\left[1 + \frac{p_0(k)M}{P_0(k-1)} +O\left(\left(\frac{p_0(k)}{P_0(k-1)}\right)^2\right) - 1\right]\right)$$ (4)

$$= p_1(k)\left(1-P_0(k-1)^{M-1}\right) + O(p_0(k))$$

$$= p_1(k)\left(1-\left(1-f_k\right)^{M-1}\right) + O(p_0(k))$$

$$= p_1(k)(M-1)f_k + O(p_0(k)+f_k^2)$$ (5)

where in (4) and (5) we used the Taylor series $(1-x)^M = 1 - Mx + O(x^2)$. (5) becomes accurate as $k\rightarrow\infty$, since $p_0(k)\rightarrow 0$ and $f_k\rightarrow 0$. This leads to the main result of the paper, which we now state.

The probability of symbol error is given by

$$P_e = \sum_{k=0}^{N} p_1(k) \left(1 - \frac{P_0(k)^M-P_0(k-1)^M}{p_0(k)M}\right)$$

$$+ \sum_{k=N+1}^\infty p_1(k)(M-1)f_k + O(p_0(k)+f_k^2))$$ (6)

and $N$ may be freely chosen to minimize the total computational error due to numerical imprecision in the first summation and due to the Taylor series remainder error in the second summation. Note that when $N=0$, the second summation is simply a union bound.