Ferkans — Interactive Telecom Tutor

The Combinatorial Magic

The delivery phase is where the real cleverness lives. Given the placement we just built, the server wants to send a short message that simultaneously satisfies all $K$ users. The scheme's core trick is to index the coded messages by $(t+1)$ -subsets — one message per subset, summing over the $t+1$ users' missing subfiles.

The beauty: each user in the $(t+1)$ -subset is missing exactly one of the summands (the one indexed by the $t$ -subset not containing that user), and has all others in its cache. XOR then cancels everything except the one summand the user needs — pure information-theoretic interference cancellation, via the algebra of $\mathbb{F}_2$ .

MAN Delivery Algorithm

Complexity: Number of coded messages:

\binom{K}{t+1}

. Each message is one XOR of

t+1

subfiles, each of size

F/\binom{K}{t}

. Total delivery bits:

\binom{K}{t+1} \cdot F/\binom{K}{t} = F \cdot (K-t)/(t+1) = R_{\text{MAN}} \cdot F

.

Input: Demand vector

\mathbf{d} = (d_1, \ldots, d_K) \in [N]^K

.

Subfiles

\{W_{n,\mathcal{S}}\}

from the placement phase.

Output: Coded transmission sequence

(X_{\mathcal{S}'})_{\mathcal{S}'}

.

1.

F_{\text{sub}} \leftarrow F / \binom{K}{t}

2.

\mathcal{X} \leftarrow \{\}

// transmission buffer

3. for each

(t+1)

-subset

\mathcal{S}' \subseteq [K]

do

4.

\quad X_{\mathcal{S}'} \leftarrow \mathbf{0}^{F_{\text{sub}}}

// empty vector

5.

\quad

for each user

k \in \mathcal{S}'

do

6.

\quad\quad X_{\mathcal{S}'} \leftarrow X_{\mathcal{S}'} \oplus W_{d_k,\, \mathcal{S}' \setminus \{k\}}

7.

\quad

end for

8.

\quad \mathcal{X} \leftarrow \mathcal{X} \cup \{X_{\mathcal{S}'}\}

9. end for

10. Broadcast all

\binom{K}{t+1}

messages

X_{\mathcal{S}'}

on the shared link.

11. return

\mathcal{X}

.

Theorem: Each User Decodes Its Requested File

Under the MAN placement and delivery of this chapter, every user $k$ can recover $W_{d_k}$ using its cache $\mathcal{Z}_{k}$ and the $\binom{K}{t+1}$ coded messages $(X_{\mathcal{S}'})_{\mathcal{S}'}$ .

User $k$ 's missing subfiles of $W_{d_k}$ are $W_{d_k, \mathcal{T}}$ for $t$ -subsets $\mathcal{T}$ with $k \notin \mathcal{T}$ — a total of $\binom{K-1}{t}$ missing subfiles. The coded messages $X_{\mathcal{S}'}$ containing $k$ (there are $\binom{K-1}{t}$ of them, one per $(t+1)$ -subset containing $k$ ) provide exactly those missing subfiles.

Proof

Fix a user $k$ and a missing subfile $W_{d_k, \mathcal{T}}$

User $k$ needs $W_{d_k, \mathcal{T}}$ for every $t$ -subset $\mathcal{T}$ with $k \notin \mathcal{T}$ . Fix one such $\mathcal{T}$ .

Identify the coded message that delivers it

Let $\mathcal{S}' = \mathcal{T} \cup \{k\}$ — a $(t+1)$ -subset containing $k$ . The coded message is $X_{\mathcal{S}'} \;=\; \bigoplus_{j \in \mathcal{S}'} W_{d_j,\, \mathcal{S}' \setminus \{j\}}.$ The summand for $j = k$ is $W_{d_k,\, \mathcal{S}' \setminus \{k\}} = W_{d_k, \mathcal{T}}$ — exactly what user $k$ needs.

Show all other summands are in user $k$'s cache

For $j \in \mathcal{S}' \setminus \{k\}$ (i.e., $j \in \mathcal{T}$ ), the summand is $W_{d_j, \mathcal{S}' \setminus \{j\}}$ . The index set is $\mathcal{S}' \setminus \{j\} = (\mathcal{T} \cup \{k\}) \setminus \{j\}$ , which contains $k$ (because $j \neq k$ ). By the placement rule, user $k$ has this subfile in cache. ✓

Decode via XOR cancellation

User $k$ computes $W_{d_k, \mathcal{T}} \;=\; X_{\mathcal{S}'} \;\oplus\; \bigoplus_{j \in \mathcal{T}} W_{d_j, \mathcal{S}' \setminus \{j\}},$ where the second XOR is over subfiles all in $\mathcal{Z}_{k}$ . Thus user $k$ recovers $W_{d_k, \mathcal{T}}$ .

Repeat over all $\binom{K-1}{t}$ missing subfiles

Since $\mathcal{T}$ was an arbitrary $t$ -subset not containing $k$ , user $k$ recovers all $\binom{K-1}{t}$ missing subfiles. Combined with the $\binom{K-1}{t-1}$ cached subfiles, user $k$ has all $\binom{K-1}{t} + \binom{K-1}{t-1} = \binom{K}{t}$ subfiles of $W_{d_k}$ — the entire file. $\blacksquare$

Example: Delivery Walkthrough: $K = 4$ , $t = 2$ , Demand $(1,2,3,4)$

For $K = 4$ , $t = 2$ , $N \geq 4$ , and demand vector $(d_1, d_2, d_3, d_4) = (1, 2, 3, 4)$ (all distinct), write out all coded messages and verify user 1 can decode $W_1$ .

Solution

List $(t+1)$-subsets

$(t+1) = 3$ -subsets of $[4]$ : $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$ . Four messages.

Compute each coded message

$X_{\{1,2,3\}} = W_{1,\{2,3\}} \oplus W_{2,\{1,3\}} \oplus W_{3,\{1,2\}}$ .

$X_{\{1,2,4\}} = W_{1,\{2,4\}} \oplus W_{2,\{1,4\}} \oplus W_{4,\{1,2\}}$ .

$X_{\{1,3,4\}} = W_{1,\{3,4\}} \oplus W_{3,\{1,4\}} \oplus W_{4,\{1,3\}}$ .

$X_{\{2,3,4\}} = W_{2,\{3,4\}} \oplus W_{3,\{2,4\}} \oplus W_{4,\{2,3\}}$ .

User 1 decodes W_1

User 1 has in cache: $\{W_{n,\{1,2\}}, W_{n,\{1,3\}}, W_{n,\{1,4\}}\}$ for each $n$ . Missing: $\{W_{n,\{2,3\}}, W_{n,\{2,4\}}, W_{n,\{3,4\}}\}$ .

User 1 uses $X_{\{1,2,3\}}$ : the summand $W_{1,\{2,3\}}$ is missing, but $W_{2,\{1,3\}}$ and $W_{3,\{1,2\}}$ are in cache. XOR-cancel: recover $W_{1,\{2,3\}}$ .

From $X_{\{1,2,4\}}$ : recover $W_{1,\{2,4\}}$ (cancel $W_{2,\{1,4\}}, W_{4,\{1,2\}}$ ).

From $X_{\{1,3,4\}}$ : recover $W_{1,\{3,4\}}$ (cancel $W_{3,\{1,4\}}, W_{4,\{1,3\}}$ ).

User 1 now has all $\binom{4}{2} = 6$ subfiles of $W_1$ . ✓ Similar for users 2, 3, 4.

Count messages and rate

4 coded messages, each of size $F/\binom{4}{2} = F/6$ . Total bits: $4F/6 = 2F/3$ . Rate $R = 2/3$ file. MAN formula: $R = K(K-t)/[K(t+1)] \cdot (1 - ...)$ . Quick check: $R = (K-t)/(t+1) = 2/3$ . ✓ Match.

Coded Multicast Structure

Visualize the structural quantities of the MAN delivery phase: the number of users served per coded message ( $t+1$ ), the number of coded messages transmitted ( $\binom{K}{t+1}$ ), the subpacketization per file ( $\binom{K}{t}$ ), and the uncoded baseline ( $K$ unicasts). Log-scale y-axis to span orders of magnitude.

Parameters

Number of users K8

Coded caching gain t2

Connection to Index Coding

The delivery phase is an instance of the index coding problem: given users with side information and conflicting demands, find the minimum-length broadcast to satisfy them all. For the MAN structure, the specific placement makes the index coding problem nice (its optimum is achieved by simple XORs). For general placements, index coding is NP-hard — we return to this in Chapter 4.

Historical Note: From Network Coding to Coded Caching

2000–2014

The idea that XORs can simultaneously carry information for multiple receivers has a distinguished history. Ahlswede, Cai, Li, and Yeung (2000) introduced network coding; the butterfly network showed XOR multicasting beats routing. Katti et al. (2008) demonstrated it in practice ("COPE: XORs in the Air"). Maddah-Ali and Niesen (2013–2014) then showed that this same idea — encoded across pre-placed caches — could eliminate the link bottleneck in CDN-like settings.

What was genuinely new was not the XOR delivery; it was that the caches could be designed specifically to make XOR delivery extraordinarily efficient. The combinatorial placement is a design choice that makes the delivery phase simple and short. This conceptual separation — engineer the side information for the receiver — marks coded caching's departure from classical network coding.

Delivery Phase: XOR Coded Multicast