Prerequisites & Notation

Before You Begin

This chapter tackles the practical obstacle that has kept coded caching out of production systems: subpacketization. Prerequisites: MAN placement/delivery, combinatorial basics, and index coding.

MAN placement with $\binom{K}{t}$ subfiles (Ch 2)(Review ch02)
Self-check: Can you compute subpacketization for $K = 20$ , $t = 3$ ?
Index coding and graph-coloring (Ch 4)(Review ch04)
Self-check: Can you connect MAN's conflict graph to chromatic number?
Combinatorial designs basics
Self-check: What is a balanced incomplete block design (BIBD)?
Polynomial vs exponential complexity
Self-check: Why is $\binom{K}{K/4}$ exponential in $K$ ?
Stirling's approximation
Self-check: Can you estimate $\binom{K}{t}$ for large $K$ ?

Notation for This Chapter

Symbols for PDA and subpacketization analysis.

Symbol	Meaning	Introduced
$F$	Subpacketization: number of subfiles per file	s01
$F_{\text{MAN}} = \binom{K}{t}$	MAN subpacketization — exponential in $K$	s01
$\mathbf{P}$	Placement Delivery Array (PDA) — $F \times K$ integer matrix	s02
$\mathrm{PDA}(K, F, Z, S)$	PDA with $K$ users, $F$ subfiles, $Z$ cached per file, $S$ transmissions	s02
$R_\text{PDA}$	Rate achieved by PDA: $S/F$ file units	s02
$\chi_f(G)$	Fractional chromatic number (used in graph-coloring delivery)	s03
$t$	Target caching gain (same as MAN)	s01

← Ch 13 The Subpacketization Bottleneck