Chapter 2: The Maddah-Ali–Niesen (MAN) Scheme

Learning Objectives

• State the MAN scheme: combinatorial placement $W_{n,\mathcal{S}}$ indexed by $t$-subsets $\mathcal{S} \subseteq [K]$
• Prove the MAN delivery rate $R = K(1-M/N)/(1+KM/N)$ for integer $t = KM/N$
• Construct the delivery message $X_{\mathcal{S}'} = \oplus_{k \in \mathcal{S}'} W_{d_k, \mathcal{S}' \setminus \{k\}}$ for every $(t+1)$-subset $\mathcal{S}'$
• Verify that each coded message simultaneously serves $t+1$ users
• Handle non-integer $t$ via memory-sharing (convex combination)
• Understand subpacketization $F = \binom{K}{t}$ and why it grows exponentially in $K$