Ferkans — Interactive Telecom Tutor

A Combinatorial Framework for Coded Caching

Yan, Cheng, Tang, and Chen (2017) introduced the Placement Delivery Array (PDA) framework — a combinatorial abstraction that captures both MAN and many other coded caching schemes as special cases. A PDA is simply an $F \times K$ integer matrix whose entries describe which subfiles are cached by which users and which coded messages are transmitted.

The framework has two virtues:

Unification. MAN is a specific PDA; other PDAs give different rate/subpacketization tradeoffs.
Design space. One can search for PDAs with desirable properties — e.g., polynomial subpacketization with near-MAN rate.

This section defines PDAs and presents key constructions.

Definition:
Placement Delivery Array

A $(K, F, Z, S)$ -placement delivery array (PDA) is an $F \times K$ integer matrix $\mathbf{P} = [p_{j,k}]$ whose entries are either $*$ (star) or from $\{1, 2, \ldots, S\}$ , satisfying:

Cache content rule. $p_{j,k} = *$ means user $k$ caches subfile $j$ . Each column has exactly $Z$ entries equal to $*$ , so each user caches $Z$ subfiles per file.
Delivery rule. $p_{j,k} = s \in \{1, \ldots, S\}$ means subfile $j$ is transmitted to user $k$ during the $s$ -th coded message.
Coding consistency. If $p_{j_1, k_1} = p_{j_2, k_2} = s$ for $(j_1, k_1) \neq (j_2, k_2)$ , then $k_1 \neq k_2$ and $p_{j_1, k_2} = p_{j_2, k_1} = *$ (each user in the coded message has the "other" subfile cached, enabling XOR cancellation).

The PDA describes a coded caching scheme with subpacketization $F$ and $S$ coded transmissions per delivery round.

The MAN scheme corresponds to a specific PDA with $F = \binom{K}{t}$ rows. Other PDAs have smaller $F$ at some rate cost.

Theorem: PDA Achievability

Given a $(K, F, Z, S)$ -PDA, there exists a coded caching scheme with $K$ users, cache size $M = Z \cdot F_\text{file}/F$ (i.e., $Z$ out of $F$ subfiles per file), and delivery rate $R_\text{PDA} \;=\; S/F \text{ file units}.$ The subpacketization is exactly $F$ .

The PDA encodes a valid placement and delivery. The rate equals the number of coded transmissions divided by subpacketization (each transmission contains $F_{\text{file}}/F$ bits of data).

Proof

Placement from PDA

User $k$ 's cache contains subfile $j$ iff $p_{j,k} = *$ . By assumption, $|*| = Z$ per column, so cache size = $Z$ subfiles per file.

Delivery from PDA

For each $s \in \{1, \ldots, S\}$ , the $s$ -th coded message is an XOR of the subfiles $\{W_{d_{k},j} : p_{j,k} = s\}$ — the set of $(j, k)$ pairs where that entry equals $s$ .

Decoding

User $k$ receives the $s$ -th XOR message. It contains the subfile $W_{d_k, j}$ where $p_{j,k} = s$ . Other summands are indexed by $(j', k')$ with $p_{j', k'} = s$ ; by the coding consistency rule, $p_{j', k} = *$ (user $k$ has subfile $j'$ cached). Hence user $k$ can XOR-cancel and recover its target subfile.

Correctness

User $k$ collects all subfiles $W_{d_k, j}$ with $p_{j,k} \neq *$ from the $S$ coded messages. Together with cached subfiles (where $p_{j,k} = *$ ), user $k$ has all $F$ subfiles of $W_{d_k}$ , reconstructing its demanded file. $\blacksquare$

Example: MAN as a PDA

Express the MAN scheme as a PDA. For $K = 3$ , $t = 1$ , $N = 2$ , list the PDA matrix.

Solution

MAN parameters

$F = \binom{3}{1} = 3$ subfiles per file. Subfiles indexed by 1-subsets $\{1\}, \{2\}, \{3\}$ . User $k$ caches subfile $\mathcal{S}$ iff $k \in \mathcal{S}$ , i.e., only subfile $\{k\}$ .

PDA matrix

Rows: subfile index $\mathcal{S}$ ; columns: user index $k$ . Entry $p_{\mathcal{S}, k}$ : if $k \in \mathcal{S}$ , then $*$ . Otherwise, entry = coded-message index for delivery.

Users 1, 2, 3. Subsets $\{1\}, \{2\}, \{3\}$ . Row $\{1\}$ : $*$ , 1, 2 (user 1 caches; users 2, 3 receive subfile $\{1\}$ via messages 1, 2 resp.). Row $\{2\}$ : 1, $*$ , 3 (similar). Row $\{3\}$ : 2, 3, $*$ .

Total: $S = 3$ messages. Rate: $S/F = 3/3 = 1$ file. Matches MAN: $(K-t)/(t+1) = 2/2 = 1$ . ✓

Verification

Each column has 1 $*$ (cache = 1 subfile = $\mu N = 2/3$ files — but actually here $M = 2/3$ , $N = 2$ , $\mu = 1/3$ ; each user caches 1 of 3 subfiles per file $= 1/3$ of each file $= 2/3$ total. ✓). Each coded message index appears exactly twice (once per targeted user).

PDA vs MAN Rate

PDA schemes achieve polynomial subpacketization at a small rate penalty. Plot shows MAN (exponential $F$ ) vs typical PDA (polynomial $F$ , ~1.3× rate gap). For realistic $K$ , PDA is vastly more deployable.

Parameters

Memory ratio μ0.25

Max K100

Theorem: Yan et al. Polynomial-Subpacketization Construction

For any $K, t \geq 1$ , there exists a $(K, F, Z, S)$ -PDA with: $F \;\leq\; K^t/t!, \qquad Z/F = t/K, \qquad S/F = (K-t)/(t+1),$ achieving a rate equal to MAN's $(K-t)/(t+1)$ but with polynomial (in $K$ ) subpacketization.

The construction uses a combinatorial design (based on $t$ -element subsets of $[K]$ with extra structure) to reduce $F$ from $\binom{K}{t}$ to $\approx K^t/t!$ while preserving the rate.

Proof

Construction

Use a specific combinatorial design (e.g., transversal design TD(t+1, K)) to define the placement matrix. The design guarantees the PDA properties.

Parameter verification

$F = K^t/t!$ follows from design counting. $Z/F = t/K$ (each user caches a fraction $t/K$ of subfiles). Rate $S/F = (K-t)/(t+1)$ matches MAN.

Polynomial bound

$K^t/t!$ is polynomial in $K$ (for fixed $t$ ). Contrast with $\binom{K}{t}$ exponential in $K$ for $t$ growing with $K$ .

Tradeoff

Small $t$ : both $F$ and rate are small. Large $t$ (comparable to $K$ ): both grow polynomially in $K^t$ , still exponential effect but milder than MAN. $\blacksquare$

PDA Design as Optimization

The PDA framework enables optimization: given target rate and $K$ , find minimum- $F$ PDA. This is a combinatorial optimization problem.

Known approaches:

Structured constructions. Yan-Cheng-Tang-Chen 2017: PDA from transversal designs, Steiner systems.
Integer programming. Direct search for small instances.
Graph-theoretic. Via coloring of constructed graphs (§14.3).
Heuristics. Greedy / random search with rate / $F$ objective.

The design space has been actively explored since 2017. Several PDA constructions achieve $F$ polynomial in $K$ with small constant rate gap ( $< 2$ typically). This is the practical frontier for coded caching.

Key Takeaway

PDAs unify the coded-caching scheme design space. MAN is a specific PDA; simpler PDAs have polynomial $F$ and constant rate gap. The PDA framework is the right level of abstraction for engineering coded caching — it trades subpacketization (bad) against rate (good) in a principled way.

Placement Delivery Arrays (PDAs)