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

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

15.6 BROADCAST CHANNEL 565

15.6.3 Capacity Region for the Degraded Broadcast Channel

We now consider sending independent information over a degraded broad-

cast channel at rate R

to Y

and rate R

to Y

Theorem 15.6.2 The capacity region for sending independent infor-

mation over the degraded broadcast channel X → Y

→ Y

is the convex

hull of the closure of all (R

) satisfying

≤ I(U;Y

), (15.210)

≤ I(X;Y

|U) (15.211)

for some joint distribution p(u)p(x|u)p(y

|x), where the auxiliary ran-

dom variable U has cardinality bounded by |

U|≤min{|X|, |Y

|, |Y

|}.

Proof: (The cardinality bounds for the auxiliary random variable U are

derived using standard methods from convex set theory and are not dealt

with here.) We ﬁrst give an outline of the basic idea of superposition

coding for the broadcast channel. The auxiliary random variable U will

serve as a cloud center that can be distinguished by both receivers Y

and Y

. Each cloud consists of 2

codewords X

distinguishable by the

receiver Y

. The worst receiver can only see the clouds, while the better

receiver can see the individual codewords within the clouds. The formal

proof of the achievability of this region uses a random coding argument:

Fix p(u) and p(x|u).

Random codebook generation: Generate 2

independent codewords

of length n, U(w

), w

∈{1, 2,...,2

}, according to



i=1

p(u

).For

each codeword U(w

), generate 2

independent codewords X(w

)

according to



i=1

p(x

)).Hereu(i) plays the role of the cloud

center understandable to both Y

and Y

, while x(i, j ) is the j th satellite

codeword in the ith cloud.

Encoding: To send the pair (W

), send the corresponding codeword

X(W

Decoding: Receiver 2 determines the unique

such that (U(

) ∈ A

(n)



. If there are none such or more than one such, an error is

declared.

Receiver 1 looks for the unique (

) such that (U(

), X(

) ∈ A

(n)



. If there are none such or more than one such, an error is

declared.

Analysis of the probability of error: By the symmetry of the code gen-

eration, the probability of error does not depend on which codeword was

566 NETWORK INFORMATION THEORY

sent. Hence, without loss of generality, we can assume that the mes-

sage pair (W

) = (1, 1) was sent. Let P(·) denote the conditional

probability of an event given that (1,1) was sent.

Since we have essentially a single-user channel from U to Y

, we will

be able to decode the U codewords with a low probability of error if

<I(U;Y

). To prove this, we deﬁne the events

={(U(i), Y

) ∈ A

(n)



}. (15.212)

Then the probability of error at receiver 2 is

(n)

(2) = P(E

Y 1



i=1

) (15.213)

≤ P(E

Y 1

) +



i=1

P(E

) (15.214)

≤  + 2

−n(I (U;Y

)−2)

(15.215)

≤ 2 (15.216)

if n is large enough and R

<I(U;Y

), where (15.215) follows from the

AEP. Similarly, for decoding for receiver 1, we deﬁne the events

={(U(i), Y

) ∈ A

(n)



}, (15.217)

Yij

={(U(i), X(i, j ), Y

) ∈ A

(n)



}, (15.218)

where the tilde refers to events deﬁned at receiver 1. Then we can bound

the probability of error as

(n)

(1) = P





Y 1



Y 11



i=1



j=1

Y 1j





(15.219)

≤ P(

Y 1

) + P(

Y 11

) +



i=1

) +



j=1

Y 1j

). (15.220)

By the same arguments as for receiver 2, we can bound P(

) ≤

−n(I (U;Y

)−3)

. Hence, the third term goes to 0 if R

<I(U;Y

).But

by the data-processing inequality and the degraded nature of the chan-

nel, I(U;Y

) ≥ I(U;Y

), and hence the conditions of the theorem imply

15.6 BROADCAST CHANNEL 567

that the third term goes to 0. We can also bound the fourth term in the

probability of error as

Y 1j

) = P((U(1), X(1,j),Y

) ∈ A

(n)



) (15.221)



(U,X,Y

)∈A

(n)



P((U(1), X(1,j),Y

)) (15.222)



(U,X,Y

)∈A

(n)



P(U(1))P (X(1,j)|U(1))P (Y

|U(1)) (15.223)

≤



(U,X,Y

)∈A

(n)



−n(H (U )−)

−n(H (X|U)−)

−n(H (Y

|U)−)

(15.224)

≤ 2

n(H (U,X,Y

)+)

−n(H (U )−)

−n(H (X|U)−)

−n(H (Y

|U)−)

(15.225)

= 2

−n(I (X;Y

|U)−4)

. (15.226)

Hence, if R

<I(X;Y

|U), the fourth term in the probability of error

goes to 0. Thus, we can bound the probability of error

(n)

(1) ≤  +  + 2

−n(I (U;Y

)−3)

+ 2

−n(I (X;Y

|U)−4)

(15.227)

≤ 4 (15.228)

if n is large enough and R

<I(U;Y

) and R

<I(X;Y

|U). The above

bounds show that we can decode the messages with total probability

of error that goes to 0. Hence, there exists a sequence of good ((2

), n) codes C

∗

with probability of error going to 0. With this, we com-

plete the proof of the achievability of the capacity region for the degraded

broadcast channel. Gallager’s proof [225] of the converse is outlined in

Problem 15.11.



So far we have considered sending independent information to each

receiver. But in certain situations, we wish to send common information

to both receivers. Let the rate at which we send common information be

. Then we have the following obvious theorem:

Theorem 15.6.3 If the rate pair (R

) is achievable for a broadcast

channel with independent information, the rate triple (R

− R

−

) withacommonrateR

is achievable, provided that R

≤

min(R

568 NETWORK INFORMATION THEORY

In the case of a degraded broadcast channel, we can do even better.

Since by our coding scheme the better receiver always decodes all the

information that is sent to the worst receiver, one need not reduce the

amount of information sent to the better receiver when we have common

information. Hence, we have the following theorem:

Theorem 15.6.4 If the rate pair (R

) is achievable for a degraded

broadcast channel, the rate triple (R

− R

) is achievable for the

channel with common information, provided that R

We end this section by considering the example of the binary symmetric

broadcast channel.

Example 15.6.5 Consider a pair of binary symmetric channels with

parameters p

and p

that form a broadcast channel as shown in Fig-

ure 15.27. Without loss of generality in the capacity calculation, we can

recast this channel as a physically degraded channel. We assume that

. Then we can express a binary symmetric channel with

parameter p

as a cascade of a binary symmetric channel with parameter

with another binary symmetric channel. Let the crossover probability

of the new channel be α. Then we must have

(1 − α) + (1 − p

)α = p

(15.229)

FIGURE 15.27. Binary symmetric broadcast channel.

15.6 BROADCAST CHANNEL 569

1 − b

− a

1 − a

−

1 −

FIGURE 15.28. Physically degraded binary symmetric broadcast channel.

α =

− p

1 − 2p

. (15.230)

We now consider the auxiliary random variable in the deﬁnition of the

capacity region. In this case, the cardinality of U is binary from the bound

of the theorem. By symmetry, we connect U to X by another binary

symmetric channel with parameter β, as illustrated in Figure 15.28.

We can now calculate the rates in the capacity region. It is clear by sym-

metry that the distribution on U that maximizes the rates is the uniform

distribution on {0, 1},sothat

I(U;Y

) = H(Y

) − H(Y

|U) (15.231)

= 1 −H(β ∗ p

), (15.232)

where

β ∗ p

= β(1 − p

) + (1 − β)p

. (15.233)

Similarly,

I(X;Y

|U) = H(Y

|U)− H(Y

|X, U ) (15.234)

= H(Y

|U)− H(Y

|X) (15.235)

= H(β ∗p

) − H(p

), (15.236)

where

β ∗ p

= β(1 − p

) + (1 − β)p

. (15.237)

Plotting these points as a function of β, we obtain the capacity region

in Figure 15.29. When β = 0, we have maximum information transfer

to Y

[i.e., R

= 1 −H(p

) and R

= 0]. When β =

, we have maxi-

mum information transfer to Y

[i.e., R

= 1 −H(p

)] and no information

transfer to Y

. These values of β give us the corner points of the rate

region.

570 NETWORK INFORMATION THEORY

−

(

)

−

(

)

FIGURE 15.29. Capacity region of binary symmetric broadcast channel.

(0,

)

′

(0,

−

)

FIGURE 15.30. Gaussian broadcast channel.

Example 15.6.6 (Gaussian broadcast channel ) The Gaussian broad-

cast channel is illustrated in Figure 15.30. We have shown it in the case

where one output is a degraded version of the other output. Based on

the results of Problem 15.10, it follows that all scalar Gaussian broadcast

channels are equivalent to this type of degraded channel.

= X + Z

, (15.238)

= X + Z

= Y

+ Z



, (15.239)

where Z

∼ N(0,N

) and Z



∼ N(0,N

− N

Extending the results of this section to the Gaussian case, we can show

that the capacity region of this channel is given by



αP



(15.240)



(1 − α)P

αP + N



, (15.241)

15.7 RELAY CHANNEL 571

where α may be arbitrarily chosen (0 ≤ α ≤ 1). The coding scheme that

achieves this capacity region is outlined in Section 15.1.3.

15.7 RELAY CHANNEL

The relay channel is a channel in which there is one sender and one

receiver with a number of intermediate nodes that act as relays to help

the communication from the sender to the receiver. The simplest relay

channel has only one intermediate or relay node. In this case the channel

consists of four ﬁnite sets

X, X

, Y,andY

and a collection of probability

mass functions p(y, y

|x, x

) on Y × Y

, one for each (x, x

) ∈ X × X

The interpretation is that x is the input to the channel and y is the output

of the channel, y

is the relay’s observation, and x

is the input symbol

chosen by the relay, as shown in Figure 15.31. The problem is to ﬁnd the

capacity of the channel between the sender X and the receiver Y .

The relay channel combines a broadcast channel (X to Y and Y

)anda

multiple-access channel (X and X

to Y ). The capacity is known for the

special case of the physically degraded relay channel. We ﬁrst prove an

outer bound on the capacity of a general relay channel and later establish

an achievable region for the degraded relay channel.

Deﬁnition A (2

,n) code for a relay channel consists of a set of

integers

W ={1, 2,...,2

}, an encoding function

X : {1, 2,...,2

}→X

, (15.242)

a set of relay functions {f

}

i=1

such that

= f

,...,Y

1i−1

), 1 ≤ i ≤ n, (15.243)

and a decoding function,

g :

→{1, 2,...,2

}. (15.244)

FIGURE 15.31. Relay channel.

572 NETWORK INFORMATION THEORY

Note that the deﬁnition of the encoding functions includes the nonan-

ticipatory condition on the relay. The relay channel input is allowed to

depend only on the past observations y

,...,y

1i−1

. The channel is

memoryless in the sense that (Y

) depends on the past only through

the current transmitted symbols (X

). Thus, for any choice p(w),

w ∈

W, and code choice X : {1, 2,...,2

}→X

and relay functions

}

i=1

, the joint probability mass function on W × X

× X

× Y

is given by

p(w, x, x

, y, y

) = p(w)



i=1

p(x

|w)p(x

,...,y

1i−1

)

× p(y

). (15.245)

If the message w ∈ [1, 2

] is sent, let

λ(w) = Pr{g(Y) = w|w sent} (15.246)

denote the conditional probability of error. We deﬁne the average proba-

bility of error of the code as

(n)



λ(w). (15.247)

The probability of error is calculated under the uniform distribution over

the codewords w ∈{1,...,2

}.TherateR is said to be achievable

by the relay channel if there exists a sequence of (2

,n) codes with

(n)

→ 0. The capacity C of a relay channel is the supremum of the set

of achievable rates.

We ﬁrst give an upper bound on the capacity of the relay channel.

Theorem 15.7.1 For any relay channel (

X × X

,p(y,y

|x, x

), Y ×

), the capacity C is bounded above by

C ≤ sup

p(x,x

)

min

{

I(X,X

;Y),I(X;Y, Y

)

}

. (15.248)

Proof: The proof is a direct consequence of a more general max-ﬂow

min-cut theorem given in Section 15.10.



This upper bound has a nice max-ﬂow min-cut interpretation. The ﬁrst

term in (15.248) upper bounds the maximum rate of information transfer

15.7 RELAY CHANNEL 573

from senders X and X

to receiver Y . The second terms bound the rate

from X to Y and Y

We now consider a family of relay channels in which the relay receiver

is better than the ultimate receiver Y in the sense deﬁned below. Here the

max-ﬂow min-cut upper bound in the (15.248) is achieved.

Deﬁnition The relay channel (

X × X

,p(y,y

|x, x

), Y × Y

) is said

to be physically degraded if p(y, y

|x, x

) can be written in the form

p(y, y

|x, x

) = p(y

|x, x

)p(y|y

). (15.249)

Thus, Y is a random degradation of the relay signal Y

For the physically degraded relay channel, the capacity is given by the

following theorem.

Theorem 15.7.2 The capacity C of a physically degraded relay channel

is given by

C = sup

p(x,x

)

min

{

I(X,X

;Y),I(X;Y

)

}

, (15.250)

where the supremum is over all joint distributions on

X × X

Proof:

Converse: The proof follows from Theorem 15.7.1 and by degradedness,

since for the degraded relay channel, I(X;Y, Y

) = I(X;Y

Achievability: The proof of achievability involves a combination

of the following basic techniques: (1) random coding, (2) list codes,

(3) Slepian–Wolf partitioning, (4) coding for the cooperative multiple-

access channel, (5) superposition coding, and (6) block Markov encoding

at the relay and transmitter. We provide only an outline of the proof.

Outline of achievability: We consider B blocks of transmission, each of

n symbols. A sequence of B − 1 indices, w

∈{1,...,2

},i = 1, 2,...,

B − 1, will be sent over the channel in nB transmissions. (Note that as

B →∞for a ﬁxed n,therateR(B − 1)/B is arbitrarily close to R.)

We deﬁne a doubly indexed set of codewords:

C ={x(w|s),x

(s)} : w ∈{1, 2

},s ∈{1, 2

}, x ∈ X

, x

∈ X

(15.251)

We will also need a partition

S ={S

,...,S

} of W ={1, 2,...,2

} (15.252)

574 NETWORK INFORMATION THEORY

into 2

cells, with S

∩ S

= φ,i = j ,and∪S

= W. The partition will

enable us to send side information to the receiver in the manner of Slepian

and Wolf [502].

Generation of random code: Fix p(x

)p(x|x

First generate at random 2

i.i.d. n-sequences in X

, each

drawn according to p(x

) =



i=1

p(x

). Index them as x

(s), s ∈

{1, 2,...,2

}. For each x

(s), generate 2

conditionally independent

n-sequences x(w|s),w ∈{1, 2,...,2

}, drawn independently accord-

ing to p(x|x

(s)) =



i=1

p(x

(s)). This deﬁnes the random code-

book

C ={x(w|s),x

(s)}. The random partition S ={S

,...,S

} of

{1, 2,...,2

} is deﬁned as follows. Let each integer w ∈{1, 2,...,2

}

be assigned independently, according to a uniform distribution over the

indices s = 1, 2,...,2

, to cells S

Encoding: Let w

∈{1, 2,...,2

} be the new index to be sent in block

i,andlets

be deﬁned as the partition corresponding to w

i−1

(i.e., w

i−1

∈

). The encoder sends x(w

). The relay has an estimate

ˆw

i−1

of the

previous index w

i−1

. (This will be made precise in the decoding section.)

Assume that

ˆw

i−1

∈ S

ˆs

. The relay encoder sends x

(

ˆs

) in block i.

Decoding: We assume that at the end of block i − 1, the receiver

knows (w

,...,w

i−2

) and (s

,...,s

i−1

) and the relay knows (w

,...,w

i−1

) and consequently, (s

,...,s

). The decoding procedures

at the end of block i are as follows:

1. Knowing s

and upon receiving y

(i),therelay receiver estimates

the message of the transmitter

ˆw

= w if and only if there exists

a unique w such that (x(w|s

), x

), y

(i)) are jointly -typical.

Using Theorem 15.2.3, it can be shown that

ˆw

= w

with an arbi-

trarily small probability of error if

R<I(X;Y

) (15.253)

and n is sufﬁciently large.

2. The receiver declares that ˆs

= s was sent iff there exists one and

only one s such that (x

(s), y(i)) are jointly -typical. From Theo-

rem 15.2.1 we know that s

can be decoded with arbitrarily small

probability of error if

<I(X

;Y) (15.254)

and n is sufﬁciently large.