Prerequisites & Notation

Before You Begin

This chapter requires channel capacity fundamentals and broadcast channel theory. The combinatorial structure of coded caching is self-contained, but the wireless extensions build on multi-antenna broadcast channels.

Channel capacity and the coding theorem for DMCs(Review ch09)
Self-check: Can you state Shannon's channel coding theorem and outline the achievability proof?
Degraded broadcast channel capacity region(Review ch15)
Self-check: Can you state the capacity region of the degraded BC and describe superposition coding?
MIMO broadcast channel and dirty-paper coding(Review ch16)
Self-check: Can you explain how DPC achieves the MIMO BC capacity region?
Combinatorics: binomial coefficients and counting arguments
Self-check: Are you comfortable with $\binom{n}{k}$ identities and double-counting arguments?
Index coding basics
Self-check: Can you explain how a server with side information at receivers can save transmissions via XOR coding?

Notation for This Chapter

Symbols introduced in this chapter for the coded caching framework.

Symbol	Meaning	Introduced
$N$	Number of files in the server's library	s01
$K$	Number of users	s01
$M$	Cache size at each user (in file units)	s01
$t = KM/N$	Coded caching gain parameter (number of users served per multicast message)	s01
$R(M)$	Delivery load (rate) as a function of cache size	s01
$R^*(M)$	Optimal (minimum) delivery load	s02
$d_k$	File index demanded by user $k$	s01
$\mathcal{S}$	Subset of users (used in multicast addressing)	s01
$W_{d_k,\mathcal{S}}$	Sub-file of $W_{d_k}$ cached exclusively by users in $\mathcal{S}$	s01
$\text{NDT}$	Normalized delivery time (for wireless extensions)	s03
$L$	Number of transmit antennas at the server	s03

← Ch 26 The Coded Caching Problem