Placement Delivery Array Construction via Cartesian Product for Coded Caching
Jinyu Wang, Minquan Cheng, Kai Wan, Giuseppe Caire · IEEE Transactions on Information Theory · 2023
Caching prefetches some library content at users’ memories during the off-peak times (i.e., placement phase), such that the number of transmissions during the peak-traffic times (i.e., delivery phase) are reduced. A coded caching strategy was originally proposed by Maddah-Ali and Niesen (MN) leading to a multicasting gain compared to the conventional uncoded caching, where each message in the delivery phase is useful to multiple users simultaneously. The load of the MN scheme is optimal under uncoded placement, but the subpacketization level is$O\left({2^{H\left({\frac {M}{N}}\right)K}}\right)$, where$K$is the number of users,$\frac {M}{N}$is the memory ratio of each user and$H\left({\frac {M}{N}}\right)$is the binary entropy at$\frac {M}{N}$. In order to reduce the subpacketization while retaining the multicast opportunities in the delivery phase, Yan et al. proposed a combinatorial structure called placement delivery array (PDA) to design coded caching schemes with uncoded placement and clique-covering delivery. In this paper, we consider the coded caching problem from the perspective of PDA. First we propose a Cartesian product method, which constructs an$mK_{1}$-user PDA based on the piece-wise$m$-fold Cartesian product of a special$K_{1}$-user PDA (called a base PDA) while keeping the memory ratio and load unchanged. Since a base PDA must satisfy some restrictive constraints, we propose a transformation from any existing PDA to a base PDA, which makes the Cartesian product method applicable to any existing PDA. As applications of the Cartesian product method, three new coded caching schemes (i.e., Schemes A, B, C) are obtained, whose performance are validated via analytical and numerical comparisons. It is worth noting that Scheme A is asymptotically optimal under uncoded placement, in the sense that the achieved coded caching gain is only decreased by 1 with respect to the coded caching gain of the MN scheme. When the number of users is$K=mq$and memory ratio is$\frac {z}{q}$, the needed subpacketization is at most$O\left ({\sqrt {\frac {K}{q}}2^{-\frac {K}{q}}}\right)$of that of the MN scheme for large$m$, which implies that for fixed number of users and memory ratio, when we choose$q$and$z$coprime, the subpacketization can be reduced the most, since the value of$\frac {K}{q}$is maximized. Moreover, Scheme A works for arbitrary memory ratio.