Improved Hierarchical Coded Caching Schemes from t-Designs

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 ≥ K. Placement delivery array (PDA) was proposed as a tool to design coded caching schemes with reduced subpacketization level by Yan et al. in {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 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=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 et al. in {MJXQ}. Our first class of proposed PDA achieves this lower bound on S. The second class of PDA also achieves this lower bound in some cases. From these two classes of PDAs, we then construct hierarchical placement delivery arrays (HPDA), proposed by Kong et al. in {KYWM}, which characterizes a hierarchical two-layer coded caching system. These constructions give very low subpacketization level schemes with optimal rate with respect to the lower bound on S in first layer transmission from server to attached mirrors.