The Gap between Uncoded Performance and the Shannon Limit

Chapter 4 The gap between uncoded performance and the Shannon limit The channel capacity theorem gives a sharp upper limit C[b/2D] = log2 (1 + SNR) b/2D on the rate (nominal spectral efficiency) ρ b/2D of any reliable transmission scheme. However, it does not give constructive coding schemes that can approach this limit. Finding such schemes has been the main problem of coding theory and practice for the past half century, and will be our main theme in this book. We will distinguish sharply between the power-limited regime, where the nominal spectral efficiency ρ is small, and the bandwidth-limited regime, where ρ is large. In the power-limited regime, we will take 2-PAM as our baseline uncoded scheme, whereas in the bandwidth-limited regime, we will take M -PAM (or equivalently (M × M )-QAM) as our baseline. By evaluating the performance of these simplest possible uncoded modulation schemes and comparing baseline performance to the Shannon limit, we will establish how much “coding gain” is possible. 4.1 Discrete-time AWGN channel model We have seen that with orthonormal PAM or QAM, the channel model reduces to an analogous real or complex discrete-time AWGN channel model Y = X + N, where X is the random input signal point sequence, and N is an independent iid Gaussian noise sequence with mean zero and variance σ 2 = N0 /2 per real dimension. We have also seen that there is no essential difference between the real and complex versions of this model, so from now on we will consider only the real model. We recapitulate the connections between the parameters of this model and the corresponding continuous-time parameters. If the symbol rate is 1/T real symbols/s (real dimensions per second), the bit rate per two dimensions is ρ b/2D, and the average signal energy per two dimensions is Es , then: • The nominal bandwidth is W = 1/2T Hz; • The data rate is R = ρW b/s, and the nominal spectral efficiency is ρ (b/s)/Hz; • The signal power (average energy per second) is P = Es W ; • The signal-to-noise ratio is SNR = Es /N0 = P/N0 W ; • The channel capacity in b/s is C[b/s] = W C[b/2D] = W log2 (1 + SNR) b/s. 4.2 Normalized SNR and Eb /N0 In this section we introduce two normalized measures of SNR that are suggested by the capacity bound ρ < C[b/2D] = log2 (1 + SNR) b/2D, which we will now call the Shannon limit. An equivalent statement of the Shannon limit is that for a coding scheme with rate ρ b/2D, if the error probability is to be small, then the SNR must satisfy SNR > 2ρ − 1. This motivates the definition of the normalized signal-to-noise ratio SNRnorm as SNRnorm = SNR . 2ρ − 1 (4.1) SNRnorm is commonly expressed in dB. Then the Shannon limit may be expressed as SNRnorm > 1 (0 dB). Moreover, the value of SNRnorm in dB measures how far a given coding scheme is operating from the Shannon limit, in dB (the “gap to capacity”). Another commonly used normalized measure of signal-to-noise ratio is Eb /N0 , where Eb is the average signal energy per information bit and N0 is the noise variance per two dimensions. Note that since Eb = Es /ρ, where Es is the average signal energy per two dimensions, we have Eb /N0 = Es /ρN0 = SNR/ρ. The quantity Eb /N0 is sometimes called the “signal-to-noise ratio per information bit,” but it is not really a signal-to-noise ratio, because its numerator and denominator do not have the same units. It is probably best just to call it “Eb /N0 ” (pronounced “eebee over enzero” or “ebno”). Eb /N0 is commonly expressed in dB. Since SNR > 2ρ − 1, the Shannon limit on Eb /N0 may be expressed as Eb /N0 > 2ρ − 1 . ρ (4.2) Notice that the Shannon limit on Eb /N0 is a monotonic function of ρ. For ρ = 2, it is equal to 3/2 (1.76 dB); for ρ = 1, it is equal to 1 (0 dB); and as ρ → 0, it approaches ln 2 ≈ 0.69 (-1.59 dB), which is called the ultimate Shannon limit on Eb /N0 . 4.3 Power-limited and bandwidth-limited channels Ideal band-limited AWGN channels may be classified as bandwidth-limited or power-limited according to whether they permit transmission at high spectral efficiencies or not. There is no sharp dividing line, but we will take ρ = 2 b/2D or (b/s)/Hz as the boundary, corresponding to the highest spectral efficiency that can be achieved with binary transmission. We note that the behavior of the Shannon limit formulas is very different in the two regimes. If SNR is small (the power-limited regime), then we have ρ < log2 (1 + SNR) ≈ SNR log2 e; SNR = (Eb /N0 ) log2 e. SNRnorm ≈ ρ ln 2 In words, in the power-limited regime, the capacity (achievable spectral efficiency) increases linearly with SNR, and as ρ → 0, SNRnorm becomes equivalent to Eb /N0 , up to a scale factor of log2 e = 1/ ln 2. Thus as ρ → 0 the Shannon limit SNRnorm > 1 translates to the ultimate Shannon limit on Eb /N0 , namely Eb /N0 > ln 2. On the other hand, if SNR is large (the bandwidth-limited regime), then we have ρ < log2 (1 + SNR) ≈ log2 SNR; SNR SNRnorm ≈ . 2ρ Thus in the bandwidth-limited regime, the capacity (achievable spectral efficiency) increases logarithmically with SNR, which is dramatically different from the linear behavior in the powerlimited regime. In the power-limited regime, every doubling of SNR doubles the achievable rate, whereas in the bandwidth-limited regime, every additional 3 dB in SNR yields an increase in achievable spectral efficiency of only 1 b/2D or 1 (b/s)/Hz. Example 1. A standard voice-grade telephone channel may be crudely modeled as an ideal band-limited AWGN channel with W ≈ 3500 Hz and SNR ≈ 37 dB. The Shannon limit on spectral efficiency and bit rate of such a channel are roughly ρ < 37/3 ≈ 12.3 (b/s)/Hz and R < 43,000 b/s. Increasing the SNR by 3 dB would increase the achievable spectral efficiency ρ by only 1 (b/s)/Hz, or the bit rate R by only 3500 b/s. Example 2. In contrast, there are no bandwidth restrictions on a deep-space communication channel. Therefore it makes sense to use as much bandwidth as possible, and operate deep in the power-limited region. In this case the bit rate is limited by the ultimate Shannon limit on Eb /N0 , namely Eb /N0 > ln 2 (-1.59 dB). Since Eb /N0 = P/RN0 , the Shannon limit becomes R < (P/N0 )/(ln 2). Increasing P/N0 by 3 dB will now double the achievable rate R in b/s. We will find that the power-limited and bandwidth-limited regimes differ in almost every way. In the power-limited regime, we will be able to use binary coding and modulation, whereas in the bandwidth-limited regime we must use nonbinary (“multilevel”) modulation. In the powerlimited regime, it is appropriate to normalize everything “per information bit,” and Eb /N0 is a reasonable normalized measure of signal-to-noise ratio. In the bandwidth-limited regime, on the other hand, we will see that it is much better to normalize everything “per two dimensions,” and SNRnorm will become a much more appropriate measure than Eb /N0 . Thus the first thing to do in a communications design problem is to determine which regime you are in, and then proceed accordingly. 4.4 Performance of M -PAM and (M × M )-QAM We now evaluate the performance of the simplest possible uncoded systems, namely M -PAM and (M × M )-QAM. This will give us a baseline. The difference between the performance achieved by baseline systems and the Shannon limit determines the maximum possible gain that can be achieved by the most sophisticated coding systems. In effect, it defines our playing field. 4.4.1 Uncoded 2-PAM We first consider the important special case of a binary 2-PAM constellation A = {−α, +α}, where α > 0 is a scale factor chosen such that the average signal energy per bit, Eb = α2 , satisfies the average signal energy constraint. For this constellation, the bit rate (nominal spectral efficiency) is ρ = 2 b/2D, and the average signal energy per bit is Eb = α2 . The usual symbol-by-symbol detector (which is easily seen to be optimum) makes an independent decision on each received symbol yk according to whether the sign of yk is positive or negative. The probability of error per bit is evidently the same regardless of which of the two signal values is transmitted, and is equal to the probability that a Gaussian noise variable of variance σ 2 = N0 /2 exceeds α, namely Pb (E) = Q (α/σ) , where the Gaussian probability of error Q(·) function is defined by � ∞ 1 2 √ e−y /2 dy. Q(x) = 2π x Substituting the energy per bit Eb = α2 and the noise variance σ 2 = N0 /2, the probability of error per bit is � �� 2Eb /N0 . (4.3) Pb (E) = Q This gives the performance curve of Pb (E) vs. Eb /N0 for uncoded 2-PAM that is shown in Figure 1, below. 4.4.2 Power-limited baseline vs. the Shannon limit In the power-limited regime, we will take binary pulse amplitude modulation (2-PAM) as our baseline uncoded system, since it has ρ = 2. By comparing the performance of the uncoded baseline system to the Shannon limit, we will be able to determine the maximum possible gains that can be achieved by the most sophisticated coding systems. In the power-limited regime, we will primarily use Eb /N0 as our normalized signal-to-noise ratio, although we could equally well use SNRnorm . Note that when ρ = 2, since Eb /N0 = SNR/ρ and SNRnorm = SNR/(2ρ − 1), we have 2Eb /N0 = 3SNRnorm . The baseline performance curve can therefore be written in two equivalent ways: � �� � �� 2Eb /N0 = Q 3SNRnorm . Pb (E) = Q × Uncoded 2−PAM 0 10 Uncoded 2−PAM Shannon Limit Shannon Limit for ρ = 2 −1 10 −2 Pb(E) 10 −3 10 −4 10 −5 10 −6 10 −2 −1 0 1 2 3 4 5 6 Eb/No [dB] 7 8 9 10 11 12 Figure 1. Pb (E) vs. Eb /N0 for uncoded binary PAM. Figure 1 gives us a universal design tool. For example, if we want to achieve Pb (E ) ≈ 10−5 with uncoded 2-PAM, then we know that we will need to achieve Eb /N0 ≈ 9.6 dB. We may also compare the performance shown in Figure 1 to the Shannon limit. The rate of 2-PAM is ρ = 2 b/2D. The Shannon limit on Eb /N0 at ρ = 2 b/2D is Eb /N0 > (2ρ − 1)/ρ = 3/2 (1.76 dB). Thus if our target error rate is Pb (E) ≈ 10−5 , then we can achieve a coding gain of up to about 8 dB with powerful codes, at the same rate of ρ = 2 b/2D. However, if there is no limit on bandwidth and therefore no lower limit on spectral efficiency, then it makes sense to let ρ → 0. In this case the ultimate Shannon limit on Eb /N0 is Eb /N0 > ln 2 (-1.59 dB). Thus if our target error rate is Pb (E) ≈ 10−5 , then Shannon says that we can achieve a coding gain of over 11 dB with powerful codes, by letting the spectral efficiency approach zero. 4.4.3 Uncoded M -PAM and (M × M )-QAM We next consider the more general case of an M -PAM constellation A = α{±1, ±3, . . . , ±(M − 1)}, where α > 0 is again a scale factor chosen to satisfy the average signal energy constraint. The bit rate (nominal spectral efficiency) is then ρ = 2 log2 M b/2D. The average energy per M -PAM symbol is E(A) = α2 (M 2 − 1) . 3 An elegant way of making this calculation is to consider a random variable Z = X + U , where X is equiprobable over A and U is an independent continuous uniform random variable over the interval (−α, α]. Then Z is a continuous random variable over the interval (−M α, M α], and1 X2 = Z2 − U 2 = (αM )2 α2 − . 3 3 The average energy per two dimensions is then Es = 2E(A) = 2α2 (M 2 − 1)/3. Again, an optimal symbol-by-symbol detector makes an independent decision on each received symbol yk . In this case the decision region associated with an input value αzk (where zk is an odd integer) is the interval α[zk − 1, zk + 1] (up to tie-breaking at the boundaries, which is immaterial), except for the two outermost signal values ±α(M − 1), which have decision regions ±α[M − 2, ∞). The probability of error for any of the M − 2 inner signals is thus equal to twice the probability that a Gaussian noise variable Nk of variance σ 2 = N0 /2 exceeds α, namely 2Q (α/σ) , whereas for the two outer signals it is just Q (α/σ). The average probability of error with equiprobable signals per M -PAM symbol is thus Pr(E) = 2 2(M − 1) M −2 2Q (α/σ) + Q (α/σ) . Q (α/σ) = M M M For M = 2, this reduces to the usual expression for 2-PAM. For M ≥ 4, the “error coefficient” 2(M − 1)/M quickly approaches 2, so Pr(E) ≈ 2Q (α/σ). Since an (M × M )-QAM signal set A = A2 is equivalent to two independent M -PAM transmissions, we can easily extend this calculation to (M × M )-QAM. The bit rate (nominal spectral efficiency) is again ρ = 2 log2 M b/2D, and the average signal energy per two dimensions (per QAM symbol) is again Es = 2α2 (M 2 − 1)/3. The same dimension-by-dimension decision method and calculation of probability of error per dimension Pr(E) hold. The probability of error per (M × M )-QAM symbol, or per two dimensions, is given by Ps (E) = 1 − (1 − Pr(E))2 = 2 Pr(E) − (Pr(E))2 ≈ 2 Pr(E). Therefore for (M × M )-QAM we obtain a probability of error per two dimensions of Ps (E) ≈ 2 Pr(E) ≈ 4Q (α/σ) . 4.4.4 (4.4) Bandwidth-limited baseline vs. the Shannon limit In the bandwidth-limited regime, we will take (M × M )-QAM with M ≥ 4 as our baseline uncoded system, we will normalize everything per two dimensions, and we will use SNRnorm as our normalized signal-to-noise ratio. For M ≥ 4, the probability of error per two dimensions is given by (4.4): Ps (E) ≈ 4Q (α/σ) . 1 This calculation is actually somewhat fundamental, since it is based on a perfect one-dimensional spherepacking and on the fact that the difference between the average energy of a continuous random variable and the average energy of an optimally quantized discrete version thereof is the average energy of the quantization error. As the same principle is used in the calculation of channel capacity, in the relation Sy = Sx + Sn , we can even say that the “1” that appears in the capacity formula is the same “1” as appears in the formula for E(A). Therefore the cancellation of this term below is not quite as miraculous as it may at first seem. × Substituting the average energy Es = 2α2 (M 2 − 1)/3 per two dimensions, the noise variance σ 2 = N0 /2, and the normalized signal-to-noise ratio SNRnorm = SNR Es /N0 = 2 , 2ρ − 1 M −1 we find that the factors of M 2 − 1 cancel (cf. footnote 1) and we obtain the performance curve � �� (4.5) 3SNRnorm . Ps (E) ≈ 4Q Note that this curve does not depend on M , which shows that SNRnorm is correctly normalized for the bandwidth-limited regime. The bandwidth-limited baseline performance curve (4.5) of Ps (E) vs. SNRnorm for uncoded (M × M )-QAM is plotted in Figure 2. Uncoded QAM 0 10 Uncoded QAM Shannon Limit −1 10 −2 −3 10 s P (E) 10 −4 10 −5 10 −6 10 0 1 2 3 4 SNR 5 [dB] 6 7 8 9 10 norm Figure 2. Ps (E) vs. SNRnorm for uncoded (M × M )-QAM. Figure 2 gives us another universal design tool. For example, if we want to achieve Ps (E) ≈ 10−5 with uncoded (M × M )-QAM (or M -PAM), then we know that we will need to achieve SNRnorm ≈ 8.4 dB. (Notice that SNRnorm , unlike Eb /N0 , is already normalized for spectral efficiency.) The Shannon limit on SNRnorm for any spectral efficiency is SNRnorm > 1 (0 dB). Thus if our target error rate is Ps (E) ≈ 10−5 , then Shannon says that we can achieve a coding gain of up to about 8.4 dB with powerful codes, at any spectral efficiency. (This result holds approximately even for M = 2, as we have already seen in the previous subsection.)