Caching is a promising solution to satisfy the ever increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into $F$ packets, which usually increases exponentially with the number of users $K$. Thus, designing caching schemes that decrease the order of $F$ is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is firstly formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Secondly, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least $F$. Thirdly, we present a new construction of PDA for the centralized caching system, wherein the cache size of each user $M$ (identical cache size is assumed at all users) and the number of files $N$ satisfies $M/N=1/q$ or ${ (q-1)}/{ q}$ ($q$ is an integer such that $q\geq 2$). The new construction can decrease the required $F$ from the order $O\left(e^{ K\cdot\left(\frac{ M}{ N}\ln \frac{ N}{ M} +(1-\frac{ M}{ N})\ln \frac{ N}{ N-M}\right)}\right)$ of Ali-Niesen scheme to $O\left(e^{ K\cdot\frac{ M}{ N}\ln \frac{ N}{ M}}\right)$ or $O\left(e^{ K\cdot(1-\frac{ M}{ N})\ln\frac{ N}{ N-M}}\right)$ respectively, while the coding gain loss is only $1$.
Categories: cs.IT math.IT