1

Caching and Coded Delivery over Gaussian
Broadcast Channels for Energy Efficiency

arXiv:1712.03433v1 [cs.IT] 9 Dec 2017

Mohammad Mohammadi Amiri and Deniz Gündüz

Abstract
A cache-aided K-user Gaussian broadcast channel (BC) is considered. The transmitter has a library
of N equal-rate files, from which each user demands one. The impact of the equal-capacity receiver cache
memories on the minimum required transmit power to satisfy all user demands is studied. Considering
uniformly random demands across the library, both the minimum average power (averaged over all
demand combinations) and the minimum peak power (minimum power required to satisfy all demand
combinations) are studied. Upper bounds are presented on the minimum required average and peak
transmit power as a function of the cache capacity considering centralized caching. The proposed
scheme is then extended to the decentralized caching scenario. The lower bounds on the minimum
required average and peak power values are also derived assuming uncoded cache placement. The
bounds for both the peak and average power are shown to be tight in the centralized scenario through
numerical results. The results in this paper show that proactive caching and coded delivery can provide
significant energy savings in wireless networks.

I. I NTRODUCTION
We study proactive content caching to user devices and coded delivery [1], assuming that the
delivery phase takes place over a noisy channel. In particular we consider a Gaussian broadcast
channel (BC) from the server to the users. Several other recent papers have studied delivery
over noisy channels. Fading and interference channel models are considered in [2] and [3],
respectively. In [4] and [5], centralized caching is considered while the delivery phase takes
place over a packet-erasure BC. The capacity-memory trade-off is investigated in this setting
assuming that only the weak users have caches, which requires knowledge about the channel
qualities in the delivery phase in advance. Proactive caching and coded delivery over a Gaussian
Part of this work was presented at the IEEE International Symposium on Information Theory, Aachen, Germany, June 2017
[13].

2

BC is studied in [6] in the high power regime. In [7] cache-aided data delivery is studied
over a degraded BC in a centralized setting. Serving the users with a multi-antenna server over a
Gaussian BC is studied in [8]–[10] for different scenarios of channel state information availability
at the transmitter during the delivery phase.
While most of the previous works on coded delivery over noisy wireless broadcast channels
focus on the high signal-to-noise ratio (SNR) regime; in this work, our goal is to highlight the
benefits of proactive caching and coded delivery from an energy efficiency perspective. The
impact of proactive caching on energy efficiency was previously studied in [11] and [12] in
an offline scenario, assuming known demands and channel conditions. However, these works
consider only proactive caching and do not benefit from coded delivery.
In the aforementioned works [3]–[7], users’ channel conditions during the delivery phase are
assumed to be known in advance during the placement phase. However, in practical wireless
networks, it is often not possible to know the identities of users that will participate in a particular
delivery phase, let alone their channel conditions. Therefore, our goal here is to study the benefits
of proactive caching in reducing the transmit power, assuming that the noiseless cache placement
phase is carried out without the knowledge of channel conditions during the delivery phase.
Assuming that all the files are equally likely to be requested by each user, we first consider
the minimum required average power to serve all the users, averaged over all the user demand
combinations. We then consider the lowest transmit power required to satisfy the worst-case
demand combination, called the peak power. Building upon our previous work in [13], we first
provide upper bounds on the minimum average and peak power values as a function of the file
rate and the cache capacity, proposing an achievable scheme with centralized cache placement.
We then extend the achievable scheme to the decentralized caching scenario. The proposed
delivery strategy employs superposition coding and power allocation for coded content delivery.
We further derive lower bounds on the performance assuming an uncoded cache placement phase.
The achievable transmit power for any demand combination is developed thanks to the degradeness of a Gaussian BC. We show that the proposed achievable scheme reduces the transmit power
significantly, even with the availability of a small cache capacity at each receivers, for both the
centralized and decentralized scenarios. The gap between the achievable transmit powers required
for centralized and decentralized caching scenarios with the same system parameters is shown
to be relatively small, which shows that the power loss is small going from a centralized to a
more practical decentralized scenario. Furthermore, numerical results show that the gap between

3

the peak and average transmit powers of the proposed achievable scheme for the centralized
scenario and the corresponding lower bound is negligible. Numerical results also illustrate that
adjusting the transmit power based on the demand combination can significantly reduce the
power compared to the worst-case demand combination.
The rest of the paper is organized as follows. In Section II, system model and preliminaries are
introduced. The main results of the paper are summarized, and simulation results are presented in
Section III. The proposed caching and coded delivery scheme is presented for the centralized and
decentralized settings in Section IV and Section V, respectively. Finally the paper is concluded
in Section VI. The details of the proofs are provided in the Appendix.
II. S YSTEM M ODEL

AND

P RELIMINARIES

We study cache-aided content delivery over a K-user Gaussian BC. The server has a library


∆
of N files, W = (W1 , ..., WN ), each distributed uniformly over the set1 2nR , where R is
the rate of the files and n denotes the blocklength, referring to n uses of the BC. Each user has
∆

a cache of size nMR bits. We define the normalized global cache capacity as t = MK/N.
Data delivery from the server to the users takes place in two phases. Cache memories of the
users are filled during the initial placement phase, which takes place within a period of low
traffic; and therefore, data delivery in the placement phase is assumed to be error-free; however,
without either the knowledge of the user demands, or the users’ future channel conditions when
they place their requests. The caching function for user k ∈ [K] is given by
φk :

 nR N


2
→ 2nM R ,

(1)

which maps the library to the cache content Uk of user k, i.e., Uk = φk (W), for k ∈ [K].
During the peak traffic period, each user requests a single file from the library, where dk ∈ [N]
denotes the index of the file requested by user k ∈ [K]. We assume that the user demands
are independent and uniformly distributed over the file library; that is Pr {dk = i} = 1/N,
∆

∀i ∈ [N], ∀k ∈ [K], and d = (d1 , ..., dK ) denotes the demand vector. The requests must be
satisfied simultaneously during the delivery phase. As opposed to the placement phase, the data
delivery in the delivery phase takes place over a noisy BC, characterized as follows:
Yk,i (W, d) = hk Xi (W, d) + Zk,i ,
1

For any positive integer i, [i] denotes the set {1, ..., i}.

for i ∈ [n], k ∈ [K],

(2)

4

where Xi (W, d) denotes the transmitted signal from the server at time i, hk is a real channel
gain between the server and user k, Zk,i is the zero-mean unit-variance real Gaussian noise at
user k at time i, i.e., Zk,i ∼ N (0, 1), and Yk,i (W, d) is the signal received at user k. The noise
components are assumed to be independent and identically distributed (i.i.d.) across time and
receivers. Without loss of generality, we assume that h21 ≤ h22 ≤ · · · ≤ h2K . The channel input
vector Xi (W, d) is generated by the delivery function
ψ:



2nR

N

× [N]K → Rn .

(3)
∆ 1
n

The average power of the channel input vector X n (W, d) is given by P (W, d) =

We define the average power of this encoding function for demand vector d as

n
P

i=1

Xi2 (W, d).

∆

P (d) = max P (W, d) ,
W1 ,...,WN

(4)

where the maximization is over all possible realizations of the file library.
User k ∈ [K] reconstructs Ŵdk using its channel output Ykn (W, d), local cache contents Uk ,
∆

channel vector h = (h1 , ..., hK ), and demand vector d through the following function
µ k : Rn ×

 nM R 


2
× RK × [N]K → 2nR ,

where Ŵdk = µk (Ykn (W, d) , Uk , h, d). The probability of error is defined as


K n
 [ [
o
∆
Ŵdk 6= Wdk
.
Pe = Pr


K
d∈[N ]

(5)

(6)

k=1

An (n, R, M) code for the above caching system consists of K caching functions φ1 , . . . , φK ,


channel encoding function ψ, and K decoding functions µ1 , . . . , µK . We say that an R, M, P̄ , P̂

tuple is achievable if for every ε > 0, there exists an (n, R, M) code with sufficiently large n,

which satisfies Pe < ε, Ed [P (d)] ≤ P̄ , and P (d) ≤ P̂ , ∀d. For given rate R and normalized
cache capacity M, the average and peak power-memory trade-offs are defined, respectively, as


∆
P̄ ∗ (R, M ) = inf P̄ : R, M, P̄ , ∞ is achievable ,
n


o
∆
P̂ ∗ (R, M ) = inf P̂ : R, M, P̂ , P̂ is achievable .

(7a)
(7b)

Note that P̄ ∗ is evaluated by allowing a different transmission power for each demand combination, and minimizing the average power value across demand combinations. On the other hand,

5

P̂ ∗ characterizes the worst-case transmit power, that is, the minimum transmit power required
to satisfy all possible demand combinations.
We consider both the centralized and decentralized caching scenarios, and assume, for both
that the placement phase is performed without any information about the channel qualities during
the delivery phase. This assumption is trivial in the decentralized scenario as we do not even
know the active users in advance. On the other hand, even in the centralized scenario, it may
not be possible to know the future states of wireless channels.
Proposition 1. [14] Consider a K-user Gaussian BC presented above with M = 0, where a
distinct message of rate Rk is targeted for user k, for k ∈ [K]. The minimum total power P
that is required to deliver all K messages reliably can be achieved by superposition coding with
Gaussian codewords of power αk P allocated for user k, ∀k ∈ [K], where2
!
 Y

 2Rk
i−1
K  2Ri
X
2
−
1
2
−1
22Rj ,
1 + h2k
αk P =
2
h2k
h
i
j=k+1
i=k+1

(8)

and the total transmitted power is
 k−1
K  2Rk
X
2
− 1 Y 2Ri
P =
2 .
h2k
i=1

(9)

k=1

For a demand vector d in the delivery phase, we denote the number of distinct demands by
Nd , where Nd ≤ min {N, K}. Let Ud denote the set of users with distinct requests, which have
the worst channel qualities; that is, Ud consists of Nd indices corresponding to users with distinct
requests, where a user is included in set Ud iff it has the worst channel quality among all the
users with the same demand, i.e., if k ∈ Ud and dk = dm for some m ∈ [K], then h2k ≤ h2m ,
or equivalently, k ≤ m. Note that, for any demand vector d, 1 ∈ Ud . For given d and user k,
k ∈ [K], let Ud,k denote the set of users in Ud which have better channels than user k:
∆

Ud,k = {i ∈ Ud : i > k} ,

k ∈ [K].

∆

We denote the cardinality of Ud,k by Nd,k , i.e., Nd,k = |Ud,k |.
2

For two integers i and j, if i > j, we assume that

j
P

n=i

an = 0, and

j
Q

n=i

an = 1, where an is an arbitrary sequence.

(10)

6

III. M AIN R ESULTS
We present the upper bounds on P̄ ∗ (R, M) and P̂ ∗(R, M) in the following theorem, while the
schemes achieving these bounds for centralized and decentralized caching scenarios are presented
in Section IV and Section V, respectively.
Theorem 1. In centralized caching followed by delivery over a Gaussian BC, we have
! i−1
#
" K
2RC
X X
Y
d,i − 1
C
2
1
∆
C
22Rd,j ,
P̄ ∗(R, M) ≤ P̄UB
(R, M) = K
2
N
h
i
K
j=1
i=1

(11a)

d∈[N ]

where3

C
Rd,k

and


( K−k )
(K−k)


 ⌊t⌋
(⌊t⌋ + 1 − t) R + ⌊t⌋+1
(t − ⌊t⌋) R,
if k ∈ Ud ,
K
K
)
(⌊t⌋)
(⌊t⌋+1
∆
(11b)
=
K−k−N
K−k−N
K−k
d,k
−
(K−k
)
)−( ⌊t⌋+1d,k )
(⌊t⌋+1

⌊t⌋ ) (
⌊t⌋

(⌊t⌋ + 1 − t) R +
(t − ⌊t⌋) R, otherwise,

K
K
)
)
(⌊t⌋
(⌊t⌋+1
∆

C
P̂ ∗ (R, M) ≤ P̂UB
(R, M) =

K
X
i=1

C

22R̂d,i − 1
h2i

! i−1
Y

C

22R̂d,j ,

(12a)

j=1

where
C
R̂d,k

 K−k
K−k
)
)
(⌊t⌋+1

 ( ⌊t⌋
(⌊t⌋
+
1
−
t)
R
+
(t − ⌊t⌋) R, if k ∈ [min{N, K}],
K
K
∆
)
(
(
⌊t⌋
⌊t⌋+1)
=

0,
otherwise.

(12b)

Theorem 2. For decentralized caching followed by delivery over a Gaussian BC, we have
#
! i−1
" K
2RD
Y
X X
d,i − 1
D
2
1
∆
2R
D
(13a)
2 d,j ,
P̄ ∗ (R, M) ≤ P̄UB
(R, M) = K
2
N
h
i
K
j=1
i=1
d∈[N ]

where, for k = 1, ..., K,
∆

D
Rd,k
=

3



 1−


M k
R,
N

if k ∈ Ud ,

 

 1− M k 1− 1−
N

Given two integers i and j with i < j, we assume

i
j



= 0.


M Nd,k
N



R,

otherwise,

(13b)

7

and
min{N,K}

X

∆

D
(R, M) =
P̂ ∗ (R, M) ≤ P̂UB

i=1

i

22R(1− N ) − 1
h2i
M

!

2R N −1
2 (M )



i−1
1−(1− M
N)

.

(14)

If we constrain the placement phase to uncoded caching, we can lower bound P̄ ∗ (R, M ) and
P̂ ∗ (R, M ) as in the following theorem, whose proof is given in Appendix A.
Theorem 3. In cache-aided content delivery over a Gaussian BC with uncoded cache placement
phase, the minimum required average power is lower bounded by P̄LB (R, M) defined as
! i−1
#
"N
d
X
22R(1−min{iM/N,1}) − 1 Y 2R(1−min{jM/N,1})
∆
,
(15)
2
P̄LB (R, M) = EUd
2
h
(i)
π
U
j=1
i=1
d

where EUd [·] takes the expectation over all possible sets Ud , and πS is a permutation over any
subset of users S ⊂ [K], such that h2πS (1) ≤ h2πS (2) ≤ · · · ≤ h2πS (|S|) . The minimal required peak
transmit power for the same system is lower bounded by P̂LB (R, M) defined as


! i−1
|S|

X
2R(1−min{iM/N,1})
Y
2
−1
∆
2R(1−min{jM/N,1})
.
2
P̂LB (R, M) =
max

S⊂[min{N,K}] 
h2πS (i)
j=1
i=1

(16)

Remark 1. We note that, considering all possible demand vectors, we have a total of 2K−1

different Ud sets. This follows from the fact that Nd ≤ K and 1 ∈ Ud , ∀d. For a given demand
vector d, let Ud = {u1 , u2 , ..., uNd }, where 1 = u1 ≤ u2 ≤ · · · ≤ uNd . The number of demand
vectors with the same Ud is given by
∆

NUd =

!

Nd
Y
N
uj+1 −uj −1
,
Nd !
j
Nd
j=2



(17)

∆

where we define uNd +1 = K + 1. Thus, the lower bound in (15) reduces to
! i−1
#
"N
d
X
X
22R(1−min{iM/N,1}) − 1 Y 2R(1−min{jM/N,1})
1
. (18)
NUd
2
P̄LB (R, M) = K
2
N
h
(i)
π
U
j=1
i=1
Ud ⊂[K],1∈Ud

d

A. Numerical Results
Here, for simulation results, we assume that the rate of the files in the library is fixed to
R = 1, and 1/h2k = 2 − 0.2(k − 1), for k = 1, . . . , K.

8

500
x

o

x

1200

o

D
P̂UB
(R, M ), K = 5, N = 8
C
P̂UB (R, M ), K = 5, N = 8
P̂LB (R, M ), K = 5, N = 8

1000

Peak power, P̂

Average power, P̄

400

1400

D
P̄UB
(R, M ), K = 5, N = 8
C
P̄UB
(R, M ), K = 5, N = 8
P̄LB (R, M ), K = 5, N = 8

300

200

100

0

800
600
400
200
0

0

1

2

3

Cache capacity, M
(a) Average power-memory trade-off

4

0

1

2

3

4

Cache capacity, M
(b) Peak power-memory trade-off

Fig. 1: Power-memory trade-off for a Gaussian BC with K = 5 users, and N = 8 files.

The average power-memory trade-off P̄ ∗ (R, M) and peak power-memory trade-off P̂ ∗ (R, M)
are investigated in Fig. 1a and Fig. 1b, respectively, for K = 5 users, and N = 8 files in
the library. The gap between the centralized caching and decentralized one, which measures the
power required to compensate for the decentralization of the cache placement phase, is relatively
small, particularly for small and large values of the cache capacity. We observe that the minimum
average and peak powers drop very quickly even with a small cache capacity available at the
users. The lower bound is generally tight for both average and peak power values with respect to
the upper bound for the centralized scenario for all range of cache capacities4 . As it can be seen,
the peak power values exhibit similar behaviour to the average power, with significantly higher
values. This shows that adapting the transmit power to the demand combination can reduce the
energy consumption on average, while the transmitter may need to spend significantly higher
energy for some demand combinations.
Fig. 2 illustrates the effect of number of files N on the upper bounds on the average and
peak power values for both centralized and decentralized scenarios. In Fig. 2a and Fig. 2b the
average power values and the peak power values are considered, respectively, for K = 5 users,
4

Note that the figure does not include the cache capacity range 4 ≤ M ≤ 8, in which case the three curves in both Figures
1a and 1b coincide.

9

o
x

1200

o

Average power, P̄

x

1000

o

800

o
x

x

D
P̄UB
(R, M ),
C
P̄UB
(R, M ),
D
P̄UB
(R, M ),
C
P̄UB
(R, M ),
D
P̄UB
(R, M ),
C
P̄UB
(R, M ),
D
P̄UB
(R, M ),
C
P̄UB
(R, M ),

1400
K
K
K
K
K
K
K
K

= 5, N
= 5, N
= 5, N
= 5, N
= 5, N
= 5, N
= 5, N
= 5, N

= 100
= 100
= 40
= 40
= 20
= 20
= 10
= 10

o
o
x

600
400
200
0

x

1200

Peak power, P̂

1400

1000

o

800

o

x
x

D
P̂UB
(R, M ),
C
P̂UB
(R, M ),
D
P̂UB
(R, M ),
C
P̂UB
(R, M ),
D
P̂UB
(R, M ),
C
P̂UB
(R, M ),
D
P̂UB
(R, M ),
C
P̂UB
(R, M ),

K
K
K
K
K
K
K
K

= 5, N
= 5, N
= 5, N
= 5, N
= 5, N
= 5, N
= 5, N
= 5, N

= 100
= 100
= 40
= 40
= 20
= 20
= 10
= 10

18

21

600
400
200

0

3

6

9

12

15

18

Cache capacity, M
(a) Average power-memory trade-off

21

24

0

0

3

6

9

12

15

24

Cache capacity, M
(b) Peak power-memory trade-off

Fig. 2: Power-memory trade-off for a Gaussian BC with K = 5 users, and various number of
files N ∈ {10, 20, 40, 100} in the library.

and different number of files N ∈ {10, 20, 40, 100}. As it can be seen from both figures, the
gap between the performance of the centralized and decentralized scenarios increases with the
number of files N. Another observation to be noted is the increase in the average power with the
number of files in the library, even though the number of files requested by the users remains the
same. This stems from two reasons: first, the effect of the local caches diminishes as the library
size increases; and second, the users are less likely to request the same files from a larger library
(and hence the increase in the average power values for low M values). We also observe that
the peak power values increases as well with the library size, but only for non-zero M values.
This is because the increase in the peak power is only due to the diminished utility of the cache
capacity, whereas the peak power depends only on the worst-case demand combination; and
thus, does not depend on the likelihood of common requests. We note that, for a fixed number
of users K, the gap between the average power and the peak power reduces by increasing N,
and for N ≫ K, the gap diminishes since, with high probability, the users demand distinct files.
The effect of the number of users K on the average and peak power values for both the
centralized and decentralized scenarios is shown in Fig. 3. Fig. 3a and Fig. 3b demonstrate
the average and peak power values as a function of M, respectively, for N = 10 files, and

10

o
x

Average power, P̄

500

o
x
o

400

x

D
P̄UB
(R, M ),
C
P̄UB
(R, M ),
D
P̄UB
(R, M ),
C
P̄UB
(R, M ),
D
P̄UB
(R, M ),
C
P̄UB
(R, M ),

K
K
K
K
K
K

= 5, N
= 5, N
= 4, N
= 4, N
= 3, N
= 3, N

1400

= 10
= 10
= 10
= 10
= 10
= 10

o

o
x

1000

300
200
100
0

x

1200

Peak power, P̂

600

o
x

800

D
P̂UB
(R, M ),
C
P̂UB
(R, M ),
D
P̂UB
(R, M ),
C
P̂UB
(R, M ),
D
P̂UB
(R, M ),
C
P̂UB
(R, M ),

K
K
K
K
K
K

= 5, N
= 5, N
= 4, N
= 4, N
= 3, N
= 3, N

= 10
= 10
= 10
= 10
= 10
= 10

600
400
200
0

0

1

2

3

4

0

1

Cache capacity, M
(a) Average power-memory trade-off

2

3

4

Cache capacity, M
(b) Peak power-memory trade-off

Fig. 3: Power-memory trade-off for a Gaussian BC with various number of users K ∈ {3, 4, 5},
and N = 10 in the library.

K ∈ {3, 4, 5} users. The gap between the centralized and decentralized scenarios increases with
the number of users K in both figures. The average and peak power values also increase with
K, as expected. For a fixed N value, the increase in the peak power is higher than the one in
the average power. This is due to the fact that the likelihood of common demands increases with
K, and so does the gap between the average and peak power values.
IV. C ENTRALIZED C ACHING

AND

D ELIVERY

C
Here we present our centralized caching and coded delivery scheme, which achieves P̄UB
(R, M)
C
and P̂UB
(R, M) in (11) and (12), respectively. For simplicity, we assume that both nR and

nMR are integers. The proposed scheme is first presented for integer normalized global cache
capacities, that is t ∈ [0 : K]. The scheme is then extended to any t ∈ [0, K].
A. Integer Values of Normalized Global Cache Capacity t
Here, we assume that t ∈ [0 : K]. We denote the t-element subsets of the K users by
C1t , C2t , . . . , C t K .
(t)
Placement phase: Assuming that the active users are known during the placement phase, a
centralized cache placement phase is performed without the knowledge the future user demands

11

or the channel gains in the delivery phase. Given a normalized cache size of M = tN/K,

t ∈ [0 : K], each file Wi , i ∈ [N], is split into Kt equal-length subfiles Wi,C1t , Wi,C2t , . . . , Wi,C t K ,
t)
 K( 

K
t
each of rate R/ t . User k, k ∈ [K], caches subfile Wi,Clt , if k ∈ Cl , for i ∈ [N] and l ∈ t .

Hence, the cache content of user k at the end of the placement phase is given by
Uk =

[

i∈[N ] l∈[(

[

K
t

Wi,Clt ,

for k = 1, . . . , K,

(19)

)]:k∈Clt

where, it can be checked that, the cache capacity constraint is satisfied with equality.
Delivery phase: For an arbitrary demand vector d = (d1 , . . . , dK ), we will deliver the fol K 
lowing coded message to the users in Clt+1 , ∀l ∈ t+1
:
∆

QC t+1 =
l

M

k∈Clt+1

Wdk ,C t+1\{k} ,

(20)

l

where ⊕ represents the bitwise XOR operation. Then, each user i ∈ Clt+1 can recover subfile
Wdi ,C t+1\{i} , since it has cached all the other subfiles Wdj ,C t+1\{j} , ∀j ∈ Clt+1 \{i}. Note that
l
 K 
l
K
each coded message QC t+1 , l ∈ t+1 , has a rate of R/ t . Note also that, for each k ∈ [K],
l
 
S
delivering
QC t+1 to user k enables that user to obtain all the subfiles Wdk ,Clt , ∀l ∈ Kt
and k ∈
/

l:k∈Clt+1
t
Cl . Thus,

l

together with its cache content, the demand of user k ∈ [K] is fully satisfied
S
after receiving
QC t+1 . As observed in [15], for a demand vector d with Nd distinct requests,
l
l:k∈Clt+1
 
if K − Nd ≥ t + 1, not all the coded messages QC t+1 , ∀l ∈ Kt , are required to be delivered.
l

Following [15, Lemma 1], for a demand vector d with Nd distinct requests and set Ud , let

Ud ⊂ B ⊂ [K]. We define GB as the set consisting of all the subsets of B with cardinality Nd , such
L
that all Nd users in each subset request distinct files. For any set B, we have G∈GB QB\G = 0,
where 0 denotes the all-zero vector.

Remark 2. Given a demand vector d with set Ud of size Nd < K, and for any set S ⊂ [K]\Ud
of users, by setting B = S ∪ Ud , we have
M

M
M
QB\G =
QB\G ⊕ QB\Ud =
G∈GB

G∈GB \Ud

G∈GB \Ud

QB\G



⊕ QS = 0,

(21)

which leads to
QS =

M

G∈GB \Ud

QB\G .

(22)

Thus, having received all the coded messages QB\G , ∀G ∈ GB \Ud , QS can be recovered through

12

(22). Note that, for any G ∈ GB \Ud , we have
|B\G| = |S| ,

(23a)

(B\G) ∩ Ud 6= ∅,

(23b)

that is, each coded message on the right hand side (RHS) of (22) is targeted for a set of |S|
users, at least one of which is in set Ud . Furthermore, for each k ∈ S, there is a user k ′ ∈ Ud
with h2k′ ≤ h2k , such that dk′ = dk . Note that, since no two users with the same demand are in
any of the sets G ∈ GB , for any set G ∈ GB \Ud , we have either k ∈ B\G or k ′ ∈ B\G.
Given a demand vector d, the delivery phase is designed such that only the coded messages
 K 
QC t+1 , ∀l ∈ t+1
such that Clt+1 ∩ Ud 6= ∅, are delivered, i.e., the coded messages that
l

are targeted for at least one user in Ud are delivered, and the remaining coded messages can be

recovered through (22). To achieve this, for any such set Clt+1 with Clt+1 ∩Ud 6= ∅, the transmission
power is adjusted such that the worst user in Clt+1 can decode the delivered message QC t+1 ; and
l

thus, can all the other users in

Clt+1

due to the degradedness of the Gaussian BC. As a result,

the demand of every user in Ud will be satisfied.
In delivering the coded messages, we start from the worst user, i.e., user 1, and first transmit
all the coded messages targeted for user 1. We then target the second worst user, and transmit
the coded messages targeted for it that have not been already delivered, keeping in mind that
only the coded messages QC t+1 for which Clt+1 ∩ Ud 6= ∅ are delivered. We continue similarly
l

until we deliver the messages targeted for the best user in Ud . In this process we denote the
contents targeted for user k by Q̃k , and their total rate by Rd,t,k , for k ∈ [K].
For a demand vector d, contents
Q̃1 =

[

QC t+1
l

(24)

l:1∈Clt+1

are targeted for user 1. Note that there are



K−1
t

different (t + 1)-element subsets Clt+1 , in which

user 1 is included. Thus, the total rate of the messages targeted for user 1 is given by

K−1
K −t
t
R.
Rd,t,1 = K  R =
K
t

(25)

For k ∈ [2 : K], the coded contents targeted for user k that have not been sent through the

transmissions to the previous k −1 users and are targeted for at least one user in Ud are delivered.

13

Thus, for k ∈ [2 : K], we deliver
[

Q̃k =

QC t+1 ,

(26)

l

l:Clt+1 ∩Ud 6=∅,Clt+1 ∩[k−1]=∅,k∈Clt+1

which is equivalent to

Q̃k = 

[

K−k
t

[

l:Clt+1 ∩Ud =∅,Clt+1 ∩[k−1]=∅,k∈Clt+1





QC t+1  .
l

(27)

different (t + 1)-element subsets Clt+1 , such that

K
∩ [k − 1] = ∅ and k ∈ Clt+1 , for l = 1, . . . , t+1
. On the other hand, for each user

For each user k ∈ [2 : K], there are
Clt+1



QC t+1  − 
l

l:Clt+1 ∩[k−1]=∅,k∈Clt+1



k ∈ [2 : K]\Ud , since there are Nd,k users among the set of users [k : K] which belong to set

d,k
different (t+1)-element subsets Clt+1 , such that Clt+1 ∩(Ud ∪ [k − 1]) = ∅
Ud , there are K−k−N
t

K
and k ∈ Clt+1 , for l = 1, . . . , t+1
. Note that, if k ∈ Ud , the second term on the RHS of (27)
includes no content. Thus, if k ∈ [2 : K] ∩ Ud , total rate targeted for user k is
!

k−1
K−k
YK −t−i
R.
Rd,t,k = Kt  R =
K−i
t
i=0

While, the total rate targeted for user k, k ∈ [2 : K]\Ud , is given by


K−k
d,k
− K−k−N
t+1
t

R.
Rd,t,k =
K

(28)

(29)

t

In summary, the proposed achievable scheme intends to deliver contents of total rate Rd,t,k to

user k, for k ∈ [K], where

Rd,t,k

 K−k

 ( Kt ) R,
∆
(t)
=
K−k−Nd,k
K−k

(
 t )−(K t ) R,
(t)

if k ∈ Ud ,
(30)
otherwise.

The centralized caching and coded packets generation targeted for each user are summarized in
Algorithm 1.
Given a demand vector d, we generate K codebooks, where the codebook k ∈ [K] is designed
to deliver the contents Q̃k to user k. The k-th codebook consists of 2nRd,t,k i.i.d. Gaussian

C
codewords xnk (W, d), generated according to the normal distribution N 0, αk PUB
(R, M, d) ,
K
P
where αk ≥ 0 and
αi = 1. The transmission is performed through linear superposition coding;
i=1

14

Algorithm 1 Centralized Caching and Coded Delivery Scheme
1:
2:

procedure P LACEMENT P HASE
K
(S
t)
Wi =
Wi,Clt , for i = 1, ..., N
l=1

3:

Uk =

S

S

i∈[N ] l∈[(K )]:k∈C t
t

Wi,Clt ,

for k = 1, . . . , K

l

4:

end procedure

5:

procedure DL
ELIVERY P HASE
QC t+1 = k∈C t+1 Wdk ,C t+1 \{k} ,

6:
7:

l

l

l

Q̃k =

for l = 1, ...,

S

l:Clt+1 ∩Ud 6=∅,Clt+1 ∩[k−1]=∅,k∈Clt+1

8:

end procedure

that is, the channel input is given by

K
P

k=1

QC t+1 ,
l

xnk

K
t+1



for k = 1, . . . , K

h C i
(W, d, q̃k ), where q̃k ∈ 2nRd,t,k . User k decodes

codewords xn1 (W, d) , ..., xnk (W, d) by successive decoding, considering all the codewords in
higher levels as noise. If all the k codewords are decoded successfully, user k ∈ [K] can recover
contents Q̃1 , ..., Q̃k . Accordingly, any user k ∈ [K] will receive all the coded contents targeted for
it except those that are not intended for at least one user in Ud (which have not been delivered);
that is, user k receives all the coded contents
[

QC t+1 .

(31)

l

l:Clt+1 ∩Ud 6=∅,k∈Clt+1

Thanks to the degradeness of the underlying Gaussian BC, it can also obtain all the coded
contents targeted for users in [k − 1], which are also intended for at least one user in Ud , i.e.,
all the coded contents
[

QC t+1 .
l

(32)

l:Clt+1 ∩Ud 6=∅,[k−1]∩Clt+16=∅

Note that, if k ∈ Ud , (31) reduces to

S

l:k∈Clt+1

QC t+1 , which shows that the demand of each user
l

k ∈ Ud is satisfied. Next, we illustrate that the users in [K]\Ud can obtain their requested files
without being delivered any extra messages. Given any set of users Clt+1 such that Clt+1 ∩ Ud = ∅,
we need to show that every user in Clt+1 can decode all the coded messages QB\G , ∀G ∈ GB \Ud ,
where B = Clt+1 ∪ Ud . In this case, they can also decode QC t+1 through (22).
l

Assume that there exists a set of users

Clt+1

such that Clt+1 ∩ Ud = ∅; set B = Clt+1 ∪ Ud .

15

According to (23b), there is at least one user in Ud in any set of users B\G, ∀G ∈ GB \Ud . Thus,
all the coded messages QB\G have been delivered by the proposed delivery scheme. Remember
the fact that, for each user k ∈ Clt+1 and ∀G ∈ GB \Ud , either k ∈ B\G or ∃k ′ ∈ B\G, where
dk′ = dk and k ′ ∈ Ud , i.e., h2k′ ≤ h2k . If k ∈ B\G, since B\G ∩ Ud 6= ∅, according to (31), user
k can obtain QB\G . If ∃k ′ ∈ B\G with dk′ = dk and k ′ ∈ Ud , then user k ′ can decode QB\G ,
and since h2k′ ≤ h2k , user k can also decode QB\G . Thus, each user k ∈ Clt+1 can decode QC t+1
l

successfully, for any set of users

Clt+1

that satisfies

Clt+1

∩ Ud = ∅. This fact confirms that the

demands of all the users in [K]\Ud will be satisfied.
B. Non-integer Values of Normalized Global Cache Capacity t
Here we extend the proposed scheme for the normalized cache capacity M = tN/K, where
t ∈ [0, K] is not necessarily an integer. We divide the whole database as well as the cache memory
of the users into two, such that the corresponding t parameters for both parts are integer. This
way we can employ the placement and delivery schemes introduced in Section IV-A for each
part separately.
Placement phase: Each file Wi , for i = 1, ..., N, is divided into two non-overlapping subfiles,
Wi1 of rate R1 and Wi2 of rate R2 . We set
R1 = (⌊t⌋ + 1 − t) R,

(33a)

R2 = (t − ⌊t⌋) R,

(33b)

such that R1 +R2 = R. For subfiles {W11 , . . . , WN1 }, we perform the placement phase proposed in
Section IV-A corresponding to the normalized global cache capacity ⌊t⌋, which requires a cache


⌊t⌋N
capacity of n K R1 bits. While, for subfiles {W12 , W22 , . . . , WN2 }, we perform the placement

phase proposed in Section IV-A corresponding to the normalized global cache capacity ⌊t⌋ + 1,


which requires a cache capacity of n (⌊t⌋+1)N
R2 bits. By summing up, the total cache capacity
K

is found to be nMR bits, which shows that the cache capacity constraint is satisfied.

Delivery phase: For any demand vector d, we perform the proposed coded delivery phase in
Section IV-A corresponding to the normalized global cache capacity ⌊t⌋ to deliver the missing
bits of subfiles {W11 , . . . , WN1 } to the intended users. Moreover, the missing bits of subfiles
{W12 , . . . , WN2 } are delivered to the intended users by performing the coded delivery scheme
proposed in Section IV-A corresponding to the normalized global cache capacity ⌊t⌋ + 1.

16

For an arbitrary demand vector d = (d1 , . . . , dK ), we define
M

∆

QiC ti +1 =
l

∆

∆

t +1

k∈Cl i

Wdi

ti +1
\{k}
k ,Cl

,

for i = 1, 2,

(34)

where t1 = ⌊t⌋ and t2 = ⌊t⌋ + 1. According to Algorithm 1, by performing the centralized
caching and coded delivery scheme proposed in Section IV-A for the normalized global cache
capacity ⌊t⌋ to serve the subfiles {W11 , . . . , WN1 }, each of rate R1 , user k ∈ [K] should receive
Q̃1k =
⌊t⌋+1

l:Cl

[

⌊t⌋+1

∩Ud 6=∅,Cl

Q1C ⌊t⌋+1 ,
⌊t⌋+1

(35)

l

∩[k−1]=∅,k∈Cl

of the following total rate obtained according to (30)

(K−k)


 ⌊t⌋
R,
K
) 1
(⌊t⌋
Rd,⌊t⌋,k =
K−k−Nd,k
−
)
(K−k

⌊t⌋ ) (
⌊t⌋

R1 ,

K
(⌊t⌋)

if k ∈ Ud ,
(36)
otherwise.

Similarly, to serve the subfiles {W12 , . . . , WN2 }, each of rate R2 , user k ∈ [K] should receive
Q̃2k =
⌊t⌋+2

l:Cl

[

⌊t⌋+2

∩Ud 6=∅,Cl

Q2C ⌊t⌋+2 ,
⌊t⌋+2

(37)

l

∩[k−1]=∅,k∈Cl

of total rate

Rd,⌊t⌋+1,k

∆

Thus, Q̃k =

C
Rd,k



Q̃1k , Q̃2k




( K−k )


 ⌊t⌋+1
R,
K
) 2
(⌊t⌋+1
=
K−k
d,k
)−(K−k−N
)
 (⌊t⌋+1
⌊t⌋+1

R2 ,

K
(⌊t⌋+1)

if k ∈ Ud ,
(38)
otherwise.

∆

C
, at a total rate of Rd,k
= Rd,⌊t⌋,k + Rd,⌊t⌋+1,k given by


K−k
)
(⌊t⌋+1
(K−k)


 ⌊t⌋
(⌊t⌋
+
1
−
t)
R
+
(t − ⌊t⌋) R,
K
K
(⌊t⌋)
(⌊t⌋+1)
=
K−k−Nd,k
K−k
d,k
−
(K−k
)
)−(K−k−N
(⌊t⌋+1
)

⌊t⌋ ) (
⌊t⌋
⌊t⌋+1

(⌊t⌋
+
1
−
t)
R
+
(t − ⌊t⌋) R,

K
K
(⌊t⌋)
(⌊t⌋+1)

if k ∈ Ud ,
(39)
otherwise

is delivered to user k, for k = 1, ..., K.
C. Power Analysis

For a demand vector d in the delivery phase, the proposed scheme delivers a message of rate
C
Rd,k
, given in (39), to user k ∈ [K], equipped with a cache of capacity M ∈ [0, N] through

17

linear superposition coding

K
P

k=1

ykn (W, d)

xnk (W, d, q̃k ), and the received signal at user k ∈ [K] is

= hk

K
X

xnk (W, d, q̃k ) + zkn ,

k=1

h C i
where q̃k ∈ 2nRd,k .

(40)

User k ∈ [K] decodes codewords xn1 (W, d) , . . . , xnk (W, d) successively considering all the other
codewords in higher levels as noise. User k can decode its intended message successfully if


C
Rd,k


1

≤ log2 1 +
2


h2k


C
αk h2k PUB
(R, M, d)

,
K
P

C
αi PUB (R, M, d) + 1

for k = 1, ..., K.

(41)

i=k+1

From Proposition 1, the corresponding minimum required power is given by
! i−1
K
2RC
Y
X
d,i − 1
C
2
∆
C
22Rd,j .
PUB
(R, M, d) =
2
hi
j=1
i=1

(42)

Thus, the average power-memory trade-off of the proposed achievable scheme is given by
 C

C
C
Ed PUB
(R, M, d) = P̄UB
(R, M), while the peak power-memory trade-off is P̂UB
(R, M) =
 C
max PUB (R, M, d) , as stated in Theorem 1, where the demands are distributed uniformly.
d

C
Observe that, for demand vectors with the same Ud set, the required power PUB
(R, M, d) is the

C
same. Let DUd denote set of all demand vectors with the same Ud set. We define PUB
(R, M, DUd )
C
as the required power PUB
(R, M, d) for any demand vector d ∈ DUd . Thus, we have

 C
C
(R, M, DUd ) .
P̂UB
(R, M) = max PUB
Ud

(43)

It is shown in Appendix C that the worst-case demand combination for the proposed centralized
caching scheme happens when the first min{N, K} users; that is, the users with the worst channel
C
gains, request distinct files, i.e., when Ud = [min{N, K}], and P̂UB
(R, M) is found as in (12).

V. D ECENTRALIZED C ACHING

AND

D ELIVERY

Here we extend the proposed centralized caching scheme to the decentralized caching scenario,
which achieves the average and peak power-memory trade-offs in (13) and (14), respectively.
A. Placement Phase
We perform decentralized uncoded cache placement [16], where each user caches nMR/N
random bits of each file of length nR bits independently. Since there are a total of N files,

18

the cache capacity constraint is satisfied. The part of file i cached exclusively by the users in
set S ⊂ [K] is denoted by Wi,S , for i = 1, ..., N. For n large enough, the rate of Wi,S can be
|S|
K−|S|
1− M
R. The cache content at user k is given by
approximated by M
N
N
Uk =

[

[

Wi,S .

(44)

i∈[N ] S⊂[K]:k∈S

B. Delivery phase
Consider any non-empty set of users S ⊂ [K]. For a demand vector d, by delivering the coded
|S|−1

L
M K−|S|+1
1
−
R to users in S, each user i ∈ S
message QS = k∈S Wdk ,S\{k} of rate M
N
N

can recover subfile Wdi ,S\{i} since it has cached all the subfiles Wdj ,S\{j} , ∀j ∈ S\{i}. For each
S
k ∈ [K], delivering
QS enables user k to recover all the subfiles Wdk ,S\{k}, ∀S ⊂ [K]
S⊂[K]:k∈S
S
and k ∈ S. The demand of user k, k ∈ [K], is fully satisfied after receiving
QS along
S⊂[K]:k∈S

with its cache content.

Similarly to the proposed scheme for the centralized caching scenario, given a demand vector
d, the delivery phase is designed such that only the coded messages QS , ∀S ⊂ [K] that satisfy
S ∩ Ud 6= ∅, are delivered, and the remaining coded messages can be recovered through (22). To
achieve this, for any such set S with S ∩ Ud 6= ∅, the transmission power is adjusted such that
the worst user in S can decode it; and so can all the other users in S due to the degradedness
of the Gaussian BC. Therefore, the demand of every user in Ud is satisfied.
Note that in the centralized scenario described in Section IV-A, each coded packet QC t+1 is
l
 K 
targeted for a (t + 1)-element subset of users, where t ∈ [0 : K], for l ∈ t+1 . While, in the

decentralized scenario, coded packets are targeted for any subset of users, i.e., for (t+1)-element
subset of users, ∀t ∈ [0 : K]. By applying a similar technique as the delivery phase outlined in
Algorithm 1, given a demand vector d, the following contents are targeted for user k, k ∈ [K]:
[

Q̃k =

QS ,

(45)

S⊂[k:K]:S∩Ud6=∅,k∈S

which are equivalent to
Q̃k =

[

QS −

S⊂[k:K]:k∈S

For each user k, k ∈ [K], there are

K−k
i



[

QS .

(46)

S⊂[k:K]\Ud,k ,k∈S

different (i + 1)-element subsets of [k : K], which

19

include k, for i ∈ [0 : K − k]. Thus, if k ∈ Ud , from (46), the total rate targeted for user k is
D
Rd,k

=

K−k
X

K −k
i

i=0



M
N

i 
K−i
k

M
M
1−
R= 1−
R.
N
N

On the other hand, for each user k, k ∈ [K], there are

K−k−Nd,k
i



(47)

different (i + 1)-element

subsets of [k : K]\Ud,k , which include k, for i ∈ [0 : K − k]. Thus, if k ∈
/ Ud , from (46), the
total rate targeted for user k ∈ [K] is given by
D
Rd,k

=

K−k
X
i=0

K−k
i



M
N

i 
K−i
M
1−
R
N

K−k−Nd,k

 i 

K−i
M
K − k − Nd,k
M
−
1−
R
i
N
N
i=0
k

Nd,k !

M
M
R.
1− 1−
= 1−
N
N
X

(48)

In total, the rate of contents targeted for user k, k ∈ [K], is given by



 1 − M k R,
if k ∈ Ud ,
N
D
Rd,k
=





 1 − M k 1 − 1 − M Nd,k R, otherwise.
N
N

(49)

Given a demand vector d in the delivery phase, the transmitted codeword xn (W, d) is gen-

erated as the linear superposition of K codewords xn1 (W, d) , ..., xnK (W, d), each chosen from
D

an independent codebook. Codebook k consists of 2nRd,k i.i.d. codewords xnk (W, d) generated
K

P
D
according to the normal distribution N 0, αk PUB
(R, M, d) , where αk ≥ 0 and
αi = 1,
i=1

which satisfy the power constraint, for k = 1, ..., K.

User k, k ∈ [K], decodes codewords xn1 (W, d) , ..., xnk (W, d) through successive decoding,
while considering all the codewords xnk+1 (W, d) , ..., xnK (W, d) as noise. Thus, if user k ∈ [K]
can successfully decode all the k channel codewords intended for it, it can then recover the conS
tents Q̃1 , ..., Q̃k , from which it can obtain all the coded contents
QS . Accordingly,
S∩Ud 6=∅,[k]∩S6=∅

each user k ∈ [K] can obtain all the coded contents targeted for it except those that are not

intended for at least one user in Ud (which have not been delivered), i.e., all the coded contents
[

QS .

(50)

S∩Ud 6=∅,k∈S

It can further obtain all the coded contents targeted for users [k − 1], which are also intended for

20

S
at least one user in Ud , i.e., all the coded contents
QS . Note that, if k ∈ Ud , (50)
S∩Ud 6=∅,[k−1]∩S6=∅
S
reduces to
QS , which shows that the demand of each user k ∈ Ud is satisfied through the
k∈S

proposed delivery scheme. Next, we illustrate that the users in [K]\Ud can obtain their requested

files without being delivered any extra messages. Similarly to the centralized scenario, given any
set of users S such that S ∩ Ud = ∅, by setting B = S ∪ Ud , from the fact that, for each user
k ∈ S, k ∈ B\G or k ′ ∈ B\G, where k ′ < k, it can be illustrated that every user in S can decode
all coded contents QB\G , ∀G ∈ GB \Ud . In this case, they all can also decode QS through (22).
C. Power Analysis
For a demand vector d in the delivery phase, user k receives
ykn

(W, d) = hk

K
X

xnk (W, d, q̃k ) + zkn ,

(51)

k=1

h D i
where q̃k ∈ 2nRd,k , and it can decode the channel codewords up to level k successfully if
D
Rd,k




1

≤ log2 1 +
2




h2k


D
αk h2k PUB
(R, M, d)

,
K
P

D
αi PUB (R, M, d) + 1

for k = 1, ..., K.

(52)

i=k+1

From Proposition 1, the minimum required power is given by
! i−1
K
2RD
X
Y
d,i − 1
2
D
∆
D
PUB
(R, M, d) =
22Rd,j .
2
hi
i=1
j=1

(53)

Thus, the average power-memory trade-off for the proposed decentralized caching and coded
 D

D
delivery scheme is given by Ed PUB
(R, M, d) = P̄UB
(R, M) stated in Theorem 2.

With the proposed decentralized caching scheme, the following peak power performance can
 D
(R, M, d) . Observe that, for demand vectors with the
be achieved P̂ D (R, M) = max PUB
d

D
D
same set of users Ud , the required power PUB
(R, M, d) is the same. We define PUB
(R, M, DUd )

D
as the required power PUB
(R, M, d) for any demand vector d ∈ DUd . Thus, we have

 D
(R, M, DUd ) .
P̂ D (R, M) = max PUB
Ud

(54)

It is shown in Appendix D that the worst-case demand combination happens when Ud =
D
[min{N, K}], and P̂UB
(R, M) is found as in (14).

21

VI. C ONCLUSIONS
We have considered cache-aided content delivery over a Gaussian BC, where the receivers
are equipped with equal-size cache memories. For a given rate for the contents in the library,
and imposing the transmitter to satisfy all the user demands reliably, we have studied both
the minimum peak transmission power, which is the minimum transmit power that can satisfy
all user demand combinations, and the minimum average power assuming uniform demand
distributions. We have first proposed a centralized caching and coded delivery scheme assuming
that the channel conditions in the delivery phase are not known beforehand. The cache-aided
coded contents are transmitted in the delivery phase to the intended users using superposition
coding and power allocation. We have provided an upper bound on the required peak and
average transmission power values using the proposed centralized caching scheme. We have
then extended the achievable centralized caching scheme to the decentralized caching scenario,
and characterized the achievable peak and average power values for the proposed scheme. We
have also provided a lower bound on the required peak and average transmission power values
assuming uncoded cache placement. Our results indicate that even a small cache capacity at the
receivers can provide a significant reduction in the required transmission power level highlighting
the benefits of content caching in increasing the energy efficiency of wireless networks.
A PPENDIX A
P ROOF

OF

T HEOREM 3

For any given Ud , let DUd denote the set of all demand vectors with the same Ud . The union
S
Ud

DUd form the set of all possible demand vectors [N]K . Therefore, the set of all possible

demand vectors can be broken into classes DUd based on the Ud set they correspond to.
For any given Ud , and an (n, R, M) code as defined in (1), (3) and (5) in Section II, define
the error probability as follows:
Pe U d



 [ [ n
o
∆
Ŵdk 6= Wdk
.
= Pr



(55)

d∈DUd k∈Ud

Let PUd (d) denote the average power of the codeword this code generates for a demand vector


d ∈ DUd . We say that an R, M, P̄ , P̂ tuple is Ud -achievable if for every ε > 0, there exists

an (n, R, M) code with sufficiently large n, which satisfies PeUd < ε, Ed [PUd (d)] ≤ P̄ , and

22

PUd (d) ≤ P̂ , ∀d ∈ DUd . We can also define P̄U∗d (R, M) and P̂U∗d (R, M) as in (7a) and (7b),
respectively, by considering Ud -achievable codes.
We note from (55) that, a Ud -achievable code satisfies only the demands of the users in set Ud .


Accordingly, an achievable R, M, P̄ , P̂ tuple is also Ud -achievable, since Pe ≥ PeUd , for any Ud
set. Thus, lower bounds on P̄U∗d (R, M ) and P̂U∗d (R, M ) also serve as lower bounds on P̄ ∗ (R, M)
and P̂ ∗ (R, M), respectively. In the following, we provide lower bounds on P̄U∗d (R, M ) and
P̂U∗d (R, M ).


Let R, M, P̄ , P̂ be any Ud -achievable tuple. For uniformly distributed demands, we have


P̄ ≥ Ed [PUd (d)] = EUd 

1
NUd

X

d∈DUd



PUd (d) ,

(56)

where we used the fact that the probability of each demand vector in DUd is equal. We divide
the set of demand vectors DUd into different subsets according to the demands of users in Ud ,
where each subset consists of the demand vectors for which the demands of all the users in Ud

∆
are the same. Note that, there are D = NNd Nd ! such subsets5, denoted by DUl d , for l = 1, ..., D,
D
S
DUl d .
i.e., DUd =
l=1

l
Example 1. Consider N = K = 4, and Ud = {1, 2}. The subsets of demand vectors D{1,2}
,

5

For simplicity, we drop the dependence of D on N and Nd .

23

l = 1, ..., 12, are given by
1
D{1,2}
={(1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 2, 2)},

(57a)

2
D{1,2}
={(1, 3, 1, 1), (1, 3, 1, 3), (1, 3, 3, 1), (1, 3, 3, 3)},

(57b)

3
D{1,2}
={(1, 4, 1, 1), (1, 4, 1, 4), (1, 4, 4, 1), (1, 4, 4, 4)},

(57c)

4
D{1,2}
={(2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 2, 2)},

(57d)

5
D{1,2}
={(2, 3, 2, 2), (2, 3, 2, 3), (2, 3, 3, 2), (2, 3, 3, 3)},

(57e)

6
D{1,2}
={(2, 4, 2, 2), (2, 4, 2, 4), (2, 4, 4, 2), (2, 4, 4, 4)},

(57f)

7
D{1,2}
={(3, 1, 1, 1), (3, 1, 1, 3), (3, 1, 3, 1), (3, 1, 3, 3)},

(57g)

8
D{1,2}
={(3, 2, 2, 2), (3, 2, 2, 3), (3, 2, 3, 2), (3, 2, 3, 3)},

(57h)

9
D{1,2}
={(3, 4, 3, 3), (3, 4, 3, 4), (3, 4, 4, 3), (3, 4, 4, 4)},

(57i)

10
D{1,2}
={(4, 1, 1, 1), (4, 1, 1, 4), (4, 1, 4, 1), (4, 1, 4, 4)},

(57j)

11
D{1,2}
={(4, 2, 2, 2), (4, 2, 2, 4), (4, 2, 4, 2), (4, 2, 4, 4)},

(57k)

12
D{1,2}
={(4, 3, 3, 3), (4, 3, 3, 4), (4, 3, 4, 3), (4, 3, 4, 4)}.

(57l)

We note that the number of demand vectors in each DUl d , denoted by NU′ d , is the same, and
is given by
NU′ d

=

Nd
Y

j uj+1 −uj −1 ,

(58)

j=2

where, we remind that Ud = {u1 , u2 , ..., uNd }, where 1 = u1 ≤ u2 ≤ · · · ≤ uNd . Thus, we have
NUd = DNU′ d , and (56) can be rewritten as follows:





D
1 X
 1 X 1 X

P̄ ≥ EUd 
PUd (d) = EUd 
PUd (d) .

NUd d∈D
D l=1 NU′ d
l
Ud

d∈DU

(59)

d

For any arbitrary demand vector dlUd ∈ DUl d , for l ∈ [D], it is proved in [7, Lemma 14] that there






exist random variables6 X dlUd , YπUd (1) dlUd , . . . , YπUd (Nd ) dlUd , and V1 dlUd , ..., VNd −1 dlUd ,
For ease of presentation, we drop the dependence of the transmitted signal X n , and the received signals Ykn , ∀k ∈ [K], on
the library W.
6

24

where





V1 dlUd → · · · → VNd −1 dlUd → X dlUd → YπUd(Nd ) dlUd → · · · → YπUd (1) dlUd

forms a Markov chain, and satisfy




1
; UπUd (1) + I VUd ,1 ; YπUd (1) dlUd ,
R − εn ≤ I Wdl
πU (1)
n
d


1
R − εn ≤ I Wdlπ (i) ; UπUd (1) , . . . , UπUd (i) Wdlπ (1) , . . . , Wdlπ (i−1)
Ud
Ud
Ud
n





+ I Vi dlUd ; YπUd (i) dlUd Vi−1 dlUd , ∀i ∈ [2 : Nd − 1],


1
R − εn ≤ I Wdlπ (N ) ; UπUd (1) , . . . , UπUd (Nd ) Wdlπ (1) , . . . , Wdlπ (N −1)
d
Ud
Ud
d
Ud
n





+ I X dlUd ; YπUd (Nd ) dlUd VNd −1 dlUd ,

where dlπU

d

(i)

(60)

(61a)

(61b)

(61c)

is the πUd (i)-th element of demand vector dlUd , i ∈ [Nd ], and εn > 0 tends to zeros

as n → ∞. We note that, due to the independence of the files and the fact that the users in Ud
demand distinct files, for any uncoded cache placement phase and any Ud set, we have




; UπUd (1) , . . . , UπUd (i) ,
=I Wdl
, . . . , Wdl
; UπUd (1) , . . . , UπUd (i) Wdl
I Wdl
πU (i)
d

πU (1)
d

πU (i−1)
d

πU (i)
d

∀i ∈ [2 : Nd ], l ∈ [D]. (62)
Thus, for an uncoded cache placement phase, (61) is equivalent to




1
R − εn ≤ I Wdlπ (1) ; UπUd (1) + I VUd ,1 ; YπUd (1) dlUd ,
Ud
n


1
; UπUd (1) , . . . , UπUd (i)
R − εn ≤ I Wdl
πU (i)
n
d




+ I Vi dlUd ; YπUd (i) dlUd Vi−1 dlUd , ∀i ∈ [2 : Nd − 1],


1
R − εn ≤ I Wdl
; UπUd (1) , . . . , UπUd (Nd )
πU (Nd )
n
d




l
l
l
+ I X dUd ; YπUd (Nd ) dUd VNd −1 dUd ,

(63a)

(63b)

(63c)

25

For the Gaussian channel (2), for i = 1, ..., Nd , we have [14]





 1

I Vi dlUd ; YπUd (i) dlUd Vi−1 dlUd
≤ log2 1 +

2

βi h2πU

h2πU (i)
d

Nd
P

(i) PUd
d

j=i+1

dlUd



dlUd

βj PUd




+1



,


(64)

Nd
 ∆
P
βi = 1, where we set V0 dlUd = 0, and
for some βi ≥ 0, for i = 1, ..., Nd , such that
i=1
∆


VNd dlUd = X dlUd . From (63) and (64), for n sufficiently large, the average power PUd dlUd

to satisfy any demand vector dlUd ∈ DUl d , for l ∈ [D], is lower bounded by

 l
2cπ (i)
Nd
i−1
 X

Ud

− 1  Y 2clπU (j)
2
∆
l
l
l

2 d ,
PUd dUd ≥ f cπU (1) , . . . , cπU (Nd ) =
2
d
d
h
πU (i)
j=1
i=1

(65a)

d

where

∆
clπU (i) =
d



1
R − I Wdlπ (i) ; UπUd (1) , . . . , UπUd (i) ,
Ud
n

for i = 1, ..., Nd , l = 1, ..., D.

(65b)

Note that the lower bound in (65a) does not depend on any particular demand in DUl d , l ∈ [D].
Thus, from (59) and (65), we have
P̄ ≥ EUd

"

#
D

1 X  l
f cπU (1) , . . . , clπU (Nd ) .
d
d
D l=1

(66)

Lemma 1. Given a set of users Ud of size Nd with distinct demands, we have
! i−1
Nd
D
 X
2R(1−min{iM/N,1})
Y
1 X  l
2
−
1
f cπU (1) , . . . , clπU (Nd ) ≥
22R(1−min{jM/N,1}) .
2
d
d
D l=1
h
πU (i)
i=1
j=1

(67)

d


Proof. It is proved in Appendix B that f (·) is a convex function of clπU
D


1 X  l
f cπU (1) , . . . , clπU (Nd ) ≥ f
d
d
D l=1

D

d

l
(1) , . . . , cπU

!

D

d


(Nd ) . Thus,

1 X l
1 X l
.
cπU (1) , ...,
c
d
D l=1
D l=1 πUd (Nd )

(68)

From the definition, we have


D
D
1 X l
1 X
c
=R−
I Wdlπ (i) ; UπUd (1) , . . . , UπUd (i) ,
Ud
D l=1 πUd (i)
nD l=1
where, due to the symmetry, each file Wk , for k = 1, ..., N, appears

for i = 1, ..., Nd .

(69)


(Nd − 1)! times in

N −1
Nd −1

26

the sum on the RHS of (69) for each i value. Thus, for i = 1, ..., Nd , we have

N −1
D
N


(Nd − 1)! X
1 X l
Nd −1
c
=R−
I Wk ; UπUd (1) , . . . , UπUd (i)
D l=1 πUd (i)
nD
k=1

N

1 X 
=R−
I Wk ; UπUd (1) , . . . , UπUd (i)
nN k=1

(a)
1 
R
≥R−
I W1 , ..., WN ; UπUd (1) , . . . , UπUd (i) = R − min{iM, N},
nN
N

(70)

where (a) follows from the independence of the files. From (68) and (70), and according to the
definition of function f , we have
D


1 X  l
l
f cπU (1) , . . . , cπU (Nd ) ≥ f
d
d
D l=1

 





iM
iM
R 1 − min
,1
, . . . , R 1 − min
,1
,
N
N
(71)

which concludes the proof of Lemma 1.
According to (66) and Lemma 1, P̄ is lower bounded by P̄LB (R, M) defined in (15). Thus,
P̄LB (R, M) is a lower bound on P̄U∗d (R, M) as well as P̄ ∗ (R, M).
Next, we prove the lower bound on P̂ ∗ (R, M) stated in Theorem 3. For any Ud set, let


R, M, P̄ , P̂ tuple be Ud -achievable. We have P̂ ≥ PUd (d), ∀d ∈ DUd , which is equivalent to

P̂ ≥ PUd dlUd ,

∀dlUd ∈ DUl d , for l = 1, ..., D.

(72)

Averaging over all NUd = DNU′ d possible demands with the same Ud set, we have


D
X

1 X 1
PUd dlUd  .
P̂ ≥
 ′
D l=1 NUd l
l
dU ∈DU
d

(73)

d

According to (65) and Lemma 1, P̂ is lower bounded as follows:
! i−1
Nd
X
22R(1−min{iM/N,1}) − 1 Y 2R(1−min{jM/N,1})
2
,
P̂ ≥
2
h
π
(i)
U
i=1
j=1

∀Ud .

(74)

d

Thus, we have
P̂ ≥ max
Ud

(N
d
X
i=1

22R(1−min{iM/N,1}) − 1
h2πU (i)
d

! i−1
Y
j=1

22R(1−min{jM/N,1})

)

.

(75)

27

We note that the term on the RHS of the inequality in (75) is equivalent to P̂LB (R, M) defined
in (16). Thus, P̂LB (R, M) is a lower bound on P̂U∗d (R, M ) as well as P̂ ∗ (R, M).
A PPENDIX B
P ROOF

OF

C ONVEXITY

OF

F UNCTION f (·)

We show that, for 1 ≤ Nd ≤ K, function f : RNd → R is a convex function of (s1 , ..., sNd ):
f (s1 , . . . , sNd ) =

Nd
X

22sk − 1
h2πU (i)

i=1

d

! i−1
Y

22sj .

(76)

j=1

After mathematical manipulation, one can obtain
f (s1 , . . . , sNd ) =

Nd
X
i=1

where h2πU

∆

d

(Nd +1)

h2πU (i)
d

−

1
h2πU (i+1)
d

!

2

2aT
i s

!

−

1
h2πU (1)
d

,

(77)

∆

= ∞, s = [s1 s2 · · · sNd ]T , and


We note that h2πU

1

d

(i)

T

∆
ai = 1| 1{z
· · · 1} |0 0{z
· · · 0} ,

≤ h2πU

d

(i+1) ,

1×i

1×(Nd −i)

for i = 1, ..., Nd .

(78)

∀i ∈ [Nd ], and the function 22s , s ∈ R, is a convex function

T

of s. Thus, all the functions 22ai s , ∀i ∈ [Nd ], are convex since the affine substitution of the
arguments preserves convexity. As a result, function f is convex with respect to (s1 , ..., sNd )
since any linear combination of convex functions with non-negative coefficients is convex.
A PPENDIX C
P ROOF

OF

WORST-C ASE D EMAND C OMBINATION

FOR

C ENTRALIZED C ACHING

To obtain the worst-case demand combination for the proposed centralized caching scheme,
we first illustrate that, among all the demand combinations with a fixed Nd , the worst-case is
∗
the one when Ud = [Nd ]. Let, for a fixed Nd , DN
denotes the set of demand vectors with
d

Ud = [Nd ]. Note that, the required power, given in (42), is the same for any demand vector
∗
∗
d ∈ DN
. Assume that there is a demand combination d̃ ∈
/ DN
, with required transmitted power
d
d


∆
C
P̃ C = PUB
R, M, d̃ determined through (42), that has the highest transmitted power among

∗
all the demand combinations with the same Nd . For such demand vector d̃ ∈
/ DN
, there is at
d

least one user k ∈ Ud̃ such that k − 1 ∈
/ Ud̃ , where we have Nd̃,k−1 = Nd̃,k + 1. Now, consider

28

another demand vector d̂ with the same entries as demand vector d̃ except that k ∈
/ Ud̂ and
k − 1 ∈ Ud̂ . An example of such demand vector d̂ is as follows:



d̃i+1 , if i = k − 1,


d̂i = d̃i−1 , if i = k,




d̃ ,
otherwise.
i

(79)

∆

We denote the required transmitted power to satisfy demand vector d̂ by P̂ C , where P̂ C =


C
PUB
R, M, d̂ . Note that, for demand vector d̂, we have Nd̂,k−1 = Nd̂,k = Nd̃,k , and from (39),
C
C
= Rd̃,i
,
Rd̂,i

∀i ∈ [K]\{k − 1, k}.

(80)

Having defined


K−k
∆ ⌊t⌋
RL,k = K 
⌊t⌋
K−k
∆ ⌊t⌋

RNL,k (Nd,k ) =



(⌊t⌋ + 1 − t) R +
−

K−k−Nd,k
⌊t⌋

K
⌊t⌋



according to (42), we have
P̂ C − P̃ C =


1
h2k−1



K−k
⌊t⌋+1

K
⌊t⌋+1

(t − ⌊t⌋) R,

(⌊t⌋ + 1 − t) R +

(81a)


K−k
⌊t⌋+1

K−k−Nd,k
⌊t⌋+1

K
⌊t⌋+1

−



(t − ⌊t⌋) R, (81b)

k−2

Y 2RC
 k−2
Y
1 
2RC
2 d̃,j
22RL,k−1 − 1
2 d̃,j + 2 22RNL,k (Nd̃,k ) − 1 22RL,k−1
h
k
j=1
j=1


K

X
 1  2RC

d̃,i
+
−1
 h2 2
i
i=k+1

i−1
Y

j=1
j6=k−1,k

 C 
  2RNL,k (N ) 
2R
2RL,k−1

d̃,k
d̃,j
2
2
2


 k−2
Y 2RC
Y 2RC
  2RNL,k−1 (N +1)  k−2
1 2RL,k
d̃,k
d̃,j
−1
2 d̃,j
2
2
− 2 2
−1 2
− 2
hk−1
h
k
j=1
j=1


K
i−1

 C 
 Y
X
 1  2RC

2R
2RNL,k−1 (Nd̃,k +1)

d̃,j
d̃,i − 1
(82)
22RL,k 
2
2
2
−
,
 h2
i
j=1
1 

i=k+1

2RNL,k−1 (Nd̃,k +1)

j6=k−1,k

where we have used Nd̃,k−1 = Nd̃,k + 1, and Nd̂,k−1 = Nd̂,k = Nd̃,k . From (81), we have


RNL,k−1 Nd̃,k + 1 = RNL,k Nd̃,k + RL,k−1 − RL,k .

(83)

29

By substituting (83) into (82), we obtain
!

k−2
 1
Y 2RC

1
N
−2R
2R
C
C
2R
P̂ − P̃ =
2 d̃,j
2 L,k−1 1 − 2 NL,k ( d̃,k ) L,k
−
.
h2k−1 h2k
j=1

(84)

Note that,
RNL,k (Nd,k ) − RL,k = −

K−k−Nd,k
⌊t⌋

K
⌊t⌋



(⌊t⌋ + 1 − t) R −

K−k−Nd,k
⌊t⌋+1

K
⌊t⌋+1



(t − ⌊t⌋) R ≤ 0,

(85)

and since h2k−1 ≤ h2k , from (84), we have P̂ C ≥ P̃ C , which contradicts the assumption that
∗
demand vector d̃ ∈
/ DN
has the highest required transmit power among all the demand combid
∗
nations with the same Nd . Therefore, for a fixed Nd , the demand vectors in DN
, i.e., the demand
d

vectors with Ud = [Nd ], require the maximum transmit power with the proposed scheme. From
∗
(39), for all the demand vectors in DN
, user k ∈ [K] is delivered a message of rate
d
 K−k
K−k
)
)
(⌊t⌋+1

 ( ⌊t⌋
(⌊t⌋
+
1
−
t)
R
+
(t − ⌊t⌋) R, if k ∈ [Nd ],
K
K
∆
(⌊t⌋)
(⌊t⌋+1)
R∗C
(N
)
=
d
d,k

0,
otherwise.

(86)

Thus, according to (42), for a fixed Nd , the required power to satisfy any demand combination
∗
d ∈ DN
is given by
d

C
PUB

(R, M, d) =

Nd
X
i=1

∗ C (N )
d
d,i

22R

h2i

−1

! i−1
Y

∗C (N )
d
d,j

22R

,

∗
for any d ∈ DN
.
d

(87)

j=1

Observe that, (87) is an increasing function of Nd , and the required power is maximized for the
highest value of Nd , which is min{N, K}. Thus, the worst-case demand combination for the
proposed centralized caching and coded delivery scheme happens when Ud = [min{N, K}].
A PPENDIX D
P ROOF

OF

WORST-C ASE D EMAND C OMBINATION

FOR

D ECENTRALIZED C ACHING

Similarly to the centralized caching scenario, assume that, for a fixed Nd , there is a demand


∗
D ∆
D
R,
M,
d̃
determined
combination d̃ ∈
/ DN
,
with
required
transmitted
power
P̃
=
P
UB
d

through (53), that has the highest transmitted power among all the demand combinations with the
∗
same Nd . For such demand vector d̃ ∈
/ DN
, there is at least one user k ∈ Ud̃ such that k−1 ∈
/ Ud̃ ,
d

where we have Nd̃,k−1 = Nd̃,k + 1. Similarly to (79), consider another demand vector d̂ with the
same entries as demand vector d̃ except that k ∈
/ Ud̂ and k − 1 ∈ Ud̂ . We denote the required

30

D

transmitted power for demand vector d̂ by P̂ , defined as P̂

D ∆

=

D
PUB

demand vector d̂, we have Nd̂,k−1 = Nd̂,k = Nd̃,k , and from (49),
D
D
= Rd̃,i
Rd̂,i
,



R, M, d̂ . Note that, for

∀i ∈ [K]\{k − 1, k}.

(88)

According to (53), we have
P̂ D − P̃ D =

+

1
h2k



2

1 

h2k−1

2(1−M/N )k



22(1−M/N )

k−1

R

h2k−1

2

2RD

d̃,j


 k−2
Y 2RD
2(1−M/N )k−1 R
−1 2
2 d̃,j
j=1



i=k+1

−

 k−2
Y
j=1


N
1−(1−M/N ) d̃,k R

i−1
K
 Y
X
 1  2RD

d̃,i
−1
+
 h2 2
i
j=1

1

−1

j6=k−1,k



2






 D 

N
2R
2(1−M/N )k 1−(1−M/N ) d̃,k R 
2(1−M/N )k−1 R

d̃,j
2
2
2




N
+1
2(1−M/N )k−1 1−(1−M/N ) d̃,k
R

−1

Y
k−2

2

2RD

d̃,j

j=1


 Y
k−2

N
+1
1  2(1−M/N )k R
2RD
2(1−M/N )k−1 1−(1−M/N ) d̃,k
R
− 2 2
−1 2
2 d̃,j
hk
j=1



 
i−1
K

 D 
 Y
N
+1
X
 1  2RD
2R
2(1−M/N )k−1 1−(1−M/N ) d̃,k
R 
2(1−M/N )k R
,

d̃,j
d̃,i
2
2
2
2
−
1
−

 h2
i
j=1
i=k+1
j6=k−1,k

(89)

which is equal to
D

D

P̂ − P̃ =

k−2
Y
j=1

2

2RD

d̃,j

!

2

2(1−M/N )k−1 R

−2


 
N
+1
2(1−M/N )k−1 1−(1−M/N ) d̃,k
R

1
h2k−1

1
− 2
hk



.

(90)

Since h2k−1 ≤ h2k , and 0 ≤ (1 − M/N)Nd̃,k +1 ≤ 1, from (90), we have P̂ D ≥ P̃ D , which
∗
contradicts the assumption that demand vector d̃ ∈
/ DN
has the highest required power among
d

all the demand combinations with the same Nd . Therefore, for a fixed Nd , the demand vectors
∗
in DN
, i.e., the demand vectors with Ud = [Nd ], require the maximum transmitted power with
d

31

∗
the proposed scheme. From (49), for all the demand vectors in DN
, we have
d



 1 − M k R, if k ∈ [Nd ],
∆
N
D
R∗ d,k (Nd ) =

0,
otherwise.

(91)

∗
Thus, according to (53), the required power to satisfy any demand combination d ∈ DN
is
d

D
PUB
(R, M, d) =

Nd
X
i=1

i

22(1−M/N ) R − 1
h2i

! i−1
Y

j

22(1−M/N ) R ,

∗
for any d ∈ DN
.
d

(92)

j=1

Observe that, (92) is an increasing function of Nd , and the required power is maximized for the
highest value of Nd , which is min{N, K}. Thus, the worst-case demand combination for the
proposed scheme happens when Ud = [min{N, K}].
R EFERENCES
[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Inform. Theory, vol. 60, no. 5, pp.
2856–2867, May 2014.
[2] W. Huang, S. Wang, L. Ding, F. Yang, and W. Zhang, “The performance analysis of coded cache in wireless fading
channel,” arXiv:1504.01452v1 [cs.IT], Apr. 2015.
[3] N. Naderializadeh, M. Maddah-Ali, and A. S. Avestimehr, “Fundamental limits of cache-aided interference management,”
arXiv:1602.04207v1 [cs.IT], Feb. 2016.
[4] S. Saeedi Bidokhti, R. Timo, and M. Wigger, “Noisy broadcast networks with receiver caching,” arXiv:1605.02317v1
[cs.IT], May 2016.
[5] M. Mohammadi Amiri and D. Gündüz, “Cache-aided content delivery over erasure broadcast channels,” IEEE Trans.
Commun., vol. PP, no. 99, pp. 1–1, Sep. 2017.
[6] J. Zhang and P. Elia, “Wireless coded caching: A topological perspective,” arXiv:1606.08253v1 [cs.IT], Jun. 2016.
[7] S. Saeedi Bidokhti, M. Wigger, and A. Yener, “Benefits of cache assignment on degraded broadcast channels,”
arXiv:1702.08044v1 [cs.IT], Feb. 2017.
[8] E. Piovano, H. Joudeh, and B. Clerckx, “On coded caching in the overloaded miso broadcast channel,” in Proc. IEEE Int’l
Symp. on Inform. Theory (ISIT), Aachen, Germany, Jun. 2017, pp. 2795–2799.
[9] K.-H. Ngo, S. Yang, and M. Kobayashi, “Scalable content delivery with coded caching in multi-antenna fading channels,”
arXiv:1703.06538v2 [cs.IT], Jul. 2017.
[10] S. P. Shariatpanahi, G. Caire, and B. H. Khalaj, “Physical-layer schemes for wireless coded caching,” arXiv:1711.05969
[cs.IT], Nov. 2017.
[11] A. C. Güngör and D. Gündüz, “Proactive wireless caching at mobile user devices for energy efficiency,” in Proc. IEEE
Int’l Symp. on Wireless Comm. Systems (ISWCS), Brussels, Belgium, Aug. 2015.
[12] M. Gregori, J. Gomez-Vilardebo, J. Matamoros, and D. Gündüz, “Wireless content caching for small cell and D2D
networks,” IEEE J. Sel. Areas Commun., vol. 34, no. 5, pp. 1222–1234, May 2016.
[13] M. Mohammadi Amiri and D. Gündüz, “Decentralized caching and coded delivery over gaussian broadcast channels,” in
Proc. IEEE Int’l Symp. on Inform. Theory (ISIT), Aachen, Germany, Jun. 2017, pp. 2785–2789.

32

[14] P. Bergmans, “Coding theorem for broadcast channels with degraded components,” IEEE Trans. Inform. Theory, vol. 19,
no. 2, pp. 197–207, Mar. 1973.
[15] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,”
arXiv:1609.07817v1 [cs.IT], Sep. 2016.
[16] M. A. Maddah-Ali and U. Niesen, “Decentralized caching attains order optimal memory-rate tradeoff,” IEEE/ACM Trans.
Netw., vol. 23, no. 4, pp. 1029–1040, Apr. 2014.

