Performance of Small Signal Sets

Chapter 5 Performance of small signal sets In this chapter, we show how to estimate the performance of small-to-moderate-sized signal constellations on the discrete-time AWGN channel. With equiprobable signal points in iid Gaussian noise, the optimum decision rule is a minimumdistance rule, so the optimum decision regions are minimum-distance (Voronoi) regions. We develop useful performance estimates for the error probability based on the union bound. These are based on exact expressions for pairwise error probabilities, which involve the Gaussian probability of error Q(·) function. An appendix develops the main properties of this function. Finally, we use the union bound estimate to find the “coding gain” of small-to-moderatesized signal constellations in the power-limited and bandwidth-limited regimes, compared to the 2-PAM or (M × M )-QAM baselines, respectively. 5.1 Signal constellations for the AWGN channel In general, a coding scheme for the discrete-time AWGN channel model Y = X + N is a method of mapping an input bit sequence into a transmitted real symbol sequence x, which is called encoding, and a method for mapping a received real symbol sequence y into an estimated transmitted signal sequence x̂, which is called decoding. Initially we will consider coding schemes of the type considered by Shannon, namely block codes with a fixed block length N . With such codes, the transmitted sequence x consists of a sequence (. . . , xk , xk+1 , . . .) of N -tuples xk ∈ RN that are chosen independently from some block code of length N with M codewords. Block codes are not the only possible kinds of coding schemes, as we will see when we study convolutional and trellis codes. Usually the number M of codewords is chosen to be a power of 2, and codewords are chosen by some encoding map from blocks of log2 M bits in the input bit sequence. If the input bit sequence is assumed to be an iid random sequence of equiprobable bits, then the transmitted sequence will be an iid random sequence X = (. . . , Xk , Xk+1 , . . .) of equiprobable random codewords Xk . We almost always assume equiprobability, because this is a worst-case (minimax) assumption. Also, the bit sequence produced by an efficient source coder must statistically resemble an iid equiprobable bit sequence. In digital communications, we usually focus entirely on the code, and do not care what encoding map is used from bits to codewords. In other contexts the encoding map is also important; e.g., in the “Morse code” of telegraphy. If the block length N and the number of codewords M are relatively small, then a block code for the AWGN channel may alternatively be called a signal set, signal constellation, or signal alphabet. A scheme in which the block length N is 1 or 2, corresponding to a single signaling interval of PAM or QAM, may be regarded as an “uncoded” scheme. Figure 1 illustrates some 1-dimensional and 2-dimensional signal constellations. r3 r1 r −1 r −1 r r 1 r r1 r −1 r −3 (a) (b) (c) r r r r r r −3 −1 r r r 1 r r 3 r r r r r √ 2 3 √ r r r r 3 −2.r5−0.r5 1.r5 3.r5 √ r r r r− 3 √ r r −2 3 (d) r r (e) Figure 1. Uncoded signal constellations: (a) 2-PAM; (b) (2 × 2)-QAM; (c) 4-PAM; (d) (4 × 4)-QAM; (e) hexagonal 16-QAM. An N -dimensional signal constellation (set, alphabet) will be denoted by A = {aj , 1 ≤ j ≤ M }. Its M elements aj ∈ RN will be called signal points (vectors, N -tuples). The basic parameters of a signal constellation A = {aj , 1 ≤ j ≤ M } are its dimension N ; its 1 � 2 size M (number of signal points); its average energy E(A) = M j ||aj || ; and its minimum squared distance d2min (A), which is an elementary measure of its noise resistance. A secondary parameter is the average number Kmin (A) of nearest neighbors (points at distance dmin (A)). From these basic parameters we can derive such parameters as: • The bit rate (nominal spectral efficiency) ρ = (2/N ) log2 M b/2D; • The average energy per two dimensions Es = (2/N )E(A), or the average energy per bit Eb = E(A)/(log2 M ) = Es /ρ; • Energy-normalized figures of merit such as d2min (A)/E(A), d2min (A)/Es or d2min (A)/Eb , which are independent of scale. For example, in Figure 1, the bit rate (nominal spectral efficiency) of the 2-PAM and (2 × 2)QAM constellations is ρ = 2 b/2D, whereas for the other three constellations it is ρ = 4 b/2D. The average energy per two dimensions of the 2-PAM and (2 × 2)-QAM constellations is Es = 2, whereas for the 4-PAM and (4 × 4)-QAM constellations it is Es = 10, and for the hexagonal 16-QAM constellation it is Es = 8.75. For all constellations, d2min = 4. The average numbers of nearest neighbors are Kmin = 1, 2, 1.5, 3, and 4.125, respectively. 5.1.1 Cartesian-product constellations Some of these relations are explained by the fact that an (M × M )-QAM constellation is the Cartesian product of two M -PAM constellations. In general, a Cartesian-product constellation AK is the set of all sequences of K points from an elementary constellation A; i.e., AK = {(x1 , x2 , . . . , xK ) | xk ∈ A}. If the dimension and size of A are N and M , respectively, then the dimension of A
= AK is N
= KN and its size is M
= M K . Exercise 1 (Cartesian-product constellations). (a) Show that if A
= AK , then the parameters N, log2 M, E(A
) and Kmin (A
) of A
are K times as large as the corresponding parameters of A, whereas the normalized parameters ρ, Es , Eb and d2min (A) are the same as those of A. Verify that these relations hold for the (M × M )-QAM constellations of Figure 1. Notice that there is no difference between a random input sequence X with elements from A and a sequence X with elements from a Cartesian-product constellation AK . For example, there is no difference between a random M -PAM sequence and a random (M × M )-QAM sequence. Thus Cartesian-product constellations capture in a non-statistical way the idea of independent transmissions. We thus may regard a Cartesian-product constellation AK as equivalent to (or a “version” of) the elementary constellation A. In particular, it has the same ρ, Es , Eb and d2min . We may further define a “code over A” as a subset C ⊂ AK of a Cartesian-product constellation AK . In general, a code C over A will have a lower bit rate (nominal spectral efficiency) ρ than A, but a higher minimum squared distance d2min . Via this tradeoff, we hope to achieve a “coding gain.” Practically all of the codes that we will consider in later chapters will be of this type. 5.1.2 Minimum-distance decoding Again, a decoding scheme is a method for mapping the received sequence into an estimate of the transmitted signal sequence. (Sometimes the decoder does more than this, but this definition will do for a start.) If the encoding scheme is a block scheme, then it is plausible that the receiver should decode block-by-block as well. That there is no loss of optimality in block-by-block decoding can be shown from the theorem of irrelevance, or alternatively by an extension of the exercise involving Cartesian-product constellations at the end of this subsection. We will now recapitulate how for block-by-block decoding, with equiprobable signals and iid Gaussian noise, the optimum decision rule is a minimum-distance (MD) rule. For block-by-block decoding, the channel model is Y = X + N, where all sequences are N tuples. The transmitted sequence X is chosen equiprobably from the M N -tuples aj in a signal constellation A. The noise pdf is pN (n) = 1 2 2 e−||n|| /2σ , N/2 2 (2πσ ) where the symbol variance is σ 2 = N0 /2. In digital communications, we are usually interested in the minimum-probability-of-error (MPE) decision rule: given a received vector y, choose the signal point â ∈ A to minimize the probability of decision error Pr(E). ˆ is correct is simply the a posteriori probability p(ˆ Since the probability that a decision a a | y), the MPE rule is equivalent to the maximum-a-posteriori-probability (MAP) rule: choose the ˆ ∈ A such that p(ˆ a a | y) is maximum among all p(aj | y), aj ∈ A. By Bayes’ law, p(y | aj )p(aj ) . p(y) If the signals aj are equiprobable, so p(aj ) = 1/M for all j, then the MAP rule is equivalent to ˆ ∈ A such that p(y | a) ˆ is maximum among all the maximum-likelihood (ML) rule: choose the a p(y | aj ), aj ∈ A. p(aj | y) = Using the noise pdf, we can write p(y | aj ) = pN (y − aj ) = 1 2 2 e−||y−aj || /2σ . N/2 2 (2πσ ) Therefore the ML rule is equivalent to the minimum-distance (MD) rule: choose the â ∈ A such that ||y − â||2 is minimum among all ||y − aj ||2 , aj ∈ A. In summary, under the assumption of equiprobable inputs and iid Gaussian noise, the MPE rule is the minimum-distance rule. Therefore from this point forward we consider only MD detection, which is easy to understand from a geometrical point of view. Exercise 1 (Cartesian-product constellations, cont.). (b) Show that if the signal constellation is a Cartesian product AK , then MD detection can be performed by performing independent MD detection on each of the K components of the received KN -tuple y = (y1 , y2 , . . . , yK ). Using this result, sketch the decision regions of the (4 × 4)-QAM signal set of Figure 1(d). (c) Show that if Pr(E) is the probability of error for MD detection of A, then the probability of error for MD detection of A
is Pr(E)
= 1 − (1 − Pr(E))K , Show that Pr(E)
≈ K Pr(E) if Pr(E) is small. Example 1. The K-fold Cartesian product A
= AK of a 2-PAM signal set A = {±α} corresponds to independent transmission of K bits using 2-PAM. Geometrically, A
is the vertex set of a K-cube of side 2α. For example, for K = 2, A
is the (2 × 2)-QAM constellation of Figure 1(b). From Exercise 1(a), the K-cube constellation A
= AK has dimension N
= K, size M
= 2K , bit rate (nominal spectral efficiency) ρ = 2 b/2D, average energy E(A
) = Kα2 , average energy per bit Eb = α2 , minimum squared distance d2min (A
) = 4α2 , and average number of nearest
(A
) = K. From Exercise 1(c), its probability of error is approximately K times neighbors Kmin the single-bit error probability: � �� 2Eb /N0 . Pr(E)
≈ KQ Consequently, if we define the probability of error per bit as Pb (E) = Pr(E)
/K , then we obtain the curve of (4.3) for all K-cube constellations: � �� 2Eb /N0 , Pb (E) ≈ Q including the (2 × 2)-QAM constellation of Figure 1(b). A code over the 2-PAM signal set A is thus simply a subset of the vertices of a K-cube. 5.1.3 Decision regions Under a minimum-distance (MD) decision rule, real N -space RN is partitioned into M decision regions Rj , 1 ≤ j ≤ M , where Rj consists of the received vectors y ∈ RN that are at least as close to aj as to any other point in A: Rj = {y ∈ RN : ||y − aj ||2 ≤ ||y − aj
||2 for all j
= j}. (5.1) The minimum-distance regions Rj are also called Voronoi regions. Under the MD rule, given a received sequence y, the decision is aj only if y ∈ Rj . The decision regions Rj cover all of N -space RN , and are disjoint except on their boundaries. Since the noise vector N is a continuous random vector, the probability that y will actually fall precisely on the boundary of Rj is zero, so in that case it does not matter which decision is made. The decision region Rj is the intersection of the M − 1 pairwise decision regions Rjj
defined by Rjj
= {y ∈ RN : ||y − aj ||2 ≤ ||y − aj
||2 }. Geometrically, it is obvious that Rjj
is the half-space containing aj that is bounded by the perpendicular bisector hyperplane Hjj
between aj and aj
, as shown in Figure 2. 6 aj
|aj
−aj r y|aj
−aj = m|aj
−aj r aj|aj
−aj r aj
6 m y Hjj
'$  aj  &% - Figure 2. The boundary hyperplane Hjj
is the perpendicular bisector between aj and aj
. Algebraically, since Hjj
is the set of points in RN that are equidistant from aj and aj
, it is characterized by the following equivalent equations: ||y − aj ||2 = ||y − aj
||2 ; −2y, aj  + ||aj ||2 = −2y, aj
 + ||aj
||2 ; aj + aj
, aj
− aj  = m, aj
− aj . (5.2) y, aj
− aj  =  2 where m denotes the midvector m = (aj + aj
)/2. If the difference vector between aj
and aj is aj
− aj and aj
− aj φj→j
= ||aj
− aj || is the normalized difference vector, so that ||φj→j
||2 = 1, then the projection of any vector x onto the difference vector aj
− aj is x|aj
−aj = x, φj→j
φj→j
= x, aj
− aj  (aj
− aj ). ||aj
− aj ||2 The geometric meaning of Equation (5.2) is thus that y ∈ Hjj
if and only if the projection y|aj
−aj of y onto the difference vector aj
−aj is equal to the projection m|aj
−aj of the midvector m = (aj + aj
)/2 onto the difference vector aj − aj
, as illustrated in Figure 2. The decision region Rj is the intersection of these M − 1 half-spaces: � Rj = Rjj
. j
=  j (Equivalently, the complementary region Rj is the union of the complementary half-spaces Rjj
.) A decision region Rj is therefore a convex polytope bounded by portions of a subset {Hjj
, aj
∈ N (aj )} of the boundary hyperplanes Hjj
, where the subset N (aj ) ⊆ A of neighbors of aj that contribute boundary faces to this polytope is called the relevant subset. It is easy to see that the relevant subset must always include the nearest neighbors to aj . 5.2 Probability of decision error The probability of decision error given that aj is transmitted is the probability that Y = aj + N falls outside the decision region Rj , whose “center” is aj . Equivalently, it is the probability that the noise variable N falls outside the translated region Rj − aj , whose “center” is 0: � � � Pr(E | aj ) = 1 − pY (y | aj ) dy = 1 − pN (y − aj ) dy = 1 − pN (n) dn. Rj Rj Rj −aj Exercise 2 (error probability invariance). (a) Show that the probabilities of error Pr(E | aj ) are unchanged if A is translated by any vector v; i.e., the constellation A
= A + v has the same error probability Pr(E) as A. (b) Show that Pr(E) is invariant under orthogonal transformations; i.e., the constellation A
= U A has the same Pr(E) as A when U is any orthogonal N × N matrix (i.e., U −1 = U T ). (c) Show that Pr(E) is unchanged if both the constellation A and the noise N are scaled by the same scale factor α > 0. Exercise 3 (optimality of zero-mean constellations). Consider an arbitrary signal set A = 1 � a {aj , 1 ≤ j ≤ M }. Assume that all signals are equiprobable. Let m(A) = M j j be the average signal, and let A
be A translated by m(A) so that the mean of A
is zero: A
= A − m(A) = {aj − m(A), 1 ≤ j ≤ M }. Let E(A) and E(A
) denote the average energies of A and A
, respectively. (a) Show that the error probability of an optimum detector is the same for A
as it is for A. (b) Show that E(A
) = E(A) − ||m(A)||2 . Conclude that removing the mean m(A) is always a good idea. (c) Show that a binary antipodal signal set A = {±a} is always optimal for M = 2. In general, there is no closed-form expression for the Gaussian integral Pr(E | aj ). However, we can obtain an upper bound in terms of pairwise error probabilities, called the union bound, which is usually quite sharp. The first term of the union bound, called the union bound estimate, is usually an excellent approximation, and will be the basis for our analysis of coding gains of small-to-moderate-sized constellations. A lower bound with the same exponential behavior may be obtained by considering only the worst-case pairwise error probability. 5.2.1 Pairwise error probabilities We now show that each pairwise probability has a simple closed-form expression that depends only on the squared distance d2 (aj , aj
) = ||aj − aj
||2 and the noise variance σ 2 = N0 /2. From Figure 2, it is clear that whether y = aj + n is closer to aj
than to aj depends only on the projection y|aj
−aj of y onto the difference vector aj
− aj . In fact, from (5.2), an error can occur if and only if |n|aj
−aj | = |n, φj→j
| = |n, aj
− aj | ||aj
− aj || ≥ aj
− aj , aj
− aj  ||aj
− aj || = . 2 2||aj
− aj || In other words, an error can occur if and only if the magnitude of the one-dimensional noise component n1 = n|aj
−aj , the projection of n onto the difference vector aj
− aj , exceeds half the distance d(aj
, aj ) = ||aj
− aj || between aj
and aj . We now use the fact that the distribution pN (n) of the iid Gaussian noise vector N is spherically symmetric, so the pdf of any one-dimensional projection such as n1 is pN (n1 ) = √ 1 2πσ 2 2 2 e−n1 /2σ . In other words, N is an iid zero-mean Gaussian vector with variance σ 2 in any coordinate system, including a coordinate system in which the first coordinate axis is aligned with the vector aj
−aj . Consequently, the pairwise error probability Pr{aj → aj
} that if aj is transmitted, the received vector y = aj + n will be at least as close to aj
as to aj is given simply by � � � ∞ d(aj
, aj ) 1 2 2 , (5.3) e−x /2σ dx = Q Pr{aj → aj
} = √ 2σ 2πσ 2 d(aj
,aj )/2 where Q(·) is again the Gaussian probability of error function. As we have seen, the probability of error for a 2-PAM signal set {±α} is Q(α/σ). Since the distance between the two signals is d = 2α, this is just a special case of this general formula. In summary, the spherical symmetry of iid Gaussian noise leads to the remarkable result that the pairwise error probability from aj to aj
depends only on the squared distance d2 (aj
, aj ) = ||aj
− aj ||2 between aj and aj
and the noise variance σ 2 . Exercise 4 (non-equiprobable signals). Let aj and aj
be two signals that are not equiprobable. Find the optimum (MPE) pairwise decision rule and pairwise error probability Pr{aj → aj
}. 5.2.2 The union bound and the UBE The union bound on error probability is based on the elementary union bound of probability theory: if A and B are any two events, then Pr(A ∪ B) ≤ Pr(A)+Pr(B). Thus the probability of detection error Pr(E | aj ) with minimum-distance detection if aj is sent— i.e., the probability that y will be closer to some other aj
∈ A than to aj – is upperbounded by the sum of the pairwise error probabilities to all other signals aj
= aj ∈ A: � � � � d(aj , aj
) . Pr(E | aj ) ≤ Pr{aj → aj
} = Q 2σ aj =aj
∈A aj =  aj
∈A Let D denote the set of distances between signal points in A; then we can write the union bound as � � � d Pr(E | aj ) ≤ , (5.4) Kd (aj )Q 2σ d∈D where Kd (aj ) is the number of signals aj
= aj ∈ A at distance d from aj . Because Q(x) 2 decreases exponentially as e−x /2 (see Appendix), the factor Q(d/2σ) will be largest for the minimum Euclidean distance dmin (A) = min aj =aj
∈A ||aj
− aj ||, and will decrease rapidly for larger distances. The union bound estimate (UBE) of Pr(E | aj ) is based on the idea that the nearest neighbors to aj at distance dmin (A) (if there are any) will dominate this sum. If there are Kmin (aj ) neighbors at distance dmin (A) from aj , then � � dmin (A) . (5.5) Pr(E | aj ) ≈ Kmin (aj ) Q 2σ Of course this estimate is valid only if the next nearest neighbors are at a significantly greater distance and there are not too many of them; if these assumptions are violated, then further terms should be used in the estimate. The union bound may be somewhat sharpened by considering only signals in the relevant subset N (aj ) that determine faces of the decision region Rj . However, since N (aj ) includes all nearest neighbors at distance dmin (A), this will not affect the UBE. Finally, if there is at least one neighbor aj
at distance dmin (A) from aj , then we have the pairwise lower bound � � dmin (A) , (5.6) Pr(E | aj ) ≥ Pr{aj → aj
} = Q 2σ since there must be a detection error if y is closer to aj
than to aj . Thus we are usually able to obtain upper and lower bounds on Pr(E | aj ) that have the same “exponent” (argument of the Q(·) function) and that differ only by a small factor of the order of Kmin (aj ). We can obtain similar upper and lower bounds and estimates for the total error probability Pr(E) = Pr(E | aj ), where the overbar denotes the expectation over the equiprobable ensemble of signals in A. For example, if Kmin (A) = Kmin (aj ) is the average number of nearest neighbors at distance dmin (A), then the union bound estimate of Pr(E) is � � dmin (A) . (5.7) Pr(E) ≈ Kmin (A)Q 2σ Exercise 5 (UBE for M -PAM constellations). For an M -PAM constellation A, show that Kmin (A) = 2(M − 1)/M . Conclude that the union bound estimate of Pr(E) is � � � � d M −1 Q . Pr(E) ≈ 2 M 2σ Show that in this case the union bound estimate is exact. Explain why. 5.3 Performance analysis in the power-limited regime Recall that the power-limited regime is defined as the domain in which the nominal spectral efficiency ρ is not greater than 2 b/2D. In this regime we normalize all quantities “per bit,” and generally use Eb /N0 as our normalized measure of signal-to-noise ratio. The baseline uncoded signal set in this regime is the one-dimensional 2-PAM signal set A = {±α}, or equivalently a K -cube constellation AK . Such a constellation has bit rate (nominal spectral efficiency) ρ = 2 b/2D, average energy ber bit Eb = α2 , minimum squared distance d2min (A) = 4α2 , and average number of nearest neighbors per bit Kb (A) = 1. By the UBE (5.7), its error probability per bit is given by √ Pb (E ) ≈ Q (2Eb /N0 ), (5.8) √ √ √ where we now use the “Q-of-the-square-root-of” function Q , defined by Q (x) = Q( x) (see Appendix). This baseline curve of Pb (E) vs. Eb /N0 is plotted in Chapter 4, Figure 1. The effective coding gain γeff (A) of a signal set A at a given target error probability per bit Pb (E ) will be defined as the difference in dB between the Eb /N0 required to achieve the target Pb (E ) with A and the Eb /N0 required to achieve the target Pb (E) with 2-PAM (i.e., no coding). For example, we have seen that the maximum possible effective coding gain at Pb (E) ≈ 10−5 is approximately 11.2 dB. For lower Pb (E), the maximum possible gain is higher, and for higher Pb (E ), the maximum possible gain is lower. In this definition, the effective coding gain includes any gains that result from using a lower nominal spectral efficiency ρ < 2 b/2D, which as we have seen can range up to 3.35 dB. If ρ is held constant at ρ = 2 b/2D, then the maximum possible effective coding gain is lower; e.g., at Pb (E) ≈ 10−5 it is approximately 8 dB. If there is a constraint on ρ (bandwidth), then it is better to plot Pb (E) vs. SNRnorm , especially to measure how far A is from achieving capacity. The UBE allows us to estimate the effective coding gain as follows. The probability of error per bit (not in general the same as the bit error probability!) is � � Kmin (A) √ d2min (A) Pr(E) , Q ≈ Pb (E) = 2N0 log2 |A| log2 |A| � √� since Q d2min (A)/2N0 = Q(dmin (A)/2σ). In the power-limited regime, we define the nominal coding gain γc (A) as d2 (A) . (5.9) γc (A) = min 4Eb This definition is normalized so that for 2-PAM,√ γc (A) = 1. Because nominal coding gain is a multiplicative factor in the argument of the Q (·) function, it is often measured in dB. The UBE then becomes √ Pb (E) ≈ Kb (A)Q (2γc (A)Eb /N0 ), (5.10) where Kb (A) = Kmin (A)/ log2 |A| is the average number of nearest neighbors per transmitted bit. Note that for 2-PAM, this expression is exact. Given γc (A) and Kb (A), we may obtain a plot of the UBE (5.10) simply by moving the baseline curve (Figure 1 of Chapter 4) to the left by γc (A) (in dB), and then up by a factor of Kb (A), since Pb (E) is plotted on a log scale. (This is an excellent reason why error probability curves are always plotted on a log-log scale, with SNR measured in dB.) Thus if Kb (A) = 1, then the effective coding gain γeff (A) is equal to the nominal coding gain γc (A) for all Pb (E ), to the accuracy of the UBE. However, if Kb (A) > 1, then the effective coding gain is less than the nominal coding gain by an amount which depends on the steepness of the Pb (E) vs. Eb /N0 curve at the target Pb (E). At Pb (E) ≈ 10−5 , a rule of thumb which is fairly accurate if Kb (A) is not too large is that an increase of a factor of two in Kb (A) costs about 0.2 dB in effective coding gain; i.e., γeff (A) ≈ γc (A) − (0.2)(log2 Kb (A)) (in dB). (5.11) A more accurate estimate may be obtained by a plot of the union bound estimate (5.10). Exercise 6 (invariance of coding gain). Show that the nominal coding gain γc (A) of (5.9), the UBE (5.10) of Pb (E), and the effective coding gain γeff (A) are invariant to scaling, orthogonal transformations and Cartesian products. 5.4 Orthogonal and related signal sets Orthogonal, simplex and biorthogonal signal sets are concrete examples of large signal sets that are suitable for the power-limited regime when bandwidth is truly unconstrained. Orthogonal signal sets are the easiest to describe and analyze. Simplex signal sets are believed to be optimal for a given constellation size M when there is no constraint on dimension. Biorthogonal signal sets are slightly more bandwidth-efficient. For large M , all become essentially equivalent. The following exercises develop the parameters of these signal sets, and show that they can achieve reliable transmission for Eb /N0 within 3 dB from the ultimate Shannon limit.1 The drawback of these signal sets is that the number of dimensions (bandwidth) becomes very large and the spectral efficiency ρ very small as M → ∞. Also, even with the “fast” Walsh-Hadamard transform (see Chapter 1, Problem 2), decoding complexity is of the order of M log2 M , which increases exponentially with the number of bits transmitted, log2 M , and thus is actually “slow.” Exercise 7 (Orthogonal signal sets). An orthogonal signal set is a set A = {aj , 1 ≤ j ≤ M } of M orthogonal vectors in RM with equal energy E (A); i.e., aj , aj
 = E(A)δjj
(Kronecker delta). (a) Compute the nominal spectral efficiency ρ of A in bits per two dimensions. Compute the average energy Eb per information bit. (b) Compute the minimum squared distance d2min (A). Show that every signal has Kmin (A) = M − 1 nearest neighbors. (c) Let the noise variance be σ 2 = N0 /2 per dimension. Show that the probability of error of an optimum detector is bounded by the UBE √ Pr(E) ≤ (M − 1)Q (E(A)/N0 ). (d) Let M → ∞ with Eb held constant. Using an asymptotically accurate upper bound for √ the Q (·) function (see Appendix), show that Pr(E) → 0 provided that Eb /N0 > 2 ln 2 (1.42 dB). How close is this to the ultimate Shannon limit on Eb /N0 ? What is the nominal spectral efficiency ρ in the limit? 1 Actually, it can be shown that with optimum detection orthogonal signal sets can approach the ultimate Shannon limit on Eb /N0 as M → ∞; however, the union bound is too weak to prove this. Exercise 8 (Simplex signal sets). Let A be an orthogonal signal set as above.  0, and compute ||m(A)||2 . (a) Denote the mean of A by m(A). Show that m(A) = The zero-mean set A
= A − m(A) (as in Exercise 2) is called a simplex signal set. It is universally believed to be the optimum set of M signals in AWGN in the absence of bandwidth constraints, except at ridiculously low SNRs. (b) For M = 2, 3, 4, sketch A and A
. (c) Show that all signals in A
have the same energy E(A
). Compute E(A
). Compute the inner products aj , aj
 for all aj , aj
∈ A
. (d) [Optional]. Show that for ridiculously low SNRs, a signal set consisting of M − 2 zero signals and two antipodal signals {±a} has a lower Pr(E) than a simplex signal set. [Hint: see M. Steiner, “The strong simplex conjecture is false,” IEEE Transactions on Information Theory, pp. 721-731, May 1994.] Exercise 9 (Biorthogonal signal sets). The set A

= ±A of size 2M consisting of the M signals in an orthogonal signal set A with symbol energy E(A) and their negatives is called a biorthogonal signal set. (a) Show that the mean of A

is m(A

) = 0, and that the average energy per symbol is E(A). (b) How much greater is the nominal spectral efficiency ρ of A

than that of A, in bits per two dimensions? (c) Show that the probability of error of A

is approximately the same as that of an orthogonal signal set with the same size and average energy, for M large. (d) Let the number of signals be a power of 2: 2M = 2k . Show that the nominal spectral efficiency is ρ(A

) = 4k2−k b/2D, and that the nominal coding gain is γc (A

) = k/2. Show that the number of nearest neighbors is Kmin (A

) = 2k − 2. Example 2 (Biorthogonal signal sets). Using Exercise 9, we can estimate the effective coding gain of a biorthogonal signal set using our rule of thumb (5.11), and check its accuracy against a plot of the UBE (5.10). The 2k = 16 biorthogonal signal set A has dimension N = 2k−1 = 8, rate k = 4 b/sym, and nominal spectral efficiency ρ(A) = 1 b/2D. With energy E(A) per symbol, it has Eb = E(A)/4 and d2min (A) = 2E(A), so its nominal coding gain is γc (A) = d2min (A)/4Eb = 2 (3.01 dB), The number of nearest neighbors is Kmin (A) = 2k − 2 = 14, so Kb (A) = 14/4 = 3.5, and the estimate of its effective coding gain at Pb (E) ≈ 10−5 by our rule of thumb (5.11) is thus γeff (A) ≈ 3 − 2(0.2) = 2.6 dB. A more accurate plot of the UBE (5.10) may be obtained by shifting the √ baseline curve (Figure 1 of Chapter 4) left by 3 dB and up by half a vertical unit (since 3.5 ≈ 10), as shown in Figure 3. This plot shows that the rough estimate γeff (A) ≈ 2.6 dB is quite accurate at Pb (E) ≈ 10−5 . Similarly, the 64-biorthogonal signal set A
has nominal coding gain γc (A
) = 3 (4.77 dB), Kb (A
) = 62/6 ≈ 10, and effective coding gain γeff (A
) ≈ 4.8 - 3.5(0.2) = 4.1 dB by our rule of thumb. The 256-biorthogonal signal set A

has nominal coding gain γc (A

) = 4 (6.02 dB), Kb (A

) = 254/8 ≈ 32, and effective coding gain γeff (A

) ≈ 6 - 5(0.2) = 5.0 dB by our rule of thumb. Figure 3 also shows plots of the UBE (5.10) for these two signal constellations, which show that our rule of thumb continues to be fairly accurate. Biorthogonal signal sets 0 10 Uncoded 2−PAM biorthogonal M=16 biorthogonal M=64 biorthogonal M=256 −1 10 −2 Pb(E) 10 −3 10 −4 10 −5 10 −6 10 −2 −1 0 1 2 3 4 5 6 Eb/N0 [dB] 7 8 9 10 11 12 Figure 3. Pb (E) vs. Eb /N0 for biorthogonal signal sets with 2k = 16, 64 and 256. 5.5 Performance in the bandwidth-limited regime Recall that the bandwidth-limited regime is defined as the domain in which the nominal spectral efficiency ρ is greater than 2 b/2D; i.e., the domain of nonbinary signaling. In this regime we normalize all quantities “per two dimensions,” and use SNRnorm as our normalized measure of signal-to-noise ratio. The baseline uncoded signal set in this regime is the M -PAM signal set A = α{±1, ±3, . . . , ±(M − 1)}, or equivalently the (M × M )-QAM constellation A2 . Typically M is a power of 2. Such a constellation has bit rate (nominal spectral efficiency) ρ = 2 log2 M b/2D and minimum squared distance d2min (A2 ) = 4α2 . As shown in Chapter 4, its average energy per two dimensions is d2 (A)(2ρ − 1) 2α2 (M 2 − 1) = min . (5.12) Es = 3 6 The average number of nearest neighbors per two dimensions is twice that of M -PAM, namely Ks (A) = 4(M − 1)/M , which rapidly approaches Ks (A) ≈ 4 as M becomes large. By the UBE (5.7), the error probability per two dimensions is given by √ Ps (E) ≈ 4Q (3SNRnorm ). This baseline curve of Ps (E) vs. SNRnorm was plotted in Figure 2 of Chapter 4. (5.13) In the bandwidth-limited regime, the effective coding gain γeff (A) of a signal set A at a given target error rate Ps (E) will be defined as the difference in dB between the SNRnorm required to achieve the target Ps (E) with A and the SNRnorm required to achieve the target Ps (E) with M -PAM or (M × M )-QAM (no coding). For example, we saw from Figure 2 of Chapter 4 that the maximum possible effective coding gain at Ps (E) ≈ 10−5 is approximately 8.4 dB, which is about 3 dB less than in the power-limited regime (due solely to the fact that the bandwidth is fixed). The effective coding gain is again estimated by the UBE, as follows. The probability of error per two dimensions is � � 2Kmin (A) √ d2min (A) 2 Pr(E) . ≈ Q Ps (E) = N N 2N0 In the bandwidth-limited regime, we define the nominal coding gain γc (A) as (2ρ − 1)d2min (A) . (5.14) 6Es This definition is normalized so that for M -PAM or (M × M )-QAM, γc (A) = 1. Again, γc (A) is often measured in dB. The UBE (5.10) then becomes γc (A) = √ Ps (E) ≈ Ks (A)Q (3γc (A)SNRnorm ), (5.15) where Ks (A) = 2Kmin (A)/N is the average number of nearest neighbors per two dimensions. Note that for M -PAM or (M × M )-QAM, this expression reduces to (5.13). Given γc (A) and Ks (A), we may obtain a plot of (5.15) by moving the baseline curve (Figure 2 of Chapter 4) to the left by γc (A) (in dB), and up by a factor of Ks (A)/4. The rule of thumb that an increase of a factor of two in Ks (A) over the baseline Ks (A) = 4 costs about 0.2 dB in effective coding gain at Ps (E) ≈ 10−5 may still be used if Ks (A) is not too large. Exercise 6 (invariance of coding gain, cont.) Show that in the bandwidth-limited regime the nominal coding gain γc (A) of (5.14), the UBE (5.15) of Ps (E), and the effective coding gain γeff (A) are invariant to scaling, orthogonal transformations and Cartesian products. 5.6 Design of small signal constellations The reader may now like to try to find the best constellations of small size M in N dimensions, using coding gain γc (A) as the primary figure of merit, and Kmin (A) as a secondary criterion. Exercise 10 (small nonbinary constellations). (a) For M = 4, the (2 × 2)-QAM signal set is known to be optimal in N = 2 dimensions. Show however that there exists at least one other inequivalent two-dimensional signal set A
with the same coding gain. Which signal set has the lower “error coefficient” Kmin (A)? (b) Show that the coding gain of (a) can be improved in N = 3 dimensions. [Hint: consider the signal set A

= {(1, 1, 1), (1, −1, −1), (−1, 1, −1), (−1, −1, 1)}.] Sketch A

. What is the geometric name of the polytope whose vertex set is A

? (c) For M = 8 and N = 2, propose at least two good signal sets, and determine which one is better. [Open research problem: Find the optimal such signal set, and prove that it is optimal.] (d) [Open research problem.] For M = 16 and N = 2, the hexagonal signal set of Figure 1(e), Chapter 4, is thought to be near-optimal. Prove that it is optimal, or find a better one. 5.7 Summary: Performance analysis and coding gain The results of this chapter may be summarized very simply. In the power-limited regime, the nominal coding gain is γc (A) = d2min (A)/4Eb . To the accuracy √ /N0 ). This curve may be plotted by moving the of the UBE, Pb (E) ≈ Kb (A)Q (2γc (A)E √b power-limited baseline curve Pb (E) ≈ Q (2Eb /N0 ) to the left by γc (A) in dB and up by a factor of Kb (A). An estimate of the effective coding gain at Pb (E) ≈ 10−5 is γeff (A) ≈ γc (A) − (0.2)(log2 Kb (A)) dB. 2 (A)/6E . In the bandwidth-limited regime, the nominal√ coding gain is γc (A) = (2ρ − 1)dmin s To the accuracy of the UBE, Ps (E) ≈ Ks (A)Q (3γc (A)SNR√ norm ). This curve may be plotted by moving the bandwidth-limited baseline curve Ps (E) ≈ 4Q (3SNRnorm ) to the left by γc (A) in dB and up by a factor of Ks (A)/4. An estimate of the effective coding gain at Ps (E) ≈ 10−5 is γeff (A) ≈ γc (A) − (0.2)(log2 Ks (A)/4) dB. Appendix: The Q function The Gaussian probability of error (or Q) function, defined by � ∞ 1 2 √ e−y /2 dy, Q(x) = 2π x arises frequently in error probability calculations on Gaussian channels. In this appendix we discuss some of its properties. As we have seen, there is very often a square root in the argument of the Q function. This suggests that it might have been more useful to define a “Q-of-the-square-root-of” function √ √ Q (x) such that Q (x2 ) = Q(x); i.e., � ∞ √ √ 1 2 Q (x) = Q( x) = √ √ e−y /2 dy. 2π x √ From now on we will use this Q function instead of the Q function. For example, our baseline curves for 2-PAM and (M × M )-QAM will be √ Pb (E) = Q (2Eb /N0 ); √ Ps (E) ≈ 4Q (3SNRnorm ). √ The Q or Q functions do not have a closed-form expression, but must be looked up in tables. Non-communications texts usually tabulate the complementary error function, namely � ∞ 1 2 √ e−y dy. erfc(x) = π x � √ √ Evidently Q(x) = erfc(x/ 2), and Q (x) = erfc( x/2). √ The main property of the Q or Q function is that it decays exponentially with x2 according to √ 2 Q (x2 ) = Q(x) ≈ e−x /2 . The following exercise gives several ways to prove this, including upper bounds, a lower bound, and an estimate. √ Exercise A (Bounds on the Q function). (a) As discussed in Chapter 3, the Chernoff bound on the probability that a real random variable Z exceeds b is given by s≥0 Pr{Z ≥ b} ≤ es(Z−b) , (since es(z−b) ≥ 1 when z ≥ b, and es(z−b) ≥ 0 otherwise). When optimized over s ≥ 0, the Chernoff exponent is asymptotically correct. Use the Chernoff bound to show that √ Q (x2 ) ≤ e−x 2 /2 . (5.16) (b) Integrate by parts to derive the upper and lower bounds √ 1 2 √ e−x /2 ; 2 � 2πx � √ 1 1 2 1− 2 √ e−x /2 . Q (x2 ) > 2 x 2πx Q (x2 ) < (5.17) (5.18) (c) Here is another way to establish these tight upper and lower bounds. By using a simple change of variables, show that � 2 � � √ −y 1 −x2 ∞ 2 2 exp − xy dy. Q (x ) = √ e 2 2π 0 Then show that y2 ≤ exp 1− 2 � −y 2 2 � ≤ 1. Putting these together, derive the bounds of part (b). For (d)-(f), consider a circle of radius x inscribed in a square of side 2x as shown below. '$ x&% (d) Show that the probability that a two-dimensional iid real Gaussian random variable X √ 2 2 2 with variance σ = 1 per dimension falls inside the square is equal to (1 − 2Q (x )) . 2 (e) Show that the probability that X falls inside the circle is 1 − e−x /2 . [Hint: write 2 1 re−r /2 . You can then compute the integral pX (x) in polar coordinates: i.e., pRΘ (r, θ) = 2π � 2π � x 0 dθ 0 dr pRΘ (r, θ) in closed form.] (f) Show that (d) and (e) imply that when x is large, √ 1 2 Q (x2 ) ≤ e−x /2 . 4