Ferkans — Interactive Telecom Tutor

The Headline Result

We are now ready for the headline result of coded caching. Having built the placement (§2.2) and verified the delivery (§2.3), the rate formula falls out as a direct counting argument. The result is clean, memorable, and — when first seen — slightly astonishing: the rate decomposes into a local factor $(1 - M/N)$ times a coded factor $(1 + KM/N)^{-1}$ , with the latter growing the total gain without bound in $K$ .

Theorem: Maddah-Ali–Niesen Memory-Load Theorem

Let $K \in \mathbb{N}$ , $N \in \mathbb{N}$ , and $M \in \{0, N/K, 2N/K, \ldots, N\}$ , i.e., $t = K M/N \in \{0, 1, \ldots, K\}$ is integer. Then the MAN scheme achieves the worst-case delivery rate $\boxed{\; R_{\text{MAN}}(M) \;=\; \frac{K - t}{t + 1} \;=\; K \cdot \frac{1 - M/N}{1 + K M/N}\; }.$

We send $\binom{K}{t+1}$ coded messages, each of size $F/\binom{K}{t}$ bits. Total bits is $\binom{K}{t+1}/\binom{K}{t} \cdot F = (K-t)/(t+1) \cdot F$ . Rate equals total bits divided by $F$ : done. The only remaining question is whether a shorter scheme exists — that is Chapter 3.

Proof

Count coded messages

The delivery phase transmits one coded message $X_{\mathcal{S}'}$ per $(t+1)$ -subset of $[K]$ . Number of such subsets: $\binom{K}{t+1}$ .

Size of each coded message

Each $X_{\mathcal{S}'}$ is an XOR of $t+1$ subfiles, each of size $F/\binom{K}{t}$ bits. The XOR preserves size, so $|X_{\mathcal{S}'}| = F/\binom{K}{t}$ bits.

Total delivery bits

$\text{Total bits} \;=\; \binom{K}{t+1} \cdot \frac{F}{\binom{K}{t}} \;=\; F \cdot \frac{K-t}{t+1}.$ $Using the identity$ \binom{K}{t+1}/\binom{K}{t} = (K-t)/(t+1)$.

Rate in file units

The rate $R$ is the total delivery bits divided by $F$ : $R \;=\; \frac{K - t}{t + 1}.$

Substitute $t = KM/N$

With $t = KM/N$ : $R \;=\; \frac{K - KM/N}{KM/N + 1} \;=\; K \cdot \frac{1 - M/N}{1 + KM/N}.$ $\blacksquare$

Correctness (already proven in §2.3)

Theorem §2.3 showed every user decodes its requested file. Hence the MAN scheme is a valid $(M, R)$ scheme with $R = K(1-M/N)/(1+KM/N)$ .

Key Takeaway

Coded caching gain = $1 + t$ . Compared with uncoded delivery ( $R_{\text{unc}} = K(1-M/N)$ ), the MAN scheme divides the rate by $1 + t$ . This is a multiplicative saving that grows with the aggregate cache size, not just per-user cache. For large networks this gain dominates the trivial local cache gain.

Memory–Load Tradeoff: MAN vs. Uncoded

The definitive plot of Chapter 2. The blue solid curve is the MAN rate $R = K(1-M/N)/(1+KM/N)$ ; the red dashed curve is the uncoded baseline $R_{\text{unc}} = K(1-M/N)$ . Comparison curves at $K/2$ and $2K$ show that the MAN rate shrinks as $K$ grows: more users = more coded multicasting opportunities. For $K \to \infty$ at fixed $M/N$ , the MAN rate saturates at $(1-M/N)/(M/N) = 1/\mu - 1$ , a finite limit independent of $K$ .

Parameters

Number of users K10

Number of files N10

MAN Rate vs. Number of Users (at Fixed $M/N$ )

As $K$ grows at fixed memory ratio $M/N$ , the uncoded rate $K(1-M/N)$ grows linearly, while the MAN rate $K(1-M/N)/(1+KM/N)$ saturates at $(1-M/N)/(M/N)$ . The gap between the two curves is the coded caching gain $1 + KM/N$ , which is unbounded in $K$ . This is the single most important qualitative feature of coded caching.

Parameters

Memory ratio M/N0.2

Max number of users K100

🎓CommIT Contribution(2014)

The Maddah-Ali–Niesen Scheme — Framework

M. A. Maddah-Ali, U. Niesen, G. Caire — IEEE Transactions on Information Theory

The MAN scheme opened the field of coded caching. Though the 2014 paper lists Maddah-Ali and Niesen as authors (Caire was in the acknowledgments), the subsequent CommIT program — extending the scheme to wireless, D2D, correlated-files, privacy, and cloud-RAN settings — is a sustained collaboration led by Caire. The basic scheme presented in this chapter is the "shared link" version; every later chapter builds on this scaffold, so mastering it is non-optional.

Key insight (restated). The placement is combinatorial (each subfile in exactly $t$ caches, uniformly distributed); the delivery is coded (one XOR per $(t+1)$ -subset). Together they achieve $R = K(1-M/N)/(1+KM/N)$ — a rate that is later proven optimal under uncoded placement (Chapter 3).

coded-cachingachievabilityman-schemeView Paper →

Two Illuminating Extremes

The formula $R_{\text{MAN}} = K(1-M/N)/(1+KM/N)$ has two informative limits:

Small $M$ ( $t \approx 0$ ): $R_{\text{MAN}} \approx K(1 - M/N) \cdot 1 = K - KM/N$ . Almost no coding gain — each user needs a nearly full unicast, as caches are too small to create multicast opportunities.

Large $M$ ( $t \approx K$ ): $R_{\text{MAN}} \approx 1 \cdot (1 - 1)/(K+1) = 0$ . Naturally — if every user can cache the whole library, no delivery is needed.

Intermediate $M$ ( $t$ moderate): The gain $(1 + t)^{-1}$ is substantial. For $t = 10$ , the MAN rate is $\frac{1}{11}$ of the uncoded rate. This is the regime where coded caching shines.

Common Mistake: Rate Is in File Units, Not Bits

Mistake:

Stating " $R_{\text{MAN}} = 0.5$ " without specifying the unit and being confused when comparing to capacity results.

Correction:

$R$ is measured in files per shared-link channel use, where one shared-link channel use has capacity $F$ bits (in the error-free model). A rate $R = 0.5$ means the server sends $0.5 F$ bits per delivery round to satisfy all $K$ users. Equivalently, the rate is dimensionless (files/files). When you later combine coded caching with a noisy channel of capacity $C$ bits/sec, the effective file delivery time is $R F / C$ seconds per round.

Quick Check

For $K = 20$ , $N = 40$ , $M = 10$ , compute the MAN worst-case rate.

$R = 1$

$R = 2.5$

$R = 5$

$R = 15$

Correction:

R = 2.5

Correct. $t = KM/N = 5$ . $R_{\text{MAN}} = (K-t)/(t+1) = 15/6 = 2.5$ file units. Equivalently: $R = 20 \cdot (1 - 0.25)/(1 + 0.25 \cdot 20) = 20 \cdot 0.75/6 = 2.5$ .

The Memory-Load Theorem and Its Proof

The Headline Result

Theorem: Maddah-Ali–Niesen Memory-Load Theorem

Count coded messages

Size of each coded message

Total delivery bits

Rate in file units

Substitute $t = KM/N$

Correctness (already proven in §2.3)

Key Takeaway

Memory–Load Tradeoff: MAN vs. Uncoded

Parameters

MAN Rate vs. Number of Users (at Fixed M/NM/NM/N)

Parameters

The Maddah-Ali–Niesen Scheme — Framework

Two Illuminating Extremes

Common Mistake: Rate Is in File Units, Not Bits

Quick Check

MAN Rate vs. Number of Users (at Fixed $M/N$ )