Placement Delivery Array Construction via Cartesian Product for Coded Caching

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 <inline-formula> <tex-math notation="LaTeX">$O\left({2^{H\left({\frac {M}{N}}\right)K}}\right)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> is the number of users, <inline-formula> <tex-math notation="LaTeX">$\frac {M}{N}$ </tex-math></inline-formula> is the memory ratio of each user and <inline-formula> <tex-math notation="LaTeX">$H\left({\frac {M}{N}}\right)$ </tex-math></inline-formula> is the binary entropy at <inline-formula> <tex-math notation="LaTeX">$\frac {M}{N}$ </tex-math></inline-formula>. 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 <inline-formula> <tex-math notation="LaTeX">$mK_{1}$ </tex-math></inline-formula>-user PDA based on the piece-wise <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>-fold Cartesian product of a special <inline-formula> <tex-math notation="LaTeX">$K_{1}$ </tex-math></inline-formula>-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 <inline-formula> <tex-math notation="LaTeX">$K=mq$ </tex-math></inline-formula> and memory ratio is <inline-formula> <tex-math notation="LaTeX">$\frac {z}{q}$ </tex-math></inline-formula>, the needed subpacketization is at most <inline-formula> <tex-math notation="LaTeX">$O\left ({\sqrt {\frac {K}{q}}2^{-\frac {K}{q}}}\right)$ </tex-math></inline-formula> of that of the MN scheme for large <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>, which implies that for fixed number of users and memory ratio, when we choose <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$z$ </tex-math></inline-formula> coprime, the subpacketization can be reduced the most, since the value of <inline-formula> <tex-math notation="LaTeX">$\frac {K}{q}$ </tex-math></inline-formula> is maximized. Moreover, Scheme A works for arbitrary memory ratio.