1

On Coded Caching in the Overloaded MISO
Broadcast Channel

arXiv:1702.01672v3 [cs.IT] 24 Jun 2017

Enrico Piovano, Hamdi Joudeh and Bruno Clerckx
Department of Electrical and Electronic Engineering, Imperial College London, United Kingdom
Email: {e.piovano15, hamdi.joudeh10, b.clerckx}@imperial.ac.uk

Abstract—This work investigates the interplay of coded caching
and spatial multiplexing in an overloaded Multiple-Input-SingleOutput (MISO) Broadcast Channel (BC), i.e. a system where
the number of users is greater than the number of transmitting
antennas. On one hand, coded caching uses the aggregate global
cache memory of the users to create multicasting opportunities.
On the other hand, multiple antennas at the transmitter leverage
the available CSIT to transmit multiple streams simultaneously.
In this paper, we introduce a novel scheme which combines both
the gain derived from coded-caching and spatial multiplexing
and outperforms existing schemes in terms of delivery time and
CSIT requirement.

I. I NTRODUCTION
Caching is a promising technique proposed to improve the
throughput and reduce the latency in communication networks
[1]–[3]. In a seminal work by Maddah-Ali and Niesen [2], the
fundamental limits of cache-aided networks were explored by
considering a setting in which a single transmitter (server)
communicates with multiple users over a shared medium. The
analysis revealed that although users cannot cooperate, there
exists a (hidden) global caching gain that scales with the
aggregated memory distributed across the network, alongside
the more obvious local caching gain.
In the context of wireless networks, recent efforts have
been made to combine coded caching with the conventional
interference management techniques [4], [5] and proved to
provide performance gains in different settings [6]–[10]. In
this work, we focus on the cache-aided multiple-input-singleoutput (MISO) broadcast channel (BC), in which a transmitter equipped with multiple antennas serves multiple singleantenna users equipped with cache memories.
Overloading the MISO BC: The ability to simultaneously
serve a large number of users is a key feature envisioned for
future wireless networks, pushing them towards overloaded
regimes in which the number of users exceeds the number
of transmit antennas. In this context, the setting considered
in [2] is intrinsically an overloaded BC where all nodes are
equipped with a single antenna. In this work, we consider
a more general overloaded BC in which the transmitter is
allowed to have multiple antennas K > 1, which is yet
still smaller than the number of users Kt . A recent work on
overloaded system can be found in [11]. In this paper, we make
progress towards characterizing the optimum caching strategy
This work has been partially supported by the EPSRC of UK, under grant
EP/N015312/1.

and cache-aided performance in such setting, which remain
unknown. To simplify the analysis, we consider scenarios in
which the number of scheduled users is an integer multiple of
the number of antennas, i.e. Kt = GK, where G is a positive
integer denoted as an overloading factor.
First, we consider the above setting under the assumption of
perfect CSIT. A natural way to serve the GK users is to divide
them into G groups of K users, each served independently in
an orthogonal manner (e.g. over time). Caching is carried out
independently for each group in which only the local caching
gain is relevant. This is denoted by the Orthogonal Scheme
(OS). An alternative scheme is the one proposed by MaddahAli and Niesen (MAN) [2], in which spatial multiplexing gains
from zero-forcing are completely ignored. We show that both
strategies are in fact suboptimal for the considered setting by
proposing a scheme that outperforms both in terms of the
delivery time, i.e. the time required to deliver the requested
information during the delivery phase.
Proposed scheme (PS): We propose to partition the library
of files at the transmitter into two parts by dividing each file
into two subfiles. One part of the library is stored in the
global memory of all Kt users in the MAN manner (cached
part), and the remaining part is never cached (uncached part).
During the delivery phase, information requested from the
cached part is transmitted through a single coded multicasting
stream. This is superposed on top of a zero-forcing layer
shared in an orthogonal manner between the G groups, and
carrying information requested from the uncached part. From
its structure, it can be seen that such scheme can exploit both
the zero-forcing gains of the MISO BC, and the global cache
memory of all users. We show that under adequate partitioning
of the library, PS outperforms both OS and MAN.
Partial CSIT: We relax the assumption of perfect CSIT. We
show that the delivery time achieved by the PS with perfect
CSIT is in fact maintained under partial CSIT, up to a certain
quality. We then extend the PS to deal with any partial CSIT
level. This is implemented by caching a fraction of the library
tailored to the actual CSIT and we show, through numerical
results, the gain compared to the MAN scheme. We then
compare with the OS. However, we consider now the coded
caching strategy in [8] applied independently to each group
of K users. We show that this allows to serve the overloaded
system by achieving the same delivery time as in perfect CSIT
with a reduced quality. We prove then that the PS achieves the
same delivery time with a further reduced CSIT requirement.

2

II. S YSTEM M ODEL
A. Overloaded cache-aided MISO BC
We consider the overloaded scenario described before. The
transmitter has access to a library with Nf distinct files, denoted as W1 , W2 , . . . , WNf , each of size f bits and we assume
Nf ≥ Kt . Each user k ∈ Kt is equipped with a cache-memory
Zk of size M f bits, where M < Nf . For tractability, we
is an integer. This allows for
assume that the ratio Γ = KNt M
f
a closed-form expression of the achievable delivery time for
the MAN scheme. The communication takes place over two
phases: the placement phase and the delivery phase. During
the placement phase, before actual user demands are revealed,
the caches Zk are pre-filled with information from the Nf
files W1 , W2 , . . . , WNf . During the delivery phase, each user
k requests a single file Fk , for some Fk ∈ {1, 2, · · · , Nf }.
The requested files WF1 , . . . , WFKt are jointly mapped into
the transmitted signal x ∈ CK×1 , which satisfies the power
constraint E(xH x) ≤ P . At the t-th discrete channel use, the
k-th user’s received signal is given by
yk (t) = hH
k (t)x(t) + nk (t),
hH
k (t)

k = 1, 2, . . . , Kt

(1)

1×K

where
∈C
is the channel between the transmitter
and the k-th user and nk (t) ∼ CN (0, 1) is the Additive White
Gaussian Noise (AWGN). The duration of the delivery phase
is given by T , which is a normalized measure as explained in
the next subsection. The discrete channel uses are indexed by
t, where t ∈ [0, T ] as in [9]. In the remainder of the paper, the
index t of the channel use will be omitted for ease of notation.
At the end of the delivery phase, each user combines the signal
yk with its own cached information Zk in order to retrieve the
requested file WFk .
B. Performance measure
In this paper, the analysis is restricted to the high-SNR
regime. Such analysis gives insight into the role of coded
caching in interference management. The metric of evaluation
is the duration T needed to complete the delivery phase for
every request by the users. T is measured in time slots per
file served. As in [8], the time is normalized such that one
time slot is the amount of time required to transfer a single
file to a single receiver without caching and interference.
As a consequence, since the single-stream capacity scales as
log2 (P ) for the high-SNR regime, we can impose the size of
each file f = log2 (P ) to align our measure of performance
with [2] and make the two comparable. Finally, it is worth
noting that similar to [2], [8], T represents the worst case
scenario, i.e. the case when each user requests a different file.
For ease of notation, and without loss of generality, we assume
that user k requests file Wk for all k ∈ Kt .

which is assumed to have a covariance matrix σk2 I. The
variance σk2 is parametrized as a function of the SNR P in
the form of P −αk , where αk is the CSIT quality exponent
defined as
log(σk2 )
, k = 1, 2, . . . , Kt .
(3)
αk = lim −
P →∞
log(P )
The exponent is restricted to αk ∈ [0, 1] which captures the
entire range of CSIT (from unknown to perfect) in the highSNR regime [12], [13].
III. M ULTIPLEXING AND M ULTICASTING
In this section, we present what we consider to be the two
most obvious ways to deal with the cached-aided scenario at
hand. We further assume that CSIT is perfectly known.
A. The Orthogonal Scheme (OS)
The OS transmits K interference-free streams due to the
presence of K antennas and perfect CSIT. Each user stores
the same fraction from each file in the library, hence during
M
f bits from
the placement phase its memory is filled with N
f
M
each file. This leaves (1 − Nf )f bits to be delivered during the
delivery phase. The Kt users are divided into G groups of K
users each, where groups are orthogonalized in time and each
group is served using zero-forcing. It follows that the delivery
M
from which the total
time of each group is given by 1 − N
f
delivery time is given by


M
.
(4)
TDOS = G 1 −
Nf

M
corresponds to the local caching gain achieved
The term 1− N
f
due to the locally stored content in the memory of each user. It
is evident that the OS only exploits the local caching gain and
no coded multicasting is needed. In fact multiuser interference
is eliminated through time-sharing and zero-forcing.

B. Maddah-Ali Niesen scheme (MAN)
Alternatively, all Kt users can be served jointly using the
MAN scheme proposed in [2]. While this scheme is designed
for a system with a single transmitting antenna, it can be used
here by ignoring the multiplexing gains of the antenna array.
Following the same placement and delivery procedure in [2],
the total delivery time is given by


M
1
·
(5)
TDMAN = Kt 1 −
Nf 1 + Γ

M
The term 1 − N
corresponds to the local caching gain as in
f
1
·
the OS, while the global caching gain is captured by 1+Γ

C. Motivations for a new scheme
C. Partial Instantaneous CSIT
To study the influence of CSIT imperfections, the channel
is modelled by
hk = ĥk + h̃k
(2)
where ĥk denotes the instantaneous channel estimate available
at the transmitter for user k, and h̃k denotes the CSIT error,

We compare the performance of OS and MAN using the
OS
TD
ratio T MAN
= 1+Γ
K . The value of Γ, which is an integer,
D
belongs to the set {1, . . . , Kt }. It is evident from the ratio that
the OS performs comparatively better or equal to the MAN
scheme for Γ ∈ {1, . . . , K −1}. On the other hand, for Γ ≥ K,
MAN scheme performs better than the OS scheme. The OS

3

and MAN schemes can be seen as the two extreme cases of
utilizing the available CSIT on one side and caching on the
other side. We propose a scheme that combines elements of
OS and MAN by incorporating both spatial multiplexing and
global cache gains. This is shown to outperform both OS and
MAN in the region Γ ∈ {1, . . . , ζ}, where ζ ≥ K − 1 is some
integer. For the region Γ ∈ {ζ + 1, . . . , Kt }, the proposed
scheme matches the performance of MAN. In this paper we
focus on Γ ≤ K − 1, i.e. Γ belongs to the set {1, . . . , K − 1}.
IV. P ROPOSED S CHEME
The design of the PS involves a partition of the library
into two parts: one treated in the MAN manner, while the
other is never cached, hence delivered using zero-forcing. Such
partition is implemented by caching a fraction p ∈ [0, 1] of
each file, so that the MAN scheme consists of pNf files, while
the remaining (1 − p)Nf files correspond to the zero-forcing
part. Since we treat the cached part in a MAN manner, the
tM
ratio η = KpN
is assumed to be an integer, where η indicates
f
the number of times the cached part is repeated inside the
memories. In case of p = 1, we cache all the library and
M
, the cached part fits
η = Γ. On the other hand, for p = N
f
exactly in every single memory and in this case η = Kt .
tM
We can write p in terms of η, i.e. p = KηN
, where
f
η ∈ [Γ, Kt ] ∩ Z. Increasing η translates into a decreased
cached portion from each file and higher replication in the
memories which, in turn, is translated into multicasting messages intended for more receivers. However, a larger uncached
part needs to be delivered using zero-forcing. Selecting the
right parameter η (or equivalently the right p), is crucial to
achieve an optimum trade-off between spatial multiplexing and
coded multicasting gains as we see in what follows. Next, the
placement and delivery phase of the PS is described in detail.

B. Delivery Phase
During the delivery phase, the actual demands from users
are revealed. A given file Wk requested by the corresponding
user k consists of three parts: a) a part that is contained in
the cache Zk and hence it is not requested during the delivery
phase, b) a part that is contained in the memories of other users
Zm for m ∈ Kt \ k, which is termed as the requested cached
(c)
part and given by the subfiles Wk,τ , for all k ∈
/ τ c) a part
that has never been cached termed as the uncached part which
(p)
is denoted by Wk . The delivery phase is carried out using a
superposed transmission of the requested cached part, where
the coded multicasting information is delivered by a common
symbol decoded by all Kt users, and the uncached parts,
delivered through private symbols in a zero-forcing fashion.
Since the users share the zero-forcing layer in a orthogonal
manner, the transmission is carried out over G sub-phases
indexed by g = 1, . . . , G. Without loss of generality, we
assume that in the g-th sub-phase, the private symbols are
intended to the group Kg = {(g − 1)K + 1, . . . , gK}.
We denote the common symbols transmitted over the G
(c)
sub-phases as {xg }G
g=1 . They carry the coded messages
(c)

(c)

WS = (⊕k∈S Wk,S\{k} : S ∈ Θ)

(7)

where Θ = {S ⊂ Kt : |S| = η + 1}. These coded messages
are a combination of the requested cached part as they were
first proposed in [2] and each of them contains information for
η + 1 users. Similarly, at the g-th sub-phase, private symbols
(p)
(p)
xk carry the uncached parts Wk , where k ∈ Kg . During
the g-th delivery sub-phase, the transmitted signal is
X √
√
(p) (p)
(8)
P β vk xk +O(1)
xg = P v(c) x(c)
g +
|
{z
} k∈Kg
MAN
{z
}
|
ZF

(p)

A. Placement Phase
We first describe the placement and delivery for a given
tM
factor η, or equivalently p = KηN
. Then η is optimized to
f
minimize the delivery time. We divide each of the Nf files
W1 , W2 , . . . , WNf into two subfiles:
Wn = (Wn(c) , Wn(p) )

(6)

(c)
Wn ,

where
of size pf , is cached into the memories while
(p)
Wn , of size (1 − p)f , is never cached. We apply the idea in
(c)
(c)
(c)
[2] to the subfiles W1 , W2 , . . . , WNf by jointly encoding
all Kt users together considering their total global cache
(c)
memory. Consequently,
according to [2], each subfile Wn

(c)
Kt
is split into η smaller subfiles Wn,τ , for all τ ∈ Ω, where
(c)

Ω = {τ ⊂ Kt : |τ | = η}. It follows that each subfile Wn,τ has
. From each file n ∈ {1, 2, . . . , Nf }, user k caches
size pf
(Kηt )
(c)
the subfiles Wn,τ such that k ∈ τ . Hence each user caches Mf
Nf
(c)
bits from any Wn . Since we assume different demands across
users, the total number of files to be delivered from the cached
(c)
M
tM
part of the library is given by Qη = Kt ( KηN
−N
) 1 ·
f
f 1+η
Additionally, the number of files to be delivered
through zero
(p)
Kt M
forcing is given by Qη = Kt 1 − ηNf ·

where v(c) ∈ CM×1 and vk ∈ CM×1 are unitary precoding
vectors, and β ∈ [0, 1] is the power partitioning factor [11].
Note that the term O(1) guarantees that the power constraint is
not violated. Such term has no influence on high-SNR analysis.
(c)
Since xg has to be decoded by all Kt users, v(c) is chosen as
a generic precoding vector. On the other hand, private symbols
are precoded using the well-known zero-forcing precoders.
The received signal for each user k ∈ Kt is given by
X√
√
(p) (p)
(c) (c)
y k = P hH
+ O(1).
P β hH
k v xg +
k vi xi
i∈Kg
(c)

All users in Kt decode xg by treating the interference
(c)
from all the other symbols as noise. Hence, xg can carry
(1 − β) log2 (P ) bits per time slot. Users in Kg proceed to
(c)
remove the contribution of xg to the received signal and
(p)
(p)
decode their private symbols xk . The symbol xk is decoded
β
with a SINR of O(P ), hence carrying β log2 (P ) bits per
time slot. It follows that the cached part of the library is
delivered with a rate of (1 − β) log2 (P ) bits per time slot and
the uncached part of the library with a rate of Kβ log2 (P ) bits
(c)
per time slot. From {xg }G
g=1 each user k ∈ Kt retrieves the
(c)
messages WS and consequently its cached part. In fact any

4

(c)

missing sub-files Wk,τ , so that k ∈
/ τ , can be recovered by
(c)
(c)
combining WS with the pre-stored sub-files Wi,S\{i} , where
(p)

S = τ ∪ {k} and i ∈ S \ {k}. On the other hand, from xk
(p)
each user k ∈ Kg retrieves the uncached part Wk .
C. Delivery time

During the communication both the cached and uncached
∗
parts must be delivered. We indicate as TD,η
the delivery
time of such communication. The power partitioning factor,
indicated as β ∗ , is chosen to let both parts to be delivered
(p)
over this delivery time. Hence, the two equalities Qη f =
(c)
∗
∗
Kβ ∗ f TD,η
and Qη f = (1 − β ∗ )f TD,η
must be simultaneously satisfied. It can be verified that the solution is given by
Q(p)
(c)
η
K + Qη and
(p)
(c)
Qη and Qη , we obtain

∗
TD,η
=

∗
TD,η

β∗ =

Q(p)
η /K
(p)
(c)
Qη /K+Qη

. By expanding





M Kt
M Kt
M
Kt
=G 1−
−
+
.
ηNf
η + 1 ηNf
Nf

(9)

The value of η ∈ [Γ, Kt ] ∩ Z must be chosen to minimize the
delivery time in (9). This is given by
TD∗ =

min

η∈[Γ,Kt ]∩Z

∗
TD,η
.

(10)

where TD∗ denotes the minimum delivery time. The following
result holds for which proof can be found in the appendix.
Proposition 1. In case of perfect CSIT, the PS achieves a
delivery time TD∗ given by
TD∗ =

min

η∈{⌊x⌋,⌈x⌉}

∗
TD,η

x=

∗

which scales as O(P β ), where β ∗ =

(p)
Qη∗ /K
(p)
(c)
Qη∗ /K+Qη∗

. If the

channel estimation error decays as O(P −α ), where α ≥ β ∗ ,
each user can still decode its own private symbol as interference from other symbols is at (or below) the noise floor.
[14]. Hence the SINR still scales as in case of perfect CSIT. It
follows that, the delivery time TD∗ is mantained for any CSIT
quality no less than β ∗ . Since this represents a CSIT quality
threshold, by indicating it as α∗ , we obtain


t
G 1 − MK
η ∗ Nf

.

(13)
α∗ = β ∗ = 
MKt
Kt
M
t
G 1 − η∗ Nf + η∗ +1 MK
η ∗ Nf − Nf

B. General Case
The case α < α∗ is treated by caching a larger fraction
of the library which reduces the load carried by the private
symbols. We proceed by considering a given η which will be
then optimized based on the actual CSIT. For the delivery of
the uncached part, zero-forcing is replaced by rate-splitting,
which is well suited to operate under partial CSIT [14]. The
placement phase and delivery phase follow the same steps
as in perfect CSIT. In rate-splitting, at the g-th delivery sub(p)
phase, the uncached parts Wk with k ∈ Kg are divided
(p)
and partially mapped to the private symbols xk , while
the remaining parts are jointly encoded into the symbol x̃g ,
decoded by all users in Kg . The transmitted signal is
X √
√
√
(p) (p)
β (c) x̃ +
P a vk xk +O(1)
xg = P v(c) x(c)
g
g + P v
{z
}
|
k∈Kg
MAN
{z
}
|
RS

(11)

where
G(K − 1) +

A. CSIT Relaxation
In Section IV-B, perfect CSIT was exploited to deliver K
interference-free private symbols, transmitted with a power

p
G2 (K − 1)2 + G(G + 1)(K − 1)
.
G+1
(12)

The value of η that minimizes the delivery time in (11) is
∗
denoted by η ∗ , i.e. TD∗ = TD,η
∗ . By comparing the result in
Preposition 1 with the delivery time in (4) and (5), it is verified
that TD∗ < TDOS ≤ TDMAN . Hence, simultaneously exploiting
the global cache memory of all users and the multiplexing
gain, the PS strictly outperforms both OS and MAN.

V. PARTIAL CSIT
In this section, we relax the constraint of perfect CSIT
and consider a setting with partial CSIT. The scheme in turn
is generalized to account for such imperfection. We start by
showing that the delivery time in (11) can be maintained, while
relaxing the CSIT quality α. Then we modify the PS to be
adaptable for any α, by properly tailoring the cached part of
the library based on the available CSIT.

where symbols, precoding vectors and powers are defined as in
the previous section, with the difference that the power of the
private symbols scales as O(P a ), with a ≤ β. Furthermore,
to force interference between private symbols to the noise
floor level, we need a ≤ α. Hence, we take a = min(α, β).
(c)
All users in Kt decode xg by treating the other symbols as
noise, hence it can carry (1 − β) log2 (P ) bits per time slot.
(c)
Then, all users in Kg proceed to cancel xg and decode x̃g ,
which is then canceled before decoding their respective private
symbols. It can be easily verified that rate-splitting achieves a
total rate of (β+(K −1) min(α, β)) log 2 (P ) bits per time slot.
Further details on the rate-splitting procedure can be found in
(c)
[11], [14]. As before, from {xg }G
g=1 each user can retrieve
(p)
its desired cached part, while from x̃g and xk users k ∈ Kg
retrieve their uncached parts.
C. Delivery Time
As in Section IV-C, the power partitioning factor β ∗ is cho(p)
sen such that Qη f = (β ∗ + (K − 1) min(α, β ∗ ))f TD,η (α)
(c)
and Qη f = (1 − β ∗ )f TD,η (α), where TD,η (α) denotes the
delivery time. The delivery time is given by
( ∗
TD,η , α ≥ α∗η
(c)
(14)
TD,η (α) = Q(p)
η +Qη
∗
1+(K−1)α , α < αη

5

(c)

TD (α) =

min

η∈[Γ,Kt ]∩Z

TD,η (α).

8
7

MAN
PS

6

TD

5
4
3
2
1
0

0.2

0.4

0.6

0.8

1

α

Fig. 1. TD as function of the CSIT quality α for K = 8 and G = 2

(15)

The following result holds for which the proof is given in the
appendix.

0.8

0.8
α th

Proposition 2. Given a CSIT quality α, we can achieve the
following delivery time:
(
TD∗ , α ≥ α∗
TD (α) =
1+(K−1)α∗
η+1
∗
∗
∗
min{TD,η
, TD,η+1
1+(K−1)α }, α < α
(16)
where
η = arg ′ max∗ {η ′ : α∗η′ ≤ α}.
(17)

1

1

OS
PS

0.6

OS, K=4
PS, K=4
OS, K=8
PS, K=8

0.6

α th

Q(p)

Q(p) /K

η
∗
where α∗η = (p) η
(c) and TD,η =
K + Qη . It can be
Qη /K+Qη
seen that given a certain partition η, the same delivery time
as in perfect CSIT can be maintained as long as α ≥ α∗η . On
the other hand, in case of α < α∗η , the delivery time is given
by the ratio between the total number of transmitted files and
the total communication rate. In case of η = η ∗ , we reduce to
∗
∗
α∗η∗ = α∗ and TD,η
∗ = TD , in agreement with Section V-A.
For a given quality α, the minimum achievable delivery time,
denoted by TD (α), is given as

0.4

0.4

0.2

0.2

0
1

2

3

4

G

OS
a) αPS
th and αth with respect to G

0

0.5

1

1.5
M

2

2.5

3

OS
b) αPS
th and αth with respect to M

OS
Fig. 2. CSIT qualities for the PS and OS to achieve TD

η ∈[Γ,η )∩Z

∗

For α ≥ α we can achieve the same delivery time as perfect
CSIT given in Proposition 1. Examining the delivery time from
the expression in (16) for the entire range of α is not an easy
task as we were not able to derive a more tractable expression.
However, it can be seen that for α = 0, we obtain η = Γ
in (17) and the scheme reduces to MAN. The influence of
increasing α is examined through simulations in the following
section where it is shown that the PS leverages the available
CSIT and outperforms the MAN scheme.
Looking at the PS from a different perspective, we investigate the minimum CSIT quality required to achieve a given
delivery time T . This is given through the following result for
which the proof is given in the appendix.
Proposition 3. A delivery time T ≥ TD∗ can be achieved by
a CSIT quality α equal to


∗
TD,η
1 + (K − 1)α∗η − T
(18)
α=
(K − 1)T

where

η = arg

min

η ′ ∈[Γ,η ∗ ]∩Z

∗
{η ′ : TD,η
′ ≤ T }.

(19)

Since the MAN scheme does not require CSIT, it is suitable
to compare to the OS in this context. We further assume that
each orthogonal group of K users is served using the strategy
in [8] to account for imperfect CSIT. It follows that the delivery time TDOS can be achieved while applying coded caching
N −

Nf

−M

f
K
and relaxing the CSIT quality to αOS
th = M +N − Nf −M . In
f
K
K
comparision, by applying Proposition 3, we can characterize
the minimum CSIT quality needed by the PS to achieve TDOS,
OS
∗
denoted as αPS
th . We observe that TD = TD,K−1 . Hence the
PS
value of αth in (18) is given by

αPS
th =

Nf −

M
K

Nf
K

+ Nf −

− MG
Nf
K

−M

.

(20)

PS
PS
By comparing αOS
th and αth , we can see that αth is strictly
lower for the overloaded case (G ≥ 2).

VI. N UMERICAL RESULTS
In this section, we numerically evaluate the PS. First, we
compare the delivery time TD (α) achieved under different
CSIT qualities to the one achieved using the MAN scheme, i.e.
TDMAN . This is given in Fig. 1 for a setup with K = 8 antennas,
overloading factor G = 2 and memories of size M f bits, with
M = 1. We consider a library of Nf = Kt throughout the
simulations. We observe that the PS leverages the available
CSIT quality to reduce the delivery time compared to MAN.
In particular, for α = 1, the delivery time is four times lower.
Next, we compare the PS with OS in terms of the minimum
CSIT quality needed to achieve TDOS in (4). In Fig. 2a we plot
OS
αPS
th and αth as a function of G. We consider a setup with
K = 4, 8 and M = 2. As we can see, the OS suffers when
G increases, while the PS, in addition to outperforming OS,
benefits from a larger G. Finally, in Fig. 2b we plot αPS
th and
αOS
as
a
function
of
M
with
K
=
4
and
G
=
2.
We
can
see
th
OS
for
increasing
M
.
decreases
much
faster
than
α
that αPS
th
th
VII. C ONCLUSION
In this paper, we studied the complementary gain of coded
caching and spatial multiplexing gain for an overloaded
MISO BC. We investigated how to simultaneously combine
the gain offered from the aggregate global cache memory,
with the gain offered by the presence of available CSIT.
We introduced a novel scheme which superimposes MaddahAli Niesen scheme, to exploit the coded caching gain, to a
multiuser transmission scheme, to leverage the available CSIT.
Analytical and numerical results showed a significant gain
compared to the existing schemes, both in terms of delivery
time and CSIT quality requirement.

6

A PPENDIX

C. Proof of Proposition 3

A. Proof of Proposition 1
In order to prove Proposition 1, we need to evaluate the
∗
minimum of the function TD,η
in (9) with respect to η over
the interval [Γ, Kt ] ∩ Z, and we remember that Kt = GK.
The minimum value is indicated as TD∗ in (10). We start by a
relaxation, where η is allowed to take any value in [Γ, Kt ].
∗
We can notice that TD,η
is convex over such interval and
∗
∗
∗
TD,K−1 = TD,GK , hence TD,η
has a minimum in [K − 1, Kt ].
∗
The first derivative of TD,η with respect to η is equal to zero
for η = x, given in (12). By restricting η to be an integer, i.e.
∗
η ∈ [Γ, Kt ] ∩ Z, we have that TD,η
is minimum in either ⌊x⌋
or ⌈x⌉, from which the expression in (11) follows. It can be
∗
∗
easily verified that TD,K−1
= TD,GK
= TDOS , where TDOS is
∗
OS
MAN
given in (4). Hence, TD < TD ≤ TD .
B. Proof of Proposition 2
In order to prove Proposition 2, we need to find the value
of TD (α) in (15). We have
TD (α) =

min

η ′ ∈[Γ,Kt ]∩Z

TD,η′ (α)

(21)

where TD,η′ (α) is defined as in (14). As explained in
Section V-A, in case α ≥ α∗ , it is possible to achieve the
same delivery time as in the case of perfect CSIT. Hence,
TD (α) = TD (1) = TD∗ . We now focus on the case α < α∗ .
We start by considering α∗η′ in Section V-C
(p)

Qη′ /K

α∗η′ =

(p)
Qη′ /K

+

(c)
Qη ′

=

1
(c)

(p)

1 + KQη′ /Qη′

.

(22)

(c)

It can be shown that Qη′ is a decreasing function of η ′ while
(p)
Qη′ is an increasing function of η ′ . It follows that α∗η′ is
also an increasing function of η ′ . Then, by denoting the total
number of files to be transmitted as Qη′ , we have
(c)

(p)

Qη ′ = Qη ′ + Qη ′ = Kt −

M 1
(K 2 + Kt )
Nf η ′ + 1 t

(23)

which is also an increasing function of η ′ . Moreover, from
(14), the following relationship is verified
∗
∗
Qη′ = TD,η
′ (1 + (K − 1)αη ′ ).

(24)

Given that we are considering α < α∗ and we know that
α∗η∗ = α∗ and α∗Γ = 0, there must exist an η such that
η = arg maxη′ ∈[Γ,η∗ )∩Z {η ′ : α∗η′ ≤ α}. Moreover, from the
∗
proof of Proposition 1, we know that TD,η
′ is a decreasing
′
∗
function with respect to η in [Γ, η ) ∩ Z. From (14), consid∗
∗
ering η ′ ≤ η, we have TD,η′ (α) = TD,η
′ ≥ TD,η . In case of
′
η ≥ η + 1, we have
(p)

(c)

Qη ′ + Qη ′

(p)

(c)

Qη+1 + Qη+1
= TD,η+1 (α).
1 + (K − 1)α
1 + (K − 1)α
(25)
∗
Hence, TD (α) is the minimum between TD,η
and TD,η+1 (α),
from which Proposition 2 follows.
TD,η′ (α) =

≥

∗
From the proof of Proposition 1, we know that TD,η
′ is
′
∗
a decreasing function with respect to η in [Γ, η ] ∩ Z and
increasing in [η ∗ , Kt ] ∩ Z. Hence, there must exist

η = arg

min

∗
{η ′ : TD,η
′ ≤ T}

(26)

∗
{η ′ : TD,η
′ ≤ T }.

(27)

η ′ ∈[Γ,η ∗ ]∩Z

and
ζ = arg

max

η ′ ∈[η ∗ ,Kt ]∩Z

∗
In case of η ′ < η or η ′ > ζ, we have TD,η
′ > T , thus
the delivery time T is not achievable. On the other hand, by
considering η ′ ∈ [η, ζ] and applying (14), the delivery time T
is achieved by a CSIT quality given by
(p)

α

η′

=

(c)

Qη ′ + Qη ′ − T
(K − 1)T

.

(28)
(p)

(c)

As expressed in the proof of Proposition 2, Qη′ + Qη′
increases with η ′ . It follows that η = arg minη′ ∈[η,ζ]∩Z αη′ .
(p)
(c)
∗
From Qη + Qη = TD,η
(1 + (K − 1)α∗η ), we obtain (18).
R EFERENCES
[1] N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and
G. Caire, “Femtocaching: Wireless video content delivery through
distributed caching helpers,” in Proc. IEEE INFOCOM, pp. 1107–1115,
Mar. 2012.
[2] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”
IEEE Trans. Inf. Theory, vol. 60, pp. 2856–2867, May 2014.
[3] M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains
order-optimal memory-rate tradeoff,” IEEE/ACM Trans. Net., vol. 23,
pp. 1029–1040, Aug. 2015.
[4] D. Gesbert, S. Hanly, H. Huang, S. S. Shitz, O. Simeone, and W. Yu,
“Multi-cell MIMO cooperative networks: A new look at interference,”
IEEE J. Sel. Areas Commun., vol. 28, pp. 1380–1408, Dec. 2010.
[5] S. A. Jafar, “Interference alignment a new look at signal dimensions in
a communication network,” Found. Trends Commun. Inf. Theory, vol. 7,
no. 1, pp. 1–134, 2011.
[6] M. A. Maddah-Ali and U. Niesen, “Cache-aided interference channels,”
in Proc. IEEE ISIT, pp. 809–813, Jun. 2015.
[7] N. Naderializadeh, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental limits of cache-aided interference management,” in Proc. IEEE
ISIT, pp. 2044–2048, Jul. 2016.
[8] J. Zhang, F. Engelmann, and P. Elia, “Coded caching for reducing CSITfeedback in wireless communications,” in Proc. Allerton, pp. 1099–1105,
Sep. 2015.
[9] J. Zhang and P. Elia, “Fundamental limits of cache-aided wireless
BC: Interplay of coded-caching and CSIT feedback,” arXiv:1511.03961,
2015.
[10] S. Yang, K. H. Ngo, and M. Kobayashi, “Content delivery with coded
caching and massive MIMO in 5G,” in Proc. ISTC, pp. 370–374, Sep.
2016.
[11] E. Piovano, H. Joudeh, and B. Clerckx, “Overloaded multiuser MISO
transmission with imperfect CSIT,” arXiv:1612.00628, 2016.
[12] N. Jindal, “MIMO broadcast channels with finite-rate feedback,” IEEE
Trans. Inf. Theory, vol. 52, pp. 5045–5060, Nov. 2006.
[13] S. Yang, M. Kobayashi, D. Gesbert, and X. Yi, “Degrees of freedom
of time correlated MISO broadcast channel with delayed CSIT,” IEEE
Trans. Inf. Theory, vol. 59, pp. 315–328, Aug. 2013.
[14] H. Joudeh and B. Clerckx, “Sum-rate maximization for linearly precoded
downlink multiuser MISO systems with partial CSIT: A rate-splitting
approach,” IEEE Trans. Commun., vol. 64, pp. 4847–4861, Aug. 2016.

