Thomas M. Cover, Joy A. Thomas. Elements of information theory

Подождите немного. Документ загружается.

8.6 DIFFERENTIAL ENTROPY, RELATIVE ENTROPY, AND MUTUAL INFORMATION 255

=−h(g) −



log φ

(8.75)

=−h(g) + h(φ

), (8.76)

where the substitution



g log φ



log φ

follows from the fact

that g and φ

yield the same moments of the quadratic form log φ

(x).



In particular, the Gaussian distribution maximizes the entropy over

all distributions with the same variance. This leads to the estimation

counterpart to Fano’s inequality. Let X be a random variable with differ-

ential entropy h(X).Let

X be an estimate of X,andletE(X −

the expected prediction error. Let h(X) be in nats.

Theorem 8.6.6 (Estimation error and differential entropy) For any

random variable X and estimator

E(X −

≥

2πe

2h(X)

with equality if and only if X is Gaussian and

X is the mean of X.

Proof: Let

X be any estimator of X;then

E(X −

≥ min

E(X −

(8.77)

= E

(

X − E(X)

)

(8.78)

= var(X) (8.79)

≥

2πe

2h(X)

, (8.80)

where (8.78) follows from the fact that the mean of X is the best estimator

for X and the last inequality follows from the fact that the Gaussian

distribution has the maximum entropy for a given variance. We have

equality only in (8.78) only if

X is the best estimator (i.e.,

X is the mean

of X and equality in (8.80) only if X is Gaussian).



Corollary Given side information Y and estimator

X(Y ), it follows that

E(X −

X(Y ))

≥

2πe

2h(X|Y)

256 DIFFERENTIAL ENTROPY

SUMMARY

h(X) = h(f ) =−



f(x)log f(x)dx (8.81)

f(X

)

−nh(X)

(8.82)

Vo l (A

(n)



)

nh(X)

. (8.83)

(

[X]

−n

)

≈ h(X) + n. (8.84)

N(0,σ

)) =

log 2πeσ

. (8.85)

(µ, K)) =

log(2πe)

|K|. (8.86)

D(f ||g) =



f log

≥ 0. (8.87)

h(X

,...,X

) =



i=1

h(X

,...,X

i−1

). (8.88)

h(X|Y) ≤ h(X). (8.89)

h(aX) = h(X) + log |a|. (8.90)

I(X;Y) =



f (x,y)log

f (x,y)

f(x)f(y)

≥ 0. (8.91)

max

EXX

h(X) =

log(2πe)

|K|. (8.92)

E(X −

X(Y ))

≥

2πe

2h(X|Y)

nH (X)

is the effective alphabet size for a discrete random variable.

nh(X)

is the effective support set size for a continuous random variable.

is the effective alphabet size of a channel of capacity C.

PROBLEMS

8.1 Differential entropy. Evaluate the differential entropy h(X) =

−



f ln f for the following:

(a) The exponential density, f(x) = λe

−λx

, x ≥ 0.

PROBLEMS 257

(b) The Laplace density, f(x) =

λe

−λ|x|

and X

, where X

and X

are independent

normal random variables with means µ

and variances σ

,i =

1, 2.

8.2 Concavity of determinants.LetK

and K

be two symmetric non-

negative deﬁnite n × n matrices. Prove the result of Ky Fan [199]:

| λK

+ λK

|≥| K

| K

for 0 ≤ λ ≤ 1, λ = 1 − λ,

where | K | denotes the determinant of K.[Hint:LetZ = X

where X

∼ N(0,K

), X

∼ N(0,K

) and θ = Bernoulli(λ).Then

use h(Z | θ) ≤ h(Z).]

8.3 Uniformly distributed noise. Let the input random variable X to

a channel be uniformly distributed over the interval −

≤ x ≤+

Let the output of the channel be Y = X + Z, where the noise ran-

dom variable is uniformly distributed over the interval −a/2 ≤ z ≤

+a/2.

(a) Find I(X;Y) as a function of a.

(b) For a = 1 ﬁnd the capacity of the channel when the input X

is peak-limited; that is, the range of X is limited to −

≤ x ≤

. What probability distribution on X maximizes the mutual

information I(X;Y)?

again assuming that the range of X is limited to −

≤ x ≤+

8.4 Quantized random variables. Roughly how many bits are required

on the average to describe to three-digit accuracy the decay time

(in years) of a radium atom if the half-life of radium is 80 years?

Note that half-life is the median of the distribution.

8.5 Scaling.Leth(X) =−



f(x) log f(x)dx. Show

h(AX) = log | det(A) |+h(X).

8.6 Variational inequality. Verify for positive random variables X

that

log E

(X) = sup



(log X) − D(Q||P)



, (8.93)

where E

(X) =



xP(x) and D(Q||P) =



Q(x) log

Q(x)

P(x)

and the supremum is over all Q(x)≥0,



Q(x) =1. It is enough

to extremize J(Q)=E

ln X−D(Q||P)+λ(



Q(x)−1).

258 DIFFERENTIAL ENTROPY

8.7 Differential entropy bound on discrete entropy.LetX beadis-

crete random variable on the set

X ={a

,...} with Pr(X =

) = p

. Show that

H(p

,...) ≤

log(2πe)





∞



i=1

−



∞



i=1







(8.94)

Moreover, for every permutation σ ,

H(p

,...) ≤

log(2πe)





∞



i=1

σ(i)

−



∞



i=1

σ(i)







(8.95)

[Hint: Construct a random variable X



such that Pr(X



= i) = p

Let U be a uniform (0,1] random variable and let Y = X



+ U ,

where X



and U are independent. Use the maximum entropy bound

on Y to obtain the bounds in the problem. This bound is due to

Massey (unpublished) and Willems (unpublished).]

8.8 Channel with uniformly distributed noise. Consider a additive

channel whose input alphabet

X ={0,±1,±2} and whose output

Y = X+Z,whereZ is distributed uniformly over the interval

[−1, 1]. Thus, the input of the channel is a discrete random vari-

able, whereas the output is continuous. Calculate the capacity C =

max

p(x)

I(X;Y) of this channel.

8.9 Gaussian mutual information. Suppose that (X,Y,Z) are jointly

Gaussian and that X → Y → Z forms a Markov chain. Let X and

Y have correlation coefﬁcient ρ

and let Y and Z have correlation

coefﬁcient ρ

.FindI(X;Z).

8.10 Shape of the typical set.LetX

be i.i.d. ∼ f(x),where

f(x)= ce

−x

Let h =−



f ln f . Describe the shape (or form) or the typical set

(n)



={x

∈ R

: f(x

) ∈ 2

−n(h±)

8.11 Nonergodic Gaussian process. Consider a constant signal V in

the presence of iid observational noise {Z

}. Thus, X

= V + Z

where V ∼ N(0,S) and Z

are iid ∼ N(0,N). Assume that V and

} are independent.

(a) Is {X

} stationary?

HISTORICAL NOTES 259

(b) Find lim

n−→ ∞



i=1

. Is the limit random?

(d) Find the least-mean-squared error predictor

n+1

),andﬁnd

∞

= lim

n−→ ∞

− X

)

(e) Does {X

} have an AEP? That is, does −

log f(X

) −→ h?

HISTORICAL NOTES

Differential entropy and discrete entropy were introduced in Shannon’s

original paper [472]. The general rigorous deﬁnition of relative entropy

and mutual information for arbitrary random variables was developed by

Kolmogorov [319] and Pinsker [425], who deﬁned mutual information as

sup

P,Q

I([X]

;[Y ]

), where the supremum is over all ﬁnite partitions P

and Q.

CHAPTER 9

GAUSSIAN CHANNEL

The most important continuous alphabet channel is the Gaussian channel

depicted in Figure 9.1. This is a time-discrete channel with output Y

time i,whereY

is the sum of the input X

and the noise Z

. The noise

is drawn i.i.d. from a Gaussian distribution with variance N. Thus,

= X

+ Z

∼ N(0,N). (9.1)

The noise Z

is assumed to be independent of the signal X

. This channel

is a model for some common communication channels, such as wired and

wireless telephone channels and satellite links. Without further conditions,

the capacity of this channel may be inﬁnite. If the noise variance is zero,

the receiver receives the transmitted symbol perfectly. Since X can take

on any real value, the channel can transmit an arbitrary real number with

no error.

If the noise variance is nonzero and there is no constraint on the input,

we can choose an inﬁnite subset of inputs arbitrarily far apart, so that

they are distinguishable at the output with arbitrarily small probability of

error. Such a scheme has an inﬁnite capacity as well. Thus if the noise

variance is zero or the input is unconstrained, the capacity of the channel

is inﬁnite.

The most common limitation on the input is an energy or power constraint.

We assume an average power constraint. For any codeword (x

,...,x

)

transmitted over the channel, we require that



i=1

≤ P. (9.2)

This communication channel models many practical channels, includ-

ing radio and satellite links. The additive noise in such channels may be

due to a variety of causes. However, by the central limit theorem, the

Elements of Information Theory, Second Edition, By Thomas M. Cover and Joy A. Thomas

261

262 GAUSSIAN CHANNEL

FIGURE 9.1. Gaussian channel.

cumulative effect of a large number of small random effects will be

approximately normal, so the Gaussian assumption is valid in a large

number of situations.

We ﬁrst analyze a simple suboptimal way to use this channel. Assume

that we want to send 1 bit over the channel in one use of the channel.

Given the power constraint, the best that we can do is to send one of

two levels, +

√

P or −

√

P . The receiver looks at the corresponding Y

received and tries to decide which of the two levels was sent. Assuming

that both levels are equally likely (this would be the case if we wish to

send exactly 1 bit of information), the optimum decoding rule is to decide

that +

√

P was sent if Y>0 and decide −

√

P was sent if Y<0. The

probability of error with such a decoding scheme is

Pr(Y < 0|X =+

√

P)+

Pr(Y > 0|X =−

√

P) (9.3)

Pr(Z < −

√

P |X =+

√

P)+

Pr(Z >

√

P |X =−

√

P) (9.4)

= Pr(Z >

√

P) (9.5)

= 1 −





P/N



, (9.6)

where (x) is the cumulative normal function

(x) =



−∞

√

2π

−t

dt. (9.7)

Using such a scheme, we have converted the Gaussian channel into a dis-

crete binary symmetric channel with crossover probability P

. Similarly,

by using a four-level input signal, we can convert the Gaussian channel

9.1 GAUSSIAN CHANNEL: DEFINITIONS 263

into a discrete four-input channel. In some practical modulation schemes,

similar ideas are used to convert the continuous channel into a discrete

channel. The main advantage of a discrete channel is ease of processing

of the output signal for error correction, but some information is lost in

the quantization.

9.1 GAUSSIAN CHANNEL: DEFINITIONS

We now deﬁne the (information) capacity of the channel as the maxi-

mum of the mutual information between the input and output over all

distributions on the input that satisfy the power constraint.

Deﬁnition The information capacity of the Gaussian channel with

power constraint P is

C = max

f(x):EX

≤P

I(X;Y). (9.8)

We can calculate the information capacity as follows: Expanding

I(X;Y),wehave

I(X;Y) = h(Y ) − h(Y |X) (9.9)

= h(Y ) − h(X + Z|X) (9.10)

= h(Y ) − h(Z|X) (9.11)

= h(Y ) − h(Z), (9.12)

since Z is independent of X.Now,h(Z) =

log 2πeN.Also,

= E(X + Z)

= EX

+ 2EXEZ + EZ

= P + N, (9.13)

since X and Z are independent and EZ = 0. Given EY

= P + N ,the

entropy of Y is bounded by

log 2πe(P + N) by Theorem 8.6.5 (the

normal maximizes the entropy for a given variance).

Applying this result to bound the mutual information, we obtain

I(X;Y) = h(Y ) − h(Z) (9.14)

≤

log 2πe(P + N) −

log 2πeN (9.15)

log



1 +



. (9.16)

264 GAUSSIAN CHANNEL

Hence, the information capacity of the Gaussian channel is

C = max

≤P

I(X;Y) =

log



1 +



, (9.17)

and the maximum is attained when X ∼

N(0,P).

We will now show that this capacity is also the supremum of the rates

achievable for the channel. The arguments are similar to the arguments

for a discrete channel. We will begin with the corresponding deﬁnitions.

Deﬁnition An (M, n) code for the Gaussian channel with power con-

straint P consists of the following:

1. An index set {1, 2,...,M}.

2. An encoding function x : {1, 2,...,M}→

, yielding codewords

(1), x

(2),...,x

(M), satisfying the power constraint P ;thatis,

for every codeword



i=1

(w) ≤ nP , w = 1, 2,...,M. (9.18)

3. A decoding function

g :

→{1, 2,...,M}. (9.19)

The rate and probability of error of the code are deﬁned as in Chapter 7

for the discrete case. The arithmetic average of the probability of error is

deﬁned by

(n)



. (9.20)

Deﬁnition ArateR is said to be achievable for a Gaussian channel

with a power constraint P if there exists a sequence of (2

,n) codes

with codewords satisfying the power constraint such that the maximal

probability of error λ

(n)

tends to zero. The capacity of the channel is the

supremum of the achievable rates.

Theorem 9.1.1 The capacity of a Gaussian channel with power con-

straint P and noise variance N is

C =

log



1 +



bits per transmission. (9.21)