Optimal Placement Delivery Arrays from $t$-Designs with Application to Hierarchical Coded Caching

Coded caching scheme originally proposed by Maddah-Ali and Niesen (MN) achieves an optimal transmission rate $R$ under uncoded placement but requires a subpacketization level $F$ which increases exponentially with the number of users $K$ where the number of files $N\ge K$. Placement delivery array (PDA) was proposed as a tool to design coded caching schemes with reduced subpacketization level by Yan $\mathit{\text{et}}\mathit{\text{al.}}$ in \cite{YCT}. This paper proposes two novel classes of PDA constructions from combinatorial $t$-designs that achieve an improved transmission rate for a given low subpacketization level, cache size and number of users compared to existing coded caching schemes from $t$-designs. A $(K,F,Z,S)$ PDA composed of a specific symbol $\star$ and $S$ non-negative integers corresponds to a coded caching scheme with subpacketization level $F$, $K$ users each caching $Z$ packets and the demands of all the users are met with a rate $R=\frac{S}{F}$. For a given $K$, $F$ and $Z$, a lower bound on $S$ such that a $(K,F,Z,S)$ PDA exists is given by Cheng $\mathit{\text{et}}\mathit{\text{al.}}$ in \cite{MJXQ} and by Wei in \cite{Wei} . Our first class of proposed PDA achieves the lower bound on $S$. The second class of PDA also achieves the lower bound in some cases. From these two classes of PDAs, we then construct hierarchical placement delivery arrays (HPDA), proposed by Kong $\mathit{\text{et}}\mathit{\text{al.}}$ in \cite{KYWM}, which characterizes a hierarchical two-layer coded caching system. These constructions give low subpacketization level schemes.