# Benefits of Cache Assignment on Degraded Broadcast Channels

Shirin Saeedi Bidokhti, Michèle Wigger, Shirin Saeedi Bidokhti, Aylin Yener

► To cite this version:

Shirin Saeedi Bidokhti, Michèle Wigger, Shirin Saeedi Bidokhti, Aylin Yener. Benefits of Cache Assignment on Degraded Broadcast Channels. IEEE Transactions on Information Theory, 2019, 65 (11), pp.6999-7019. 10.1109/TIT.2019.2926714. hal-02439575

HAL Id: hal-02439575

https://hal.science/hal-02439575

Submitted on 14 Jan 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Benefits of Cache Assignment on Degraded Broadcast Channels

Shirin Saeedi Bidokhti<sup>ID</sup>, Member, IEEE, Michèle Wigger<sup>ID</sup>, Senior Member, IEEE, and Aylin Yener<sup>IF</sup>, Fellow, IEEE

**Abstract**—Degraded K-user broadcast channels (BCs) are studied when the receivers are facilitated with cache memories. Lower and upper bounds are derived on the capacity-memory tradeoff, i.e., on the largest rate of reliable communication over the BC as a function of the receivers' cache sizes, and the bounds are shown to match for interesting special cases. The lower bounds are achieved by two new coding schemes that benefit from *nonuniform cache assignments*. Lower and upper bounds are also established on the global capacity-memory tradeoff, i.e., on the largest capacity-memory tradeoff that can be attained by optimizing the receivers' cache sizes subject to a total cache memory budget. The bounds coincide when the total cache memory budget is sufficiently small or sufficiently large, where the thresholds depend on the BC statistics. For small cache memories, it is optimal to assign all the cache memory to the weakest receiver. In this regime, the global capacity-memory tradeoff grows by the total cache memory budget divided by the number of files in the system. In other words, a *perfect global caching gain* is achievable in this regime and the performance corresponds to a system where all the cache contents in the network are available to all receivers. For large cache memories, it is optimal to assign a positive cache memory to every receiver, such that the weaker receivers are assigned larger cache memories compared to the stronger receivers. In this regime, the growth rate of the global capacity-memory tradeoff is further divided by the number of users, which corresponds to a local caching gain. It is observed numerically that a uniform assignment of the total cache memory is suboptimal in all regimes, unless the BC is completely symmetric. For erasure BCs, this claim is proved analytically in the regime of small cache sizes.

**Index Terms**—Broadcast channel (BC), caching, capacity-memory tradeoff, Gaussian channels, joint source-channel coding.

## I. INTRODUCTION

STORING popular contents at or close to the end users improves the network performance during peak-traffic

Manuscript received February 26, 2017; revised February 4, 2019; accepted June 14, 2019. Date of publication July 4, 2019; date of current version October 18, 2019. S. Saeedi Bidokhti was supported by the National Science Foundation under Award 1850356. M. Wigger was supported by the European Research Council under Grant 715111. This paper was presented in part at the IEEE International Conference on Communications 2017, in Paris, France, and at the IEEE International Symposium on Information Theory 2017, in Aachen, Germany.

S. Saeedi Bidokhti is with the Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104 USA (e-mail: saeedi@seas.upenn.edu).

M. Wigger is with LTCI, Télécom Paris, IP Paris, 75013 Paris, France (e-mail: michele.wigger@telecom-paristech.fr).

A. Yener is with the Department of Electrical Engineering, School of Electrical Engineering and Computer Science, Pennsylvania State University, State College, PA 16802 USA (e-mail: yener@engr.psu.edu).

Communicated by F. Alajaji, Associate Editor for Shannon Theory.

Color versions of one or more of the figures in this article are available online at http://ieeexplore.ieee.org.

Digital Object Identifier 10.1109/TIT.2019.2926714

times. The main challenge is that the contents have to be cached before knowing which files the users will request in peak-traffic periods. A conventional approach is to store popular contents in the cache memories of all the users. This allows the receivers to locally retrieve the contents without burdening the network and attain the so-called *local caching gain*. Maddah-Ali and Niesen [1] have shown that further caching gains, i.e., the so-called *global caching gains*, are achievable if different contents are stored at different users in a careful manner.

In particular, reference [1] considered a broadcast scenario with a transmitter that has access to a library of N independent files and with K receivers that are all equipped with individual cache memories of the same size. Communication during off-peak periods, when contents are cached, is assumed error-free and constrained only by the amount of information that can be placed in the cache memories at the receivers. This communication is henceforth called *cache placement or placement phase*. The subsequent peak-traffic communication is called *delivery phase*. In this phase, each receiver requests a single file from the library and the transmitter delivers the requested files by communicating over a common noise-free link to all K receivers. Reference [1] has proposed to diversify the placed contents across cache memories so as to allow for coding opportunities during the delivery phase. These coding opportunities allow to simultaneously serve multiple receivers in each transmission, providing gains that scale with the total size of all cache memories in the network, i.e., global caching gains. By contrast, the previously reported gains depend only on individual cache sizes and are thus referred to as local caching gains.

The performance metric in [1] is the minimum required delivery rate for given cache sizes, leading to the fundamental quantity of interest, the *delivery rate-memory tradeoff*. Upper and lower bounds on this tradeoff are provided in [1]. Improved upper bounds (achievability results) have subsequently been presented in [2]–[8] and improved lower bounds (converse results) in [9]–[13]. The common noise-free link model of [1] has also been studied for networks in which receivers have cache memories of different sizes [14]–[16]. Rate-limited links in delivery have been considered in [17].

In this paper, we relax the assumption that delivery takes place over a noise-free link. Instead, we model the delivery phase by a degraded broadcast channel (BC). The class of degraded broadcast channels is a fairly general class that includes practical noisy channel models such as broadcast erasure channels and Gaussian channels. Our model is depicted
<figure><img src="image_2.png" /><figcaption>Fig. 1. Noisy broadcast channel with cache memories at the receivers.</figcaption></figure>

in Figure 1. A transmitter communicates with receivers $1, \dots, K$, which are equipped with cache memories of sizes $nM_1, \dots, nM_K$ when communication is of blocklength $n$.

Noisy broadcast channels with caching receivers have been studied in different settings [18]–[30]. For example, references [18]–[20] explore the benefits of coded caching for Gaussian or slow fading BCs when all users have the same cache sizes. References [26]–[30] study the interplay between coded caching with spatial multiplexing, channel state information (CSI), or feedback. Most related to the current work are [21]–[24], which focus on erasure BCs with a set of weak receivers that are equipped with cache memories of equal size and a set of strong receivers without cache memories or with smaller cache memories. In accordance with multi-user information theory metrics, performance in these works is measured in terms of the capacity-memory tradeoff, i.e., the largest message rate for which receivers can decode their requested messages reliably as a function of the cache sizes. Lower bounds (achievability results) and upper bounds (converse results) are presented on the capacity-memory tradeoff. The lower bounds are based on joint cache-channel coding schemes where encoders and decoders exploit both the knowledge of the channel statistics and the cache contents. This is in contrast to previous works, e.g., [18], which adopt a separate cache-channel coding architecture. In separate cache-channel coding, the encoders (resp. decoders) consist of (i) a cache encoder (resp. decoder) that only exploits the cache contents and (ii) a channel encoder (resp. decoder) that only exploits the channel statistics; see Figure 2. As the results in [21], [22] show, when receivers have different channel statistics and weaker receivers have larger cache sizes, then adopting a joint cache-channel coding architecture can significantly improve performance. Moreover, [21] illustrates that it is beneficial to assign larger cache memories to weaker receivers than to stronger receivers.

Joint cache-channel coding schemes<fnref n="1" /> have also been employed for transmission over noisy BCs with caching receivers when the files to be sent are correlated [31], [32] or when receivers have different fidelity constraints [24], [25], [33]. In these applications, improvements are

<figure><img src="image_3.png" /><figcaption>Fig. 2. Separate cache-channel coding architecture.</figcaption></figure>

possible even when users have perfectly symmetric channels and cache sizes.

In this work, we consider the problem of efficient cache assignment in degraded broadcast channels and how to code under these assignments. We quantify new caching gains obtained through such assignments and appropriate coding.

### A. A Motivating Example

Consider an erasure BC with $K = 10$ users where receiver 1 has erasure probability $\delta_1 = 0.4$ and all other receivers $2, \dots, K$ have erasure probability $\delta_2 = \dots = \delta_K = 0.1$. Assuming no cache memories, denote the point to point channel capacity of user $k$ by $C_{(k)}$, and the symmetric capacity of the K-user broadcast channel by $C_{\{1, \dots, K\}}$ (see Section III for definitions). Now suppose that the communication blocklength is $n$ and we are given a total cache size of $nM$ to be distributed across the receivers (with any desired assignment), hence $nM = n(M_1 + \dots + M_K)$. We seek cache assignments, as well as coding schemes, that achieve high message rate. In particular, we are interested in the global capacity-memory tradeoff which we define as the largest rate achievable given the total cache budget $M$.

The traditional approach assigns the same cache size $n M_K$ to each receiver. We assign cache memories according to the channel strengths. For example, when the total cache rate $M$ is small, we assign all the cache rate to the weak receiver, so $M_1 = M$. For large total cache rate, in the example at hand, we propose to assign a larger portion to the weak receiver and to distribute the rest uniformly over all strong receivers. The meaning of small and large cache sizes are made precise in Corollary 11 in Section VI. Tables I and II compare the rates that are achievable for this example by the cache assignments and coding schemes of this paper as well as traditional uniform cache assignments and standard (separate cache-channel) codes. Table I treats the regime of small cache memories and Table II treats the regime of large cache memories. In both tables, the first column presents an upper bound on the capacity-memory tradeoff $C(M_K, \dots, M_K)$ under uniform cache assignment (i.e., when the total cache memory $M$ is assigned uniformly over the $K$ users). The second column shows the rate that is achievable using the cache assignments and coding schemes proposed in this paper. We will show that these rates equal the global capacity-memory tradeoff $C^*(M)$ in the regimes of small and large cache sizes. The third column considers the same cache assignment as in column 2, but presents the achievable rate $R$ using standard (separate cache-channel) codes. More specifically, in the regime of small

<footnote n="1">¹Joint cache-channel coding schemes are also referred to as joint source channel coding schemes because once the cache contents are fixed, they can be recast as realizations of sources that contribute side-information to the receivers.</footnote>
<table><caption>TABLE I
COMPARISON OF TRADITIONAL SCHEMES WITH THE ONES PROPOSED IN THIS PAPER IN THE REGIME OF “SMALL” TOTAL CACHE SIZES M</caption><tr><td>M<sub>1</sub> = M<sub>2</sub> = ... = M<sub>K</sub></td><td colspan="2">M<sub>1</sub> = M and M<sub>2</sub> = ... = M<sub>K</sub> = 0</td></tr><tr><td>Upper bound with uniform assignment</td><td>New coding</td><td>Standard coding</td></tr><tr><td>C(M<sub>K</sub>, ..., M<sub>K</sub>) ≤ C<sub>{1,...,K}</sub> + <sup>M</sup>&frasl;<sub>530</sub> · <sup>M</sup>&frasl;<sub>N</sub></td><td>C*(M) = C<sub>{1,...,K}</sub> + <sup>M</sup>&frasl;<sub>N</sub></td><td>R = C<sub>{1,...,K}</sub> + <sup>1</sup>&frasl;<sub>7</sub> · <sup>M</sup>&frasl;<sub>N</sub></td></tr></table>

<table><caption>TABLE II
COMPARISON OF TRADITIONAL SCHEMES WITH THE ONES PROPOSED IN THIS PAPER IN THE REGIME OF “LARGE” TOTAL CACHE SIZES M</caption><tr><td>M<sub>1</sub> = M<sub>2</sub> = ... = M<sub>K</sub></td><td colspan="2">M<sub>1</sub> = (8.1 + Δ)N and M<sub>2</sub> = ... = M<sub>K</sub> = (7.8 + Δ)N, for any Δ > 0</td></tr><tr><td>Upper bound with uniform assignment</td><td>New coding</td><td>Standard coding</td></tr><tr><td>C(M<sub>K</sub>, ..., M<sub>K</sub>) ≤ C<sub>{1}</sub> + <sup>M</sup>&frasl;<sub>K·N</sub><br>= 0.6 + <sup>M</sup>&frasl;<sub>K·N</sub></td><td>C*(M) = <sup>1</sup>&frasl;<sub>K</sub> ∑<sub>k=1</sub><sup>K</sup> C<sub>{k}</sub> + <sup>M</sup>&frasl;<sub>K·N</sub><br>= 0.87 + <sup>M</sup>&frasl;<sub>K·N</sub></td><td>R = <sup>1</sup>&frasl;<sub>K</sub> ∑<sub>k=1</sub><sup>K</sup> (C<sub>{k}</sub> - C<sub>{1}</sub>) + <sup>M</sup>&frasl;<sub>K·N</sub><br>= 0.27 + <sup>M</sup>&frasl;<sub>K·N</sub></td></tr></table>

cache sizes, a standard BC code is used to communicate to each receiver the part of its requested file that is not in its cache memory. Since in this example only the weak receiver has a cache memory, coded caching (multicasting) is not possible. Under the cache assignment in Table II (large cache memories), the rate achieved with separate source-channel coding is sufficiently small so that the weak receiver 1 can store all files in its cache memory, thus precluding delivery communication to this receiver. The optimal separation-based strategy is then to perform coded caching with parameter K − 2 (designed for the strong receivers) followed by a standard BC multicast code to those receivers. A comparison of columns 2 and 3 in Tables I and II shows that a smart cache assignment creates new coding opportunities that can be exploited by joint cache-channel coding.

From Table I, column 2, we further observe the following behavior of the global capacity-memory tradeoff $C^*(M)$: First of all, without cache memory, $C^*(M=0)$ equals the largest symmetric rate $C_{\{1,...,K\}}$ that is achievable to all the receivers in the BC. Now consider the slope with which $C^*(M)$ increases with M. For small total cache budget M, smart cache assignment and coding (see column 2) allow to attain a steeper slope than traditional uniform cache assignment (see column 1) as well as separate cache-channel coding (see column 3). In particular, our proposed cache assignment and coding allow to achieve what we call a *perfect caching gain*, where the capacity-memory tradeoff grows as $\frac{M}{N}$, i.e., like the *total size of all cache memories* in the network divided by the number of files N. This is the same performance as if each receiver had access to all cache memories in the network.

From Table II, we observe that for large cache memories, a smart cache assignment increases the capacity from $C_{\{1\}} + \frac{M}{KN}$ to $\frac{1}{K} \sum_{k=1}^{K} C_{\{k\}} + \frac{M}{KN}$. So the weak channel of user 1 is no longer limiting in the delivery phase. The gain of additional cache memories is, however, only local, i.e., the capacity-memory tradeoff only grows as $\frac{M}{KN}$.

We remark that the results in this paper are not restricted to erasure BCs and hold for general memoryless degraded BCs.

## B. Main Contributions and Implications

The main contributions of this paper are as follows.

* **New coding schemes:** We propose two new joint cache-channel coding schemes for degraded broadcast networks with heterogeneous cache sizes: superposition piggyback coding and generalized coded caching. In superposition piggyback coding, we assume a single cache memory at the weakest receiver and our delivery scheme loads (piggybacks) the information that is intended for stronger receivers and cached at weakest receiver onto the information that is communicated to this weakest receiver.<fnref n="2" /> When the rate of the piggybacked information is modest, the decoding at the strong receivers can be done without harming the performance at the weak receivers. The communication to the stronger receivers can thus be viewed as being almost for free. In some sense, piggyback coding provides the stronger receivers virtual access to the weak receivers' cache-memories as if these cache contents were locally present at the stronger receivers. All receivers gain virtual access to the weakest receiver's cache memory (the only cache memory in this case) and hence perfect caching gain is achieved.

In generalized coded caching, all receivers have cache memories, but weaker receivers have larger cache sizes than stronger receivers. We build the placement and delivery similar to the coded-caching scheme in [1]. However, by assigning larger cache memories to the weaker users, we create a new coding opportunity: piggyback coding. We piggyback information for the stronger receivers on the communication to the weaker receivers (without harming the weaker receivers' decodability). Using our coding scheme, the amount of the virtual cache memory that is provided to the stronger receivers

<footnote n="2">²Piggyback coding was proposed in a version without superposition coding in [21], [22]. This original version can be seen as a simplified version of the coding scheme in [34] (without binning) in the context of Slepian-Wolf coding over broadcast channels.</footnote>
increases compared to the original coded-caching scheme, resulting in an improved performance. We show that generalized coded caching is optimal for a specific cache assignment.

* A New Converse Result: We prove a general converse result for degraded BCs with arbitrary cache sizes at the receivers. Our result strictly improves over the existing converse results for degraded BCs in [22], [35], and at the time of submission,<fnref n="3" /> also over all previous converse results for the noise-free bit-pipe model [1], [10]–[12].

* Global Capacity-Memory Tradeoff: We study the problem of cache assignment on cache-aided noisy broadcast networks, and derive new upper and lower bounds on the global capacity-memory tradeoff, i.e., on the largest rate that is achievable under an optimized cache assignment. The bounds match when the total available cache budget is small or large. For a small total cache budget M, a perfect global caching gain is achievable. For larger cache budgets M, the caching gain diminishes as M increases. Finally for M larger than a certain threshold, only a local caching gain is possible; i.e., the performance corresponds to a system where all receivers store the same content and no coded delivery is possible. In this case, the global capacity-memory tradeoff grows as $\frac{M}{K \cdot N}$, where K denotes the number of receivers. Finally, we demonstrate numerically that the popular approach of assigning equal cache sizes to all receivers is suboptimal over Gaussian and erasure BCs. We further prove this analytically for erasure BCs in the small cache size regime.

## C. Notation

Random variables are denoted by uppercase letters, e.g. $\mathcal{A}$, their alphabets by matching calligraphic font, e.g. $\mathcal{A}$, and elements of an alphabet by lowercase letters, e.g. $a \in \mathcal{A}$. We also use uppercase letters for deterministic quantities like rate $R$, capacity $C$, number of users $K$, cache size $M$, and number of files in the library $N$. Vectors are identified by bold font symbols, e.g., **a**. We use the shorthand notation $A^n$ for the sequence $A_1, \dots, A_n$ where $n$ is an integer. The Cartesian product of $\mathcal{A}$ and $\mathcal{A}'$ is $\mathcal{A} \times \mathcal{A}'$, and the $n$-fold Cartesian product of $\mathcal{A}$ is $\mathcal{A}^n$. Further, $|\mathcal{A}|$ denotes the cardinality of $\mathcal{A}$. The notation $(a)^+$, for $a \in \mathbb{R}$, refers to $\max(0, a)$.

We will be using the abbreviation i.i.d. for independent and identically distributed.

For indices $w_1$ and $w_2$ taking value in $\{1, \dots, \lceil 2^{\ell_1} \rceil\}$ and $\{1, \dots, \lceil 2^{\ell_2} \rceil\}$, respectively, we define the generalized XOR as the index in $\{1, \dots, \lceil 2^{\ell_{\max}} \rceil\}$ that corresponds to the componentwise XOR of the length-$\ell_{\max}$ binary representations of $w_1$ and $w_2$, where $\ell_{\max} := \max\{\ell_1, \ell_2\}$. We denote the generalized XOR of $w_1$ and $w_2$ by

$$w_1 \oplus w_2.$$

## D. Outline

The remainder of the paper is organized as follows. Section II describes the problem setup. Section III summarizes known results for the scenario where there is no cache memory in the network. The main results of this paper are described in Sections IV–VI. Section VII specializes these results to the examples of erasure and Gaussian BCs, and to the noise-free bit-pipe model. The paper is concluded in Section VIII.

## II. PROBLEM DEFINITION

Consider a network with a transmitter and receivers $1, \dots, K$. The transmitter has access to a library with $N$ independent messages, $W_1, \dots, W_N$, each distributed uniformly over the set $\{1, \dots, \lceil 2^{nR} \rceil\}$. Here, $R \ge 0$ denotes the rate of transmission and $n$ is the transmission blocklength. We assume that $N \ge K$.

Each receiver $k \in \mathcal{K} := \{1, \dots, K\}$ is equipped with a cache of size $nM_k$ bits, where we have $M_k \ge 0$. The sizes of the cache memories thus scale linearly in the blocklength $n$. Communication takes place in two phases. First, in the placement phase, the transmitter chooses caching functions

$$g_k: \{1, \dots, \lceil 2^{nR} \rceil\}^N \rightarrow \{1, \dots, \lceil 2^{nM_k} \rceil\}, \quad k \in \mathcal{K}, \quad (1)$$

and places

$$V_k := g_k(W_1, \dots, W_N) \quad (2)$$

in receiver $k$'s cache. This phase takes place in a noiseless fashion.

The subsequent delivery phase takes place over a degraded BC [38] with finite input alphabet $\mathcal{X}$, finite output alphabets $\mathcal{Y}_1, \dots, \mathcal{Y}_K,^4$ and the channel transition law

$$\Gamma(y_1, \dots, y_K|x), \text{ for } x \in \mathcal{X}, y_1 \in \mathcal{Y}_1, \dots, y_K \in \mathcal{Y}_K \quad (3)$$

which decomposes as

$$\Gamma(y_1, \dots, y_K|x) = \Gamma_K(y_K|x) \cdot \Gamma_{K-1}(y_{K-1}|y_K) \cdots \Gamma_1(y_1|y_2). \quad (4)$$

Without loss of generality, this decomposition assumes that the $K$ users of the degraded BC are ordered from weakest to strongest.

At the beginning of the delivery phase, each receiver $k$ produces a random demand $D_k$ from the set $\mathcal{N} := \{1, \dots, N\}$ to indicate that it wishes to learn message $W_{D_k}$. The transmitter and all the receivers are informed about the entire demand vector

$$\mathbf{D} := (D_1, \dots, D_K).$$

Using this information, the transmitter forms the channel input sequence $X^n = (X_1, \dots, X_n)$ as

$$X^n = f(W_1, \dots, W_N, \mathbf{D}) \quad (5)$$

for some encoding function $f: \{1, \dots, \lceil 2^{nR} \rceil\}^N \times \mathcal{N}^K \rightarrow \mathcal{X}^n$.

Each receiver $k \in \mathcal{K}$ observes the outputs $Y_k^n := (Y_{k,1}, \dots, Y_{k,n})$ of the DMC $\Gamma(y_1, \dots, y_K|x)$ for inputs $X^n$. With the previously learned demand vector $\mathbf{D}$, its local cache

<footnote n="3">³The parallel work [36] slightly improves on this bound for the noise-free bit-pipe model (but does not generalize to noisy channels); see also [37].</footnote>

<footnote n="4">⁴The results of this paper readily extend to continuous alphabets. We will consider Gaussian BCs in Section VII-C.</footnote>
content $V_k$, and the channel outputs $Y_k^n$, it then produces its guess of the desired message $W_{D_k}$:

$$ \hat{W}_k := \varphi_k(Y_k^n, V_k, \mathbf{D}) \quad (6) $$

by means of a decoding function

$$ \varphi_k: \mathcal{Y}_k^n \times \{1, \dots, \lfloor 2^{nM_k} \rfloor\} \times \mathcal{N}^K \rightarrow \{1, \dots, \lfloor 2^{nR} \rfloor\}. \quad (7) $$

We define the probability of error as:

$$ \mathbf{P}_e^{(n)} := \mathbb{E}_{\mathbf{D}} [ \mathbf{P}_e^{(n)}(\mathbf{D}) ], \quad (8) $$

where

$$ \mathbf{P}_e^{(n)}(\mathbf{d}) := \mathbb{P} \left[ \bigcup_{k=1}^{K} \{ \hat{W}_k \neq W_{d_k} \} \middle| \mathbf{D} = \mathbf{d} \right], \quad (9) $$

and we assume that the random demand vector $\mathbf{D}$ has a uniform distribution on $\mathcal{N}^K$, i.e., $\mathbf{D} = \mathbf{d}$ with probability $1/|\mathcal{N}^K|$ for every $\mathbf{d} \in \mathcal{N}^K$. Notice that the probability of error cannot be reduced by using stochastic instead of deterministic caching, encoding, and/or decoding functions. It is thus without loss in optimality that in this paper we assume deterministic functions.

A rate-memory tuple $(R, \mathbf{M}_1, \dots, \mathbf{M}_K)$ is achievable if for any $\epsilon > 0$ there exists a sufficiently large blocklength $n$ and caching, encoding, and decoding functions as in (2), (5), and (6) so that $\mathbf{P}_e^{(n)} \le \epsilon$.

**Definition 1:** The capacity-memory tradeoff $C(\mathbf{M}_1, \dots, \mathbf{M}_K)$ is the largest rate $R$ for which the rate-memory tuple $(R, \mathbf{M}_1, \dots, \mathbf{M}_K)$ is achievable:

$$ C(\mathbf{M}_1, \dots, \mathbf{M}_K) := \sup\{R: (R, \mathbf{M}_1, \dots, \mathbf{M}_K) \text{ achievable}\}. $$

Our main goal in this paper is to optimize the cache assignment $(\mathbf{M}_1, \dots, \mathbf{M}_K)$ to attain the largest capacity-memory tradeoff $C(\mathbf{M}_1, \dots, \mathbf{M}_K)$ under the total cache constraint:

$$ \sum_{k=1}^{K} \mathbf{M}_k \le \mathbf{M}. \quad (10) $$

**Definition 2:** The global capacity-memory tradeoff $C^*(\mathbf{M})$ is defined as:

$$ C^*(\mathbf{M}) := \max_{\substack{\mathbf{M}_1, \dots, \mathbf{M}_K > 0: \\ \sum_{k=1}^K \mathbf{M}_k \le \mathbf{M}}} C(\mathbf{M}_1, \dots, \mathbf{M}_K). \quad (11) $$

**Remark 1:** The global capacity memory tradeoff depends on the BC law $\Gamma(y_1, \dots, y_K|x)$ only through its marginal conditional laws $\Gamma_1(y_1|x), \dots, \Gamma_K(y_K|x)$. All our results thus also apply to stochastically degraded BCs.

## A. Minimum Delivery Rate

Most previous works on caching that modeled the BC as a noise-free bit-pipe, e.g. [1], have fixed the size of the messages to $F$ bits and assumed that delivery takes place over $\rho \cdot F$ channel uses and that each receiver $k \in \mathcal{K}$ has $m_k F$ bits of cache memory. A delivery rate $\rho$ is then said to be achievable given normalized cache memory sizes $m_1, \dots, m_K$ if there exist caching, encoding, and decoding functions such that the probability of error in (8) tends to 0 as $F \to \infty$. In Section VII-B, we specialize our results to the noise-free

bit-pipe channel model and use the notion of delivery rate to compare our results with the state-of-the-art.

It is not difficult to see the following correspondence between the two definitions:

Message rate $R$ is achievable with $(\mathbf{M}_1, \dots, \mathbf{M}_K)$

⇔

Delivery rate $\rho = 1/R$ is achievable with $(m_1, \dots, m_K)$

where $m_1 = \frac{\mathbf{M}_1}{R}, \dots, m_K = \frac{\mathbf{M}_K}{R}$.

## III. PRELIMINARIES: CAPACITIES WITHOUT CACHE MEMORIES

In this section, we recall known results for our network in the special case when there are no cache memories:

$$ \mathbf{M}_1 = \dots = \mathbf{M}_K = 0. \quad (12) $$

These results will be utilized in the subsequent sections to state our results for cache-aided broadcast networks.

When (12) holds, it is known from [38], [39] that it is optimal to have the stronger receivers also decode messages intended to weaker receivers. This is done by the so-called superposition coding. Here, the worst case probability of error in (8) is attained for a demand vector $\mathbf{d}$ that has all different entries and the capacity-memory tradeoff $C(\mathbf{M}_1 = 0, \dots, \mathbf{M}_K = 0)$ is the largest symmetric rate $R$ with which $K$ independent messages can be sent reliably to the $K$ receivers. We thus have

$$ C(\mathbf{M}_1 = 0, \dots, \mathbf{M}_K = 0) = C_{\mathcal{K}} \quad (13) $$

where $C_{\mathcal{K}}$ is found from the capacity of degraded broadcast channels [38], [39]:

$$ C_{\mathcal{K}} := \max \min \left\{ I(U_1; Y_1), I(U_2; Y_2|U_1), \dots, I(U_{K-1}; Y_{K-1}|U_{K-2}), I(X; Y_K|U_{K-1}) \right\}. \quad (14) $$

The maximization in (14) is over all auxiliary random tuples $U_1, \dots, U_{K-1}, X, Y_1, \dots, Y_K$ that satisfy the following Markov chain:

$$ U_1 \to U_2 \to \dots \to U_{K-1} \to X \to (Y_1, \dots, Y_K) \quad (15a) $$

and the channel transition law:

$$ P_{Y_1 \dots Y_K | X} (y_1, \dots, y_K | x) = \Gamma(y_1, \dots, y_K | x). \quad (15b) $$

Denote the alphabet sets of the auxiliary random variables $U_1, \dots, U_K$ by $U_1, \dots, U_K$. Using the Fenchel-Eggleston-Carathéodory theorem [40, Appendix A], without loss of generality, one can restrict the cardinality of the sets as follows:

$$ |\mathcal{U}_k| \le |\mathcal{U}_{k+1}| + 2 \quad (16) $$

$$ |\mathcal{U}_{K-1}| \le |\mathcal{X}| + 2. \quad (17) $$

To present the results in this paper, we will also need the no-cache capacity region of the BC to a subset of
the receivers

$$
S := \{j_1, \dots, j_{|S|}\} \subseteq \mathcal{K}, \quad j_1 < \dots < j_{|S|}. \quad (18)
$$

The no-cache capacity region $C_S$ is naturally given by the set
of all nonnegative rate-tuples $(R_1, \dots, R_{|S|})$ for which there
exist random variables $U_1, \dots, U_{|S|-1}, X, Y_{j_1}, \dots, Y_{j_{|S|}}$ that
satisfy (15b) and form the Markov chain

$$
U_1 \to U_2 \to \dots \to U_{|S|-1} \to X \to (Y_{j_1}, \dots, Y_{j_{|S|}}), \quad (19)
$$

such that the following conditions hold:

$$
R_1 \le I(U_1; Y_{j_1}), \quad (20a)
$$

$$
R_k \le I(U_k; Y_{j_k} | U_{k-1}), \quad k \in \{2, \dots, |S|-1\}, \quad (20b)
$$

$$
R_{|S|} \le I(X; Y_{j_{|S|}} | U_{|S|-1}). \quad (20c)
$$

We denote by $C_S$ the largest symmetric rate $R \ge 0$ in $C_S$:

$$
C_S := \max_{R \ge 0} \{R : (R, \dots, R) \in C_S\}. \quad (21)
$$

Notice that $C_{\{k\}}$ is simply the point-to-point capacity to
receiver $k$ and we will abbreviate it as $C_k$.

By (20) and (21):

$$
C_S = \max \min \left\{ I(U_1; Y_{j_1}), I(U_2; Y_{j_2} | U_1), \dots, I(U_{|S|-1}; Y_{j_{|S|-1}} | U_{|S|-2}), I(X; Y_{j_{|S|}} | U_{|S|-1}) \right\}, \quad (22)
$$

where the maximization is over all random tuples $U_1, \dots, U_{|S|-1}, X, Y_{j_1}, \dots, Y_{j_{|S|}}$ that satisfy (15b) and (19).

IV. CODING SCHEMES AND LOWER BOUNDS ON
THE CAPACITY-MEMORY TRADEOFF

We present three lower bounds on the capacity-memory tradeoff along with coding schemes that achieve them. The first coding scheme and lower bound apply for general cache assignments $M_1, \dots, M_K$. The second and third ones apply only to specific cache assignments. Nevertheless, the proposed schemes are useful for a broad set of cache-assignments by time- (and memory-) sharing different coding schemes, or equivalently, taking convex combinations of different lower bounds.

A. The Local Caching Gain

The simplest way to use receiver cache memories is to store
the same information at each and every receiver. This allows
the receivers to retrieve this information locally, without trans-
mission over the BC. Global caching gains are not possible
under this caching strategy.

Applying the described simple caching strategy to only a
part of the cache memory that is of size $\Delta \ge 0$, while allowing
a smart use of the remaining memory, leads to the following
proposition, see also [41, Proposition 1].

Proposition 1 (Local caching gain): For all $\Delta > 0$ and $M_1, \dots, M_K \ge 0$:

$$
C(M_1 + \Delta, \dots, M_K + \Delta) \ge C(M_1, \dots, M_K) + \frac{\Delta}{N}. \quad (23)
$$

As a consequence, for all $\Delta_{\text{total}} > 0$ and $M \ge 0$:

$$
C^*(M + \Delta_{\text{total}}) \ge C^*(M) + \frac{\Delta_{\text{total}}}{K \cdot N}. \quad (24)
$$

<figure><img src="image_4.png" /><figcaption>Fig. 3. Superposition piggyback code construction $\mathcal{C}$ for $K = 4$ receivers. Recall that receiver 1 is the weakest. Each dot represents a codeword.</figcaption></figure>

We will see that this lower bound is tight in certain regimes
of operation, namely, when the cache budget is larger than a
threshold.

B. Superposition Piggyback Coding

We generalize the piggyback coding scheme of [22], [35],
that was specific to erasure BCs, to general degraded BCs
by introducing superposition coding. The scheme assigns all
the available cache memory to the weakest receiver, and uses
a layered superposition code for delivery, see Fig. 3. In this
superposition code:

* the lower-most layer encodes the part of message $W_{d_1}$ (intended for receiver 1) that is *not* stored in receiver 1's cache memory and the parts of messages $W_{d_2}, \dots, W_{d_K}$ that are stored at receiver 1.

* the k-th lowest layer, for $k \in \{2, \dots, K\}$, encodes the part of the message $W_{d_k}$ (intended for receiver $k$) that is not stored in the cache memory of receiver 1.

When decoding, each receiver $k \in \{2, \dots, K\}$, decodes the $k$ lowest layers using, e.g., a standard joint typicality decoder. In particular, receiver 1 (the weakest user) only decodes the lowest layer. This layer encodes a part of message $W_{d_1}$ that is desired at receiver 1 together with parts of messages $W_{d_2}, \dots, W_{d_K}$ that are not desired at receiver 1, but are locally available at its cache memory. As we will see, the cache content allows receiver 1 to achieve the same decoding performance as if the additional messages to the other receivers were not encoded in the lowest layer. In other words, we can encode information desired at the stronger receivers 2, \dots, K through the lowest superposition layer without affecting the decoding performance at the weakest receiver.

1) *Lower Bound on Capacity-Memory Tradeoff:* Let $(U_1^*, \dots, U_{K-1}^*, X^*)$ be a random $K$-tuple that achieves the Symmetric Capacity $C_K$, i.e., it is a solution to the optimization problem in (14). Define

$$
M_1^{\text{single}} := \frac{N}{K-1} (I(U_1^*; Y_2) - I(U_1^*; Y_1)). \quad (25)
$$

**Theorem 2:** Under the following cache assignment

$$
M_1 = M_1^{\text{single}} \qquad (26a)
$$

$$
M_2 = \dots = M_K = 0, \qquad (26b)
$$
we have

$$C(M_1, \dots, M_K) \geq C_K + \frac{M_1}{N}. \qquad (27)$$

**Remark 2:** Since the receivers can always choose to ignore their cache memories, and because the superposition piggyback coding scheme can be time- and memory-shared with a no-caching scheme, Theorem 2 remains valid for all

$$0 \leq M_1 \leq M_1^{\text{single}}, \qquad (28)$$

$$M_2, \dots, M_K \geq 0. \qquad (29)$$

We will see in Corollary 6 ahead that (27) holds with equality for all $0 \leq M_1 \leq M_1^{\text{single}}$ provided that $M_2 = \dots = M_K = 0$.

The RHS of (27) coincides with the capacity-memory tradeoff of a scenario where each and every receiver has access to receiver 1's cache memory. Superposition piggyback coding can thus be viewed as a coding technique that virtually provides all stronger receivers access to the weakest receiver's cache memory.

**2) Coding Scheme:** Let $(U_1^*, \dots, U_{K-1}^*, X^*)$ be a solution to the optimization problem in (14) so that the following inequality is strict:

$$I(U_1^*; Y_1) < I(U_1^*; Y_k), \quad k \in \{2, \dots, K\}. \qquad (30)$$

(If no such choice exists, Theorem 2 reduces to $C(M_1, \dots, M_K) \geq C_K$ and is trivial.)

Let $\epsilon > 0$ be arbitrary small, and define the rates

$$R^{(A)} := C_K - \epsilon, \qquad (31a)$$

$$R^{(B)} := \frac{1}{K-1} (I(U_1^*; Y_2) - I(U_1^*; Y_1)). \qquad (31b)$$

The RHS of (31b) is positive by (30). Split each message $W_d$, $d \in \{1, \dots, N\}$, into two parts:

$$W_d = (W_d^{(A)}, W_d^{(B)}),$$

where $W_d^{(A)}$ and $W_d^{(B)}$ are of rates $R^{(A)}$ and $R^{(B)}$, and thus the total message rate is

$$R = R^{(A)} + R^{(B)}. \qquad (32)$$

**Placement Phase:** Store $W_1^{(B)}, \dots, W_N^{(B)}$ in the cache memory of receiver 1. This is possible by (26a) and the definition of $M_1^{\text{single}}$ in (28).

**Delivery Phase:** For the transmission in the delivery phase, construct a K-level superposition code $C$ with a cloud center of rate $R^{(A)} + (K-1)R^{(B)}$ and satellites of rates $R^{(A)}$ in levels 2, ..., K. For the code construction, use a probability distribution

$$P_{U_1^*} \cdot P_{U_2^*|U_1^*} \cdots P_{U_{K-1}^*|U_{K-2}^*} \cdot P_{X^*|U_{K-1}^*}$$

that achieves $C_K$.

It will be convenient to arrange the codewords in the cloud center in an array with $\lfloor 2^{nR^{(A)}} \rfloor$ columns and $(\lfloor 2^{nR^{(B)}} \rfloor)^{K-1}$ rows. The columns are used to encode message $W_{d_1}^{(A)}$ and the rows to encode the message tuple

$$\mathbf{W}^{(B)} := (W_{d_2}^{(B)}, \dots, W_{d_{K-1}}^{(B)}, W_{d_K}^{(B)}). \qquad (33)$$

The k-th level satellite is used to encode message $W_{d_k}^{(A)}$, for $k \in \{2, \dots, K\}$. See Figure 3 for an illustration of the code construction.

Let $u_1^n(w_1, \text{column}, w_1, \text{row})$ denote the cloud-center codeword of $C$ in column $w_1, \text{column}$ and row $w_1, \text{row}$. Similarly, let $x^n(w_1, \text{column}, w_1, \text{row}; w_2; w_3; \dots; w_K)$ denote the level-K satellite codeword of $C$ that corresponds to the cloud center codeword $u_1^n(w_1, \text{column}, w_1, \text{row})$ and to the $w_2$-th, $w_3$-th, $w_4$-th, etc. satellite codewords in levels 2, 3, 4, ...

The transmitter chooses and sends the codeword

$$x^n(W_{d_1}^{(A)}, \mathbf{W}^{(B)}; W_{d_2}^{(A)}; W_{d_3}^{(A)}; \dots; W_{d_K}^{(A)})$$

over the channel.

**Decoding:** Receiver $k \in \{2, \dots, K\}$, decodes all messages in levels 1, ..., k. Recall that its desired message parts $W_{d_1}^{(A)}$ and $W_{d_2}^{(B)}$ are encoded in levels k and 1 (i.e., the cloud center), respectively.

Receiver 1 only has to decode $W_{d_1}^{(A)}$, because it can retrieve $W_{d_1}^{(B)}$ directly from its cache memory. To decode $W_{d_1}^{(A)}$ it performs the following steps:

1) It retrieves the message-tuple $\mathbf{W}^{(B)}$ from its cache memory.

2) It forms the subcodebook $C'(\mathbf{W}^{(B)}) \subseteq C$ that contains all level-1 codewords that are “compatible” with the retrieved tuple $\mathbf{W}^{(B)}$:

$$C'(\mathbf{W}^{(B)}) := \{u_1^n(w, \mathbf{W}^{(B)})\}_{w=1}^{\lfloor 2^{nR^{(A)}} \rfloor}. \qquad (34)$$

Figure 3 illustrates such a subcodebook in red.

3) It decodes its desired message $W_{d_1}^{(A)}$ using an optimal decoding rule for the subcodebook $C'(\mathbf{W}^{(B)})$.

**Error Analysis:** Each receiver $k \in \{2, \dots, K\}$ reliably decodes messages $(W_{d_1}^{(A)}, W_{d_2}^{(B)}, \dots, W_{d_K}^{(B)})$ as well as $(W_{d_2}^{(A)}, \dots, W_{d_K}^{(A)}$ if the following inequalities hold:

$$kR^{(A)} + (K-1) \cdot R^{(B)} < I(U_k^*; Y_k), \qquad (35a)$$

$$(k - \ell) \cdot R^{(A)} < I(U_k^*; Y_k | U_\ell^*), \quad \ell \in \{1, \dots, k-1\}, \qquad (35b)$$

where we define $U_k^* = X^*$. One can verify that for degraded BCs the choice of $R^{(A)}$ and $R^{(B)}$ in (31) satisfies the constraints in (35). In fact, by (31) and the degradedness of the BC, we have for all $j \in \{2, \dots, k\}$

$$R^{(A)} \leq I(U_j^*; Y_j | U_{j-1}^*) - \epsilon < I(U_j^*; Y_k | U_{j-1}^*) - \epsilon \qquad (36)$$

$$R^{(A)} + (K-1) \cdot R^{(B)} \leq I(U_1^*; Y_2) - \epsilon < I(U_1^*; Y_k). \qquad (37)$$

Summing (37) over all $j \in \{2, \dots, k\}$, adding (36), and using the chain rule of mutual information and the Markov chain $U_1^* \to U_2^* \to \dots \to U_K^*$, establishes (35a). Similarly, summing up (36) for $j \in \{\ell, \dots, k\}$ establishes (35b).

Finally, receiver 1 can decode with arbitrarily small probability of error because subcodebook $C'(\mathbf{W}^{(B)})$ contains $\lfloor 2^{nR^{(A)}} \rfloor$ codewords that are generated i.i.d. according to $P_{U_1^*}$ and because

$$R^{(A)} < I(U_1^*; Y_1).$$

Letting $\epsilon \to 0$ proves achievability of Theorem 2.
### C. Generalized Coded-Caching

We generalize the coded-caching scheme of [1] to degraded BCs and to unequal cache sizes. In [1], the authors have proposed a scheme for error free channels, parametrized by an integer $t \in [1:K-1]$, that can simultaneously communicate to groups of $t+1$ users and hence offer global caching gains. In (noisy) broadcast channels, users have different channel statistics. The main idea in this section is to assign a larger cache memory at weaker receivers to balance the worse channel condition and to send generalized XOR-messages to groups of $t+1$ receivers at a time. Our cache assignment and delivery scheme are designed such that, in the transmission to any group of $t+1$ receivers, each of the involved receivers is served at a rate close to its capacity. This is possible because each receiver has stored all other transmitted messages in its cache memory, and can exploit this knowledge in the decoding. Notice that if separate cache-channel coding was applied, the rate to each receiver was limited by the worst channel capacity.

1) *Lower Bound on Capacity-Memory Tradeoff:* We will need the following definitions. Let for each $t \in \mathcal{K}$

$$ \mathcal{G}_1^{(t)}, \dots, \mathcal{G}_{\binom{K}{t}}^{(t)} \qquad (38a) $$

denote all unordered size-$t$ subsets of $\mathcal{K}$. Define their complements as:

$$ \mathcal{G}_{\ell}^{(t),c} := \mathcal{K} \setminus \mathcal{G}_{\ell}^{(t)}, \quad \ell \in \{1, \dots, \binom{K}{t}\}. \qquad (38b) $$

For any given distribution $P_X$ and $t = 1, \dots, K-1$, define the cache sizes and rates:

$$ \mathbf{M}_k^{(t)} = \mathbf{N} \cdot \frac{\sum_{\ell: k \in \mathcal{G}_{\ell}^{(t)}} \prod_{k' \in \mathcal{G}_{\ell}^{(t),c}} I(X; Y_{k'})}{\sum_{j=1}^{\binom{K}{t+1}} \prod_{k' \in \mathcal{G}_{j}^{(t+1),c}} I(X; Y_{k'})}, \qquad (39) $$

$$ R^{(t)} = \frac{\sum_{\ell=1}^{\binom{K}{t}} \prod_{k' \in \mathcal{G}_{\ell}^{(t),c}} I(X; Y_{k'})}{\sum_{j=1}^{\binom{K}{t+1}} \prod_{k' \in \mathcal{G}_{j}^{(t+1),c}} I(X; Y_{k'})}. \qquad (40) $$

Note that when $t = K-1$ the denominators of (39) and (40) are equal to 1, and hence we have

$$ \mathbf{M}_k^{(K-1)} = \mathbf{N} \sum_{\ell \in \mathcal{K} \setminus \{k\}} I(X; Y_\ell), \qquad (41) $$

$$ R^{(K-1)} = \sum_{\ell} I(X; Y_{\ell}). \qquad (42) $$

Observe that for any given $P_X$, we have

$$ \mathbf{M}_1^{(t)} \ge \mathbf{M}_2^{(t)} \ge \dots \ge \mathbf{M}_K^{(t)}, \quad t \in \{1, \dots, K-1\}, \qquad (43) $$

so a larger cache memory is assigned the weaker a receiver is. The choices of $\mathbf{M}^{(t)}$ in (39) and $R^{(t)}$ in (40) become clear in the description of the coding scheme. In particular, these choices ensure decodability of (sub-)messages in different phases of the coding scheme.

**Theorem 3:** Fix a $t \in \{1, \dots, K-1\}$ and an input distribution $P_X$, and consider the corresponding cache assignment in (39). Then,

$$ \mathbf{C}(\mathbf{M}_1^{(t)}, \dots, \mathbf{M}_K^{(t)}) \ge R^{(t)}, \qquad (44) $$

where $\mathbf{M}_1^{(t)}, \dots, \mathbf{M}_K^{(t)}$ and $R^{(t)}$ are calculated from $P_X$ as described in (39) and (40).

As we will see in Corollary 7, the inequality in (44) holds with equality for $t = K-1$.

We first explain the scheme for the special case of two users.

2) *Coding Scheme in the Special Case $K=2$ and $t=1$: Fix an input distribution $P_X$ and a small $\epsilon > 0$, and define the rates*

$$ R^{(A)} = I(X; Y_1) - \epsilon, \qquad (45) $$

$$ R^{(B)} = I(X; Y_2) - \epsilon. \qquad (46) $$

Notice that by the degradedness of the BC:

$$ R^{(B)} \ge R^{(A)}. \qquad (47) $$

Fix a blocklength $n$ and generate a random codebook

$$ \mathcal{C} := \{x^n(j)\}_{j=1}^{[2^n R^{(B)}]} \qquad (48) $$

by choosing all entries i.i.d. according to $P_X$. The codebook $\mathcal{C}$ is revealed to all terminals of the network.

Allocate cache memories

$$ \mathbf{M}_1 = \mathbf{N} \cdot R^{(B)} = \mathbf{N} \cdot (I(X; Y_2) - \epsilon), \qquad (49a) $$

$$ \mathbf{M}_2 = \mathbf{N} \cdot R^{(A)} = \mathbf{N} \cdot (I(X; Y_1) - \epsilon), \qquad (49b) $$

to receivers 1 and 2, respectively.

Split each message $W_d$, for $d \in \{1, \dots, N\}$, into two parts:

$$ W_d = (W_d^{(A)}, W_d^{(B)}), $$

which are of rates $R^{(A)}$ and $R^{(B)}$, respectively.

In the caching phase, the transmitter stores messages

$$ W_1^{(B)}, \dots, W_N^{(B)} $$

in receiver 1's cache memory and messages

$$ W_1^{(A)}, \dots, W_N^{(A)} $$

in receiver 2's cache memory. This is possible given the cache assignment in (49).

In the delivery phase the transmitter uses codebook $\mathcal{C}$ to send the XOR message$^5$

$$ W_{d_1}^{(A)} \oplus W_{d_2}^{(B)} \qquad (50) $$

to both receivers using the codeword

$$ x^n \left( W_{d_1}^{(A)} \oplus W_{d_2}^{(B)} \right). $$

To guess $W_{d_2}^{(B)}$, Receiver 2 decodes the XOR-message and XORs the decoded message with $W_{d_1}^{(A)}$, which it has stored in its cache memory. The remaining part of its desired message, $W_{d_2}^{(A)}$, is retrieved from its cache memory.

Receiver 1 performs joint cache-channel decoding where it can exploit that it has more cache memory than receiver 2. Specifically, it retrieves $W_{d_2}^{(B)}$ from its cache memory, and

<footnote>$^5$Recall that in Section I-C we defined the generalized XOR operation $\oplus$ as the component-wise XOR over the binary representations of two messages zero-padded to the length of the longer one.</footnote>
extracts a subcodebook $C'(W_{d_2}^{(B)}) \subseteq C$ containing all code-words that are compatible with $W_{d_2}^{(B)}$:

$$C'(W_{d_2}^{(B)}) := \{x^n(w \oplus W_{d_2}^{(B)})\}_{w=1}^{2^{nR^{(A)}}} \quad (51)$$

Note that subcodebook $C'(W_{d_2}^{(B)})$ is of rate $R^{(A)}$ which is smaller than the rate $R^{(B)}$ of the original codebook $C$.

To guess $W_{d_1}^{(A)}$, receiver 1 decodes the XOR message in (50) using an optimal decoding rule for this subcodebook $C'(W_{d_2}^{(B)})$, and XORs the decoded message with $W_{d_2}^{(B)}$, which it has stored in its cache memory. The remaining part of its desired message, $W_{d_1}^{(B)}$, is retrieved from its cache memory.

With this scheme, both receivers correctly recover their desired messages $W_{d_1}$ and $W_{d_2}$ whenever they successfully decode the XOR-message in (50). Since the rate $R^{(B)}$ of the original codebook $C$ satisfies

$$R^{(B)} < I(X; Y_2), \quad (52)$$

and the rate of $R^{(A)}$ of the subcodebook $C'(W_{d_2}^{(B)})$ satisfies

$$R^{(A)} < I(X; Y_1), \quad (53)$$

the probability of decoding error at both receivers tends to 0 as the blocklength $n$ tends to infinity.

Letting $\epsilon \to 0$, we conclude that for $K = 2$ the rate-memory triple

$$\begin{aligned}
R &= I(X; Y_1) + I(X; Y_2), \\
M_1 &= I(X; Y_2), \\
M_2 &= I(X; Y_1)
\end{aligned}$$

is achievable.

Notice that the weaker receiver 1 is assigned a larger cache memory than the stronger receiver 2:

$$M_1 \ge M_2. \quad (54)$$

The described scheme can also be applied with a uniform cache assignment $M_1 = M_2 = N \cdot R^{(A)}$, however at the cost of a decreased achievable rate $R = 2 \cdot I(X; Y_1)$. In fact, assigning a larger cache memory $M_1$ to receiver 1 allows to transmit more information to receiver 2 during the communication to receiver 1.

### 3) General Coding Scheme
Fix a positive integer $t \in \{1, \dots, K-1\}$. This parameter is an indicator of the number of receivers that cache each part of a file. Similar to the work of [1], this caching scheme ensures that $t+1$ receivers can be simultaneously served in each transmission during the delivery phase. Pick a small number $\epsilon > 0$ and an input distribution $P_X$. Consider the cache assignment in (39), where mutual informations are calculated with respect to $P_X$.

Split each message $W_d$ into $\binom{K}{t}$ independent submessages:

$$W_d = \{ W_{d, \mathcal{G}_t^{(t)}} : \ell = 1, \dots, \binom{K}{t} \},$$

where each submessage $W_{d, \mathcal{G}_t^{(t)}}$ is of rate

$$R_{\mathcal{G}_t^{(t)}} := \frac{\prod_{k \in \mathcal{G}_t^{(t),c}} I(X; Y_k)}{\sum_{j=1}^{\binom{K}{t+1}} \prod_{k \in \mathcal{G}_j^{(t+1),c}} I(X; Y_k)} - \epsilon. \quad (55)$$

The total message rate is thus

$$R = \sum_{\ell=1}^{\binom{K}{t}} R_{\mathcal{G}_\ell^{(\ell)}} = \frac{\sum_{\ell=1}^{\binom{K}{t}} \prod_{k \in \mathcal{G}_\ell^{(\ell),c}} I(X; Y_k)}{\sum_{j=1}^{\binom{K}{t+1}} \prod_{k \in \mathcal{G}_j^{(t+1),c}} I(X; Y_k)} - \binom{K}{t} \epsilon. \quad (56)$$

**Placement Phase:** For each $d \in \{1, \dots, N\}$, store the tuple

$$\{W_{d, \mathcal{G}_t^{(t)}} : k \in \mathcal{G}_t^{(t)}\} \quad (57)$$

in the cache memory of receiver $k \in K$. This is possible by (55) and the cache assignment in (39).

**Delivery Phase:** Transmission in the delivery phase takes place in $\binom{K}{t+1}$ subphases.

We define the subphase $j \in \{1, \dots, \binom{K}{t+1}\}$ to be of length

$$n_j := \left\lfloor \frac{\prod_{k \in \mathcal{G}_j^{(t+1),c}} I(X; Y_k)}{\sum_{j'=1}^{\binom{K}{t+1}} \prod_{k \in \mathcal{G}_{j'}^{(t+1),c}} I(X; Y_k)} \right\rfloor, \quad (58)$$

and to transmit messages

$$\{W_{d_k, \mathcal{G}_j^{(t+1)} \setminus \{k\}}\}_{k \in \mathcal{G}_j^{(t+1)}} \quad (59)$$

to the intended receivers in $\mathcal{G}_j^{(t+1)}$. For this purpose, the transmitter creates the generalized XOR message

$$W_{\text{XOR}, \mathcal{G}_j^{(t+1)}} = \bigoplus_{k \in \mathcal{G}_j^{(t+1)}} W_{d_k, \mathcal{G}_{j+1}^{(t)} \setminus \{k\}}, \quad (60)$$

which is of rate

$$\begin{aligned}
R_{\text{XOR}, \mathcal{G}_j^{(t+1)}} &:= \max_{\mathcal{G}_t^{(t)} \subseteq \mathcal{G}_j^{(t+1)}} R_{\mathcal{G}_t^{(t)}} \\
&= \left( \max_{k' \in \mathcal{G}_j^{(t+1)}} I(X; Y_{k'}) \right) \cdot \frac{\prod_{k \in \mathcal{G}_j^{(t+1),c}} I(X; Y_k)}{\sum_{j=1}^{\binom{K}{t+1}} \prod_{k \in \mathcal{G}_j^{(t+1),c}} I(X; Y_k)} - \epsilon,
\end{aligned}$$

and generates a codebook

$$C_j = \{ x_j^{n_j}(w) : w = 1, \dots, \binom{2^{n_R}}{K} \}, \quad (61)$$

by drawing all entries i.i.d. according to $P_X$. The transmitter then sends the codeword

$$x_j^{n_j} \left( W_{\text{XOR}, \mathcal{G}_j^{(t+1)}} \right) \quad (62)$$

over the channel.

We now describe the decoding. Each receiver $k \in K$ can retrieve messages

$$\{ W_{d_k, \mathcal{G}_t^{(t)}} : k \in \mathcal{G}_t^{(t)} \} \quad (63)$$

directly from its cache, see (57), and thus only needs to decode messages

$$\{ W_{d_k, \mathcal{G}_t^{(t)}} : k \notin \mathcal{G}_t^{(t)} \}. \quad (64)$$
For each $j \in \{1, \dots, \binom{K}{t+1}\}$ and $k \in G_j^{(t+1)}$, receiver $k$ decodes message $W_{d_k, G_j^{(t+1)} \setminus \{k\}}$ from its subphase-$j$ outputs

$$Y_{k,j}^{n_j} := \left( Y_{k, \sum_{j'=1}^{j-1} n_{j'} + 1}, \dots, Y_{k, \sum_{j'=1}^{j} n_{j'}} \right).$$

Specifically, with the messages stored in its cache memory, it forms the XOR message

$$W_{\text{XOR},j,k} := \overline{\bigoplus}_{k' \in G_j^{(t+1)} \setminus \{k\}} W_{d_{k'}, G_j^{(t+1)} \setminus \{k'\}}, \quad (65)$$

and it extracts a subcodebook $C'_{j,k}(W_{\text{XOR},j,k})$ from $C_j$ that consists of all codewords that are compatible with $W_{\text{XOR},j,k}$:

$$C'_{j,k}(W_{\text{XOR},j,k}) := \{x_j^{n_j} (w \overline{\oplus} W_{\text{XOR},j,k})\}_{w=1}^{\left\lfloor 2^{\frac{n_R}{|G_j^{(t+1)}|}} \right\rfloor}.$$

It then decodes the XOR message $W_{\text{XOR},G_j^{(t+1)}}$ by applying an optimal decoding rule for subcodebook $C'_{j,k}(W_{\text{XOR},j,k})$ to the subphase-$j$ outputs $Y_{k,j}^{n_j}$, and XORs the resulting message $\hat{W}_{\text{XOR},G_j^{(t+1)}}$ with $W_{\text{XOR},j,k}$ to obtain

$$\hat{W}_{d_k, G_j^{(t+1)} \setminus \{k\}} = \hat{W}_{\text{XOR}, G_j^{(t+1)} \overline{\oplus} W_{\text{XOR},j,k}}. \quad (66)$$

After the last sub-phase $\binom{K}{t+1}$, each receiver $k \in K$ has decoded all its missing messages in (64), and can thus recover $W_{d_k}$.

**Error Analysis:** If each XOR-message $W_{\text{XOR},G_j^{(t+1)}}$ is decoded correctly by all its intended receivers in $G_j^{(t+1)}$, $j = 1, \dots, \binom{K}{t+1}$, then all receivers $1, \dots, K$ recover their desired messages $W_{d_1}, \dots, W_{d_K}$.

The probability that receiver $k \in G_j^{(t+1)}$ finds an incorrect value for the XOR message $W_{\text{XOR},G_j^{(t+1)}}$ tends to 0 as $n$ (and thus $n_j) \to \infty$ because the rate of the subcodebook $C'_{j,k}$ satisfies

$$\lim_{n \to \infty} \frac{n}{n_j} \cdot R_{G_j^{(t+1)} \setminus \{k\}} < I(X; Y_k),$$

see (55) and (58). Letting then $\epsilon \to 0$, establishes Theorem 3.

## V. UPPER BOUNDS AND EXACT RESULTS ON THE CAPACITY-MEMORY TRADEOFF

We present a general upper bound on the capacity-memory tradeoff. We further show that the upper bound matches the lower bounds derived in the previous section in certain regimes of cache sizes. In these regimes, we can thus characterize the exact capacity-memory tradeoff.

### A. Upper Bounds

Our upper bound is formulated in terms of the following parameters. Consider any set $S \subseteq K$ and represent it by $S = \{j_1, \dots, j_{|S|}\}$ as in (18). Define

$$\alpha_{S,1}^* := \frac{M_{j_1}}{N} \quad (67a)$$

and for $k \in \{2, \dots, |S|\}$:

$$\alpha_{S,k}^* := \min \left\{ \frac{\sum_{i=1}^{k} M_{j_i}}{N - k + 1}, \frac{1}{|S| - k + 1} \left( \frac{|S|}{N} \sum_{i=1}^{|S|} M_{j_i} - \sum_{i=1}^{k-1} \alpha_{S,i}^* \right) \right\}. \quad (67b)$$

**Theorem 4:** There exist random variables $X, Y_1, \dots, Y_K$ and for every receiver set $S$ as in (18) random variables $\{U_{S,1}, \dots, U_{S,|S|-1}\}$ so that the channel law (15b) and the following Markov chain hold:

$$U_{S,1} \to U_{S,2} \to \dots \to U_{S,|S|-1} \to X \to (Y_1, \dots, Y_K), \quad (68)$$

and so that for each $S$ we have

$$C(M_1, \dots, M_K) \le I(U_{S,1}; Y_{j_1}) + \alpha_{S,1}^*, \quad (69a)$$

$$C(M_1, \dots, M_K) \le I(U_{S,k}; Y_{j_k} | U_{S,k-1}) + \alpha_{S,k}^*, \quad \forall k \in \{2, \dots, |S| - 1\}, \quad (69b)$$

$$C(M_1, \dots, M_K) \le I(X; Y_{j_{|S|}} | U_{S,|S|-1}) + \alpha_{S,|S|}^*, \quad (69c)$$

*Proof:* See Appendix A.

<figure><img src="image_5.png" /></figure>

Without cache memories, $M_1 = \dots = M_K = 0$, the parameters $\alpha_{S,1}^*, \dots, \alpha_{S,|S|}^*$ equal 0 for all $S \subseteq \{1, \dots, K\}$, and hence the upper bound in Theorem 4 recovers the exact capacity-memory tradeoff $C_K$ in (14).

The upper bound in Theorem 4 is asymmetric in the different cache sizes $M_1, M_2, \dots, M_K$, because the parameters $\alpha_{S,j_i}^*$ are not symmetric. In fact, increasing the cache memories at weaker receivers generally increases the upper bound more than increasing the cache memories at stronger receivers.

The upper bound in Theorem 4 is weakened if the constraints in (69) are ignored for certain receiver sets $S$, or if in these constraints the input/output random variables $X, Y_{j_1}, \dots, Y_{j_{|S|}}$ are allowed to depend on the receiver set $S$. Using the latter relaxation, Theorem 4 results in the following corollary.

**Corollary 5:** Given cache sizes $M_1, \dots, M_K \ge 0$, rate $R \ge 0$ is achievable only if for every receiver set $S \subseteq K$:

$$((R - \alpha_{S,1}^*)^+, (R - \alpha_{S,2}^*)^+, \dots, (R - \alpha_{S,|S|}^*)^+) \in C_S, \quad (70)$$

where $C_S$ denotes the no-cache capacity region to the receivers in $S$ (assuming no cache memories at the receivers and ignoring all receivers in $K \setminus S$).

*Proof:* If $R$ is achievable, then Theorem 4 ensures that for every set $S = \{j_1, \dots, j_{|S|}\}$, there exists a set of random variables $(U_1, U_2, \dots, U_{|S|-1}, X, Y_{j_1}, \dots, Y_{j_{|S|}})$ that satisfy (19)–(20) and hence (70) holds for every set $S$. Note that this does not necessarily hold in the reverse direction, meaning that if (70) holds for every $S$ it is not clear if the conditions of Theorem 4 are satisfied in general. This is because the choice of random variable $X$ that is found from (70) (for every $S$) may implicitly depend on $S$ while this is not permissible in condition (68) in Theorem 4.

<figure><img src="image_6.png" /></figure>
**Remark 3:** The upper bounds of Theorem 4 and Corollary 5 are relaxed when each $\alpha_{S,k}^*$ is replaced by $\tilde{\alpha}_{S,k}$, defined below:

$$ \tilde{\alpha}_{S,1} := \frac{M_{j_1}}{N}, \qquad (71a) $$

$$ \tilde{\alpha}_{S,k} := \frac{|S| \cdot \sum_{i=1}^{|S|} M_{j_i} - M_{j_1}}{(|S| - 1)N}, \quad k \in \{2, \dots, |S|\}. \qquad (71b) $$

The same holds if each $\alpha_{S,k}^*$ is replaced by

$$ \alpha'_{S,k} := \frac{\sum_{i=1}^{|S|} M_{j_i}}{N}. \qquad (72) $$

In particular, Corollary 5 recovers the previous upper bound in [22, Theorem 9] and [35, Theorem 1] if $\alpha_{S,k}^*$ is replaced by $\alpha'_{S,k}$.

*Proof:* The proof requires a close inspection of the proof of Theorem 4 in Appendix A. See Appendix D. ■

## B. Exact Results

By comparing the new upper bounds with the three lower bounds presented in Section IV, the exact expression for $C(M_1, \dots, M_K)$ can be obtained in some special cases. For example, as the following corollary states, the lower bound achieved by superposition piggyback coding matches the upper bound when only receiver 1 has a cache memory and this cache memory is small.

**Corollary 6:** Under a cache assignment satisfying

$$ 0 \le M_1 \le M_1^{\text{single}} \quad \text{and} \quad M_2 = \dots = M_K = 0, \qquad (73) $$

the capacity-memory tradeoff is

$$ C(M_1, 0, \dots, 0) = C_K + \frac{M_1}{N}. $$

*Proof:* Achievability follows by Theorem 2 (see also Remark 2) and the converse follows by Corollary 5, where it suffices to consider only the set $S = K$. In fact, under (73), $\alpha_{K,1}^* = \dots = \alpha_{K,K}^* = \frac{M_1}{N}$.

The next corollary states that the lower bound attained by generalized coded caching with parameter $t = K - 1$ matches the upper bound under the corresponding cache assignment in (41). Moreover, any extra cache memory that is uniformly distributed over the $K$ receivers only brings local caching gain.

**Proposition 7:** For each $k \in K$, let $M_k^{*(K-1)}$ be given by (41) when $P_X$ is chosen as a maximizer of

$$ C_{\text{Avg}} := \frac{1}{K} \cdot \max_{P_X} \left( \sum_{k=1}^{K} I(X; Y_k) \right). \qquad (74) $$

For any $\Delta \ge 0$, we have

$$ C(M_1^{*(K-1)} + \Delta, \dots, M_K^{*(K-1)} + \Delta) = C_{\text{Avg}} + \frac{\sum_{k=1}^{K} M_k^{*(K-1)}}{K \cdot N} + \frac{\Delta}{N}. \qquad (75) $$

*Proof:* See Appendix E. ■

## VI. BOUNDS ON THE GLOBAL CAPACITY-MEMORY TRADEOFF $C^*(M)$

The two preceding sections presented lower and upper bounds on the capacity-memory tradeoff for given cache assignments. In this section, we assume that a system designer is given a total cache budget $M \ge 0$ that it can arbitrarily distribute across users. We are thus interested in the largest capacity-memory tradeoff optimized over the cache assignment $M_1, \dots, M_K$ subject to a total cache budget $M_1 + M_2 + \dots + M_K \le M$. We introduced this quantity as the global capacity-memory tradeoff $C^*(M)$ in (11). This section presents lower and upper bounds on $C^*(M)$, for any value of $M$, as well as exact results for $C^*(M)$ when $M$ is below a certain threshold or above another threshold.

### A. Lower Bound

Proposition 1 and Theorems 2 and 3 readily yield a lower bound on $C^*(M)$, see (77). As we will see in Corollary 11 ahead, this lower bound holds with equality when the total cache size $M$ is small or large.

Let

$$ R^{(0)} := C_K, \quad M^{(0)} := 0, \qquad (76a) $$

and

$$ R^{\text{single}} := C_K + \frac{M^{\text{single}}}{N}, \quad M^{\text{single}} := M_1^{\text{single}}, \qquad (76b) $$

where $C_K$ is defined in (13) and $M_1^{\text{single}}$ is defined in (25). Also, for any given $P_X$, recall $M^{(t)}$ and $R^{(t)}$ from (39) and (40), and define for $t \in \{1, \dots, K-1\}$:

$$ M^{(t)} := \sum_{k=1}^{K} M_k^{(t)}. \qquad (76c) $$

We have proved the achievability of each pair by proposing a corresponding scheme. Consider two schemes achieving the memory-rate pairs $(M^{(t)}, R^{(t)})$ and $(M^{(t')}, R^{(t')})$. By time sharing between the two schemes, we can achieve all memory-rate pairs that lie on the line connecting $(M^{(t)}, R^{(t)})$ and $(M^{(t')}, R^{(t')})$. I.e., the upper-convex envelope of all these rate-memory pairs thus lower-bounds $C^*(M)$. This is formulated in Corollary 8 below.

**Corollary 8:** The global capacity-memory tradeoff is lower-bounded by:

$$ C^*(M) \ge \text{upp hull} \left\{ (R^{(0)}, M^{(0)}), (R^{\text{single}}, M^{\text{single}}), \bigcup_{P_X} \left\{ (R^{(1)}, M^{(1)}), \dots, (R^{(K-1)}, M^{(K-1)}) \right\} \right\}. \qquad (77) $$

Notice that for any $P_X$:

$$ M^{(0)} \le M^{\text{single}} \le M^{(1)} \le \dots \le M^{(K-1)} \qquad (78) $$

and

$$ R^{(0)} \le R^{\text{single}} \le R^{(1)} \le \dots \le R^{(K-1)}. \qquad (79) $$
## B. Upper Bounds

Theorem 4 directly yields the following upper bound on the global capacity-memory tradeoff.

**Corollary 9:** There exist random variables $X, Y_1, \dots, Y_K$ and for every receiver set $S$ as in (18) random variables $\{U_{S,1}, \dots, U_{S,|S|-1}\}$, such that (15b) and (68) hold, and such that for some $M_1, \dots, M_K \ge 0$ summing to $M$ and all $S$:

$$C^*(M) \le I(U_{S,1}; Y_{j_1}) + \alpha_{S,1}^*, \quad (80a)$$

$$C^*(M) \le I(U_{S,k}; Y_{j_k} | U_{S,k-1}) + \alpha_{S,k}^*, \quad k \in \{2, \dots, |S|-1\}, \quad (80b)$$

$$C^*(M) \le I(X; Y_{j_1|S} | U_{S,|S|-1}) + \alpha_{S,|S|}^*, \quad (80c)$$

where $\{\alpha_{S,k}^*\}$ are defined in (67).

Evaluating this bound numerically is cumbersome because for each possible subset $S$ the coefficients $\alpha_{S,1}^*, \dots, \alpha_{S,|S|}^*$ have to be computed and then the optimal choice of $U_{S,1}, \dots, U_{S,|S|-1}, X$ needs to be found in order to find the loosest upper bound in (80). To find upper bounds that have easier close-form expressions, we loosen the bound by either relaxing some of the constraints in (80); by replacing each parameter $\alpha_{S,k}^*$ in (80) by $\tilde{\alpha}_{S,k}$ or by $\alpha_{S,k}'$ (defined in (71) and (72)); and/or by allowing $X, Y_{j_1}, \dots, Y_{j_S}$ in (80) to depend on the set $S$. The following corollary presents such a simpler upper bound. Recall the definitions in (38).

**Corollary 10:** For each $t \in \mathcal{K}$:

$$C^*(M) \le \frac{1}{\binom{K}{t}} \sum_{\ell=1}^{K} C_{G_{\ell}^{(t)}} + \frac{t}{K} \cdot \frac{M}{N}. \quad (81)$$

*Proof:* Fix $t \in \mathcal{K}$. For each $\ell = 1, \dots, \binom{K}{t}$, specialize Corollary 5 to $S = G_{\ell}^{(t)}$ and relax it by replacing each parameter $\alpha_{G_{\ell}^{(t)},k}^*$ by $\alpha_{G_{\ell}^{(t)},k}'$ defined in (72). Since $\alpha_{G_{\ell}^{(t)},1}' = \dots = \alpha_{G_{\ell}^{(t)},t}'$, we obtain

$$C^*(M) \le C_{G_{\ell}^{(t)}} + \alpha_{G_{\ell}^{(t)},1}' = C_{G_{\ell}^{(t)}} + \frac{\sum_{i \in G_{\ell}^{(t)}} M_i}{N}. \quad (82)$$

Now, averaging (82) over all indices $\ell = 1, \dots, \binom{K}{t}$ and upper-bounding the sum $M_1 + \dots + M_K$ by $M$ yields the desired result. ■

## C. Exact Results

Lower and upper bounds on $C^*(M)$ presented above match for small and large total cache sizes $M$. Corollary 11 below states this more formally. Recall $M^{\text{single}}$ from (25) and define $M^L$ as follows:

$$M^L = N \cdot (K - 1) \cdot K \cdot C_{\text{avg}} \quad (83)$$

where $C_{\text{avg}}$ is defined in (74).

**Corollary 11:** For any positive total cache size $M \le M^{\text{single}}$:

$$C^*(M) = C_{\mathcal{K}} + \frac{M}{N}, \quad 0 \le M \le M^{\text{single}}, \quad (84)$$

and for any $M \ge M^L$:

$$C^*(M) = K C_{\text{avg}} + \frac{1}{K} \cdot \frac{M - M^L}{N}, \quad M \ge M^L. \quad (85)$$

Before presenting the proof of this Corollary, let us briefly discuss the implications: For small cache sizes, the entire cache memory should be assigned to the weakest receiver and the superposition piggyback coding scheme of Section IV-B is optimal. For large total cache sizes $M$, a careful assignment of the available cache memory is needed. In particular, for $M = M^L$, the generalized coded caching of Section IV-C (and its corresponding cache assignment) is optimal.

**Remark 4:** For small total cache sizes, $C^*(M)$ grows as $\frac{M}{N}$. This corresponds to a perfect global caching gain as if each receiver could access all cache contents in the network locally. For large total cache sizes, the global benefit of receivers' cache memories is fully exploited. Any additional cache budget exceeding $M^L$ should be distributed among the receivers uniformly and it only offers a local caching gain. In particular, $C^*(M)$ grows as $\frac{1}{K} \cdot \frac{M}{N}$. This is similar to the insights from [17] (for rate-limited links). For moderate cache sizes, $C^*(M)$ grows with $\frac{M}{N}$ at a slope equal to:

$$\frac{R^{(t+1)} - R^{(t)}}{\frac{M^{(t+1)}}{N} - \frac{M^{(t)}}{N}} = \frac{1}{t+1} - \frac{M^{(t)}}{t(t+1)(M^{(t+1)} - M^{(t)})},$$

for $t = 1, \dots, K-1$.

*Proof of Corollary 11:* The global capacity-memory tradeoff $C^*(M)$ is upper-bounded by the right-hand side of (84) and this follows by specializing Corollary 10 to $t = K$. Equality in (84) for $M \le M^{\text{single}}$ follows by Theorem 2.

The capacity memory tradeoff $C^*(M)$ is also upper-bounded by the right-hand side of (85). To see this, relax Corollary 9 by (i) replacing each parameter $\alpha_{S,k}^*$ with $\alpha_{S,k}'$ and (ii) considering only the constraints (80) that correspond to sets $S = \{k\}$, for $k \in \mathcal{K}$. Next, average the $K$ resulting inequalities and maximize over the input distribution $P_X$. This yields:

$$C^*(M) \le C_{\text{avg}} + \frac{1}{K} \frac{M}{N}. \quad (86)$$

Using the definition of $M^L$ as given in (83), we can equivalently write the RHS of (86) in the form of $KC_{\text{avg}} + \frac{1}{K} \frac{M-M_1}{N}$. Equality in (85) for $M \ge N(K-1)KC_{\text{Avg}}$ follows from Proposition 7 with $\Delta = 0$. Recall that $M_k^{(K-1)}$ is given in (41) as the sum of mutual information terms $I(X; Y_\ell)$ for all $\ell \in \mathcal{K} \setminus \{k\}$. So we have

$$M_1^{*(K-1)} + \dots + M_K^{*(K-1)} = N \sum_{i=1}^{K} (K-1) I(X; Y_i) \quad (87)$$

$$= N(K-1)KC_{\text{Avg}} \quad (88)$$

where in the first step we have noted that each mutual information term appears $(K-1)$ times in the sum on the LHS of (87). ■

# VII. EXAMPLES

## A. Erasure BCs

We specialize our results to erasure BCs where at time $i$ receiver $k$'s output $Y_{k,i}$ equals the channel input $X_i$ with probability $1 - \delta_k$ and it equals an erasure symbol “?” with
<figure><img src="image_7.png" /><figcaption>Fig. 4. Bounds on C*(M) for a 4-user Erasure BC with $\delta_1 = 0.9$, $\delta_2 = 0.6$, $\delta_3 = 0.1$, $\delta_4 = 0.05$.</figcaption></figure>

probability $\delta_k$. Without loss of generality, we assume that the erasure probabilities satisfy:

$$1 > \delta_1 \ge \delta_2 \ge \dots \ge \delta_K \ge 0. \quad (89)$$

For erasure BCs,

$$C_S = \left( \sum_{s \in S} \frac{1}{1 - \delta_s} \right)^{-1}, \quad S \subseteq K. \quad (90)$$

Moreover, a Bernoulli-1/2 input distribution $P_X$ maximizes $I(X; Y_k)$ and $I(X; Y_k|U)$ simultaneously for all $k \in K$ and auxiliaries $U$ that form the Markov chain $U \to X \to Y_k$. Therefore, Theorem 4 and Corollary 5 coincide. Also,

$$C_{\text{avg}} = \frac{1}{K} \sum_{k=1}^{K} C_k = 1 - \frac{\sum_{k=1}^{K} \delta_k}{K}. \quad (91)$$

Figure 4 depicts the upper and lower bounds on C*(M) in Corollaries 8 and 9. For comparison, the upper bound of Theorem 4 is also plotted under the uniform cache assignment:

$$M_1 = \dots = M_K = \frac{M}{K}.$$

One observes that a smart allocation of the total cache memory M significantly increases the global capacity-memory tradeoff of erasure BCs when different receivers have different erasure probabilities.

Analytically, we can prove that for a small total cache size $M \le M^{\text{single}}$ any cache assignment that does not allocate all the cache memory to the weakest receiver is suboptimal on the erasure BC. This follows from the achievability in Corollary 11 and Proposition 12 below.

**Proposition 12:** For a given $M_1 \ge 0$ and $M := \sum_{k=1}^K M_k$, $M \ge 0$,

$$C(M_1, \dots, M_K) \le \min \left\{ C_K + \frac{M_1}{N} + \frac{(M-M_1)}{N} \cdot \frac{K \cdot C_K}{(K-1)C_{[2, \dots, K]}}, \right. \\ \left. C_1 + \frac{M_1}{N} \right\}. \quad (92)$$

The RHS of (92) is strictly less than $C_K + \frac{M_1}{N}$ unless $M = M_1$ or $\delta_1 = \dots = \delta_K$.

*Proof:* See Appendix F.

## B. Noise-Free Bit-Pipe

Consider now the noise-free bit-pipe model in [1] with uniform cache assignment. It corresponds to an erasure BC where each receiver has zero erasure probability:

$$\delta_1 = \dots = \delta_K = 0. \quad (93)$$

Consider also the notation introduced in Section II-A. We adopt the system model of [1] with equal cache sizes

$$m_1 = \dots = m_K = m$$

and the delivery rate $\rho$.

From the upper bound on $C(M_1, \dots, M_K)$ in Theorem 4, the following lower bound on the minimum achievable delivery rate $\rho^*$ can be obtained as a function of the normalized symmetric cache size $m$.

**Corollary 13:** For the noise-free bit-pipe model in [1], the delivery rate is bounded from below as follows.

$$\rho^* \ge t - m \cdot \min \left\{ \frac{t^2}{N}, \sum_{k=1}^{t} \frac{k}{N-k+1} \right\}, \quad m \le N. \quad (94)$$

*Proof:* See Appendix G.

This lower bound improves on the lower bounds in [1], [10]–[12] that existed at the time when this manuscript was submitted. It is within a constant gap of 2.35 bits from the optimal rate-memory tradeoff [37]. A slightly improved bound has been established in a parallel work [36]. This latter bound, however, is specific to the noise-free bit-pipe model.

## C. Gaussian BCs

Finally, we specialize our results to memoryless Gaussian BCs. At time $t$, the received symbol at receiver $k$ is

$$Y_{k,t} = X_t + Z_{k,t}, \quad (95)$$

where $X_t$ is the input to the channel and $\{Z_{k,t}\}$ is an i.i.d. Gaussian process with zero mean and variance $\sigma_k^2 > 0$. The channel inputs are subject to an average block-power constraint $P$. Without loss of generality, the receivers are ordered in increasing strength:

$$\sigma_1^2 \ge \sigma_2^2 \ge \dots \ge \sigma_K^2 > 0.$$

By [39], for every set $S$ as defined in (18), we have

$$C_S = \frac{1}{2} \log_2 \left( 1 + \frac{\beta_1 P}{\sum_{k=2}^{|S|} \beta_k P + \sigma_1^2} \right), \quad (96)$$
<figure><img src="image_8.png" /><figcaption>Fig. 5. Upper and lower bounds on $C^*(M)$ on a 4-receiver Gaussian BC with input power $P = 1$ and noise variances $\sigma_1 = 4$, $\sigma_2^2 = 1$, $\sigma_3^2 = 0.5$, and $\sigma_4^2 = 0.1$. We have $N = 10$.</figcaption></figure>

where $\beta_1, \dots, \beta_{|S|}$ form a unique choice of $|S|$ real numbers in $[0, 1]$ that sum to 1 and satisfy

$$ \frac{\beta_1 P}{\sum_{k=2}^{|S|} \beta_k P + \sigma_1^2} = \frac{\beta_i P}{\sum_{k=i+1}^{|S|} \beta_k P + \sigma_{ji}^2}, \quad i \in \{1, \dots, |S|\}. \qquad (97) $$

In particular,

$$ C_k = \frac{1}{2} \log \left( 1 + \frac{P}{\sigma_k^2} \right), \quad k \in \{1, \dots, K\}. \qquad (98) $$

Moreover, given a power constraint $P > 0$, a zero-mean variance-$P$ Gaussian input distribution maximizes $I(X; Y_k)$ and $I(X; Y_k|U)$ simultaneously for all $k \in K$ and Gaussian auxiliaries $U$ that form the Markov chain $U \to X \to Y_k$. Therefore, Theorem 4 and Corollary 5 coincide. Also,

$$ C_{\text{avg}} = \frac{1}{K} \sum_{k=1}^{K} C_k = \frac{1}{K} \sum_{k=1}^{K} \frac{1}{2} \log \left( 1 + \frac{P}{\sigma_k^2} \right). \qquad (99) $$

Figure 5 shows the upper and lower bounds on $C^*(M)$ in Corollaries 8 and 9. The five blue points indicate the rate-memory points $(R^{(0)}, M^{(0)}), (R^{\text{single}}, M^{\text{single}}), (R^{(1)}, M^{(1)}), (R^{(2)}, M^{(2)}), \text{ and } (R^{(3)}, M^{(3)})$ for a zero-mean variance-$P$ Gaussian distribution $P_X$. For comparison, the figure also shows the upper bound in Theorem 4 for a setup with uniform cache assignment $\frac{M}{K}$ across all receivers. We observe that a smart cache assignment provides substantial gains in the capacity-memory tradeoff.

VIII. SUMMARY AND CONCLUSION

We have provided close upper and lower bounds on the global capacity-memory tradeoff $C^*(M)$ of degraded BCs. The bounds coincide in the regimes of small and large total cache memories with thresholds depending on the BC statistics.

For small cache memory sizes (characterized in (84)), the global capacity-memory tradeoff is achieved by assigning all the available cache memory to the weakest receiver. In this regime, $C^*(M)$ grows as $\frac{M}{N}$ which corresponds to a perfect global caching gain; i.e., all receivers can benefit from all the cache contents in the network. This performance is achieved by superposition piggyback coding which provides every receiver virtual access to the weakest receiver's cache content.

For the regime of moderate $M$, we proposed a generalized coded caching scheme that performs a particular cache assignment such that the weaker receivers are provided with larger cache sizes. It then simultaneously serves $t+1$ receivers in each delivery, where $t \in \{1, \dots, K-1\}$ is the parameter of the scheme (similar to the scheme in [1]). We observed that the larger the total cache budget $M$ is, the larger the coded caching parameter $t$ needs to be chosen. Hence, as $M$ increases, cache memories will have to store more overlapping contents, and hence the caching gain decreases. In other words, the slope of the rate-memory tradeoff (achieved by the generalized coded caching) decreases as the total cache budget $M$ increases. The same behavior is also observed from the upper bound.

In the regime of large $M$ (characterized by the threshold in (85)), the caching gain is only local and $C^*(M)$ grows as $\frac{M}{KN}$. In particular, the memory threshold in (85) corresponds to the extreme case where $t = K-1$. In this case, the generalized coded caching scheme and its corresponding cache assignment are optimal and achieve the global capacity-memory tradeoff. For larger cache memories, it is optimal to first allocate the total cache memory as proposed by our scheme for $t = K-1$, and then uniformly allocate all the remaining cache memory across all the receivers (and store the same content in those extra portions of the receivers' cache memories).

By examining several examples, we have demonstrated that assigning the total cache memory uniformly across all the receivers can be highly suboptimal over noisy BCs.

From a practical view point, one of the main technical challenges for implementing the proposed generalized coded caching scheme is its high level of subpacketization, i.e., the fact that messages need to be split into a very large number of smaller parts. Recent efforts focus on schemes with low subpacketization levels. See for example [42]–[44] for results on the noise-free bit-pipe model.

APPENDIX A

PROOF OF UPPER BOUND IN THEOREM 4

Fix the rate of communication

$$ R < C(M_1, \dots, M_K). $$

Since $R$ is achievable, for each sufficiently large blocklength $n$ and for each demand vector $\mathbf{d}$, there exist $K$ caching functions $\{g_k^{(n)}\}$, an encoding function $\{f^{(n)}(\dots, \mathbf{d})\}$, and $K$ decoding functions $\{\phi_k^{(n)}(\dots, \mathbf{d})\}$ so that the probability of error $P_e^{(n)}$ tends to 0 as $n \to \infty$. Recall that $P_e^{(n)}$ is the average over all error probabilities $P_e^{(n)}(\mathbf{d}), \mathbf{d} \in \mathcal{N}^K$. So $P_e^{(n)}$ goes to zero if and only if $P_e^{(n)}(\mathbf{d})$ goes to zero for all demand vectors $\mathbf{d}$. We note that this should hold for every demand
vector **d** and, in particular, for **d** with all-different entries. To obtain the upper bound in Theorem 4, we consider only demand vectors **d** in which all entries are different.

Fix $\epsilon > 0$ and a sufficiently large blocklength $n$ (depending on this $\epsilon$). Let

$$V_k = g_k^{(n)}(W_1, \dots, W_N), \quad k \in \{1, \dots, K\}, \quad (100)$$

denote the cache contents corresponding to the chosen caching function, and let for each demand vector **d** = ($d_1, \dots, d_K$) with all different entries

$$X_{\mathbf{d}}^{n} = f^{(n)}(W_1, \dots, W_N, \mathbf{d}) \quad (101)$$

denote the input of the degraded BC corresponding to the chosen encoding functions. Let $Y_{k,\mathbf{d}}^n$ denote the corresponding channel outputs at receiver $k$.

**Lemma 14:** There exist random variables $X_{\mathbf{d}}, Y_{1,\mathbf{d}}, \dots, Y_{K,\mathbf{d}}$ and for each set $S$ as in (18) random variables $\{U_{S,1,\mathbf{d}}, \dots, U_{S,|S|-1,\mathbf{d}}\}$, so that given $X_{\mathbf{d}} = x \in \mathcal{X}$:

$$(Y_{1,\mathbf{d}}, Y_{2,\mathbf{d}}, \dots, Y_{K,\mathbf{d}}) \sim \Gamma(\dots | x); \quad (102a)$$

and for each $S$:

$$U_{S,1,\mathbf{d}} \rightarrow \dots \rightarrow U_{S,|S|-1,\mathbf{d}} \rightarrow X_{\mathbf{d}} \rightarrow Y_{K,\mathbf{d}} \rightarrow Y_{K-1,\mathbf{d}} \rightarrow \dots \rightarrow Y_{1,\mathbf{d}} \quad (102b)$$

forms a Markov chain; and the following $|S|$ inequalities hold:

$$R - \epsilon \le \frac{1}{n} I(W_{d_{j_1}}; V_{j_1}) + I(U_{S,1,\mathbf{d}}; Y_{j_1,\mathbf{d}}), \quad (103a)$$

$$R - \epsilon \le \frac{1}{n} I(W_{d_{jk}}; V_{j_1}, \dots, V_{jk} | W_{d_{j_1}}, \dots, W_{d_{jk-1}}) \\ + I(U_{S,k,\mathbf{d}}; Y_{jk,\mathbf{d}} | U_{S,k-1,\mathbf{d}}), \\ \forall k \in \{2, \dots, |S| - 1\}, \quad (103b)$$

$$R - \epsilon \le \frac{1}{n} I(W_{d_{j_1|S}}; V_{j_1}, \dots, V_{j_1|S} | W_{d_{j_1}}, \dots, W_{d_{j_1|S|-1}}) \\ + I(X_{\mathbf{d}}; Y_{j_1|S,\mathbf{d}} | U_{S,|S|-1,\mathbf{d}}). \quad (103c)$$

**Proof:** The proof is inspired by the converse proof of the capacity of degraded BCs without caching [38]. Details are as follows. Since the worst case error probability is bounded by $\epsilon$, using Fano's inequality we have

$$R - \epsilon \le \frac{1}{n} I(W_{d_{j_1}}; Y_{j_1,\mathbf{d}}^n, V_{j_1}) \\ = \frac{1}{n} I(W_{d_{j_1}}; V_{j_1}) + \frac{1}{n} I(W_{d_{j_1}}; Y_{j_1,\mathbf{d}}^n | V_{j_1}), \quad (104a)$$

where the equality follows by the chain rule of mutual information. Similarly, for $k \in \{2, \dots, K\}$:

$$\begin{align*} R - \epsilon &\stackrel{(a)}{\le} \frac{1}{n} I(W_{d_{jk}}; Y_{jk,\mathbf{d}}^n, V_{j_1}, \dots, V_{jk} | W_{d_{j_1}}, \dots, W_{d_{jk-1}}) \\ &= \frac{1}{n} I(W_{d_{jk}}; V_{j_1}, \dots, V_{jk} | W_{d_1}, \dots, W_{d_{jk-1}}) \\ &\quad + \frac{1}{n} I(W_{d_{jk}}; Y_{jk,\mathbf{d}}^n | V_1, \dots, V_{jk}, W_{d_{j_1}}, \dots, W_{d_{jk-1}}), \quad (104b) \end{align*}$$

where (a) uses Fano's inequality as well as the fact that all messages are independent. Recall that the demand vector **d** has all different entries.

We next develop the second summands in (104a) and (104b). For the second summand in (104a) we write

$$\begin{align} \frac{1}{n} I(W_{d_{j_1}}; Y_{j_1,\mathbf{d}}^n | V_{j_1}) &= \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{j_1}}; Y_{j_1,\mathbf{d},t} | V_{j_1}, Y_{j_1,\mathbf{d}}^{t-1}) \nonumber \\ &\stackrel{(a)}{\le} \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{j_1}}; Y_{j_1,\mathbf{d},t}^{t-1}, V_{j_1}; Y_{j_1,\mathbf{d},t}) \nonumber \\ &= I(U_{S,1,\mathbf{d},T}; Y_{j_1,\mathbf{d},T} | T) \nonumber \\ &\le I(U_{S,1,\mathbf{d}}; Y_{j_1,\mathbf{d}}) \tag{105} \end{align}$$

where $T$ denotes a random variable that is uniformly distributed over $\{1, \dots, n\}$ and independent of all previously defined random variables, and where

$$U_{S,1,\mathbf{d},T} := (V_{j_1}, W_{d_{j_1}}, Y_{j_1,\mathbf{d}}^{T-1}), \quad (106)$$

$$U_{S,1,\mathbf{d}} := (U_{S,1,\mathbf{d},T}, T), \quad (107)$$

$$Y_{j_1, \mathbf{d}} := Y_{j_1, \mathbf{d}, T}, \quad (108)$$

Step (a) holds because, for any triple of random variables $(A, B, C)$, we have $I(A; B|C) \le I(A, C; B)$ by the chain rule of mutual information and the nonnegativity of mutual information.

Define further for $k \in \{2, \dots, |S| - 1\}$:

$$U_{S,k,\mathbf{d},T} := (U_{S,k-1,\mathbf{d},T}, V_{jk}, W_{d_{jk}}, Y_{jk,\mathbf{d}}^{T-1}), \quad (109)$$

$$U_{S,k,\mathbf{d}} := (U_{S,k,\mathbf{d},T}, T), \quad (110)$$

$$Y_{jk,\mathbf{d}} := Y_{jk,\mathbf{d},T}, \quad (111)$$

and

$$Y_{j_1|S,\mathbf{d}} := Y_{j_1|S,\mathbf{d},T}, \quad (112)$$

$$X_{\mathbf{d}} := X_{\mathbf{d},T}. \quad (113)$$

For $k \in \{2, \dots, K-1\}$, we expand the second summand in (104b) as:

$$\begin{align*} \frac{1}{n} I(W_{d_{jk}}; Y_{jk,\mathbf{d}}^n | V_{j_1}, \dots, V_{jk}, W_{d_{j_1}}, \dots, W_{d_{jk-1}}) \\ &= \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{jk}}; Y_{jk,\mathbf{d},t} | V_{j_1}, \dots, V_{jk}, W_{d_{j_1}}, \dots, W_{d_{jk-1}}, Y_{jk,\mathbf{d}}^{t-1}) \\ &\stackrel{(a)}{=} \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{jk}}; Y_{jk,\mathbf{d},t} | V_{j_1}, \dots, V_{jk}, W_{d_{j_1}}, \dots, W_{d_{jk-1}}, \\ &\qquad Y_{j_1,\mathbf{d}}^{t-1}, \dots, Y_{j_{k-1},\mathbf{d}}^{t-1}, Y_{jk,\mathbf{d}}^{t-1}) \\ &\le \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{jk}}, Y_{jk,\mathbf{d}}^{t-1}, V_{jk}; Y_{jk,\mathbf{d},t} | V_{j_1}, \dots, V_{jk-1}, \\ &\qquad W_{d_{j_1}}, \dots, W_{d_{jk-1}}, Y_{j_1,\mathbf{d}}^{t-1}, \dots, Y_{j_{k-1},\mathbf{d}}^{t-1}) \\ &\stackrel{(b)}{=} I(U_{S,k,\mathbf{d},T}; Y_{jk,\mathbf{d},T} | U_{S,k-1,\mathbf{d},T}, T) \\ &\stackrel{(c)}{=} I(U_{S,k,\mathbf{d}}; Y_{jk,\mathbf{d}} | U_{S,k-1,\mathbf{d}}), \quad (114) \end{align*}$$

where (a) follows from the degradedness of the outputs; (b) by (106) and the definition of $T$; and (c) by the definitions in (110), (112), and (113).
Similarly, we also have

$$
\begin{align}
& \frac{1}{n} I(W_{d_{j|S|}}; Y_{j|S|, \mathbf{d}}^{n} | V_{j1}, \dots, V_{j|S|}, W_{d_{j1}}, \dots, W_{d_{j|S|-1}}) \nonumber \\
&= \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{j|S|}}; Y_{j|S|, \mathbf{d}, t} | V_{j1}, \dots, V_{j|S|}, W_{d_{j1}}, \dots, W_{d_{j|S|-1}}, \nonumber \\
& \qquad Y_{j1, \mathbf{d}, t}^{t-1}, \dots, Y_{j|S|-1, \mathbf{d}, t}^{t-1}, Y_{j|S|, \mathbf{d}, t}^{t-1}) \nonumber \\
&\le \frac{1}{n} \sum_{t=1}^{n} I(W_{d_{j1|S|}}; Y_{j1|S|, \mathbf{d}, t}^{t-1} | V_{j1}, \dots, V_{j|S|-1}, \nonumber \\
& \qquad W_{d_{j1}}, \dots, W_{d_{j|S|-1}}, Y_{j1, \mathbf{d}, t}^{t-1}, \dots, Y_{j|S|-1, \mathbf{d}, t}^{t-1}) \nonumber \\
&\le I(X_{\mathbf{d}, T}; Y_{j|S|, \mathbf{d}, T} | U_{S, |S|-1, \mathbf{d}, T}, T) \nonumber \\
&= I(X_{\mathbf{d}}; Y_{j|S|, \mathbf{d}} | U_{S, |S|-1, \mathbf{d}}). \tag{115}
\end{align}
$$

It can be verified that the defined random variables satisfy Conditions (102). Combining this observation with (104)–(115) concludes the proof. ■

We average the bounds in (103) over demand vectors. Let $\mathcal{N}_{\mathbf{K}}^{\text{dist}}$ be the set of all the $\binom{N}{\mathbf{K}}\mathbf{K}$-K-dimensional demand vectors with all distinct entries. Also, let $\mathbf{Q}$ be a uniform random variable over the elements of $\mathcal{N}_{\mathbf{K}}^{\text{dist}}$ and independent of all other random variables. Define for each set $S$ as in (18):

$$ U_{S,1} := (U_{S,1,Q}, Q), \quad (116) $$

$$ U_{S,k} := U_{S,k,Q}, \quad k \in \{2, \dots, |S| - 1\}, \quad (117) $$

$$ X := X_Q, \quad (118) $$

$$ Y_k := Y_{k,Q}, \quad k \in \mathcal{K}. \quad (119) $$

Notice that the defined random variables defined in (116)–(119) satisfy conditions (15b) and (68) in the theorem. It remains to prove that they also satisfy (69). To this end, we average inequalities (103) over all the demand vectors in $\mathcal{N}_{\mathbf{K}}^{\text{dist}}$. Using standard arguments to take care of the averaging random variable $\mathbf{Q}$, and defining

$$ \alpha_{S,1} := \frac{1}{\binom{N}{\mathbf{K}}} \sum_{\mathbf{d} \in \mathcal{N}_{\mathbf{K}}^{\text{dist}}} \frac{1}{n} I(W_{d_{j1}}; V_1), \quad (120a) $$

$$ \alpha_{S,k} := \frac{1}{\binom{N}{\mathbf{K}}} \sum_{\mathbf{d} \in \mathcal{N}_{\mathbf{K}}^{\text{dist}}} \frac{1}{n} I(W_{d_{jk}}; V_1, \dots, V_{jk} | W_{d_{j1}}, \dots, W_{d_{jk-1}}), \quad k \in \{2, \dots, |S|\}, \quad (120b) $$

we obtain for each $S$ as in (18):

$$ R - \epsilon \le I(U_{S,1}; Y_{j1}) + \alpha_{S,1}, \quad (121a) $$

$$ R - \epsilon \le I(U_{S,k}; Y_{jk} | U_{S,k-1}) + \alpha_{S,k}, \quad \forall k \in \{2, \dots, |S|-1\}, \quad (121b) $$

$$ R - \epsilon \le I(X; Y_{j|S|} | U_{S,|S|-1}) + \alpha_{S,|S|}, \quad (121c) $$

**Lemma 15:** For each set $S$, parameters $\alpha_{S,1}, \dots, \alpha_{S,|S|}$ satisfy the following constraints:

$$ 0 \le \alpha_{S,k} \le \frac{\sum_{i=1}^{k} M_{ji}}{N-k+1}, \quad k \in \{1, \dots, |S|\}, \quad (122a) $$

$$ \alpha_{S,k'} \le \alpha_{S,k}, \quad k, k' \in \{1, \dots, |S|\}, \quad k' \le k, \quad (122b) $$

$$ \sum_{k=1}^{|S|} \alpha_{S,k} \le \frac{|S|}{N} \sum_{k=1}^{|S|} M_{jk}. \quad (122c) $$

*Proof:* See Appendix B. ■

By (121)–(122) and letting $\epsilon \to 0$, the following intermediate result—which is used in other proofs in this paper—is obtained.

**Lemma 16:** There exist random variables $X, Y_1, \dots, Y_K$ and for every receiver set $S$ as in (18) random variables $\{U_{S,1}, \dots, U_{S,|S|-1}\}$, so that (15b) and (68) hold, and for all $S$:

$$ C(M_1, \dots, M_K) \le I(U_{S,1}; Y_{j1}) + \alpha_{S,1}, \quad (123a) $$

$$ C(M_1, \dots, M_K) \le I(U_{S,k}; Y_{jk} | U_{S,k-1}) + \alpha_{S,k}, \quad \forall k \in \{2, \dots, |S|\}, \quad (123b) $$

for parameters $\alpha_{S,1}, \dots, \alpha_{S,|S|}$ satisfying (122).

By the following Lemma 17, because constraints (123) are increasing in $\alpha_{S,1}, \dots, \alpha_{S,|S|}$, and by constraint (122c), we conclude that the choice $\alpha_{S,k} = \alpha_{S,k}^*$ in (67) makes the upper bound (123) loosest. The following Lemma 17 thus concludes the proof.

**Lemma 17:** Lemma 16 remains valid, if parameters $\alpha_{S,1}, \dots, \alpha_{S,|S|}$ are further constrained to satisfy for each $k \in \{1, \dots, |S| - 1\}$ one of the two following conditions:

* $\alpha_{S,k} = \frac{\sum_{i=1}^{k} M_{ji}}{N-k+1}$; or

* $\alpha_{S,k} = \alpha_{S,k+1}$.

*Proof:* See Appendix C. ■

## APPENDIX B

### PROOF OF LEMMA 15

We only prove the lemma for $S = \mathcal{K}$. The proofs for the other sets are similar.

We first prove (122a). Every $\alpha_{\mathcal{K},k}$ is nonnegative, because mutual information is nonnegative. To prove the upper bound in (122a), we proceed as follows. Let $\mathcal{N}_{\mathbf{K}}^{\text{dist}}$ again be the set of K-dimensional demand vectors that have K distinct entries in $\{1, \dots, N\}$; and for each $k \in \{1, \dots, K\}$ and each $k-1$ dimensional demand vector $\tilde{\mathbf{d}} = (d_1, \dots, d_{k-1})$, define $W_{\tilde{\mathbf{d}}} := (W_{d_1}, \dots, W_{d_{k-1}})$. We have:

$$
\begin{align*}
\alpha_{\mathcal{K},k} &= \frac{1}{\mathbf{K}! \binom{N}{\mathbf{K}}} \sum_{\mathbf{d} \in \mathcal{N}_{\mathbf{K}}^{\text{dist}}} I(W_{d_k}; V_1, \dots, V_k | W_{d_1}, \dots, W_{d_{k-1}}) \\
&= \frac{1}{\mathbf{K}! \binom{N}{\mathbf{K}}} \sum_{\tilde{\mathbf{d}} \in \mathcal{N}_{\mathbf{K}}^{\text{dist}}} \sum_{(d_1, \dots, d_{k-1}) = \tilde{\mathbf{d}}} I(W_{d_k}; V_1, \dots, V_k | W_{\tilde{\mathbf{d}}}) \\
&\stackrel{(a)}{=} \frac{1}{\mathbf{K}! \binom{N}{\mathbf{K}}} \sum_{\tilde{\mathbf{d}} \in \mathcal{N}_{k-1}^{\text{dist}}} \sum_{j \in \mathcal{N} \setminus \{\tilde{d}_1, \dots, \tilde{d}_{k-1}\}} I(W_j; V_1, \dots, V_k | W_{\tilde{\mathbf{d}}}) \\
&\qquad \cdot \binom{N-k}{K-k} (K-k)! \\
&= \frac{1}{k! \binom{N}{k}} \sum_{\tilde{\mathbf{d}} \in \mathcal{N}_{k-1}^{\text{dist}}} \sum_{j \in \mathcal{N} \setminus \{\tilde{d}_1, \dots, \tilde{d}_{k-1}\}} I(W_j; V_1, \dots, V_k | W_{\tilde{\mathbf{d}}}) \\
&\stackrel{(b)}{=} \frac{1}{k! \binom{N}{k}} \sum_{\tilde{\mathbf{d}} \in \mathcal{N}_{k-1}^{\text{dist}}} [H(W_1, \dots, W_N | W_{\tilde{\mathbf{d}}}) \\
&\qquad - \sum_{j \in \mathcal{N} \setminus \{\tilde{d}_1, \dots, \tilde{d}_{k-1}\}} H(W_j | V_1, \dots, V_k, W_{\tilde{\mathbf{d}}})]
\end{align*}
$$
$$ \leq \frac{1}{k! \binom{N}{k}} \sum_{\tilde{d} \in \mathcal{N}_{k-1}^{\text{dist}}} I(W_1, \dots, W_N; V_1, \dots, V_k | W_{\tilde{d}}) $$

$$ \begin{aligned} & \leq \frac{(k-1)! \binom{N}{k-1}}{k! \binom{N}{k}} \sum_{i=1}^{k} M_i \\ &= \frac{\sum_{i=1}^{k} M_i}{N-k+1}, \end{aligned} \quad (124) $$

where (a) holds because for each value of $K$ and $j$ there are $\binom{N-k}{K-k}(K-k)!$ ordered demand vectors $d \in \mathcal{N}_K^{\text{dist}}$ with $(d_1, \dots, d_{k-1}) = \tilde{d}$ and with $d_k = j$; (b) holds by the independence of the messages; (c) holds because for any random tuple $(A_1, \dots, A_L)$ it holds that $\sum_{l=1}^L H(A_l) \geq H(A_1, \dots, A_L)$; and (d) holds because $I(W_1, \dots, W_N; V_1, \dots, V_k | W_{\tilde{d}})$ cannot exceed $\sum_{i=1}^k M_i$. This concludes the proof of (122a).

To prove constraint (122b), we fix a $K$-dimensional demand vector $d \in \mathcal{N}_K^{\text{dist}}$, and consider the cyclic shifts of this vector. For $\ell \in \{0, \dots, K-1\}$, let $d^{(\ell)}$ be the vector obtained from $d$ when the elements are cyclically shifted $\ell$ positions to the right. (For example, if $d = (1, 2, 3)$ then $d^{(2)} = (2, 3, 1)$.) For each $\ell \in \{0, \dots, K-1\}$ and $k \in \{1, \dots, K\}$, let $d_k^{(\ell)}$ denote the $k$-th index of demand vector $d^{(\ell)}$. So,

$$ d_k^{(\ell)} = d_{(k-\ell) \text{ mod } K} \quad (125) $$

where for each positive integer $\xi$ the term $(\xi \text{ mod } K)$ takes value in $\{1, \dots, K\}$ so that

$$ \xi \text{ mod } K = \xi - bK \quad \text{for some positive integer } b. \quad (126) $$

For each $\ell \in \{1, \dots, K-1\}$ and $k, k' \in \{2, \dots, K\}$ with $k' \leq k$, we write

$$ \begin{aligned} I(W_{d_1}; V_1) &\stackrel{(a)}{=} I(W_{d_k^{(k'-1)}}; V_1) \\ &\stackrel{(b)}{\leq} I(W_{d_k^{(k'-1)}}; V_1, \dots, V_{k'} | W_{d_1^{(k'-1)}}, \dots, W_{d_{k'-1}^{(k'-1)}}) \\ &\stackrel{(a)}{=} I(W_{d_k^{(k-1)}}; V_1, \dots, V_{k'} | W_{d_{1+k-k'}^{(k-1)}}, \dots, W_{d_{k-1}^{(k-1)}}) \\ &\stackrel{(b)}{\leq} I(W_{d_k^{(k-1)}}; V_1, \dots, V_k | W_{d_1^{(k-1)}}, \dots, W_{d_{k-1}^{(k-1)}}) \end{aligned} \quad (127) $$

where (a) follows by (125) and (b) is by the independence of messages.

Fix a demand vector $d \in \mathcal{N}_K^{\text{dist}}$ and sum up the above inequality (127) over all $K$ cyclic shifts $d^{(0)}, d^{(1)}, \dots, d^{(K-1)}$ of $d$ (where for simplicity we relabel the shifts) to obtain:

$$ \begin{aligned} & \sum_{\ell=0}^{K-1} I(W_{d_1^{(\ell)}}; V_1) \\ & \leq \sum_{\ell=0}^{K-1} I(W_{d_k^{(\ell)}}; V_1, \dots, V_{k'} | W_{d_1^{(\ell)}}, \dots, W_{d_{k'-1}^{(\ell)}}) \\ & \leq \sum_{\ell=0}^{K-1} I(W_{d_k^{(\ell)}}; V_1, \dots, V_k | W_{d_1^{(\ell)}}, \dots, W_{d_{k-1}^{(\ell)}}). \end{aligned} \quad (128) $$

Since the set $\mathcal{N}_K^{\text{dist}}$ can be partitioned into subsets of demand vectors that are cyclic shifts of each others and all cyclic shifts

of a demand vector in $\mathcal{N}_K^{\text{dist}}$ are also in $\mathcal{N}_K^{\text{dist}}$, we conclude from (128):

$$ \begin{aligned} & \sum_{d \in \mathcal{N}_K^{\text{dist}}} I(W_{d_1}; V_1) \\ & \leq \sum_{d \in \mathcal{N}_K^{\text{dist}}} I(W_{d_{k'}}; V_1, \dots, V_{k'} | W_{d_1}, \dots, W_{d_{k'-1}}) \\ & \leq \sum_{d \in \mathcal{N}_K^{\text{dist}}} I(W_{d_k}; V_1, \dots, V_k | W_{d_1}, \dots, W_{d_{k-1}}). \end{aligned} \quad (129) $$

This proves (122b).

We proceed to prove constraint (122c). For each $d \in \mathcal{N}_K^{\text{dist}}$:

$$ \begin{aligned} & I(W_{d_1}; V_1) + \sum_{k=2}^{K} I(W_{d_k}; V_1, \dots, V_k | W_{d_1}, W_{d_2}, \dots, W_{d_{k-1}}) \\ & \leq I(W_{d_1}, W_{d_2}, \dots, W_{d_K}; V_1, \dots, V_K). \end{aligned} \quad (130) $$

So,

$$ \begin{aligned} & \sum_{d \in \mathcal{N}_K^{\text{dist}}} \left[ I(W_{d_1}; V_1) \right. \\ & \qquad \left. + \sum_{k=2}^{K} I(W_{d_k}; V_1, \dots, V_k | W_{d_1}, W_{d_2}, \dots, W_{d_{k-1}}) \right] \\ & \leq \sum_{d \in \mathcal{N}_K^{\text{dist}}} I(W_{d_1}, W_{d_2}, \dots, W_{d_K}; V_1, \dots, V_K) \\ & \stackrel{(a)}{=} \sum_{d \in \mathcal{N}_K^{\text{dist}}} \left[ H(W_{d_1}) + H(W_{d_2}) + \dots + H(W_{d_K}) \right. \\ & \qquad \left. - H(W_{d_1}, \dots, W_{d_K} | V_1, \dots, V_K) \right] \\ & \stackrel{(b)}{=} \frac{K}{N} |\mathcal{N}_K^{\text{dist}}| H(W_1, \dots, W_N) \\ & \qquad - \sum_{d \in \mathcal{N}_K^{\text{dist}}} H(W_{d_1}, \dots, W_{d_K} | V_1, \dots, V_K) \\ & \stackrel{(c)}{\leq} \frac{K}{N} K! \binom{N}{K} H(W_1, \dots, W_N) \\ & \qquad - \frac{K}{N} K! \binom{N}{K} H(W_1, \dots, W_N | V_1, \dots, V_K) \\ & \stackrel{(b)}{=} \frac{K}{N} K! \binom{N}{K} I(W_1, \dots, W_N; V_1, \dots, V_K) \\ & \leq \frac{K}{N} K! \binom{N}{K} n \sum_{k=1}^{K} M_k, \end{aligned} $$

where (a) holds by the chain rule of mutual information, (b) by the independence and uniform rate of messages $W_1, \dots, W_N$ and the definition of the set $\mathcal{N}_K^{\text{dist}}$, which is of size $\binom{N}{K}K!$, and (c) by the generalized Han-Inequality (the following Proposition 18).

**Proposition 18:** Let $L$ be a positive integer and $A_1, \dots, A_L$ be a finite random $L$-tuple. Denote by $A_J$ the subset $\{A_i, i \in J\}$. For every $i \in \{1, \dots, L\}$:

$$ \frac{1}{\binom{L}{i}} \sum_{J \subseteq \{1, \dots, L\}: \quad |J| = i} \frac{H(A_J)}{i} \geq \frac{1}{L} H(A_1, \dots, A_L). \quad (131) $$

*Proof:* See [45, Theorem 17.6.1].

<figure><img src="image_9.png" /></figure>
## APPENDIX C
### PROOF OF LEMMA 17

We prove the lemma by contradiction. Fix a random tuple $(X, Y_1, \dots, Y_K)$ satisfying (15b) and for each set $S$ as in (18) a random tuple $U_{S,1}, U_{S,2}, \dots, U_{S,|S|-1}$ satisfying (68) and real numbers $\alpha_{S,1}, \dots, \alpha_{S,|S|}$ satisfying (122).

Assume that for some set $S$ as in (18) and some $\tilde{k} \in \{1, \dots, |S|-1\}$:

$$ \alpha_{S, \tilde{k}} \neq \alpha_{S, \tilde{k}+1} \quad (132) $$

and

$$ \alpha_{S, \tilde{k}} < \frac{\sum_{i=1}^{\tilde{k}} M_{ji}}{N - \tilde{k} + 1}. \quad (133) $$

Let

$$ \gamma := \max \left\{ \frac{1}{2}, \frac{\alpha_{S, \tilde{k}+1} - \frac{\sum_{i=1}^{\tilde{k}} M_{ji}}{N-\tilde{k}+1}}{\alpha_{S, \tilde{k}+1} - \alpha_{S, \tilde{k}}} \right\}. \quad (134) $$

Notice that by (133):

$$ \gamma \in \left[ \frac{1}{2}, 1 \right). \quad (135) $$

Define the new parameters

$$ \bar{\alpha}_{S,k} := \alpha_{S,k}, \quad k \in \{1, \dots, |S|\} \setminus \{\tilde{k}, \tilde{k}+1\}, \quad (136a) $$

$$ \bar{\alpha}_{S, \tilde{k}} := \gamma \alpha_{S, \tilde{k}} + (1 - \gamma) \alpha_{S, \tilde{k}+1}, \quad (136b) $$

$$ \bar{\alpha}_{S, \tilde{k}+1} := (1 - \gamma) \alpha_{S, \tilde{k}} + \gamma \alpha_{S, \tilde{k}+1}. \quad (136c) $$

Notice that this new set of parameters satisfies constraints (122) when $\alpha_{S,1}, \dots, \alpha_{S,|S|}$ are replaced by $\bar{\alpha}_{S,1}, \dots, \bar{\alpha}_{S,|S|}$. In particular,

$$ \bar{\alpha}_{S,k} \le \bar{\alpha}_{S,k+1}, \quad k \in \{1, \dots, |S|-1\}. \quad (137) $$

We will show that there exist new auxiliary random variables $\bar{U}_{S,1}, \bar{U}_{S,2}, \dots, \bar{U}_{S,|S|-1}$ satisfying the Markov chain (68), and so that upper bound (103) is looser for these new auxiliaries and the new parameters $\bar{\alpha}_{S,1}, \dots, \bar{\alpha}_{S,|S|}$ than for the original auxiliaries $U_{S,1}, \dots, U_{S,|S|-1}$ and parameters $\alpha_{S,1}, \dots, \alpha_{S,|S|-1}$.

To simplify notation in the following, we define

$$ U_{S,|S|} := X. \quad (138) $$

Notice that since $\alpha_{S,\tilde{k}} \neq \alpha_{S,\tilde{k}+1}$ and by (122b), the strict inequality

$$ \alpha_{S, \tilde{k}} < \alpha_{S, \tilde{k}+1} \quad (139) $$

must hold. Choose

$$ \bar{U}_{S,k} = U_{S,k}, \quad k \in \{1, \dots, |S|-1\} \setminus \{\tilde{k}\}, \quad (140) $$

and

$$ \bar{U}_{S,|S|} = U_{S,|S|} = X. \quad (141) $$

The choice of $\bar{U}_{S,\tilde{k}}$ depends on whether

$$ I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}) \le I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) \quad (142a) $$

or

$$ I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}) > I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}). \quad (142b) $$

If (142a) holds, choose

$$ \bar{U}_{S,\tilde{k}} = U_{S,\tilde{k}}. \quad (143) $$

If (142b) holds, let $E \in \{0, 1\}$ be a Bernoulli-$\beta$ random variable independent of everything else, where

$$ \beta := (1 - \gamma) - (1 - \gamma) \cdot \frac{I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}})}{I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1})}. \quad (144) $$

Choose

$$ \bar{U}_{S, \tilde{k}} = \begin{cases} (U_{S, \tilde{k}}, E) & \text{if } E = 0, \\ (U_{S, \tilde{k}-1}, E) & \text{if } E = 1. \end{cases} \quad (145) $$

Notice that in both cases the proposed choice satisfies the Markov chain $\bar{U}_{S,1} \to \bar{U}_{2,S} \to \dots \to \bar{U}_{S,|S|-1} \to X$.

Trivially, for $k \notin \{\tilde{k}, \tilde{k}+1\}$, constraint (103) is unchanged if we replace $(U_{S,1}, U_{S,2}, \dots, U_{S,|S|-1}, X)$ by $(\bar{U}_{S,1}, \bar{U}_{S,2}, \dots, \bar{U}_{S,K-1}, X)$ and $(\alpha_{S,1}, \dots, \alpha_{S,|S|})$ by $(\bar{\alpha}_{S,1}, \dots, \bar{\alpha}_{S,|S|})$.

If (142a) holds, then the proposed replacement relaxes constraint (103) for $k = \tilde{k}$ (because $\bar{\alpha}_{S,\tilde{k}} > \alpha_{S,\tilde{k}}$) and it tightens it for $k = \tilde{k}+1$ (because $\bar{\alpha}_{S,\tilde{k}+1} < \alpha_{S,\tilde{k}+1}$). However, the new constraint for $k = \tilde{k}+1$ is less stringent than the original constraint for $k = \tilde{k}$:

$$ \begin{align} & \bar{\alpha}_{S, \tilde{k}+1} + I(\bar{U}_{S, \tilde{k}+1}; Y_{\tilde{k}+1}|\bar{U}_{S, \tilde{k}}) \nonumber \\ & \stackrel{(a)}{=} (1 - \gamma) \cdot \alpha_{S, \tilde{k}} + \gamma \cdot \alpha_{S, \tilde{k}+1} + I(U_{S, \tilde{k}+1}; Y_{\tilde{k}+1}|U_{S, \tilde{k}}) \nonumber \\ & \stackrel{(b)}{>} \alpha_{S, \tilde{k}} + I(U_{S, \tilde{k}+1}; Y_{\tilde{k}+1}|U_{S, \tilde{k}}) \nonumber \\ & \stackrel{(c)}{\ge} \alpha_{S, \tilde{k}} + I(U_{S, \tilde{k}}; Y_{\tilde{k}}|U_{S, \tilde{k}-1}), \tag{146} \end{align} $$

where (a) holds by (136c); (b) holds by (139); and (c) holds by holds by assumption (142a). We conclude that when (142a) holds, the upper bound on $C(M_1, \dots, M_K)$ in (103) is relaxed if everywhere one replaces $(U_{S,1}, U_{S,2}, \dots, U_{S,|S|-1})$ and $(\alpha_{S,1}, \dots, \alpha_{S,|S|})$ by $(\bar{U}_{S,1}, \bar{U}_{S,2}, \dots, \bar{U}_{S,|S|-1})$ and $(\bar{\alpha}_{S,1}, \dots, \bar{\alpha}_{S,|S|})$.

We now assume that (142b) holds. We show that the new constraints obtained for $k = \tilde{k}$ and for $k = \tilde{k}+1$ cannot be more stringent than the tighter of the two original constraints for $k = \tilde{k}$ and $k = \tilde{k}+1$.

Consider $k = \tilde{k}$. By (144) and (145) we have

$$ \begin{align} I(\bar{U}_{S,\tilde{k}}; Y_{\tilde{k}}|\bar{U}_{S,\tilde{k}-1}) &= I(U_{S,\tilde{k}}; Y_{\tilde{k}}|\bar{U}_{S,\tilde{k}-1}E) \nonumber \\ &= (1-\beta) \cdot I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}) \nonumber \\ &= \gamma \cdot I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}) \nonumber \\ &\quad + (1-\gamma) \cdot I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}). \tag{147} \end{align} $$

By (136b) and (147):

$$ \begin{align} \bar{\alpha}_{S, \tilde{k}} + I(\bar{U}_{S, \tilde{k}}; Y_{\tilde{k}}|\bar{U}_{S, \tilde{k}-1}) & \nonumber \\ &= (\gamma \alpha_{S, \tilde{k}} + (1-\gamma)\alpha_{S, \tilde{k}+1}) \nonumber \\ & \quad + \gamma I(U_{S, \tilde{k}}; Y_{\tilde{k}}|U_{S, \tilde{k}-1}) + (1-\gamma)I(U_{S, \tilde{k}+1}; Y_{\tilde{k}+1}|U_{S, \tilde{k}}) \nonumber \\ & \ge \min \{ \alpha_{S, \tilde{k}} + I(U_{S, \tilde{k}}; Y_{\tilde{k}}|U_{S, \tilde{k}-1}), \nonumber \\ & \quad \alpha_{S, \tilde{k}+1} + I(U_{S, \tilde{k}+1}; Y_{\tilde{k}+1}|U_{S, \tilde{k}}) \}. \tag{148} \end{align} $$
Let now $k = \tilde{k} + 1$. We have:

$$
\begin{align}
& I(\bar{U}_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|\bar{U}_{S,\tilde{k}}) \nonumber \\
& \stackrel{(a)}{=} (1-\beta)I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) \nonumber \\
& \qquad +\beta I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}-1}) \nonumber \\
& \stackrel{(b)}{=} (1-\beta)I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) \nonumber \\
& \qquad +\beta I(U_{S,\tilde{k}+1}, U_{S,\tilde{k}}; Y_{\tilde{k}+1}|U_{S,\tilde{k}-1}) \nonumber \\
& \stackrel{(c)}{=} I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) + \beta I(U_{S,\tilde{k}}; Y_{\tilde{k}+1}|U_{S,\tilde{k}-1}) \nonumber \\
& \stackrel{(d)}{\ge} I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) + \beta I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}) \nonumber \\
& \stackrel{(e)}{=} \gamma I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) + (1-\gamma)I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}), \tag{149}
\end{align}
$$

where (a) follows by the definition of $\bar{U}_{S,\tilde{k}}$ and $\bar{U}_{S,\tilde{k}+1}$; (b) by the Markov chain (68); (c) by the chain rule of mutual information and Markov chain (68); (d) by the degradedness of the channel (15b); (e) by the definition of $\beta$ in (144).

Therefore, by (136c):

$$
\begin{align}
& \bar{\alpha}_{S,k+1} + I(\bar{U}_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|\bar{U}_{S,\tilde{k}}) \nonumber \\
& \geq (1-\gamma) \cdot \alpha_{S,\tilde{k}} + \gamma \cdot \alpha_{S,\tilde{k}+1} \nonumber \\
& \quad + (1-\gamma) \cdot I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}) + \gamma \cdot I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) \nonumber \\
& \geq \min \{ \alpha_{S,\tilde{k}} + I(U_{S,\tilde{k}}; Y_{\tilde{k}}|U_{S,\tilde{k}-1}), \nonumber \\
& \qquad \alpha_{S,\tilde{k}+1} + I(U_{S,\tilde{k}+1}; Y_{\tilde{k}+1}|U_{S,\tilde{k}}) \}. \tag{150}
\end{align}
$$

We thus conclude that also when (142b) holds, the upper bound on $C(M_1, \dots, M_K)$ in (103) is relaxed if one replaces $(U_{S,1}, U_{S,2}, \dots, U_{S,|S|-1})$ and $(\alpha_{S,1}, \dots, \alpha_{S,K})$ by $(\bar{U}_{S,1}, \bar{U}_{S,2}, \dots, \bar{U}_{S,|S|-1})$ and $(\tilde{\alpha}_{S,1}, \dots, \tilde{\alpha}_{S,|S|})$.

## APPENDIX D

### PROOF OF REMARK 3

We first prove that the bound in Theorem 4 is loosened when each $\alpha_{S,k}^*$ is replaced by $\tilde{\alpha}_{S,k}$. Consider the intermediate Lemma 16 in the proof of Theorem 4, Appendix A. Relax the upper bound in this lemma by replacing for $k = 2, \dots, K$ constraint (122a) by

$$ \alpha_{S,k} \ge 0. \tag{151} $$

Following similar steps as in the proof of Lemma 17, see also [22, Lemma 12], it can be shown that this relaxed upper bound is not changed when one imposes that

$$ \alpha_{S,2} = \alpha_{S,3} = \dots = \alpha_{S,|S|}, $$

and

$$ \alpha_{S,1} = \frac{M_1}{N} \quad \text{or} \quad \alpha_{S,1} = \alpha_{S,2}. $$

Since constraints (123) are increasing in $\alpha_{S,1}, \dots, \alpha_{S,|S|}$, by constraint (122c), we conclude that the relaxed upper bound is loosest for

$$ \alpha_{S,1} = \frac{M_1}{N} \\ \alpha_{S,k} = \frac{|S| \sum_{i=1}^{|S|} M_{ji} - M_{j1}}{(|S|-1)N}, \quad k \in \{2, \dots, |S|-1\}, $$

i.e., for $\alpha_{S,k} = \tilde{\alpha}_{S,k}$.

We now prove that the bound in Theorem 4 is loosened when each $\alpha_{S,k}^*$ is replaced by $\tilde{\alpha}_{S,k}$. Consider again the intermediate Lemma 16 in Appendix A. Relax constraint (122a) by replacing it with $\alpha_{S,k} \ge 0$, for all $k = 1, \dots, K$. Following the steps in [22, Lemma 12], it can be shown that the new constraints are loosest if each

$$ \alpha_{S,k} = \tilde{\alpha}_{S,k}. \tag{153} $$

This concludes the proof.

## APPENDIX E

### PROOF OF PROPOSITION 7

For $\Delta = 0$, achievability follows by specializing Theorem 3 to $t = K - 1$ and to the input distribution $P_X$ that maximizes (74). In fact, for this input distribution:

$$ R^{(K-1)} = K C_{\text{avg}} = C_{\text{avg}} + \frac{\sum_{k=1}^{K} M_{\tilde{k}}^{*(K-1)}}{K \cdot N}. $$

For $\Delta > 0$, achievability follows from Proposition 1.

The converse is proved as follows. Consider cache sizes $M_1^{*(K-1)}, \dots, M_K^{*(K-1)}$ as given in (41). Apply Theorem 4, but consider only the constraints (69) corresponding to the sets $S = \{k\}$, for $k \in K$. Taking the average over the resulting $K$ constraints establishes that there exists a random variable $(X, Y_1, \dots, Y_K)$ satisfying (15b) and so that

$$ C(M_1^{(K-1)}, \dots, M_K^{(K-1)}) \le \frac{1}{K} \sum_{k \in K} I(X; Y_k) + \frac{1}{K} \sum_{k \in K} \frac{M_k^{(K-1)}}{N}. \tag{154} $$

Maximizing the right-hand side over input distributions $P_X$ yields the desired converse.

## APPENDIX F

### PROOF OF PROPOSITION 12

Relax the upper bound in Theorem 4 by considering constraints (69) only for the set of all receivers $S = K$, and by replacing each $\alpha_{S,k}^*$ by $\tilde{\alpha}_{S,k}$. Specializing the resulting relaxed bound to the erasure BC, one obtains the following upper bound:

$$ C(M_1, \dots, M_K) \le \max \min \left\{ (1 - \delta_1)\beta_1 + \frac{M_1}{N}, (1 - \delta_2)\beta_2 + \frac{KM - M_1}{N \cdot (K - 1)}, \dots, (1 - \delta_K)\beta_K + \frac{KM - M_1}{N \cdot (K - 1)} \right\}, \tag{155} $$

where the maximization is over the choice of parameters $\beta_1, \beta_2, \dots, \beta_K \ge 0$ satisfying

$$ \sum_{k=1}^{K} \beta_k \le 1. \tag{156} $$

The upper bound in the proposition is established by solving this maximization problem. In fact, by noticing that the bound is increasing in $\beta_1, \beta_2, \dots, \beta_K \ge 0$, and by first fixing $\beta_1$
and optimizing over the choices $\beta_2, \dots, \beta_K \ge 0$ summing to or
$1 - \beta_1$, we obtain

$$
\begin{align}
C(M_1, \dots, M_K) &\le \max_{\beta_1 \in [0,1]} \min \left\{ \beta_1 C_1 + \frac{M_1}{N}, \right. \nonumber \\
&\phantom{\le \max_{\beta_1 \in [0,1]} \min \left\{ \beta_1 C_1 + \frac{M_1}{N}, \right.} \left. (1-\beta_1) C_{[2, \dots, K]} + \frac{KM - M_1}{(K-1) \cdot N} \right\} \nonumber \\
&= \max_{\beta_1 \in [0,1]} \min \left\{ \beta_1 C_1, (1-\beta_1) C_{[2, \dots, K]} + \frac{KM - M_1}{(K-1) \cdot N} \right\} \nonumber \\
&\phantom{=} + \frac{M_1}{N}. \tag{157}
\end{align}
$$

If

$$
\frac{K(M - M_1)}{(K - 1) \cdot N} \geq C_1,
$$

then the maximum is achieved at $\beta_1 = 1$ and the upper bound
results in

$$
C(M_1, \dots, M_K) \le C_1 + \frac{M_1}{N}. \quad (158)
$$

Otherwise the maximum is at $\beta = \beta^*$, where

$$
\beta_1^* := \frac{C_{[2,...,K]} + \frac{K(M-M_1)}{(K-1) \cdot N}}{C_1 + C_{[2,...,K]}}, \quad (159)
$$

and the upper bound results in

$$
\begin{align}
C(M_1, \dots, M_K) &\le C_K + \frac{K(M-M_1)}{(K-1) \cdot N} \cdot \frac{C_1}{C_1 + C_{[2, \dots, K]}} + \frac{M_1}{N} \nonumber \\
&= C_K + \frac{K(M-M_1)}{(K-1) \cdot N} \cdot \frac{C_K}{C_{[2, \dots, K]}} + \frac{M_1}{N} \tag{160}
\end{align}
$$

where we used that for erasure BCs

$$
C_K = \frac{C_1 \cdot C_{[2,...,K]}}{C_1 + C_{[2,...,K]}}. \quad (161)
$$

## APPENDIX G

### PROOF OF COROLLARY 13

Fix $t \in \mathcal{K}$ and $S = \{1, \dots, t\}$. For the considered channel

$$
(r_1, \dots, r_t) \in C_S \iff \sum_{k=1}^{t} r_k \le 1. \quad (162)
$$

The upper bound in Corollary 5 thus states that for this noise-
free BC a rate-memory tuple (R, M₁, ..., Mₖ) is achievable
only if

$$
tR - \sum_{k=1}^{t} \alpha_{S,k}^{*} \le 1. \quad (163)
$$

This is equivalent to the following bound on the capacity-
memory tradeoff

$$
C(M_1, \dots, M_K) \le \frac{1}{t} \left( 1 + \sum_{k=1}^{t} \alpha_{S,k}^* \right). \quad (164)
$$

Notice that the sum $\sum_{k=1}^{t} \alpha_{S,k}^*$ takes on only two different values, depending on the outcomes of the minimizations defining $\alpha_{S,k}^*$. It is either

$$
\sum_{k=1}^{t} \alpha_{S,k}^{*} = \frac{t \sum_{k=1}^{t} M_k}{N} \quad (165a)
$$

$$
\sum_{k=1}^{t} \alpha_{S,k}^{*} = \sum_{k=1}^{t} \frac{\sum_{i=1}^{k} M_i}{N - k + 1}. \quad (165b)
$$

Combining (164) with (165), applying the correspondence
$\rho = R^{-1}$ and $m_k = \frac{M_k}{R}$, and setting $m_1 = m_2 = \dots = m_k = m$ yields,

$$
1 \le \frac{1}{t} \left( \rho + m \cdot \min \left\{ \frac{t^2}{N}, \sum_{k=1}^{t} \frac{k}{N-k+1} \right\} \right), \quad (166)
$$

which is equivalent to the bound in the corollary.

REFERENCES

[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” *IEEE Trans. Inf. Theory*, vol. 60, no. 5, pp. 2856–2867, May 2014.

[2] Z. Chen, P. Fan, and K. B. Letaief, “Fundamental limits of caching: Improved bounds for users with small buffers,” *IET Commun.*, vol. 10, no. 17, pp. 2315–2318, Nov. 2016.

[3] K. Wan, D. Tuninetti, and P. Piantanida, “On caching with more users than files,” in *Proc. IEEE Int. Symp. Inf. Theory*, Jul. 2016, pp. 135–139.

[4] S. Sahraei and M. Gastpar, “K users caching two files: An improved achievable rate,” in *Proc. Annu. Conf. Inf. Sci. Syst.*, Mar. 2016, pp. 620–624.

[5] C. Tian and J. Chen, “Caching and delivery via interference elimination,” *IEEE Trans. Inf. Theory*, vol. 64, no. 3, pp. 1548–1560, Mar. 2018.

[6] M. M. Amiri, Q. Yang, and D. Gündüz, “Coded caching for a large number of users,” in *Proc. IEEE Inf. Theory Workshop*, Sep. 2016, pp. 171–175.

[7] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,” *IEEE Trans. Inf. Theory*, vol. 64, no. 2, pp. 1281–1296, Feb. 2018.

[8] J. Gómez-Vilardebó, “Fundamental limits of caching: Improved rate-memory tradeoff with coded prefetching,” *IEEE Trans. Commun.*, vol. 66, no. 10, pp. 4488–4497, Oct. 2018.

[9] C. Tian, “On the fundamental limits of coded caching and exact-repair regenerating codes,” in *Proc. Int. Symp. Netw. Coding (NetCod)*, Sydney, NSW, Australia, Jun. 2015, pp. 56–60.

[10] A. Sengupta, R. Tandon, and T. C. Clancy, “Improved approximation of storage-rate tradeoff for caching via new outer bounds,” in *Proc. IEEE Int. Symp. Inf. Theory*, Hong Kong, Jun. 2015, pp. 1691–1695.

[11] H. Ghasemi and A. Ramamoorthy, “Improved lower bounds for coded caching,” *IEEE Trans. Inf. Theory*, vol. 63, no. 7, pp. 4388–4413, Jul. 2017.

[12] C. Y. Wang, S. H. Lim, and M. Gastpar, “A new converse bound for coded caching,” in *Proc. IEEE Inf. Theory Appl. Workshop*, Jan. 2016, pp. 1–6.

[13] C. Tian, “Symmetry, demand types and outer bounds in caching systems,” in *Proc. IEEE Int. Symp. Inf. Theory*, Jul. 2016, pp. 825–829.

[14] M. M. Amiri, Q. Yang, and D. Gündüz, “Decentralized caching and coded delivery with distinct cache capacities,” *IEEE Trans. Commun.*, vol. 65, no. 11, pp. 4657–4669, Nov. 2017.

[15] S. Wang, W. Li, X. Tian, and H. Liu, “Fundamental limits of heterogeneous cache,” *CoRR*, vol. abs/1504.01123, 2015. [Online]. Available: http://arxiv.org/abs/1504.01123

[16] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Centralized coded caching with heterogeneous cache sizes,” in *Proc. IEEE Wireless Commun. Netw. Conf. (WCNC)*, San Francisco, CA, USA, Mar. 2017, pp. 1–6.

[17] A. M. Ibrahim, A. A. Zewail, and A. Yener, “Optimization of heterogeneous caching systems with rate limited links,” in *Proc. ICC*, May 2017, pp. 1–6.

[18] W. Huang, S. Wang, L. Ding, F. Yang, and W. Zhang, “The performance analysis of coded cache in wireless fading channel,” *CoRR*, vol. abs/1504.01452, 2015. [Online]. Available: http://arxiv.org/abs/1504.01452

[19] M. Ji and R. R. Chen, “Caching and coded multicasting in slow fading environment,” in *Proc. IEEE Wireless Commun. Netw. Conf. (WCNC)*, Mar. 2017, pp. 1–6.

[20] J. Zhang and P. Elia, “Wireless coded caching: A topological perspective,” in *Proc. IEEE Int. Symp. Inf. Theory*, Jun. 2017, pp. 401–405.

[21] R. Timo and M. Wigger, “Joint cache-channel coding over erasure broadcast channels,” in *Proc. Int. Symp. Wireless Commun. Syst.*, Aug. 2015, pp. 201–205.
[22] S. Saeedi Bidokhti, M. A. Wigger, and R. Timo, "Noisy broadcast networks with receiver caching," *IEEE Trans. Inf. Theory*, vol. 64, no. 11, pp. 6996-7016, Nov. 2018.

[23] M. M. Amiri and D. Gündüz, "Cache-aided data delivery over erasure broadcast channels," in *Proc. IEEE Int. Conf. Commun.*, May 2017, pp. 1-6.

[24] A. S. Cacciapuoti, M. Caleffi, M. Ji, J. Llorca, and A. M. Tulino, "Speeding up future video distribution via channel-aware caching-aided coded multicast," *IEEE J. Sel. Areas Commun.*, vol. 34, no. 8, pp. 2207-2218, Aug. 2016.

[25] P. Hassanzadeh, E. Erkip, J. Llorca, and A. Tulino, "Distortion-memory tradeoffs in cache-aided wireless video delivery," in *Proc. Allerton Conf. Commun., Control, Comput.*, Sep. 2015, pp. 1150-1157.

[26] A. Ghorbel, M. Kobayashi, and S. Yang, "Content delivery in erasure broadcast channels with cache and feedback," *IEEE Trans. Inf. Theory*, vol. 62, no. 11, pp. 6407-6422, Nov. 2016.

[27] J. Zhang and P. Elia, "Fundamental limits of cache-aided wireless BC: Interplay of coded-caching and CSIT feedback," *IEEE Trans. Inf. Theory*, vol. 63, no. 5, pp. 3142-3160, May 2017.

[28] E. Piovano, H. Joudeh, and B. Clerckx, "On coded caching in the overloaded MISO broadcast channel," in *Proc. IEEE Int. Symp. Inf. Theory*, Aachen, Germany, Jun. 2017, pp. 2795-2799.

[29] S. Yang, K.-H. Ngo, and M. Kobayashi, "Content delivery with coded caching and massive MIMO in 5G," in *Proc. 9th Int. Symp. Turbo Codes Iterative Inf. Process. (ISTC)*, Brest, France, Sep. 2016, pp. 370-374.

[30] S. P. Shariatpanahi, G. Caire, and B. H. Khalaj, "Physical-layer schemes for wireless coded caching," *IEEE Trans. Inf. Theory*, vol. 65, no. 5, pp. 2792-2807, May 2019.

[31] P. Hassanzadeh, A. M. Tulino, J. Llorca, and E. Erkip, "Broadcast caching networks with two receivers and multiple correlated sources," in *Proc. Asilomar Conf. Signals, Syst., Comput.*, Oct. 2017, pp. 1449-1454.

[32] Q. Yang, P. Hassanzadeh, D. Gündüz, and E. Erkip, "Centralized caching and delivery of correlated contents over a Gaussian broadcast channel," in *Proc. Int. Symp. Modeling Optim. Mobile, Ad Hoc, Wireless Netw. (WiOpt)*, May 2018, pp. 1-6.

[33] A. Ibrahim, A. Zewail, and A. Yener, "On coded caching with heterogeneous distortion requirements," in *Proc. IEEE Inf. Theory Appl. Workshop*, Feb. 2018, pp. 1-9.

[34] E. Tuncel, "Slepian-Wolf coding over broadcast channels," *IEEE Trans. Inf. Theory*, vol. 52, no. 4, pp. 1469-1482, Apr. 2006.

[35] S. Saeedi Bidokhti, M. Wigger, and R. Timo, "An upper bound on the capacity-memory tradeoff of degraded broadcast channels," in *Proc. Int. Symp. Turbo Codes Iterative Inf. Process.*, Sep. 2016, pp. 350-354.

[36] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, "Characterizing the rate-memory tradeoff in cache networks within a factor of 2," in *Proc. IEEE Int. Symp. Inf. Theory*, Jun. 2017, pp. 386-390.

[37] C.-Y. Wang, S. Saeedi Bidokhti, and M. Wigger, "Improved converses and gap results for coded caching," *IEEE Trans. Inf. Theory*, vol. 64, no. 11, pp. 7051-7062, Nov. 2018.

[38] R. G. Gallager, "Capacity and coding for degraded broadcast channels," *Probl. Peredachi Inf.*, vol. 10, no. 3, pp. 185-193, 1974.

[39] P. Bergmans, "A simple converse for broadcast channels with additive white Gaussian noise (Corresp.)," *IEEE Trans. Inf. Theory*, vol. IT-20, no. 2, pp. 279-280, Mar. 1974.

[40] A. E. Gamal and Y.-H. Kim, *Network Information Theory*. Cambridge, U.K.: Cambridge Univ. Press, 2011.

[41] M. Wigger, R. Timo, and S. Shamai, "Complete interference mitigation through receiver-caching in Wyner's networks," in *Proc. IEEE Inf. Theory Workshop*, Sep. 2016, pp. 335-339.

[42] Q. Yan, M. Cheng, X. Tang, and Q. Chen, "On the placement delivery array design for centralized coded caching scheme," *IEEE Trans. Inf. Theory*, vol. 63, no. 9, pp. 5821-5833, Sep. 2017.

[43] K. Shanmugam, A. M. Tulino, and A. G. Dimakis, "Coded caching with linear subpacketization is possible using Ruzsa-Szeméredi graphs," in *Proc. ISIT*, Jun. 2017, pp. 1237-1241.

[44] L. Tang and A. Ramamoorthy, "Coded caching schemes with reduced subpacketization from linear block codes," *IEEE Trans. Inf. Theory*, vol. 64, no. 4, pp. 3099-3120, Apr. 2018.

[45] T. M. Cover and J. A. Thomas, *Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)*. Hoboken, NJ, USA: Wiley, 2006.

Shirin Saeedi Bidokhti (S'09–M'12) is an assistant professor in the Department of Electrical and Systems Engineering at the University of Pennsylvania (UPenn). She received the B.Sc. degree in Electrical Engineering from University of Tehran in 2005, and the M.Sc and Ph.D. degrees in Communication Systems from École Polytechnique Fédérale de Lausanne (EPFL) in 2007 and 2012, respectively. Before joining UPenn in 2017, she was a postdoctoral fellow with the Institute for Communications Engineering at the Technische Universität München (2013-2015), a postdoctoral fellow with the Department of Electrical Engineering at Stanford University (2015-2017), and a postdoctoral research scholar with the Department of Electrical Engineering at the Pennsylvania State University (2017). She is a recipient of the 2019 NSF-CRII Research Initiative award and the prospective researcher and advanced postdoctoral fellowships from the Swiss National Science Foundation. Her research interests include network information theory, network coding, and data compression.

Michèle Wigger (S'05–M'09–SM'14) received the M.Sc. degree in electrical engineering, with distinction, and the Ph.D. degree in electrical engineering both from ETH Zurich in 2003 and 2008, respectively. In 2009, she was first a post-doctoral fellow at the University of California, San Diego, USA, and then joined Telecom Paris Tech, Paris, France, where she is currently a Full Professor. Dr. Wigger has held visiting professor appointments at the Technion-Israel Institute of Technology and ETH Zurich. Dr. Wigger has previously served as an Associate Editor of the IEEE COMMUNICATIONS LETTERS, and is now Associate Editor for Shannon Theory of the IEEE TRANSACTIONS ON INFORMATION THEORY. She is currently also serving on the Board of Governors of the IEEE Information Theory Society. Dr. Wigger's current research interests are in distributed source coding, distributed detection systems, free-space optical communication, caching systems, and networks with mixed-delay constraints.

Aylin Yener (S'91–M'01–SM'14–F'15) received the B.Sc. degree in electrical and electronics engineering and the B.Sc. degree in physics from Bogazici University, Istanbul, Turkey, and the M.S. and Ph.D. degrees in electrical and computer engineering from the Wireless Information Network Laboratory (WINLAB), Rutgers University, New Brunswick, NJ, USA. She is a Distinguished Professor of Electrical Engineering at The Pennsylvania State University, University Park, PA, USA, where she joined the faculty as an assistant professor in 2002. Since 2017, she is also a Dean's Fellow in the College of Engineering at The Pennsylvania State University. She was a visiting professor of Electrical Engineering at Stanford University in 2016-2018 and a visiting associate professor in the same department in 2008-2009. Her current research interests are in information security, green communications, caching systems, and more generally in the fields of information theory, communication theory and networked systems. She received the NSF CAREER Award in 2003, the Best Paper Award in Communication Theory from the IEEE International Conference on Communications in 2010, the Penn State Engineering Alumni Society (PSEAS) Outstanding Research Award in 2010, the IEEE Marconi Prize Paper Award in 2014, the PSEAS Premier Research Award in 2014, the Leonard A. Doggett Award for Outstanding Writing in Electrical Engineering at Penn State in 2014, the IEEE Women in Communications Engineering Outstanding Achievement Award in 2018, and the IEEE Communications Society Best Tutorial Paper Award in 2019. She is a distinguished lecturer for the IEEE Information Theory Society (2019-2020), the IEEE Communications Society (2018-2020) and the IEEE Vehicular Technology Society (2017-2019). Dr. Yener is serving as the vice president of the IEEE Information Theory Society in 2019. Previously she was the second vice president (2018), member of the Board of Governors (2015-2018) and the treasurer (2012-2014) of the IEEE Information Theory Society. She served as the Student Committee Chair for the IEEE Information Theory Society (2007-2011), and was the co-Founder of the Annual School of Information Theory in North America in 2008. She was a Technical (Co)-Chair for various symposia/tracks at the IEEE ICC, PIMRC, VTC, WCNC, and Asilomar in 2005, 2008-2014 and 2018. Previously, she served as an Editor for the IEEE TRANSACTIONS ON COMMUNICATIONS (2009-2012), an Editor for the IEEE TRANSACTIONS ON MOBILE COMPUTING (2017-2018), and an Editor and an Editorial Advisory Board Member for the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS (2001-2012). She also served a Guest Editor for the IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY in 2011, and the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS in 2015. Currently, she serves as a Senior Editor for the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS and is on the inaugural Senior Editorial Board of the IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY.