Prerequisites & Notation

Before You Begin

This chapter builds the Maddah-Ali–Niesen scheme from scratch. The required machinery is minimal — basic probability, XOR arithmetic over $\mathbb{F}_2$ , and a little combinatorics — but you should be comfortable with each item before starting.

The shared-link coded caching model (Ch 1)(Review ch01)
Self-check: Can you state the placement/delivery split and the worst-case rate $R^*(M)$ ?
Binomial coefficients and $t$ -subsets of $[K]$
Self-check: For $K = 5$ , $t = 2$ , can you enumerate $\binom{5}{2} = 10$ subsets?
XOR over $\mathbb{F}_2^F$ (bitwise addition of file-sized vectors)
Self-check: Given $a \oplus b \oplus c$ and $a, b$ , can you recover $c$ ?
Basic entropy bounds $\mathrm{H}(X, Y) \leq \mathrm{H}(X) + \mathrm{H}(Y)$ (Review ch01)
Self-check: Can you identify when equality holds (independence)?
Worst-case demand vectors in $[N]^K$ (Review ch01)
Self-check: Can you explain why worst-case means all distinct demands when $K \leq N$ ?

Notation for This Chapter

Symbols introduced in Chapter 2. The MAN scheme uses a heavy but systematic notational load: subfiles $W_{n,\mathcal{S}}$ and coded messages $X_{\mathcal{S}'}$ indexed by subsets of $[K]$ .

Symbol	Meaning	Introduced
$t = K M/N$	Coded caching gain parameter (assumed integer for the base scheme)	s01
$W_{n,\mathcal{S}}$	Subfile of file $W_n$ indexed by subset $\mathcal{S} \subseteq [K]$ , $\|\mathcal{S}\| = t$	s02
$F$	Subpacketization: number of subfiles per file; $F = \binom{K}{t}$ in the base scheme	s02
$\mathcal{S}$	$t$ -subset of $[K]$ : $\|\mathcal{S}\| = t$	s02
$\mathcal{S}'$	$(t+1)$ -subset of $[K]$ : $\|\mathcal{S}'\| = t+1$ ; indexes a coded message	s03
$X_{\mathcal{S}'}$	Coded XOR message for subset $\mathcal{S}'$ : $\bigoplus_{k \in \mathcal{S}'} W_{d_k, \mathcal{S}' \setminus \{k\}}$	s03
$\mathcal{Z}_k$	Cache content of user $k$ : the set of all $W_{n,\mathcal{S}}$ for which $k \in \mathcal{S}$	s02

← Ch 1 The MAN Scheme at a Glance