On the Placement Delivery Array Design for Centralized Coded Caching Scheme

DOI10.1109/TIT.2017.2725272MaRDI QIDQ4589410zbMATH OpenOpenAlexFDO

Authors Qifa Yan, Minquan Cheng, Xiaohu Tang, Qingchun Chen

Publication date 10 November 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.05064

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: 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 $qgeq2$). The new construction can decrease the required $F$ from the order $Oleft(e^{Kcdotleft(fracMNlnfracNM+(1-fracMN)lnfracNN-Might)}ight)$ of Ali-Niesen scheme to $Oleft(e^{KcdotfracMNlnfracNM}ight)$ or $Oleft(e^{Kcdot(1-fracMN)lnfracNN-M}ight)$ respectively, while the coding gain loss is only $1$.

Cited in

(5)

• Centralized Coded Caching Schemes: A Hypergraph Theoretical Approach
• Computing Autotopism Groups of Partial Latin Rectangles
• On optimal placement delivery arrays
• Improved multi-access coded caching schemes from maximal cross resolvable designs
• Improved hotplug caching schemes using PDAs and t-designs

This page was built for publication: On the Placement Delivery Array Design for Centralized Coded Caching Scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589410)