1

Distortion Bounds for Source Broadcast Problems
Lei Yu, Houqiang Li, Senior Member, IEEE, and Weiping Li, Fellow, IEEE

Abstract

arXiv:1601.05661v5 [] 18 Mar 2018

This paper investigates the joint source-channel coding problem of sending a memoryless source over a memoryless broadcast
channel. An inner bound and several outer bounds on the admissible distortion region are derived, which respectively generalize
and unify several existing bounds. As a consequence, we also obtain an inner bound and an outer bound for the degraded broadcast
channel case. When specialized to the Gaussian or binary source broadcast, the inner bound and outer bound not only recover
the best known inner bound and outer bound in the literature, but also generate some new results. Besides, we also extend the
inner bound and outer bounds to the Wyner-Ziv source broadcast problem, i.e., source broadcast with side information available
at decoders. Some new bounds are obtained when specialized to the Wyner-Ziv Gaussian and Wyner-Ziv binary cases.
Index Terms
Joint source-channel coding (JSCC), hybrid coding, broadcast, Wyner-Ziv, side information, multivariate covering/packing,
network information theory.

I. I NTRODUCTION
As stated in Shannon’s source-channel separation theorem [2], cascading source coding and channel coding does not lose
the optimality for point-to-point communication systems. This separation theorem does not only suggest a simple system
architecture in which source coding and channel coding are separated by a universal digital interface, but also guarantees
that such architecture does not incur any asymptotic performance loss. Consequently, it forms the basis of the architecture of
today’s communication systems. However, for many multi-user communication systems, the optimality of such a separation
does not hold any more [3], [4]. Therefore, an increasing amount of literature focus on joint source-channel coding (JSCC) in
multi-user setting.
One of the most classical problems in this area is JSCC of transmitting a Gaussian source over a K-user Gaussian broadcast
channel with average transmitting power constrained. Goblick [3] observed that when the source bandwidth and the channel
bandwidth are matched (i.e., one channel use per source sample) linear uncoded transmission (symbol-by-symbol mapping)
is optimal. However, the optimality of such a simple linear scheme cannot be extended to the bandwidth mismatch case. One
way to approximately characterize the admissible distortion region is finding its inner bound and outer bound. For inner bound,
analog coding or hybrid coding has been studied in a vast body of literature [4], [5], [6], [7]. For 2-user Gaussian broadcast
communication, Prabhakaran et al. [7] gave the best known inner bound, which is achieved by a hybrid digital-analog (HDA)
scheme. On the other hand, Reznic et al. [8] derived a non-trivial outer bound (tighter than the single-user bound) for 2-user
Gaussian broadcast problem with bandwidth expansion (i.e., more than one channel uses per source sample) by introducing
an auxiliary random variable (or remote source). Tian et al. [9] extended this outer bound to the K-user case by introducing
more than one auxiliary random variables. Similar to the results of Reznic et al., the outer bound given by Tian et al. is
also nontrivial only for the bandwidth expansion case [10]. Beyond broadcast communication, Minero et al. [15] considered
sending memoryless correlated sources over a memoryless multi-access channel, and derived an inner bound using a unified
framework of hybrid coding. Lee et al. [20] derived a unified achievability result for memoryless network communication.
Besides, in [6], [17], [18] the Wyner-Ziv source communication problem was investigated, in which side information
correlated with the source is available at decoder(s). Shamai et al. [6] studied the problem of sending a Wyner-Ziv source
over a point-to-point channel, and proved that for such communication system, the separate coding (which cascades Wyner-Ziv
coding with channel coding) does not incur any loss of optimality. Nayak et al. [17] and Gao et al. [18] investigated the
Wyner-Ziv source broadcast problem, and obtained the single-user outer bound by simply applying the cut-set bound (the
minimum distortion achieved in point-to-point setting) for each receiver.
In this paper, we consider JSCC of transmitting a memoryless source over a K-user memoryless broadcast channel, and
give an inner bound and two outer bounds on the admissible distortion region. The inner bound is derived by using a unified
framework of hybrid coding inspired by [15], and the outer bounds are derived by introducing auxiliary random variables
at the sender side or at the receiver sides. The proof method of introducing auxiliary random variables (or remote sources)
at the sender side can be found in [8] and [9]. However, to the best of our knowledge, it is the first time to prove outer
bounds by introducing auxiliary random variables (or remote channels) at the receiver sides. Our bounds are generalizations
and unifications of several existing bounds in the literature. Besides, as a consequence, we also obtain an inner bound and an
outer bound for the degraded broadcast channel case. When specialized to the Gaussian source broadcast and binary source
broadcast, our inner bound could recover the best known performance achieved by hybrid coding, and our outer bound could
The authors are all with the Department of Electronic Engineering and Information Science, University of Science and Technology of China, Hefei 230027,
China (e-mail: yulei@ustc.edu.cn, lihq@ustc.edu.cn, wpli@ustc.edu.cn). The material in this paper was presented in part at IEEE ISIT 2016 [1].

2

Y1n

Sn

Encoder

Xn

Decoder 1



PY[1:K ] | X
n
K

Y

Decoder K

Sˆ1n

SˆKn

Fig. 1. Source broadcast system.

recover the best known outer bounds given by Tian et al. [9] and Khezeli et al. [11]. Moreover, for these cases, our bounds can
be also used to generate some new results. Besides, we also extend the inner bound and outer bounds to the Wyner-Ziv source
broadcast problem, i.e., source broadcast with side information at decoders. When specialized to the Wyner-Ziv Gaussian and
binary cases, our bounds reduce to some new bounds.
The rest of this paper is organized as follows. Section II summarizes basic notations, definitions and preliminaries, and
formulates the problem. Section III gives the main results for the source broadcast problem, including the discrete, discrete
and degraded, binary, and Gaussian cases. Section IV extends the results to the Wyner-Ziv source broadcast problem. Finally,
Section V gives the concluding remarks.
II. P ROBLEM F ORMULATION AND P RELIMINARIES
A. Notation
Throughout this paper, we follow the notation in [16]. For example, for a discrete random variable X ∼ pX on alphabet X
and  ∈ (0, 1), the set of -typical n-sequences xn (or the typical set in short) is defined as


|{i : xi = x}|
(n)
n
− pX (x) ≤ pX (x), ∀x ∈ X .
T (X) = x :
n
(n)

(n)

When it is clear from the context, we will use T to denote T (X).
In addition, we use XA to denote the vector (Xj : j ∈ A), use [i : j] to denote the set {bic , bic + 1, · · · , bjc}, and use 1
to denote an all-one vector (similarly, use 2 to denote an all-2 vector). We say vector m[1:N ] is smaller than vector m0[1:N ] if
mj = m0j for k < j ≤ K and mk < m0k for some k. For two vectors mI and m0I , we say mI is component-wise unequal
to m0I , if mi 6= m0i for all i ∈ I, and denote it as mI < m0I . Besides, we use 1 {A} to denote the indicator function of an
event A, i.e.,
(
1, if A is true;
1 {A} =
0, if A is false.
B. Problem Formulation
Consider the source broadcast system shown in Fig. 1. A discrete memoryless source (DMS) S n is first coded into X n using
a source-channel code, then transmitted to K receivers through a discrete memoryless broadcast channel (DM-BC) pY[1:K] |X ,
and finally, the receiver k produces a source reconstruction Ŝkn from the received signal Ykn .
Definition 1 (Source). A discrete memoryless source (DMS) is specified by a probability mass function (pmf) pS on a finite
alphabet S. The DMS pS generates an i.i.d. random process {Si } with Si ∼ pS .
Definition 2 (Broadcast Channel). A K-user discrete memoryless broadcast channel (DM-BC) is specified by a collection of
conditional pmfs pY[1:K] |X on a finite output alphabet Y1 × · · · × YK for each x in a finite input alphabet X .
Definition 3 (Degraded Broadcast Channel). A DM-BC pY[1:K] |X is stochastically degraded (or simply degraded) if there exists
a random vector Ỹ[1:K] such that pỸk |X = pYk |X , 1 ≤ k ≤ K (i.e., Ỹ[1:K] has the same conditional marginal pmfs as Y[1:K]
given X), and X → ỸK → ỸK−1 → · · · → Ỹ1 1 form a Markov chain. In addition, as a special case, if X → YK → YK−1 →
· · · → Y1 , i.e., Ỹk = Yk , 1 ≤ k ≤ K, then pY[1:K] |X is physically degraded.
Definition 4. An n-length source-channel code is defined by a encoding function xn : S n 7→ X n and K decoding functions
ŝk : Ykn 7→ Sˆkn , 1 ≤ k ≤ K, where Sˆk is the alphabet of source reconstruction at the receiver k.
1 For

brevity, the Markov chain is assumed in this direction.This differs from that in the conference version [1].

3

For any n-length source-channel code, the induced distortion is defined as
n




1X
Edk S n , Ŝkn =
Edk St , Ŝk,t ,
n t=1

(1)

for 1 ≤ k ≤ K, where dk (s, ŝk ) : S × Sˆk 7→ [0, +∞] is a distortion measure function for the receiver k.
Definition 5. For transmitting a source S over a channel pY[1:K] |X , if there exists a sequence of source-channel codes such
that


lim sup Edk S n , Ŝkn ≤ Dk ,
(2)
n→∞

then we say that the distortion tuple D[1:K] is achievable.
Definition 6. For transmitting a source S over a channel pY[1:K] |X , the admissible distortion region is defined as

D , D[1:K] : D[1:K] is achievable .

(3)

The admissible distortion region R only depends on the marginal distributions of pY[1:K] |X , hence for the stochastically
degraded channel case, it suffices to only consider the corresponding physically degraded channel case.
In addition, Shannon’s source-channel separation theorem shows that the minimum distortion for transmitting a source over
a point-to-point channel satisfies
Rk (Dk ) = Ck ,
(4)
where Rk (· ) is the rate-distortion function of the source with the distortion measure dk , and Ck is the capacity for the receiver
k. Therefore, the optimal distortion (Shannon limit) is
Dk∗ = Rk−1 (Ck ) .

(5)


D ⊆ D∗ , D[1:K] : Dk ≥ Dk∗ , 1 ≤ k ≤ K ,

(6)

Obviously,
where D∗ is named single-user outer bound.
In the system above, the source bandwidth and channel bandwidth are matched. In this paper, we also consider the
communication system with bandwidth mismatch, whereby m samples of a DMS are transmitted through n uses of a DM-BC.
n
.
For this case, the bandwidth mismatch factor is defined as b = m
C. Multivariate Covering/Packing Lemma
We first introduce the following multivariate covering and packing lemmas which are important in the achievability part in
this work.
Let (U, V[0:k] ) ∼ pU,V[0:k] . Let (U n , V0n ) ∼ pU n ,V0n be a random vector sequence. For each j ∈ [1Q: k], let Aj ⊆
[1 : j − 1]. Assume Aj satisfies if i ∈ Aj , then Ai ⊆ Aj . For each j ∈ [1 : k] and each mAj ∈ i∈Aj [1 : 2nri ],
let Vjn (mAj , mj ), mj ∈ [1 : 2nrj ], be pairwise conditionally independent random sequences, each distributed according to
Q
n
i=1 pVj |VAj ,V0 (vj,i |vAj ,i (mAj ), v0,i ). Hence for each j ∈ [1 : k], Aj ∪ {0} denotes the index set of the random variables on
which the codeword Vjn is superposed. Based on the notations above, we have the following multivariate covering and packing
lemmas.


(n)
Lemma 1 (Multivariate Covering Lemma). Let 0 < . If limn→∞ P (U n , V0n ) ∈ T0
= 1, then there exists δ() that tends
to zero as  → 0 such that


n
lim P (U n , V0n , V[1:k]
(m[1:k] )) ∈ T(n) for some m[1:k] = 1,
(7)
n→∞

P
P
if j∈J rj > j∈J H Vj |VAj V0 − H (VJ |V0 U ) + δ() for all J ⊆ [1 : k] such that J 6= ∅ and if j ∈ J , then Aj ⊆ J .
Lemma 2 (Multivariate Packing Lemma). There exists δ() that tends to zero as  → 0 such that


n
lim P (U n , V0n , V[1:k]
(m[1:k] )) ∈ T(n) for some m[1:k] = 0,
(8)
n→∞

P
P
if j∈J rj < j∈J H Vj |VAj V0 − H (VJ |V0 U ) − δ() for some J ⊆ [1 : k] such that J 6= ∅ and if j ∈ J , then Aj ⊆ J .
Note that all the existing covering and packing lemmas such as [16, Lem. 8.2] and [19, Lem. 4], involve only single-layer
codebook. Our multivariate covering and packing lemmas generalize them to the case of multilayer codebooks.

4

5

6

7

V5

V6

V7

2

3

4

V2

V3

V4

1

V1

(a)

(b)

Fig. 2. (a) The inclusion relation of the sets Gj , 1 ≤ j ≤ N with K = 3; (b) The structure of the codebook for the unified hybrid coding with K = 3.

III. S OURCE B ROADCAST
A. Discrete Memoryless Broadcast
Now, we bound the distortion region for the source broadcast communication. To write the inner bound, for 1 ≤ j ≤ N ,
2K − 1, we first introduce an auxiliary random variable Vj for each of the 2K − 1 nonempty subsets Gj ⊆ [1 : K], and
let Vj denote a common message transmitted from the sender to all the receivers in Gj . The Vj corresponds to a subset Gj
by the following one-to-one mapping. Sort all the nonempty subsets Gj ⊆ [1 : K] in the decreasing order2 . Map the jth
subset in the resulting sequence to j. Obviously this mapping is one-to-one corresponding. For example, if K = 3, then
G1 = {1, 2, 3} , G2 = {2, 3} , G3 = {1, 3} , G4 = {1, 2} , G5 = {3} , G6 = {2} , G7 = {1}; see Fig. 2.
Besides, let
Aj , {i ∈ [1 : N ] : Gj $ Gi } , 1 ≤ j ≤ N,

(9)

Bk , {i ∈ [1 : N ] : k ∈ Gi } , 1 ≤ k ≤ K.

(10)

If K = 3, then A1 = ∅, A2 = {1} , A3 = {1} , A4 = {1} , A5 = {1, 2, 3} , A6 = {1, 2, 4} , A7 = {1, 3, 4} and B1 =
{1, 3, 4, 7} , B2 = {1, 2, 4, 6} , B3 = {1, 2, 3, 5}. Later we will show that Aj and Bk respectively correspond to the index set
of the random variables on which the codeword Vjn is superposed, and the index set of decodable codewords Vjn ’s for the
receiver k in the proposed hybrid coding scheme; see Appendix C-A. The decoder k is able to recover correctly the VBnk with
probability approaching 1 as n → ∞. In addition, it is easy to verify that if j ∈ Bk , then Aj ⊆ Bk . It means that the proposed
codebook satisfies that if the information Vjn can be recovered correctly by the receiver k (i.e., j ∈ Bk ), then VAnj can also be
recovered correctly by it.
Based on the notations above, we define a distortion region (inner bound)
n

D(i) = D[1:K] : ∃pV[1:N ] |S , r[1:N ] , x v[1:N ] , s , ŝk (vBk , yk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
X
X

rj >
H Vj |VAj − H (VJ |S)
j∈J

j∈J

for all J ⊆ [1 : N ] s.t.J =
6 ∅ and if j ∈ J , then Aj ⊆ J ,
X
X

rj <
H Vj |VAj − H (VJ c |Yk VJ )
j∈J c

j∈J c

o
for all 1 ≤ k ≤ K and for all J ⊆ Bk s.t.J c , Bk \J 6= ∅ and if j ∈ J , then Aj ⊆ J .

(11)

Besides, for any positive integer L, define a distortion region (outer bound achieved by introducing auxiliary random variables
at the sender)
n
(o)
D1 = D[1:K] : ∃pŜ[1:K] |S s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
and for any pU[1:L] |S , one can find pỸ[1:K] Ũ[1:L] X satisfying




o
I ŜA ; UB |UC ≤ I YA ; ŨB |ŨC ỸA for any A ⊆ [1 : K] , B, C ⊆ [1 : L] ,

(12)

2 We say a set G is larger than another H if |G| > |H|, or |G| = |H| and there exists some 1 ≤ i ≤ |G| such that G [i] > H [i] and G [l] = H [l] for all
1 ≤ l ≤ i − 1, where G [i] (or H [i]) denotes the ith largest element in G (or H).

5

Y1n
Sn

Source
Encoder

V[1:n N ] ( M [1:N ] )

n
x(v[1:N ] , s ) X

PY[1:K ] | X

Channel
Decoder 1


YKn

Channel
Decoder K

Vn1 ( Mˆ (1)1 )

VnK ( Mˆ ( KK ) )

sˆ1 (v1 , y1 )

sˆK (vK , yK )

Sˆ1n

SˆKn

Fig. 3. A unified hybrid coding used to prove the inner bound of Theorem 1.

and another distortion region (outer bound achieved by introducing auxiliary random variables at receivers)
n
(o)
D2 = D[1:K] : ∃pX , ŝk (ỹk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
and for any pU[1:L] |Y[1:K] , one can find pỸ[1:K] |S pŨ[1:L] |Ỹ[1:K] satisfying


o
I S; ỸB ŨB0 |ỸC ŨC 0 ≤ I (X; YB UB0 |YC UC 0 ) for any B, C ⊆ [1 : K] , B 0 , C 0 ⊆ [1 : L] .

(13)

Then we have the following theorem. The proof is given in Appendix C.
Theorem 1. For transmitting a DMS S over a DM-BC pY[1:K] |X ,
(o)

(o)

D(i) ⊆ D ⊆ D1 ∩ D2 .

(14)

Remark 1. The inner bound of Theorem 1 can be easily extended to Gaussian or any other well-behaved continuous-alphabet
source-channel pairs by the standard discretization method [16, Thm. 3.3]. Moreover for these cases the outer bounds still
hold. Theorem 1 can be also extended to the bandwidth mismatch case, where m samples of a DMS are transmitted through n
uses of a DM-BC. This can be accomplished by replacing the source and channel symbols in Theorem 1 by supersymbols of
lengths m and n, respectively. Besides, Theorem 1 could be also extended to the problems of broadcasting correlated sources
(by modifying the distortion measures) and source broadcast with channel input cost constraints (by introducing channel input
constraints).
The inner bound D(i) in Theorem 1 is achieved by a unified hybrid coding scheme depicted in Fig. 3. In this scheme,
the codebook has a layered (or superposition)
structure (see Fig. 2), and consists of randomly and independently generated
QN
n
nri
codewords V[1:N
(m
),
m
∈
[1
:
2
], where r[1:N ] satisfies (11). At the encoder side, upon a source sequence
[1:N
]
[1:N
]
i=1
]
n
S , the encoder produces digital messages M[1:N ] with Mi meant for all the receivers k’s satisfying i ∈ Bk . Then, the
n
n
codeword V[1:N
are used to generate a channel input X n by a symbol-by-symbol
] (M[1:N ] ) and the source sequence S
mapping x(v[1:N ] , s). At the decoder sides, upon the received signal Ykn , the decoder k reconstructs MBk (and also VBnk (MBk ))
losslessly, and then generates Ŝkn by a symbol-by-symbol mapping ŝk (vBk , yk ). Such a scheme could achieve any D[1:K] in
the inner bound D(i) .
To reveal essence of such hybrid coding, the digital transmission part of this hybrid coding can be roughly understood as
the cascade of a K-user Gray-Wyner source-coding and a K-user Marton’s broadcast channel-coding, which share a common
codebook.
According
to [16, Thm.
 13.3], the encoding operation of Gray-Wyner source-coding with rates r[1:N ] is successful if
P
P
r
>
H
V
|V
6 ∅ and if j ∈ J , then Aj ⊆ J , and according
j Aj − H (VJ |S) for all J ⊆ [1 : N ] such that J =
j∈J j
j∈J
P
3
to [16, Thm 8.4] the
 decoding operation of Marton’s broadcast channel-coding with rates rc [1:N ] is successful if j∈J c rj <
P
c
j∈J c H Vj |VAj − H (VJ |Yk VJ ) for all 1 ≤ k ≤ K and for all J ⊆ Bk such that J 6= ∅ and if j ∈ J , then Aj ⊆ J .
Since the proposed hybrid coding satisfies the two sufficient conditions above, VBnk (MBk ) can be correctly recovered by the
receiver k. Note that such informal understanding is inaccurate owing to the use of symbol-by-symbol mappings, but it provides
a rationale for our scheme. Besides, the design of such unified hybrid coding is inspired by the hybrid coding scheme for
sending correlated sources over a multi-access channel in [15].
3 Note that for Marton’s broadcast channel-coding [16, p. 212-213], r
[1:N ] here does not correspond to the regular broadcast-rates R[1:N ] , but corresponds
e[1:N ] of each subcodebooks. In addition, here we only require the decoding operation is successful, hence the condition that the chosen
to the total rates R
codewords and the source sequence are jointly typical, which was required in the encoding operation of Gray-Wyner source-coding, is not repeatedly required
here.

6

(o)

(o)

n
The outer bounds D1 and D2 of Theorem 1 are derived by introducing auxiliary random variables U[1:L]
at the sender side
or at the receiver sides. The proof method of introducing auxiliary random variables (or remote sources) at sender side could be
found in [9], [11, Thm. 2] and [12, Lem. 1]. In [9] it was used to derive the outer bound for Gaussian source broadcast, and in
[11, Thm. 2] and [12, Lem. 1] it was used to derive the outer bounds for sending source over 2-user general broadcast channel.
This proof method generalizes the one used to derive the single-user outer bound, but it does not always result in a tighter
outer bound than the single-user one [10]. On the other hand, to the best of our knowledge, it is the first time to prove outer
bounds by introducing auxiliary random variables (or remote channels) at receiver sides. A deeper understanding of these two
proof methods has been given by Khezeli et al. in [12]. pŜ [1:K] |S can be considered as a virtual broadcast channel realized over
physical broadcast channel pY[1:K] |X , and hence certain mutual informations (e.g., channel capacity region) based on pŜ [1:K] |S
are less than or equal to those based on pY[1:K] |X . This leads to the desired necessary conditions. Besides, the necessary
conditions can be also understood from the perspective of virtual sources. X and Y[1:K] respectively can be considered as a
virtual source and K virtual reconstructions. Then the physical source S and the physical reconstructions Ŝ [1:K] are correlated
through the virtual source and virtual reconstructions. Hence the physical source should be more “tractable” than the virtual
one, and certain mutual informations (e.g., source-coding rate region) based on the physical source and reconstructions should
(o)
be less than or equal to those based on the virtual source and reconstructions. The analysis above gives the reasons why D1 is
expressed in form of comparison of the “capacity regions” of virtual broadcast channel and physical broadcast channel, while
(o)
D2 is expressed in form of comparison of the “source-coding rate regions” of virtual source and physical source.
For the 2-user broadcast case, the inner bound of Theorem 1 reduces to
n
D(i) = (D1 , D2 ) : ∃pV0 ,V1 ,V2 |S , x (v0 , v1 , v2 , s) , ŝk (v0 , vk , yk ) , k = 1, 2, s.t.


Edk S, Ŝk ≤ Dk ,

I(V0 Vk ; S) < I(V0 Vk ; Yk ), k = 1, 2,
I(V0 V1 V2 ; S) + I(V1 ; V2 |V0 ) < min {I(V0 ; Y1 ), I(V0 ; Y2 )} + I(V1 ; Y1 |V0 ) + I(V2 ; Y2 |V0 ),
o
I(V0 V1 ; S) + I(V0 V2 ; S) + I(V1 ; V2 |V0 S) < I(V0 V1 ; Y1 ) + I(V0 V2 ; Y2 ) .
(o)

This inner bound was first given by Yassaee et. al [21]. On the other hand, letting K = 2, L = 1, D1
reduce to
n
(o)
D1 = (D1 , D2 ) : ∃pŜ1 Ŝ2 |S s.t.


Edk S, Ŝk ≤ Dk , k = 1, 2,
and for any pmf pU |S , one can find pŨ X Ỹ1 Ỹ2 satisfying




I Ŝ1 ; U ≤ I Y1 ; Ũ |Ỹ1 ,




I Ŝ2 ; U ≤ I Y2 ; Ũ |Ỹ2 ,




I Ŝ1 Ŝ2 ; U ≤ I Y1 Y2 ; Ũ |Ỹ1 Ỹ2 ,




I Ŝ1 ; S|U ≤ I Y1 ; X|Ũ Ỹ1 ,




I Ŝ2 ; S|U ≤ I Y2 ; X|Ũ Ỹ2 ,



o
I Ŝ1 Ŝ2 ; S|U ≤ I Y1 Y2 ; X|Ũ Ỹ1 Ỹ2 ,

(o)

and D2

(15)
respectively

7

or a simpler but possibly looser one,
n
(o)
D1 = (D1 , D2 ) : ∃pŜ1 Ŝ2 |S s.t.


Edk S, Ŝk ≤ Dk , k = 1, 2,
and for any pmf pU |S , one can find pX Ỹ1 Ỹ2 satisfying




I Ŝ1 ; U ≤ I Y1 ; Ỹ1 ,




I Ŝ2 ; U ≤ I Y2 ; Ỹ2 ,




I Ŝ1 Ŝ2 ; U ≤ I Y1 Y2 ; Ỹ1 Ỹ2 ,




I Ŝ1 ; S|U ≤ I Y1 ; X|Ỹ1 ,




I Ŝ2 ; S|U ≤ I Y2 ; X|Ỹ2 ,



o
I Ŝ1 Ŝ2 ; S|U ≤ I Y1 Y2 ; X|Ỹ1 Ỹ2 ,
and
n
(o)
D2 = (D1 , D2 ) : ∃pX , ŝk (ỹk ) , k = 1, 2 s.t.


Edk S, Ŝk ≤ Dk , k = 1, 2,
and for any pmf pU |Y1 Y2 , one can find pỸ1 Ỹ2 |S pŨ |Ỹ1 Ỹ2 satisfying


I S; Ũ ≤ I (X; U ) ,


I S; Ỹ1 |Ũ ≤ I (X; Y1 |U ) ,


I S; Ỹ2 |Ũ ≤ I (X; Y2 |U ) ,


I S; Ỹ1 |Ỹ2 Ũ ≤ I (X; Y1 |Y2 U ) ,


I S; Ỹ2 |Ỹ1 Ũ ≤ I (X; Y2 |Y1 U ) ,


o
I S; Ỹ1 Ỹ2 |Ũ ≤ I (X; Y1 Y2 |U ) .
(o)

(o)

Note that the outer bounds D1 and D2 are not trivial in general. The necessity of introducing nondegenerate variable(s)
(o)
for D1 can be concluded from some special cases, e.g., source broadcast over a degraded channel, quadratic Gaussian source
broadcast, or Hamming binary source broadcast (see the details in the subsequent three subsections). To show the necessity of
(o)
(o)
introducing a nondegenerate variable for D2 , we consider the first three inequalities on mutual information in D2 . Next we
show that the necessary conditions


I S; Ũ ≤ I (X; U ) ,


I S; Ỹ1 |Ũ ≤ I (X; Y1 |U ) ,


I S; Ỹ2 |Ũ ≤ I (X; Y2 |U ) ,

(16)
(17)
(18)

with a nondegenerate U results in a tighter bound than that with a degenerate U (for the latter case, the necessary conditions
reduce to the single-user bound).
Suppose the broadcast channel PY1 Y2 |X satisfies Y1 = (Y0 , Y10 ), Y2 = (Y0 , Y20 ) for some Y0 , Y10 , Y20 . Consider a lossless
transmission case (Hamming distortion measure and D1 = D2 = 0): S = (S1 , S2 ), Ŝ1 = S1 , Ŝ2 = S2 , and H(S1 ) = C1 and
H(S2 ) = C2 . Obviously, these conditions do not violate the single-user outer bound. Now we show that for some sources,these
(o)
(o)
conditions violate the outer bound D2 . Set U = Y0 in D2 . Then it is easy to obtain the following inequalities from (16)-(18).
I(S1 S2 ; V ) ≤ I(X; Y0 ),

(19)

H(S1 |V ) ≤ I(X; Y1 |Y0 ),

(20)

H(S2 |V ) ≤ I(X; Y2 |Y0 ),

(21)

8

for some pV |S1 S2 . Therefore, we further have
H(S1 ) ≤ H(S1 ) + I(S2 ; V |S1 ) = I(S1 S2 ; V ) + H(S1 |V ) ≤ I(X; Y0 ) + I(X; Y1 |Y0 ) = I(X; Y1 ) ≤ C1 .

(22)

On the other hand, by the assumptions H(S1 ) = C1 and H(S2 ) = C2 , the equalities hold in all the inequalities above, which
implies I(X; Y1 ) = C1 (i.e., PX is a capacity-achieving distribution), I(S1 S2 ; V ) = I(X; Y0 ) , and I(S2 ; V |S1 ) = 0, i.e.,
S2 → S1 → V . Similarly, we have S1 → S2 → V . In addition, the Gács-Körner common information [22], [23] is defined as
CGK (S1 ; S2 ) =

sup

I(S1 S2 ; V ).

(23)

PV |S1 S2 :S2 →S1 →V,S1 →S2 →V

Hence there exists pV |S1 S2 such that S2 → S1 → V, S1 → S2 → V and I(S1 S2 ; V ) = I(X; Y0 ) , only if CGK (S1 ; S2 ) ≥
I(X; Y0 ) > 0 (suppose the channel PY0 |X satisfies I(X; Y0 ) > 0 for the capacity-achieving distribution PX ). However the
Gács-Körner common information does not always exist for any source pair (S1 , S2 ) , e.g., CGK (S1 ; S2 ) = 0 for a doubly
(o)
symmetric binary source. This implies the outer bound is tighter than the single-user one, which in turn implies D2 are not
trivial in general.
B. Discrete Memoryless Broadcast over Degraded Channel
If the channel is degraded, define
n
(i)
DDBC = D[1:K] : ∃pVK |S pVK−1 |VK · · · pV1 |V2 , x (vK , s) , ŝk (vk , yk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk ,
I (S; Vk ) ≤

k
X

o
I (Yj ; Vj |Vj−1 ) , 1 ≤ k ≤ K, where V0 , ∅ ,

(24)

j=1

and
n
(o)
DDBC = D[1:K] : ∃pŜ[1:K] |S , pX s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
 




I Ŝ[1:k] ; Uk |Uk−1 : k ∈ [1 : K] ∈ RDBC pX pY[1:K] |X
for any pmf pUK−1 |S pUK−2 |UK−1 · · · pU1 |U2 , U0 , ∅, UK , S,
 



o
and I S; Ŝ[1:k] : k ∈ [1 : K] ∈ RSRC pX pY[1:K] |X ,

(25)

where

 n
RDBC pX pY[1:K] |X = R[1:K] : ∃pVK−1 |X pVK−2 |VK−1 · · · pV1 |V2 s.t.
Rk ≥ 0,

k
X
j=1

Rj ≤

k
X

I (Yj ; Vj |Vj−1 ) , 1 ≤ k ≤ K, where V0 , ∅, VK , X

o

(26)

j=1

denotes the capacity of the degraded broadcast channel pY[1:K] |X with the input X following pX , and
k

 n
o
X

RSRC pX pY[1:K] |X = R[1:K] : Rk ≥ 0,
Rj ≥ I X; Y[1:k] , 1 ≤ k ≤ K

(27)

j=1

denotes the successive refinement coding rate region of source X with reconstructions Y[1:K] following pY[1:K] |X .
Then as a consequence of Theorem 1, the following theorem holds.
Theorem 2. For transmitting a DMS S over a degraded DM-BC pY[1:K] |X ,
(i)

(o)

DDBC ⊆ D ⊆ DDBC .
Remark 2.

(o)
DDBC

can be also expressed as
n
(o)
DDBC = D[1:K] : ∃pŜ[1:K] |S , pX s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,




RDBC pS pŜ 0 |S ⊆ RDBC pX pY[1:K] |X ,
[1:K]




o
RSRC pS pŜ 0 |S ⊇ RSRC pX pY[1:K] |X , Ŝk0 , Ŝ[1:k] , 1 ≤ k ≤ K .
[1:K]

(28)

(29)

9

(o)

∗
From the last constraint of DDBC , one can obtain an interesting conclusion: the single-user outer bound D[1:K]
can be achieved
for source broadcast over a degraded channel only if the source is successively refinable.
(i)

Note that the last constraint of DDBC can be understood as the intersection between the successive refinement rate region
of the source S with reconstructions V[1:K] and the capacity of the degraded broadcast channel pY[1:K] |X with the input X
(o)
and auxiliary random variables V[1:K] , is not empty. The second constraint of DDBC can be understood as the capacity of the
virtual degraded broadcast channel pŜ 0 |S with the input S is included in the capacity of the physical degraded broadcast
[1:K]

(o)

channel pY[1:K] |X with the input X. Similarly, the last constraint of DDBC can be understood as the successive refinement rate
0
region of the physical source S with reconstructions Ŝ[1:K]
includes the successive refinement rate region of the virtual source
X with reconstructions Y[1:K] .
C. Hamming Binary Broadcast

Consider sending a binary source S ∼ Bern 12 with the Hamming distortion measure dk (s, ŝ) = d(s, ŝ) , 0, if s =
ŝ; 1, otherwise, over a binary broadcast channel Yk = X ⊕ Wk , 1 ≤ k ≤ K with Wk ∼ Bern (pk ) , 12 ≥ p1 ≥ p2 ≥ · · · ≥
pK ≥ 0. Assume the bandwidth mismatch factor is b.
We first consider the inner bound part. For bandwidth expansion (b > 1) case, as a special case of hybrid coding,
systematic source-channel coding (or Uncoded Systematic Coding) was first investigated in [6]. For any point-to-point lossless
communication, such systematic coding does not lose the optimality; however, for some lossy transmission cases such as
Hamming binary source communication, it is not optimal any more [6]. To retain the optimality, we can first quantize the
source S, and then transmit the quantized signal using Uncoded Systematic Coding. The performance of such code can be
obtained directly from Theorem 2.

Specifically,
let U2 = S ⊕ E2 , U1 = U2 ⊕ E1 with E2 ∼ Bern(D2 ), E1 ∼ Bern(d1 ). Let V2 = U2 , X b−1 , V1 =

b−1
U1 , X1b−1 , X1b−1 = X b−1 ⊕ B b−1 , where X1b−1 and X b−1 are independent
and B b−1
 of U2 andU1 , and X
 follow b − 1
dimensional Bern( 21 ) and Bern(θ), respectively. Let xb (v2 , s) = u2 , xb−1 , ŝ2 v2 , y2b = u2 , and ŝ1 v1 , y1b = u1 , if d1 <
(i)
p1 ; y1 , otherwise, where y1 is the first letter of y1b . Substituting these variables and functions into the inner bound DDBC in
Theorem 2, we get the following corollary.
Corollary 1 (Coded Systematic Coding). For transmitting a binary source S with the Hamming distortion measure over a
2-user binary broadcast channel with the bandwidth mismatch factor b,
n
1
(i)
D ⊇ DCSC , convexhull (D1 , D2 ) : 0 ≤ θ, d1 ≤ ,
2
D1 ≥ min {d1 ? D2 , p1 ? D2 } ,
r1 = 1 − H2 (d1 ? p1 ) + (b − 1) [1 − H2 (θ ? p1 )],
r2 = H2 (d1 ? p2 ) − H2 (p2 ) + (b − 1) [H2 (θ ? p2 ) − H2 (p2 )],
1 − H2 (d1 ? D2 ) ≤ r1 ,
o
1 − H2 (D2 ) ≤ r1 + r2 ,

(30)

where ? denotes an binary operation such that
x ? y = (1 − x)y + x(1 − y),

(31)

and H2 denotes the binary entropy function, i.e.,
H2 (p) = −p log p − (1 − p) log(1 − p).

(32)

Remark 3. Coded Systematic Coding without timesharing does not always lead to a convex distortion region, hence a
timesharing mechanism is needed to improve the performance. This is equivalent to adding a timesharing variable Q into
(i)
V2 and V1 , before substituting them into the inner bound DDBC . Besides, note that unlike Uncoded Systematic Coding, the
Coded Systematic Coding could always achieve the optimal distortion for at least one of the receivers. Moreover, unlike
separate coding the Coded Systematic Coding weakens the cliff effect, and results in a slope-cliff effect.
The outer bound of Theorem 2 reduces to the following outer bound for the Hamming binary source broadcast problem.
This outer bound was first given in [11, Eqn (41)] for the 2-user case.
Theorem 3. [11, Eqn (41)] For transmitting a binary source S with the Hamming distortion measure over a K-user binary
broadcast channel with the bandwidth mismatch factor b,
n
1
(o)
D ⊆ DDBC , D[1:K] : For any values = τ0 ≥ τ1 ≥ τ2 ≥ · · · ≥ τK = 0,
2
o
1
(H2 (τk−1 ? Dk ) − H2 (τk ? Dk ) : k ∈ [1 : K]) ∈ RBBC ,
(33)
b

10

0.2
0.18
Separate Coding
0.16
Ucoded Systematic Coding
(Wyner−Ziv Broadcast Coding)

0.14

D1

Single-user Outer Bound 2
0.12

Outer Bound 2

0.1
Outer Bound 1
Coded Systematic Coding

0.08
0.06

0.04
Single-user Outer Bound 1
0.02
0

0

0.01

0.02

0.03

0.04

0.05
D2

0.06

0.07

0.08

0.09

0.1

Fig. 4. Distortion bounds for sending a binary source over a binary broadcast channel with b = 2, p1 = 0.18, p2 = 0.12. Outer Bounds 1 and 2 respectively
correspond to the outer bound of Theorem 3 and the outer bound of Theorem 6. Separate Coding, Uncoded Systematic Coding, and Coded Systematic Coding
respectively correspond to the separate scheme (combining successive-refinement code [16, Example 13.3] with superposition code [16, Example 5.3]), the
inner bound in Corollary 2, and the inner bound in Corollary 1. Single-user Outer Bounds 1 and 2 correspond to the single-user outer bound (6) and the
single-user Wyner-Ziv outer bound (37), respectively. Besides, Single-user Outer Bound 2, Outer Bound 2 and Uncoded Systematic Coding can be considered
as outer bounds and inner bound for the Wyner-Ziv source broadcast problem with b = 1, β1 = p1 , β2 = p2 .

where RBBC denotes the capacity of the binary broadcast channel given by
n
1
RBBC = R[1:K] : There exist some values = θ0 ≥ θ1 ≥ θ2 ≥ · · · ≥ θK = 0 s.t.
2
o
0 ≤ Rk ≤ H2 (θk−1 ? pk ) − H2 (θk ? pk ) , 1 ≤ k ≤ K .

(34)

The bounds in Corollary 1 and Theorem 3 are illustrated in Fig. 4.
D. Quadratic Gaussian Broadcast
2
Consider sending a Gaussian source S ∼ N (0, NS ) with the quadratic distortion measure
 dk (s, ŝ) = d(s, ŝ) , (s − ŝ) over
2
a power-constrained Gaussian broadcast channel Yk = X + Wk , 1 ≤ k ≤ K with E X ≤ P andWk ∼ N (0, Nk ) , N1 ≥
N2 ≥ · · · ≥ NK . Assume the bandwidth mismatch factor is b. As stated in Remark 1, Theorem 1 (or 2) holds for the Gaussian
(i)
case as well. The inner bound DDBC in Theorem 2 could recover the best known inner bound [7, Thm. 5] by setting the random
variables and symbol-by-symbol mappings to some suitable ones. On the other hand, setting U[1:K−1] to be jointly Gaussian
(o)
with S, the outer bound DDBC in Theorem 2 could recover the best known outer bound [9, Thm. 2]. The bounds in [7, Thm.
5] and [9, Thm. 2] are illustrated in Fig. 5.
IV. W YNER -Z IV S OURCE B ROADCAST: S OURCE B ROADCAST WITH S IDE I NFORMATION
We now extend the source broadcast problem by allowing decoders to access side information correlated with the source.
As depicted in Fig. 6, receiver k observes memoryless side information Zkn , and it produces a source reconstruction Ŝkn from
the received signal Ykn and side information Zkn .
Definition 7. An n-length Wyner-Ziv source-channel code is defined by the encoding function xn : S n 7→ X n and K decoding
functions ŝnk : Ykn × Zkn 7→ Ŝkn , 1 ≤ k ≤ K.
Definition 8. If there exists a sequence of Wyner-Ziv source-channel codes satisfying


lim sup Edk S n , Ŝkn ≤ Dk ,

(35)

n→∞

then we say that the distortion tuple D[1:K] is achievable.
Definition 9. The admissible distortion region for the Wyner-Ziv broadcast problem is defined as

DSI , D[1:K] : D[1:K] is achievable .

(36)

11

−3

2.5

x 10

2

Inner Bound 2
Outer Bound 2

1.5
D2

Inner Bound 1
Outer Bound 1

1
Single-user Outer Bound
0.5

0

0

0.05

0.1
D1

0.15

0.2

Fig. 5. Distortion bounds for sending a Gaussian source over a Gaussian broadcast channel with b = 2, NS = 1, P = 50, N1 = 10, N2 = 1. Outer Bounds
1 and 2 and Inner Bounds 1 and 2 respectively correspond to the outer bound in [9, Thm. 2], the outer bound in Theorem 7, the inner bound in [7, Thm. 5],
and the inner bound achieved by Wyner-Ziv separate coding (uncoded systematic code) [17, Lem. 3]. Single-user Outer Bound corresponds to the single-user
outer bound (6). Besides, Outer Bound 2 and Inner Bound 2 can be considered as an outer bound and an inner bound for the Wyner-Ziv source broadcast
NS N1
NS N2
problem with b = 1, β1 = P
, β2 = P
. For this case, Single-user Outer Bound corresponds to the single-user Wyner-Ziv outer bound (37).
+N
+N
1

2

Y1n

Sn

Encoder

Xn

Decoder 1

Ŝ1n

Z1n

PY[1:K ] | X
YKn

Decoder K

Ŝ Kn

Z Kn
Fig. 6. Wyner-Ziv source broadcast system: a broadcast communication system with side information at decoders.

Shamai et al. [6, Thm. 2.1] showed that for transmitting a source over a point-to-point channel pYk |X with side information
Zk available at the decoder, the minimum achievable distortion for the receiver k satisfies RS|Zk (Dk ) = Ck , where RS|Zk (· )
is the Wyner-Ziv rate-distortion function of the source S given that the decoder observes Zk [16]. Therefore, the optimal
−1
∗
achievable distortion is DSI,k
= RS|Z
(Ck ) . Obviously,
k

∗
∗
DSI ⊆ DSI
, D[1:K] : Dk ≥ DSI,k
,1 ≤ k ≤ K ,
(37)
∗
where DSI
is named single-user Wyner-Ziv outer bound.
Besides, we also consider the bandwidth mismatch case, whereby m samples of a DMS are transmitted through n uses of
a DM-BC with l samples of side information available at each decoder. For simplicity, we assume m = l. For this case, the
n
bandwidth mismatch factor is defined as b = m
.

A. Discrete Memoryless Wyner-Ziv Broadcast
If consider S and Z[1:K] as the input and outputs of a virtual broadcast channel pZ[1:K] |S , then the Wyner-Ziv source broadcast
problem with the encoding function xn (sn ) is equivalent to the source broadcast problem of sending S over pZ[1:K] |S pY[1:K] |X
with the encoding function (sn , xn (sn )). Correspondingly, the Wyner-Ziv source broadcast system can be considered as a

12


(uncoded) systematic source-channel coding system. Hence by setting the symbol-by-symbol function as s, x v[1:N ] , s ,
from Theorem 1, we obtain the following inner bound for the Wyner-Ziv source broadcast problem.
n

(i)
DSI = D[1:K] : ∃pV[1:N ] |S , r[1:N ] , x v[1:N ] , s , ŝk (vBk , yk , zk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
X
X

rj >
H Vj |VAj − H (VJ |S)
j∈J

j∈J

for all J ⊆ [1 : N ] such that J 6= ∅ and if j ∈ J , then Aj ⊆ J ,
X
X

rj <
H Vj |VAj − H (VJ c |Yk Zk VJ )
j∈J c

j∈J c

o
for all 1 ≤ k ≤ K and for all J ⊆ Bk such that J c , Bk \J =
6 ∅ and if j ∈ J , then Aj ⊆ J .
(38)

In addition, regard U[1:L] , Z[1:K] as auxiliary random variables following pU[1:L] |S pZ[1:K] |S given S, then following steps
(o)
similar to the proof of the outer bound D1 of Theorem 1, we can obtain the following outer bound on DSI .
n
(o)
DSI,1 = D[1:K] : ∃pŜ[1:K] |S,Z[1:K] s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
and for any pU[1:L] |S,Z[1:K] , one can find pŨ[1:L] ,Z̃[1:K] ,X satisfying




o
I ŜA ; UB |UC ZA ≤ I YA ; ŨB |ŨC Z̃A for any A ⊆ [1 : K] , B, C ⊆ [1 : L] ,
(o)

Similarly, following steps similar to the proof of the outer bound D2
DSI .
n
(o)
DSI,2 = D[1:K] : ∃pX , ŝnk (ỹk , zkn ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,

(39)

of Theorem 1, we can prove another outer bound on

and for any pmf pU[1:L] |Y[1:K] , one can find pỸ[1:K] |S pŨ[1:L] |Ỹ[1:K] satisfying


o
I S n ; ỸB ŨB0 |ỸC ŨC 0 ≤ I (X; YB UB0 |YC UC 0 ) for any B, C ⊆ [1 : K] , B 0 , C 0 ⊆ [1 : L] .

(40)

Therefore, the following theorem holds. The proof is omitted.
Theorem 4. For transmitting a DMS S over a DM-BC pY[1:K] |X with side information Zk at the decoder k (k ∈ [1 : K]),
(i)

(o)

(o)

DSI ⊆ DSI ⊆ DSI,1 ∩ DSI,2 .

(41)

Remark 4. Similar to Theorem 1, Theorem 4 could be extended to a Gaussian or any other well-behaved continuous-alphabet
source-channel pair. It also can be extended to the problems of broadcasting Wyner-Ziv correlated sources, and Wyner-Ziv
source broadcast with channel input cost.
B. Discrete Memoryless Wyner-Ziv Broadcast over Degraded Channel with Degraded Side Information
Theorem 4 can be used to derive an inner bound and an outer bound for the degraded channel and degraded side information
case. Define
n
(i)
DSI−D = D[1:K] : ∃pVK |S pVK−1 |VK · · · pV1 |V2 , x (vK , s) , ŝk (vk , yk , zk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk ,
I (S; Vk ) ≤

k
X
j=1

o
I (Yj Zj ; Vj |Vj−1 ) , 1 ≤ k ≤ K, where V0 , ∅ ,

(42)

13

and
n
(o)
DSI−D = D[1:K] : ∃pVK |S pVK−1 |VK · · · pV1 |V2 , pX , ŝk (vk , zk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk ,


(I (Vk ; Uk |Uk−1 Zk ) : k ∈ [1 : K]) ∈ RDBC pX pY[1:K] |X
for any pmf pUK−1 |S pUK−2 |UK−1 · · · pU1 |U2 , U0 , ∅, UK , S,

o
and (I (Vk ; S|Zk ) : k ∈ [1 : K]) ∈ RSRC pX pY[1:K] |X ,
(43)




where RDBC pX pY[1:K] |X and RSRC pX pY[1:K] |X are given in (26) and (27), respectively. Then we have the following
theorem. The proof is analogous to that of Theorem 2, and therefore omitted.
Theorem 5. For transmitting a DMS S over a degraded DM-BC pY[1:K] |X (X → YK → YK−1 → · · · → Y1 ) with degraded
side information Zk (S → ZK → ZK−1 → · · · → Z1 ) at the decoder k (k ∈ [1 : K]),
(i)

(o)

DSI−D ⊆ DSI ⊆ DSI−D .

(44)

(o)

Remark 5. DSI−D can be also expressed as
n
(o)
DSI−D = D[1:K] : ∃pVK |S pVK−1 |VK · · · pV1 |V2 , ŝk (vk , zk ) , 1 ≤ k ≤ K s.t.


Edk S, Ŝk ≤ Dk ,




RDBC−SI pS pZ[1:K] |S pV[1:K] |S,Z[1:K] ⊆ RDBC pX pY[1:K] |X ,



o
RSRC−SI pS pZ[1:K] |S pV[1:K] |S,Z[1:K] ⊇ RSRC pX pY[1:K] |X ,

(45)

where

 n
RDBC−SI pX pZ[1:K] |X pY[1:K] |X,Z[1:K] = R[1:K] : ∃pVK−1 |X pVK−2 |VK−1 · · · pV1 |V2 s.t.
Rk ≥ 0,

k
X

Rj ≤

j=1

k
X

o
I (Yj ; Vj |Vj−1 Zj ) , 1 ≤ k ≤ K, where V0 , ∅, VK , X ,

j=1

(46)
and


RSRC−SI pX pZ[1:K] |X pY[1:K] |X,Z[1:K]



k
n
o
X
= R[1:K] : Rk ≥ 0,
Rj ≥ I (X; Yk |Zk ) , 1 ≤ k ≤ K .

(47)

j=1

C. Wyner-Ziv Binary Broadcast

Consider sending a binary source S ∼ Bern 12 with the Hamming distortion measure dk (s, ŝ) = d(s, ŝ) , 0, if s =
ŝ; 1, otherwise, over a binary broadcast channel Yk = X ⊕ Wk , 1 ≤ k ≤ K with Wk ∼ Bern (pk ) , 21 ≥ p1 ≥ p2 ≥ · · · ≥
pK ≥ 0. Assume
the side information Zk observed by the receiver k satisfies S = Zk ⊕ Bk with independent variables

Zk ∼ Bern 12 and Bk ∼ Bern (βk ). Assume
the bandwidth mismatch factor is b.

Let V1 = U1 , X1b , V2 = U2 , X b , V3 = ∅ with U1 and U2 are independent of X1b and X b . S, U2 and U1 satisfy the
distribution pS pU2 |S pU1 |U2 , where

pU2 |S

0
=
1

pU1 |U2



0
q2 ᾱ2
q2 α2

 00 0
0
q1 ᾱ1
= 1  q10 α10
2
0

1
q2 α2
q2 ᾱ2

2 
q̄2
,
q̄2

1
2 
q10 α10 q̄10
,
q10 ᾱ10 q̄10 
0
1

(48)

(49)

with 0 ≤ q2 , q10 ≤ 1, 0 ≤ α2 , α10 ≤ 21 . X b and X1b satisfy X1b = X b ⊕ B b , X b ∼ b-dimensional Bern( 21 ), and B b ∼
b-dimensional Bern(θ) with 0 ≤ θ ≤ 12 . Denote α1 = α2 ? α10 , q 1 = q 2 q10 , and set xb (v2 , s) = xb and for k = 1, 2,
(

zk , if αk ≥ βk or αk < βk , uk = 2;
b
ŝk vk , yk , zk =
(50)
uk , if αk < βk , uk = 0, 1.

14

(i)

Substituting these random variables and functions into DSI in Theorem 4 (for this case, the hybrid coding reduces to a layered
digital coding), we get the following performance, which is tighter than that of the Layered Description Scheme (LDS) [17,
Lem. 4].
Corollary 2 (Layered Digital Coding). For transmitting a binary source S with the Hamming distortion measure over a 2-user
binary broadcast channel with side information Zk at the decoder k (k ∈ [1 : K]),
n
1
1
(i)
DSI ⊇ DLDC , (D1 , D2 ) : 0 ≤ q1 ≤ q2 ≤ 1, 0 ≤ α2 ≤ α1 ≤ , 0 ≤ θ ≤ ,
2
2
q1 r(α1 , β1 ) ≤ b (1 − H2 (θ ? p1 )) ,
q1 r(α1 , β2 ) ≤ b (1 − H2 (θ ? p2 )) ,
q2 r(α2 , β2 ) ≤ b (1 − H2 (p2 )) ,
q1 r(α1 , β1 ) + (q2 r(α2 , β2 ) − q1 r(α1 , β2 )) ≤ b (1 − H2 (θ ? p1 )) + b (H2 (θ ? p2 ) − H2 (p2 )) ,
o
Di ≤ qi min {αi , βi } + (1 − qi )βi , i = 1, 2 ,

(51)

where
r(α, β) = H2 (α ? β) − H2 (α),

(52)

? denotes the binary operation given in (31), and H2 denotes the binary entropy function given in (32).
In addition, the outer bound of Theorem 5 reduces to the following one for the Wyner-Ziv binary case. The proof is given
in Appendix D.
Theorem 6. For transmitting a binary source S with the Hamming distortion measure over a K-user binary broadcast channel
with degraded side information Zk ( 21 ≥ β1 ≥ β2 ≥ · · · ≥ βK ≥ 0) at the decoder k (k ∈ [1 : K]),
n
1
(o)
DSI ⊆ DSI−D , D[1:K] : ∃0 ≤ α1 , α2 , · · · , αK ≤ s.t.
2
αk ≤ Dk0 , min {Dk , βk } , 1 ≤ k ≤ K,
1
and for any values = τ0 ≥ τ1 ≥ τ2 ≥ · · · ≥ τK = 0,
2
!
o
1
ηk (H2 (βk ? τk ) − H2 (βk ? τk−1 ) − (H4 (αk , βk , τk ) − H4 (αk , βk , τk−1 ))) : k ∈ [1 : K] ∈ RBBC ,
b
(53)
where RBBC denotes the capacity region of the binary broadcast channel given in (34),
(
0
βk −Dk
, if αk < βk ,
β
−α
k
k
ηk ,
0,
otherwise,

(54)

H4 (x, y, z) , − (xyz + xyz) log (xyz + xyz) − (xyz + xyz) log (xyz + xyz)
− (xyz + xyz) log (xyz + xyz) − (xyz + xyz) log (xyz + xyz) ,

(55)

and x , 1 − x.
The bounds in Corollary 2 and Theorem 6 are shown in Fig. 4.
D. Wyner-Ziv Gaussian Broadcast
2
Consider sending a Gaussian source S ∼ N (0, NS ) with the quadratic distortion measure
 dk (s, ŝ) = d(s, ŝ) , (s − ŝ) over
2
a power-constrained Gaussian broadcast channel Yk = X + Wk , 1 ≤ k ≤ K with E X ≤ P and Wk ∼ N (0, Nk ) , N1 ≥
N2 ≥ · · · ≥ NK . Assume the side information Zk observed by the receiver k satisfies S = Zk + Bk with independent Gaussian
variables Zk ∼ N (0, NS − βk ) and Bk ∼ N (0, βk ). Assume the bandwidth mismatch factor is b. As stated in Remark 4,
Theorem 4 (or 5) holds for the Gaussian case as well. The inner bound of Theorem 5 recovers the existing results in [17],
[18], and the outer bound of Theorem 5 generates the following outer bound for the Wyner-Ziv Gaussian source broadcast
problem. The proof is given in Appendix E.
Theorem 7. For transmitting a Gaussian source S over a Gaussian broadcast channel with degraded side information Zk
(β1 ≥ β2 ≥ · · · ≥ βK ) at the decoder k (k ∈ [1 : K]),
n
(o)
DSI ⊆ DSI−D , D[1:K] : For any values + ∞ = τ0 ≥ τ1 ≥ · · · ≥ τK = 0,


o
1 1
(βk + τk ) (Dk + τk−1 )
log
: k ∈ [1 : K] ∈ RGBC ,
(56)
b 2
(Dk + τk ) (βk + τk−1 )

15

where RGBC denotes the capacity of Gaussian broadcast channel given by
RGBC



K
k
n
o
X
X
= R[1:K] : Rk ≥ 0, 1 ≤ k ≤ K, NK+1 = 0,
(Nk − Nk+1 ) exp 2
Rj  ≤ P + N1 .

(57)

j=1

k=1

The bound of Theorem 7 is shown in Fig. 5.
V. C ONCLUDING R EMARKS
In this paper, we focused on the joint source-channel coding problem of sending a memoryless source over a memoryless
broadcast channel, and developed an inner bound and two outer bounds for this problem. The inner bound is achieved by
using a unified hybrid coding scheme, and it can recover the best known performance of hybrid coding. Similarly, our outer
bounds can also recover the best known outer bound in the literature. Besides, we extend the results to the Wyner-Ziv source
broadcast problem.
The inner bounds achieved by the proposed hybrid coding is established by using generalized multivariate covering and
packing lemmas, and the outer bounds are derived by introducing auxiliary random variables (at the sender side or receiver
sides). These lemmas and tools are expected to be exploited to derive more and stronger achievability and converse results for
network information theory.
A PPENDIX A
P ROOF OF L EMMA 1
We follow similar steps to the proof of mutual covering lemma [15]. Let
)
(
k
Y
n
[1 : 2nri ] : (U n , V0n , V[1:k]
(m[1:k] )) ∈ T(n) .
B = m[1:k] ∈

(58)

i=1

Then we only need to show limn→∞ P (|B| = 0) = 0. On the other hand,
X
lim P (|B| = 0) = lim
pU n ,V0n (un , v0n ) P (|B| = 0|un , v0n )
n→∞

n→∞

X

≤ lim

(59)

un ,v0n



(n)
pU n ,V0n (un , v0n ) P (|B| = 0|un , v0n ) + lim P (un , v0n ) ∈
/ T0

(60)

pU n ,V0n (un , v0n ) P (|B| = 0|un , v0n )

(61)

n→∞

n→∞
(n)

(un ,v0n )∈T0

= lim

X

n→∞
(n)
(un ,v0n )∈T0

(n)

To prove limn→∞ P (|B| = 0) = 0, it is sufficient to show limn→∞ P (|B| = 0|un , v0n ) = 0 for any (un , v0n ) ∈ T0 . Utilizing
the Chebyshev lemma [16, App. B], we can bound the probability as

Var(|B||un , v0n )
.
P (|B| = 0|un , v0n ) ≤ P (|B| − E|B|)2 ≥ (E|B|)2 |un , v0n ≤
(E(|B||un , v0n ))2
Next we prove the upper bound

Var(|B||un ,v0n )
(E(|B||un ,v0n ))2


E m[1:k] ,
for each m[1:k] ∈

Qk

i=1 [1

tends to zero as n → ∞. Define
(
(n)
n
1, if (un , v0n , V[1:k]
(m[1:k] )) ∈ T ;
0, otherwise,

: 2nri ], then |B| can be expressed as
X
|B| =
m[1:k] ∈

Qk

i=1


E m[1:k] .

(62)

(63)

(64)

[1:2nri ]

Denote


n
p0 = P (un , v0n , V[1:k]
(m[1:k] )) ∈ T(n) |un , v0n ,


n
n
pI = P (un , v0n , V[1:k]
(m[1:k] )) ∈ T(n) , (un , v0n , V[1:k]
(mI , m0I c )) ∈ T(n) |un , v0n ,
for m[1:k] = 1, and m0[1:k] = 2. Obviously, p[1:k] = p0 . Then

Pk
X 
n
E(|B||un , v0n ) =
P (un , v0n , V[1:k]
(m[1:k] )) ∈ T(n) |un , v0n = 2n j=1 rj p0 ,
m[1:k]

(65)
(66)

(67)

16

and
E(|B|2 |un , v0n )
X X
=
=



n
n
P (un , v0n , V[1:k]
(m[1:k] )) ∈ T(n) , (un , v0n , V[1:k]
(mI , m0I c )) ∈ T(n) |un , v0n

X

I⊆[1:k] m[1:k] m0I c :m0I c <mI c
Pk
X X
X
2n j=1 rj p0 +
I$[1:k] m[1:k] m0I c :m0I c <mI c

(68)



n
n
P (un , v0n , V[1:k]
(m[1:k] )) ∈ T(n) , (un , v0n , V[1:k]
(mI , m0I c )) ∈ T(n) |un , v0n .
(69)

Define
J , {J $ [1 : k] : if j ∈ J , then Aj ⊆ J } .

(70)

Then any set I $ [1 : k] can transform into a J (I) ∈ J by removing all the elements j’s such that Aj * I. According to
generation of random codebook, we can observe that pI = pJ (I) . Therefore,


X X
X
n
n
(m[1:k] )) ∈ T(n) , (un , v0n , V[1:k]
(mI , m0I c )) ∈ T(n) |un , v0n
P (un , v0n , V[1:k]
I$[1:k] m[1:k] m0I c :m0I c <mI c

=
≤

X

X

X

pJ (I)
0
0
m
c
I$[1:k] [1:k] mI c :mI c <mI
P
Pk
X
2n( j=1 rj + j∈Ic rj ) pJ (I)

(71)
(72)

I$[1:k]

≤

X

Pk

2n(

j=1

P
rj + j∈(J (I))c rj )

pJ (I)

(73)

I$[1:k]

≤

X

Pk

2k−|J | 2n(

j=1

P
rj + j∈J c rj )

pJ

(74)

pJ ,

(75)

J ∈J

≤

X

2n(

Pk

j=1

P
rj + j∈J c rj +o(1))

J ∈J

where (73) follows from J (I) ⊆ I, (74) follows from that for each J ⊆ J, there are at most 2k−|J | of I’s that could
transform into J , and o(1) denotes a term that vanishes as n → ∞. Hence
Var(|B||un , v0n ) ≤ E(|B|2 |un , v0n )
n

≤2

Pk

j=1

rj

p0 +

(76)
X

2

n(

Pk

j=1

P
rj + j∈J c rj +o(1))

pJ .

(77)

J ∈J

Furthermore we have
2n
Var(|B||un , v0n )
≤
(E(|B||un , v0n ))2

Pk

j=1

rj

p0 +

Pk

J ∈J

2n(



Pk

P

j=1

P
rj + j∈J c rj +o(1))

2

2n j=1 rj p0
P
Pk
X
pJ
1
+
2n(− j∈J rj +o(1)) 2 .
= 2−n j=1 rj
p0
p0

pJ

(78)

(79)

J ∈J

According to the generation process of random codebook, we can observe that


X
n
n
p0 =
P V[1:k]
(m[1:k] ) = v[1:k]
|un , v0n

(80)

(n)
n
n
v[1:k]
:(un ,v0n ,v[1:k]
)∈T

≥ 2−n(

Pk

j=1

H (Vj |VAj V0 )−H (V[1:k] |U V0 )+2δ())

,

(81)

(n)
T ,

n
where (81) follows from that for any (un , v0n , v[1:k]
)∈


Pk
n
n
P V[1:k]
(m[1:k] ) = v[1:k]
|un , v0n ≥ 2−n( j=1 H (Vj |VAj V0 )+δ()) ,

(82)

(n)

and for any (un , v0n ) ∈ T0 ,
n
o
n
n
v[1:k]
: (un , v0n , v[1:k]
) ∈ T(n) ≥ 2n(H (V[1:k] |U V0 )+δ()) .

(83)

17

Similarly, we also can get
pJ ≤ 2−n(

Pk

j=1

P
H (Vj |VAj V0 )+ j∈J c H (Vj |VAj V0 )−H (V[1:k] |U V0 )−H(VJ c |U V0 VJ )−4δ())

.

(84)

Substituting (81) and (84) into (79), we have
Pk
Pk
Var(|B||un , v0n )
≤ 2−n( j=1 rj −( j=1 H (Vj |VAj V0 )−H (V[1:k] |U V0 )+2δ()))
n
n
2
(E(|B||u , v0 ))
P
X −n P
+
2 ( j∈J rj −( j∈J H (Vj |VAj V0 )−H(VJ |U V0 )+6δ()+o(1))) .

(85)

J ∈J

(85) tends to zero if
k
X

rj >

j=1

k
X



H Vj |VAj V0 − H V[1:k] |U V0 + 2δ ()

(86)

j=1

X

X

rj >

j∈J


H Vj |VAj V0 − H (VJ |U V0 ) + 6δ () + o(1),

(87)

j∈J


P
P
i.e., j∈J rj > j∈J H Vj |VAj V0 − H (VJ |U V0 ) + δ 0 () for some δ 0 () that tends to zero as  → 0. This completes the
proof.
A PPENDIX B
P ROOF OF L EMMA 2
For any J such that J =
6 ∅ and if j ∈ J then Aj ⊆ J ,


n
P (U n , V0n , V[1:k]
(m[1:k] )) ∈ T(n) for some m[1:k]


≤ P (U n , V0n , VJn (mJ )) ∈ T(n) for some mJ


X
=
pU n ,V0n (un , v0n ) P (un , v0n , VJn (mJ )) ∈ T(n) for some mJ |un , v0n

(88)
(89)

un ,v0n

≤

X

pU n ,V0n (un , v0n )


X 
P (un , v0n , VJn (mJ )) ∈ T(n) |un , v0n .

un ,v0n

(90)

mJ

Similar to (81), we can obtain that


P
P (un , v0n , VJn (mJ )) ∈ T(n) |un , v0n ≤ 2−n( j∈J H (Vj |VAj V0 )−H(VJ |U V0 )−2δ()) .

(91)

Substituting it into (90), we have


n
P (U n , V0n , V[1:k]
(m[1:k] )) ∈ T(n) for some m[1:k]
≤ 2n(

P

j∈J

P
rj −( j∈J H (Vj |VAj V0 )−H(VJ |U V0 )−2δ()))

.

(92)


H Vj |VAj V0 − H (VJ |U V0 ) − 2δ () .

(93)

(92) tends to zero if
X
j∈J

rj <

X
j∈J

This completes the proof.
A PPENDIX C
P ROOF OF T HEOREM 1
A. Inner Bound
Actually the inner bound can be seen as a corollary to [20, Thm. 1] by choosing a proper set of network topology, transit
probability and symbol-by-symbol functions. For completeness and clarity, next we provide a direct description of the proposed
hybrid coding scheme and a direct proof for it.

18


Codebook Generation: Fix the conditional pmf pV[1:N ] |S , vector r[1:N ] , encoding function x v[1:N ] , s and decoding functions
ŝk (vBk , yk ) that satisfy


Edk S, Ŝk ≤ Dk , 1 ≤ k ≤ K,
(94)
X
X

rj >
H Vj |VAj − H (VJ |S)
j∈J

X
j∈J c

j∈J

for all J ⊆ [1 : N ] such that J 6= ∅ and if j ∈ J , then Aj ⊆ J ,
X

H Vj |VAj − H (VJ c |Yk VJ )
rj <

(95)

j∈J c

for all 1 ≤ k ≤ K and for all J ⊆ Bk such that J c , Bk \J 6= ∅ and if j ∈ J , then Aj ⊆ J .
(96)
Q
For each j ∈ [1 : N ] and each mAj ∈ i∈Aj [1 : 2nri ], randomly and independently generate a set of sequences vjn (mAj , mj ), mj ∈
Qn
[1 : 2nrj ], with each distributed according to i=1 pVj |VAj (vj,i |vAj ,i (mAj )). The codebook
n
o

QN
n
nri
m
:
m
∈
[1
:
2
]
C = v[1:N
.
(97)
[1:N
]
[1:N
]
i=1
]
is revealed to the encoder and all the decoders.


n
Encoding: We use joint typicality encoding. Given sn , encoder finds the smallest index vector m[1:N ] such that sn , v[1:N
∈
m
[1:N
]
]
(n)

T

. If there is no such index vector, let m[1:N ] = 1. Then the encoder transmits the signal
 
xi = x v[1:N ],i m[1:N ] , si , 1 ≤ i ≤ n.
0

Decoding: We use joint typicality decoding. Let  > . Upon receiving the signal
(k)
the smallest index vector m̂Bk such that
(k)
(n)
(vBnk (m̂Bk ), ykn ) ∈ T0 .

ykn ,

(98)

the decoder of the receiver k finds
(99)

(k)

If there is no such index vector, let m̂Bk = 1. The decoder reconstructs the source as
(k)

ŝk,i = ŝk (vBk ,i (m̂Bk ), yk,i ), 1 ≤ i ≤ n.

(100)

Analysis of Expected Distortion: We bound the distortions averaged over S n and the random codebook C. Define the “error”
event
!
!
[
[
E = E1 ∪
E2,k ∪
E 3,k ,
(101)
k

k

where
o
∈
/ T(n) for all m[1:N ] ,
n
o
 n
(n)
n
=
S n , V[1:N
M
,
Y
∈
/
T
,
0
[1:N ]
k
]

o
n

(n)
= VBnk (m0Bk ), Ykn ∈ T0 for some m0Bk , m0Bk 6= M Bk ,

E1 =
E2,k
E 3,k

n

n
S n , V[1:N
] m[1:N ]



(102)
(103)
(104)

for 1 ≤ k ≤ K. Using the union bound, we have
K
K
 \
 X
X
c
P (E) ≤ P (E1 ) +
P E1
E2,k +
P (E 3,k ) .
k=1

(105)

k=1

Now we claim that if (95) and (96) hold, then P (E) tends to zero as n → ∞. Before proving it, we show that this claim
implies the inner bound of Theorem 1.
Define
o
n

(k)
(n)
.
(106)
E4,k =
S n , VBnk (M̂Bk ), Ykn ∈
/ T0

19

c
then we have E c ⊆ E4,k
, i.e., E4,k ⊆ E. This implies that P (E4,k ) ≤ P (E) → 0 as n → ∞. Then utilizing the typical average
lemma [16], we have


lim sup Edk S n , Ŝkn
n→∞

h 

i
 h  n n  c i
c
= lim sup P (E4,k ) E dk S n , Ŝkn |E4,k + P E4,k
E dk S , Ŝk |E4,k
(107)
n→∞
h 

i
c
= lim sup E dk S n , Ŝkn |E4,k
(108)
n→∞


≤ (1 + 0 ) Edk S, Ŝk
(109)

≤ (1 + 0 ) Dk .

(110)
0

Therefore, the desired distortions are achieved for sufficiently small  .
Next we turn back to prove the claim above. Following from the multivariate covering lemma (Lemma 1), the first term of
(105), P (E1 ), vanishes as n → ∞, and according to conditional typicality lemma [16, Sec. 3.7], the second item tends to zero
as n → ∞.
Now we focus on the third term of (105). E 3,k can be writen as
[
E 3,k =
E I3,k ,
(111)
I⊆Bk

where
E I3,k =

n

o

(n)
VBnk (MI , m0I c ) , Ykn ∈ T0 for some m0I c , m0I c < MI c ,

(112)

with I c , Bk \I. Using the union bound we have
P (E 3,k ) ≤

X


P E I3,k .

(113)

I⊆Bk



Each Bk has a finite number of subsets, hence we only need to show for each I ⊆ Bk , P E I3,k vanishes as n → ∞. To
show this, it is needed to analyze the correlation between coding index M[1:N ] and nonchosen codewords. Specifically, M[1:N ]
depends on the source sequence and the entire codebook, and hence the standard packing lemma cannot be applied directly.
This problem has been resolved by the technique developed in [15], [20].



(n)
P VBnk (MI , m0I c ) , Ykn ∈ T0 for some m0I c , m0I c < MI c

X X 

(n)
=
P M[1:N ] = m[1:N ] , Ykn = ykn , VBnk (mI , m0I c ) , ykn ∈ T0 for some m0I c , m0I c < mI c

(114)

n
m[1:N ] yk

≤

X X

X




(n)
P M[1:N ] = m[1:N ] , Ykn = ykn , VBnk (mI , m0I c ) , ykn ∈ T0

(115)

n
m[1:N ] yk
m0I c :m0I c <mI c

where (115) follows from the union bound.
Define a sub-codebook as
n




o
n
00
00
00
00
00
0
C(mI ,m0Ic ) = V[1:N
m
,
m
,
m
:
∀
m
,
m
,
m
<
m
.
c
c
c
c
c
c
I
I
Bk
I
Bk
I
I
]

(116)

Define another coding index as M̃[1:N ] which is generated by performing the same coding process as M[1:N
 ] but on the codebook

n
C(mI ,m0Ic ) , i.e., given the source sequence sn , the encoder finds the smallest index vector m̃[1:N ] such that sn , v[1:N
m̃
∈
[1:N ]
]

20

(n)

T ; if there is no such index vector, let m̃[1:N ] = 1. Then according to the generation process of M[1:N ] and M̃[1:N ] , we
have if M[1:N ] = m[1:N ] , then M̃[1:N ] = m[1:N ] . Now continuing with (115), we have



(n)
P M[1:N ] = m[1:N ] , Ykn = ykn , VBnk (mI , m0I c ) , ykn ∈ T0


X
0n
P M[1:N ] = m[1:N ] , C(mI ,m0Ic ) = c, S n = sn , VBnk (mI , m0I c ) = vD
=
k
0n ,c,sn
vB
k

n
Y

pYk |X yk,i |x v[1:N ],i (m[1:N ] ), si

o
 n 0n n 
(n)
1 vBk , yk ∈ T0

(117)

i=1

=



0n
P M[1:N ] = m[1:N ] , M̃[1:N ] = m[1:N ] , C(mI ,m0Ic ) = c, S n = sn , VBnk (mI , m0I c ) = vD
k

X
0n ,c,sn
vB
k

n
Y

pYk |X yk,i |x v[1:N ],i (m[1:N ] ), si

o
 n 0n n 
(n)
1 vBk , yk ∈ T0

(118)

i=1

≤



0n
P M̃[1:N ] = m[1:N ] , C(mI ,m0Ic ) = c, S n = sn , VBnk (mI , m0I c ) = vD
k

X
0n ,c,sn
vB
k

n
Y

pYk |X yk,i |x v[1:N ],i (m[1:N ] ), si

o
 n 0n n 
(n)
1 vBk , yk ∈ T0

(119)

i=1

=

n

Y

P M̃[1:N ] = m[1:N ] , C(mI ,m0Ic ) = c, S n = sn
pYk |X yk,i |x v[1:N ],i (m[1:N ] ), si

X
0n ,c,sn
vB

i=1

k



 n
o

(n)
P VBnk (mI , m0I c ) = vB0nk |C(mI ,m0Ic ) = c 1 vB0nk , ykn ∈ T0
(120)
n
o




n
where c = v[1:N
mI , m00I c , m00Bc : ∀ m00I c , m00Bc , m00I c < m0I c , and (120) follows from the fact that VBnk (mI , m0I c ) →
k
k
 ]

C(mI ,m0Ic ) → S n , M̃[1:N ] forms a Markov chain.
Define
J , {J ⊆ Bk : if j ∈ J , then Aj ⊆ J } .
(121)
Then any set I ⊆ Bk can be transformed into a J (I) ∈ J by removing all the elements j’s such that Aj * I. Denote
J c , Bk \J . Then according to the generation process of the codebook, continuing with (120), we have
 n
o
X 

(n)
P VBnk (mI , m0I c ) = vB0nk |C(mI ,m0Ic ) = c 1 vB0nk , ykn ∈ T0
0n
vB

k

=

 n
o
X 

(n)
0n
n
0n
n
P VJnc (mI , m0I c ) = vJ
1
v
(m
)
,
v
∈
T
c |C(mI ,m0 c ) = c
c , yk
0
J
J
J

I

(122)

0n
vJ
c

=

n
X Y Y
0n
vJ
c


 n
o

(n)
0
0
n
0n
n
pVj |VAj vj,i
|vAj ∩J ,i (mJ ) , vA
1 vJ
(mJ ) , vJ
∈ T0
c
c , yk
j ∩J ,i

(123)

j∈J c i=1

≤ 2n(H(VJ c |Yk VJ )−

P

j∈J c

H (Vj |VAj )+(|J c |+1)δ (0 ))

,

(124)

where δ (0 ) is a term that tends to zero as 0 → 0, and (124) follows from the fact that i=1 pVj |VAj vj,i |vAj ,i ≤


n
o

0
0
(n)
(n)
n
0n
n
0n
n
2−n(H (Vj |VAj )−δ( )) for any vjn , vA
∈ T0 and
vJ
∈ T0
≤ 2n(H(VJ c |Yk VJ )+δ( )) for any
c : vJ , vJ c , yk
j

n
ykn , vJ
.
Combining (115), (120) and (124) gives



(n)
P VBnk (MI , m0I c ) , Ykn ∈ T0 for some m0I c , m0I c < MI c
Qn

≤ 2n(

P

j∈J c

P
rj −( j∈J c H (Vj |VAj )−H(VJ c |Yk VJ )−(|J c |+1)δ (0 )))

.

(125)

Hence if j∈J c rj < j∈J c H Vj |VAj − H (VJ c |Yk VJ ) − (|J c | + 1) δ (0 ) for all J ∈ J, then the third term of (105)
tends to zero as n → ∞. Letting 0 small enough, this completes the proof of the inner bound.
Besides, it is worth noting that although the multivariate packing lemma (Lemma 2) has not been employed directly in the
proof, the derivation after (123) is essentially the same as that of the multivariate packing lemma.
P

P



21

(o)

B. Outer Bound D1

n
For fixed pU[1:L] |S , we first introduce a set of auxiliary random variables U[1:L]
that follow the distribution
n
n
n
n
n
Hence the Markov chains U[1:L] → S → X → Yk → Ŝk , 1 ≤ k ≤ K hold. Consider that

Qn

i=1

I (YAn ; UBn |UCn )
n
X

=
I YAn ; UB,t |UCn UBt−1
=
=
=
≥

t=1
n
X
t=1
n
X
t=1
n
X
t=1
n
X


pU[1:L] |S u[1:L],i |si .

(126)



H UB,t |UCn UBt−1 − H UB,t |UCn UBt−1 YAn

(127)

H (UB,t |UC,t ) − H UB,t |UCn UBt−1 YAn

(128)

I UB,t ; UCn UBt−1 YAn |UC,t





(129)



I UB,t ; ŜA,t |UC,t

(130)

t=1



= nI UB,Q ; ŜA,Q |UC,Q Q


= nI UB,Q ; ŜA,Q Q|UC,Q


≥ nI UB,Q ; ŜA,Q |UC,Q


= nI UB ; ŜA |UC ,

(131)
(132)
(133)
(134)

where the time-sharing random variable Q is defined to be uniformly distributed [1 : n] and independent of all other random
variables, and in (134), Ul , Ul,Q , Ŝk , Ŝk,Q , 1 ≤ l ≤ L, 1 ≤ k ≤ K.
On the other hand,
I (YAn ; UBn |UCn )
n
X

I YA,t ; UBn |UCn YAt−1
=

(135)

t=1



= nI YA,Q ; UBn |UCn YAQ−1 Q


= nI YA ; ŨB |ŨC ỸA ,

(136)
(137)

Set Yk , Yk,Q , Ũl , Uln , Ỹk , YkQ−1 Q, 1 ≤ l ≤ L, 1 ≤ k ≤ K, then combining (134) and (137) gives us the outer bound
(o)
D1 .
(o)

C. Outer Bound D2

n
For fixed pU[1:L] |Y[1:K] , we first introduce a set of auxiliary random variables U[1:L]
that follow distribution
n

n

n
Y[1:K]

n
U[1:L]

(o)
R1 ,

Qn

i=1

pU[1:L] |Y[1:K] u[1:L],i |y[1:K]

Hence the Markov chains S → X →
→
hold. Note that different from the proof of
the auxiliary random
n
variables U[1:L]
here is introduced at receiver sides, and pY[1:K] U[1:L] |X = pU[1:L] |Y[1:K] pY[1:K] |X forms a new memoryless

22

broadcast channel. Consider that
I (S n ; YBn UBn0 |YCn UCn0 )
≤ I (X n ; YBn UBn0 |YCn UCn0 )
n
X

=
I X n ; YB,t UB0 ,t |YCn UCn0 YBt−1 UBt−1
0
=
≤
=

t=1
n
X
t=1
n
X
t=1
n
X

(138)
(139)



n
H YB,t UB0 ,t |YCn UCn0 YBt−1 UBt−1
− H YB,t UB0 ,t |YCn UCn0 YBt−1 UBt−1
0
0 X

(140)

H (YB,t UB0 ,t |YC,t UC 0 ,t ) − H (YB,t UB0 ,t |YC,t UC 0 ,t Xt )

(141)

I (YB,t UB0 ,t ; Xt |YC,t UC 0 ,t )

(142)

t=1

= nI (YB,Q UB0 ,Q ; XQ |YC,Q UC 0 ,Q Q)
= nH (YB,Q U

B0 ,Q

|YC,Q U

C 0 ,Q

(143)

Q) − nH (YB,Q U

B0 ,Q

|YC,Q U

C 0 ,Q

XQ Q)

(144)

≤ nH (YB,Q UB0 ,Q |YC,Q UC 0 ,Q ) − nH (YB,Q UB0 ,Q |YC,Q UC 0 ,Q XQ )

(145)

= nI (YB,Q UB0 ,Q ; XQ |YC,Q UC 0 ,Q )

(146)

= nI (X; YB UB0 |YC UC 0 ) ,

(147)

t−1 n
t−1
n
n
Markov chain U[1:L]
U[1:L],t+1 Y[1:K]
Y[1:K],t+1
X t−1 Xt+1
→ Xt → Y[1:K],t U[1:L],t
(145) follows from the Markov chain Q → XQ → Y[1:K],Q U[1:L],Q and the fact

where (141) follows from the
and the fact
conditioning reduces entropy,
conditioning
reduces entropy, the time-sharing random variable Q is defined to be uniformly distributed [1 : n] and independent of all other
random variables, and in (147), Ul , Ul,Q , Yk , Yk,Q , X , XQ , 1 ≤ l ≤ L, 1 ≤ k ≤ K.
On the other hand,
I (S n ; YBn UBn0 |YCn UCn0 )
n
X

I St ; YBn UBn0 |YCn UCn0 S t−1
=

(148)

t=1


= nI SQ ; YBn UBn0 |YCn UCn0 S Q−1 Q


= nI S; ỸB ŨB0 |ỸC ŨC 0 ,

(149)
(150)

Set S , SQ , Ũl , Uln S Q−1 Q, Ỹk , Ykn S Q−1 Q, 1 ≤ l ≤ L, 1 ≤ k ≤ K, then combining (147) and (150) gives us the outer
(o)
bound D2 .
A PPENDIX D
P ROOF OF T HEOREM 6
Observe that if there is no information transmitted over the channel, receiver k could produce a reconstruction within the
distortion βk . Hence we only need consider the case of D[1:K] with
Dk ≤ βk , 1 ≤ k ≤ K.

(151)

For the Wyner-Ziv binary broadcast with bandwidth mismatch case (the bandwidth mismatch factor b), Theorem 5 states
that if D[1:K] is achievable, then there exists some pmf pVK |S pVK−1 |VK · · · pV1 |V2 and functions ŝk (vk , zk ) , 1 ≤ k ≤ K such
that




Ed S, Ŝk = P Ŝk ⊕ S = 1 ≤ Dk ,
(152)
and for any pmf pUK−1 |S pUK−2 |UK−1 · · · pU1 |U2 ,
1
(I (Vk ; Uk |Uk−1 Zk ) : k ∈ [1 : K]) ∈ RBBC
b
holds, where the capacity of binary broadcast channel RBBC is given in (34) [13].
Define the sets
Ak = {vk : ŝk (vk , 0) = ŝk (vk , 1)} , 1 ≤ k ≤ K,

(153)

(154)

so that their complements
Ack = {vk : ŝk (vk , 0) 6= ŝk (vk , 1)} , 1 ≤ k ≤ K.

(155)

23

By hypothesis,


h 

i
i
h 

Ed S, Ŝk = P(Vk ∈ Ak )E d S, Ŝk |Vk ∈ Ak + P(Vk ∈ Ack )E d S, Ŝk |Vk ∈ Ack
≤ Dk .

(157)

We first show that
To do this, we write

(156)

h 

i
E d S, Ŝk |Vk ∈ Ack ≥ βk .

(158)

i
h 


i
X P(Vk = vk ) h 
E d S, Ŝk |Vk ∈ Ack =
E
d
S,
Ŝ
|V
=
v
.
k
k
k
P(Vk ∈ Ack )
c

(159)

vk ∈Ak

If vk ∈ Ack and ŝk (vk , 0) = 0 then ŝk (vk , 1) = 1. Therefore, for such vk ,
h 

i
E d S, Ŝk |Vk = vk = P (Zk = 0, S = 1|Vk = vk ) + P (Zk = 1, S = 0|Vk = vk )

(160)

= P (S = 1|Vk = vk ) P (Zk = 0|S = 1) + P (S = 0|Vk = vk ) P (Zk = 1|S = 0)

(161)

= βk ,

(162)
Ack

where (161) follows that Zk → S → Vk forms a Markov chain. If vk ∈
but ŝk (vk , 0) = 1, then for such vk ,
h 

i
E d S, Ŝk |Vk = vk = 1 − βk ≥ βk ,
since βk ≤ 12 . Therefore, (158) follows from (162) and (163).
Now we write
h 


i
i
X P(Vk = vk ) h 
E d S, Ŝk |Vk ∈ Ak =
E d S, Ŝk |Vk = vk ,
P(Vk ∈ Ak )

(163)

(164)

vk ∈Ak

dvk

P(Vk =vk )
P(Vk ∈Ak ) , µk

, P(Vk ∈ Ak ),
h 

i
, E d S, Ŝk |Vk = vk = P (S 6= gk (vk ) |Vk = vk ) ,

and define gk (vk ) , ŝk (vk , 0) , λvk ,

(165)

then utilizing (157) and (158), we have
d0k , µk

X

λvk dvk + (1 − µk ) βk ≤ Dk .

(166)

vk ∈Ak

Next we will show
I (Vk ; Uk |Zk ) ≥

βk − Dk
(H2 (βk ? τk ) − (H4 (αk , βk , τk ) − H2 (αk ? βk ))) .
βk − αk

(167)

0
and Uk = Uk+1 ⊕ Ek0 , 1 ≤ k ≤ K − 2, where Ek0 ∼ Bern (τk0 ) is independent of all the other
Choose UK−1 = S ⊕ EK−1
0
0
0
0
random variables. Define Ek = EK−1
⊕ EK−2
⊕ · · · ⊕ Ek0 ∼ Bern (τk ) with τk = τK−1
? τK−2
? · · · ? τk0 . Then

I (Vk ; Uk |Zk ) =H (Uk |Zk ) − H (Uk |Vk , Zk )
X
=H2 (βk ? τk ) − µk
λvk H (Uk |Zk , Vk = vk )

(168)

vk ∈Ak

X P(Vk = vk )
H (Uk |Zk , Vk = vk ) .
− (1 − µk )
P(Vk ∈ Ack )
c

(169)

vk ∈Ak

For fixed vk , define a set of random variables (Vk0 , S 0 , Uk0 , Zk0 ) ∼ 1 {vk0 = vk } pSUk Zk |Vk (s0 , u0k , zk0 |vk0 ), then H (Uk0 Zk0 |Vk0 ) =
H (Uk Zk |Vk = vk ) and H (Zk0 |Vk0 ) = H (Zk |Vk = vk ). Since pSUk Zk |Vk satisfies
pSUk Zk |Vk (s0 , u0k , zk0 |vk0 ) = pS|Vk (s0 |vk0 ) pZk |S (zk0 |s0 ) pUk |S (u0k |s0 ) ,
it holds that Zk0 = S 0 ⊕ B k , Uk0 = S 0 ⊕ E k . Hence Zk0 ⊕ Uk0 = B k ⊕ E k .

(170)

24

For fixed vk , consider
H (Uk |Zk , Vk = vk ) = H (Uk Zk |Vk = vk ) − H (Zk |Vk = vk )
=H
=H
=H
=H

(Uk0 Zk0 |Vk0 ) − H (Zk0 |Vk0 )
(Uk0 |Zk0 Vk0 )
(Uk0 ⊕ Zk0 |Zk0 Vk0 )
(Bk ⊕ E k |Zk0 Vk0 )

(171)
(172)
(173)
(174)
(175)

≤ H (Bk ⊕ E k )

(176)

= H2 (βk ? τk ) .

(177)

Combine (169) and (177), then we have
X

I (Vk ; Uk |Zk ) ≥ H2 (βk ? τk ) − µk

λvk H (Uk |Zk , Vk = vk ) − (1 − µk ) H2 (βk ? τk )

(178)

vk ∈Ak

= µk H2 (βk ? τk ) − µk

X

λvk H (Uk |Zk , Vk = vk ) .

(179)

vk ∈Ak

Now we consider the second term of (179).
X
X
λvk H (Uk |Zk , Vk = vk ) =
λvk (H (Uk Zk |Vk = vk ) − H (Zk |Vk = vk ))
vk ∈Ak

(180)

vk ∈Ak

=

X

λvk (H4 (dvk , βk , τk ) − H2 (dvk ? βk ))

(181)

λvk G1 (dvk , βk , τk ) ,

(182)

vk ∈Ak

=

X
vk ∈Ak

where the function H4 (x, y, z) is defined in (55) and
G1 (x, y, z) , H4 (x, y, z) − H2 (x ? y) .

(183)

Equality (181) follows from calculating the entropies according to the definition.
Now we show that G1 (x, y, z) is concave in x. To do this, we consider
∂2
G1 (x, y, z)
∂x2
2
2
2
2
2
2
(yz − yz)
(yz − yz)
(yz − yz)
(yz − yz)
(y − y)
(y − y)
=−
−
−
−
+
+
xyz + xyz
xyz + xyz
xyz + xyz
xyz + xyz
xy + xy
xy + xy
!
!
2
2
2
2
2
2
(yz − yz)
(yz − yz)
(y − y)
(yz − yz)
(yz − yz)
(y − y)
=−
+
−
−
+
−
xyz + xyz
xyz + xyz
xy + xy
xyz + xyz
xyz + xyz
xy + xy

(184)

≤ 0,

(186)

(185)

where (186) follows from the following inequality
 2

a21
a2
1
a1
a2
+ 2 =
(b1 + b2 )
+ 2
b1
b2
b1 + b2
b1
b2


2
1
b
a
b1 a22
2 1
2
2
=
a1 + a2 +
+
b1 + b2
b1
b2

1
2
2
≥
a + a2 + 2a1 a2
b1 + b2 1
2
(a1 + a2 )
=
,
b1 + b2

(187)
(188)
(189)
(190)

for b1 , b2 > 0 and arbitrary real numbers a1 , a2 . (186) implies G1 (x, y, z) is concave in x.
Then combining the concavity of G1 (x, y, z) with (179) and (182), we have
!!
I (Vk ; Uk |Zk ) ≥ µk

H2 (βk ? τk ) − G1

X

λvk dvk , βk , τk

(191)

vk ∈Ak

= µk (H2 (βk ? τk ) − G1 (αk , βk , τk ))

(192)

25

where
αk ,

X

λ vk d vk .

(193)

vk ∈Ak

From (166), αk satisfies
µk αk + (1 − µk ) βk ≤ Dk .

(194)

Combine (194) with Dk ≤ βk (i.e., (151)), then we have
0 ≤ αk ≤ Dk ≤ βk .

(195)

Therefore,
βk − Dk
(H2 (βk ? τk ) − G1 (αk , βk , τk ))
βk − αk
βk − Dk
(H2 (βk ? τk ) − (H4 (αk , βk , τk ) − H2 (αk ? βk ))) ,
=
βk − αk

I (Vk ; Uk |Zk ) ≥

(196)
(197)

i.e., (167) holds.
Next we will show
I (Vk ; Uk |Uk−1 Zk ) ≥

βk − Dk
(H2 (βk ? τk ) − H2 (βk ? τk−1 ) − (H4 (αk , βk , τk ) − H4 (αk , βk , τk−1 ))) .
βk − α k

(198)

Consider
I (Vk ; Uk |Uk−1 Zk ) = H (Uk |Uk−1 Zk ) − H (Uk |Uk−1 Zk Vk )

(199)

= H (Uk−1 |Uk ) + H (Uk |Zk ) − H (Uk−1 |Zk ) − H (Uk |Uk−1 Zk Vk )

0
= H2 τk−1
+ H2 (βk ? τk ) − H2 (βk ? τk−1 ) − H (Uk |Uk−1 Zk Vk ) .

(200)
(201)

Write the last term as
H (Uk |Uk−1 Zk Vk )
X P(Vk = vk )
X
= − (1 − µk )
H
(U
|U
,
Z
,
V
=
v
)
−
µ
λvk H (Uk |Uk−1 , Zk , Vk = vk ) .
k
k−1
k
k
k
k
P(Vk ∈ Ack )
c
vk ∈Ak

(202)

vk ∈Ak



0
For fixed vk , define Vk0 , S 0 , Uk0 , Uk−1
, Zk0 ∼ 1 {vk0 = vk } pSUk Uk−1 Zk |Vk s0 , u0k , u0k−1 , zk0 |vk0 . Since


pSUk Uk−1 Zk |Vk s0 , u0k , u0k−1 , zk0 |vk0 = pS|Vk (s0 |vk0 ) pZk |S (zk0 |s0 ) pUk |S (u0k |s0 ) pUk−1 |Uk u0k−1 |u0k ,

(203)

0
0
= B k ⊕ E k−1 . Similar
we have Zk0 = S 0 ⊕ B k , Uk0 = S 0 ⊕ E k , Uk−1
= Uk0 ⊕ E 0 k−1 . Hence Zk0 ⊕ Uk0 = B k ⊕ E k , Zk0 ⊕ Uk−1
to the derivation for H (Uk |Uk−1 , Vk = vk ), we can write

0
H (Uk |Uk−1 , Zk , Vk = vk ) = H Uk0 |Uk−1
Zk0 Vk0
(204)

0
= H Uk0 ⊕ Zk0 |Uk−1
⊕ Zk0 , Zk0 , Vk0
(205)

0
≤ H Uk0 ⊕ Zk0 |Uk−1
⊕ Zk0
(206)

= H (Bk ⊕ E k |B k ⊕ E k−1 )

(207)

= H (Bk ⊕ E k ) + H (Bk ⊕ E k−1 |B k ⊕ E k ) − H (Bk ⊕ E k−1 )

0
= H2 τk−1
+ H2 (βk ? τk ) − H2 (βk ? τk−1 ) .

(209)

Combine (201), (202) and (209), then we have
X


0
I (Vk ; Uk |Uk−1 Zk ) ≥ µk H2 τk−1
+ H2 (βk ? τk ) − H2 (βk ? τk−1 ) − µk
λvk H (Uk |Uk−1 , Zk , Vk = vk ) .
vk ∈Ak

(208)

(210)

26

Consider the last term of (210),
X
λvk H (Uk |Uk−1 , Zk , Vk = vk )
vk ∈Ak

X

=

λvk (H (Uk |Zk , Vk = vk ) + H (Uk−1 |Uk , Zk , Vk = vk ) − H (Uk−1 |Zk , Vk = vk ))

(211)



0
λvk H (Uk , Zk |Vk = vk ) + H2 τk−1
− H (Uk−1 , Zk |Vk = vk )

(212)

vk ∈Ak

X

=

vk ∈Ak

X

0
= H2 τk−1
+
λvk (H4 (dvk , βk , τk ) − H4 (dvk , βk , τk−1 ))

(213)

vk ∈Ak

X

0
= H2 τk−1
+
λvk G2 (dvk , βk , τk , τk−1 ) ,

(214)

vk ∈Ak

where (213) is by directly calculating the entropies according to the definition, and
G2 (x, y, z, t) , H4 (x, y, z) − H4 (x, y, t) .

(215)

Note that function G1 (x, y, z) is a special case of function G2 (x, y, z, t) given t = 12 , i.e.,


1
G1 (x, y, z) = G2 x, y, z,
.
2

(216)

Now we show that G2 (x, y, z, t) is concave in x when 0 ≤ z ≤ t ≤ 21 , which generalizes the concavity of G1 (x, y, z). To
do this, we consider
∂2
G2 (x, y, z, t)
∂x2
2
2
2
2
2
2
2
2
yt − yt
yt − yt
yt − yt
yt − yt
(yz − yz)
(yz − yz)
(yz − yz)
(yz − yz)
=−
−
−
−
+
+
+
+
, (217)
xyz + xyz
xyz + xyz
xyz + xyz
xyz + xyz
xyt + xyt
xyt + xyt
xyt + xyt
xyt + xyt
and
∂
∂t




∂2
∂
G2 (x, y, z, t) =
∂x2
∂t
=

2
2 !
yt − yt
yt − yt
∂
+
+
∂t
xyt + xyt
xyt + xyt

2
2 !
yt − yt
yt − yt
+
xyt + xyt
xyt + xyt

−y 2 · y 2 · (xy + xy) · (1 − 2t) −y 2 · y 2 · (xy + xy) · (1 − 2t)
2
2 +
2
2 .
xyt + xyt
xyt + xyt
xyt + xyt
xyt + xyt

(218)
(219)

Hence for 0 ≤ t ≤ 21 ,
∂
∂t
i.e.,

∂2
∂x2 G2




∂2
G2 (x, y, z, t) ≤ 0,
∂x2

(220)

(x, y, z, t) is decreasing in t. Then we have for 0 ≤ z ≤ t ≤ 21 ,
∂2
∂2
G2 (x, y, z, t) ≤
G2 (x, y, z, z) = 0.
2
∂x
∂x2

(221)

It implies G2 (x, y, z, t) is concave in x when 0 ≤ z ≤ t ≤ 21 .
Combining (210) and (214), and utilizing the concavity of G2 (x, y, z, t), we have
!!
I (Vk ; Uk |Uk−1 Zk ) ≥ µk

H2 (βk ? τk ) − H2 (βk ? τk−1 ) − G2

X

λvk dvk , βk , τk , τk−1

(222)

vk ∈Ak

= µk (H2 (βk ? τk ) − H2 (βk ? τk−1 ) − G2 (αk , βk , τk , τk−1 ))

(223)

where αk is given by (193) and satisfies (194) and (195). Therefore,
βk − Dk
(H2 (βk ? τk ) − H2 (βk ? τk−1 ) − G2 (αk , βk , τk , τk−1 ))
βk − α k
βk − Dk
(H2 (βk ? τk ) − H2 (βk ? τk−1 ) − (H4 (αk , βk , τk ) − H4 (αk , βk , τk−1 ))) ,
=
βk − α k

I (Vk ; Uk |Uk−1 Zk ) ≥

i.e., (198) holds.
Combining (153), (167) and (198) gives Theorem 6.

(224)
(225)

27

A PPENDIX E
P ROOF OF T HEOREM 7
For the Wyner-Ziv Gaussian broadcast with bandwidth mismatch case (the bandwidth mismatch factor b), Theorem 5 states
that if D[1:K] is achievable, then there exists some pmf pVK |S pVK−1 |VK · · · pV1 |V2 and functions ŝk (vk , zk ) , 1 ≤ k ≤ K such
that


Ed S, Ŝk ≤ Dk ,
(226)
and for any pmf pUK−1 |S pUK−2 |UK−1 · · · pU1 |U2 ,
1
(I (Vk ; Uk |Uk−1 Zk ) : k ∈ [1 : K]) ∈ RGBC
(227)
b
holds, where the capacity of Gaussian broadcast channel RGBC is given in (57).
0
Choose UK−1 = S + EK−1
and Uk = Uk+1 + Ek0 , 1 ≤ k ≤ K − 2, where Ek0 ∼ N (0, τk0 ) is independent of all the other
PK−1
PK−1
random variables. Define Ek = j=k Ej0 ∼ N (0, τ k ) with τk = j=k τj0 . Then


I (V1 ; U1 |Z1 ) ≥ I Ŝ1 ; U1 |Z1
(228)


= h (U1 |Z1 ) − h U1 |Ŝ1 Z1
(229)


= h (U1 |Z1 ) − h U1 − Ŝ1 |Ŝ1 Z1
(230)


≥ h (U1 |Z1 ) − h U1 − Ŝ1
(231)
1
1
log (2πe (β1 + τ1 )) − log (2πe (D1 + τ1 ))
(232)
2
2
1
β1 + τ1
= log
,
(233)
2
D1 + τ1
where (232) follows from the fact that a Gaussian distribution maximizes the differential entropy for a given second moment.
On the other hand,


I (Vk ; Uk |Uk−1 Zk ) ≥ I Ŝk ; Uk |Uk−1 Zk
(234)




= I Ŝk ; Uk |Zk − I Ŝk ; Uk−1 |Zk
(235)




= h (Uk |Zk ) − h (Uk−1 |Zk ) + h Uk−1 |Zk Ŝk − h Uk |Zk Ŝk .
(236)
≥

The first two terms of (236)
h (Uk |Zk ) − h (Uk−1 |Zk ) =

βk + τk
1
log
.
2
βk + τk−1

(237)

The last two terms of (236)








0
h Uk−1 |Zk Ŝk − h Uk |Zk Ŝk = h Uk−1 |Zk Ŝk − h Uk |Zk Ŝk Ek−1




0
= h Uk−1 |Zk Ŝk − h Uk−1 |Zk Ŝk Ek−1


0
= I Uk−1 ; Ek−1
|Zk Ŝk



0
0
= h Ek−1
− h Ek−1
|Zk Ŝk Uk−1



0
0
= h Ek−1
− h Ek−1
|Zk , Ŝk , Uk−1 − Ŝk



0
0
− h Ek−1
|Uk−1 − Ŝk
≥ h Ek−1


0
0
= I Ek−1
; S − Ŝk + Ek + Ek−1

(238)
(239)
(240)
(241)
(242)
(243)
(244)

Dk + τk−1
1
log
,
(245)
2
Dk + τk
where (245) is by applying the mutual information game result that Gaussian noise is the worst additive noise under a variance
0
constraint [14, p. 298, Problem 9.21] and taking Ek−1
as the channel input.
Combining (236), (237) and (245), we have
1
(βk + τk ) (Dk + τk−1 )
I (Vk ; Uk |Uk−1 Zk ) ≥ log
.
(246)
2
(βk + τk−1 ) (Dk + τk )
(227), (233) and (246) imply Theorem 7.
≥

28

R EFERENCES
[1] L. Yu, H. Li, and W. Li, “Distortion bounds for source broadcast over degraded channel,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Barcelona, Spain,
Jul. 2016, pp. 1834–1838.
[2] C. E. Shannon, “A mathematical theory of communication,” Bell Syst. Tech. J., vol. 27, pp. 623–656, Oct. 1948.
[3] T. J. Goblick, “Theoretical limitations on the transmission of data from analog sources,” IEEE Trans. Inf. Theory, vol. IT-11, no. 4, pp. 558–567, Oct.
1965.
[4] M. Gastpar, B. Rimoldi, and M. Vetterli, “To code, or not to code: Lossy source-channel communication revisited,” IEEE Trans. Inf. Theory, vol. 49,
no. 5, pp. 1147–1158, May 2003.
[5] C. E. Shannon, “Communication in the presence of noise,” Proc. IRE, vol. 37, no. 1, pp. 10-21, Jan. 1949.
[6] S. Shamai, S. Verdu, and R. Zamir, “Systematic lossy source/channel coding,” IEEE Trans. Inf. Theory, vol. 44, no. 3, pp. 564–579, Mar. 1998.
[7] V. Prabhakaran, R. Puri, and K. Ramchandran, “Hybrid digital-analog codes for source-channel broadcast of Gaussian sources over Gaussian channels,”
IEEE Trans. Inf. Theory, vol. 57, no. 7, pp.4573-4588, Aug. 2011.
[8] Z. Reznic, M. Feder, and R. Zamir, “Distortion bounds for broadcasting with bandwidth expansion,” IEEE Trans. Inf. Theory, vol. 52, no. 8, pp.
3778–3788, Aug. 2006.
[9] C. Tian, S. Diggavi, and S. Shamai, “Approximate characterizations for the Gaussian source broadcasting distortion region,” IEEE Trans. Inf. Theory,
vol. 57, no. 1, pp. 124-136, Jan. 2011.
[10] L. Yu, H. Li, and W. Li, “Comments on ‘Approximate characterizations for the Gaussian source broadcast distortion region’,” IEEE Trans. Inf. Theory,
vol. 62, no. 10, pp. 5966-5969, 2016. [Online]. Available: https://arxiv.org/abs/1607.08292.
[11] K. Khezeli, and J. Chen “A source-channel separation theorem with application to the source broadcast problem,” IEEE Trans. Inf. Theory, vol. 62, no.
4, pp. 1764-1781, 2016.
[12] K. Khezeli, and J. Chen “Outer bounds on the admissible source region for broadcast channels with correlated sources,” IEEE Trans. Inf. Theory, vol.
61, pp. 4616-4629, Sep. 2015.
[13] P. P. Bergmans, “Random coding theorem for broadcast channels with degraded components,” IEEE Trans. Inf. Theory, vol. 19, no. 2, pp. 197-207,
1973.
[14] T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, New York, 1991.
[15] P. Minero, S. H. Lim, and Y. H. Kim, “A unified approach to hybrid coding,” IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 1509-1523, 2015.
[16] A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge University Press, 2011.
[17] J. Nayak, E. Tuncel, and D. Gündüz, “Wyner-Ziv coding over broadcast channels: Digital schemes,” IEEE Trans. Inf. Theory, vol. 56, no. 4, pp.
1782–1799, Apr. 2010.
[18] Y. Gao and E. Tuncel, “Wyner-Ziv coding over broadcast channels: Hybrid digital/analog schemes,” IEEE Trans. Inf. Theory, vol. 57, no. 9, pp.
5660–5672, Sept. 2011.
[19] O. Shayevitz, and M. Wigger, “On the capacity of the discrete memoryless broadcast channel with feedback,” IEEE Trans. Inf. Theory, vol. 57, no. 9,
pp. 5660–5672, Sep. 2011.
[20] S.-H. Lee and S.-Y. Chung, “A unified approach for network information theory,” [Online]. Available: http://arxiv.org/abs/1401.6023.
[21] M. H. Yassaee, M. R. Aref, and A. Gohari, “Achievability proof via output statistics of random binning,” IEEE Trans. Inf. Theory, vol. 60, pp. 6760–6786,
Nov. 2014.
[22] P Gács and J. Körner, “Common information is far less than mutual information Probl. Contr lnform. Theory vol. 2, no. 2, pp. 149162, 1973.
[23] R. Ahlswede and J. Körner, “On common information and related characteristics of correlated information sources,” in Proc. 7th Prague Conf. Inf
Theory, 1974.

