First, a new perspective based on binary matrices of placement delivery array (PDA) design was introduced, by which the PDA design problem can be simplified. From this new perspective, and based on some families of combinatorial designs, new schemes with low subpacketization for centralized coded caching problem were constructed. We also give a technique for constructing new coded caching scheme from known schemes based on direct product of PDAs.
Although optimal in rate, the caching scheme in @cite_22 has its limitation in practical implementations: By this caching scheme, each file is divided into @math packets @math The number @math is also referred to as the file size or subpacketization in some literature. @math , which grows exponentially with @math @cite_9 . For practical application, it is important to construct coded caching scheme with smaller packet number.
@cite_9 @cite_22
2517585112 2915582513 2975151417 2963935351
We study a noiseless broadcast link serving @math users whose requests arise from a library of @math files. Every user is equipped with a cache of size @math files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most @math file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file @math scales to infinity. The asymptotic coding gain obtained is roughly @math . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets @math is a function of the system parameters @math , and @math . Specifically, we show that the existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of 2 even if the number of packets is exponential in the asymptotic gain @math . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of @math is at least @math . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters. Coded caching scheme recently has become quite popular in the wireless network, since the maximum transmission amount @math reduces effectively during the peak-traffic times. To realize a coded caching scheme, each file must be divided into @math packets, which usually increases the computation complexity of a coded caching scheme. So we prefer to design a scheme with @math and @math as small as possible in practice. However, there exists a tradeoff between @math and @math . In this paper, we generalize the schemes constructed by (IEEE Transactions on Information Theory, 64, 5755–5766, 2018) and (IEEE Transactions on Information Theory 63, 5821–5833, 2017), respectively. These two classes of schemes have a wider range of application due to the more flexible memory size than the original ones. By comparing with the previous known deterministic schemes, our new schemes have advantages on @math or @math . 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 @math packets, which usually increases exponentially with the number of users @math . Thus, designing caching schemes that decrease the order of @math is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is first 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. Second, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least @math . Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size @math at each user (identical cache size is assumed at all users) and the number of files @math satisfies @math or @math ( @math is an integer, such that @math ). The new construction can decrease the required @math from the order @math of Ali-Niesen scheme to @math or @math , respectively, while the coding gain loss is only 1. We consider a cache-aided interference network which consists of a library of N files, K&#60;sub&#62;T&#60;&#x002F;sub&#62; transmitters and K&#60;sub&#62;R&#60;&#x002F;sub&#62; receivers (users), each equipped with a local cache of size M&#60;sub&#62;T&#60;&#x002F;sub&#62; and M&#60;sub&#62;R&#60;&#x002F;sub&#62; files respectively, and connected via a discrete-time additive white Gaussian noise channel. Each receiver requests an arbitrary file from the library. The objective is to design a cache placement without knowing the receivers' requests and a communication scheme such that the sum Degrees of Freedom (sum-DoF) of the delivery is maximized. This network model has been investigated by , who proposed a prefetching and a delivery scheme that achieve a sum-DoF of min M&#60;sub&#62;T&#60;&#x002F;sub&#62; K&#60;sub&#62;T&#60;&#x002F;sub&#62; &#x002B; K&#60;sub&#62;R&#60;&#x002F;sub&#62; M&#60;sub&#62;R&#60;&#x002F;sub&#62;&#x002F;N, K&#60;sub&#62;R&#60;&#x002F;sub&#62; . One of the biggest limitations of this scheme is the requirement of high subpacketization level. This paper attempts to design new algorithms to reduce the file subpacketization in such a network. In particular, we propose a new approach for both prefetching and linear delivery based on a combinatorial design called hypercube. We show that the required number of packets per file can be exponentially reduced compared to the state-of-the-art scheme proposed by , or the NMA scheme. When M&#60;sub&#62;T&#60;&#x002F;sub&#62; K&#60;sub&#62;T&#60;&#x002F;sub&#62; &#x002B; K&#60;sub&#62;R&#60;&#x002F;sub&#62; M&#60;sub&#62;R&#60;&#x002F;sub&#62; &#x2264; K&#60;sub&#62;R&#60;&#x002F;sub&#62;, the achievable one-shot sum-DoF using this approach is M&#60;sub&#62;T&#60;&#x002F;sub&#62; K&#60;sub&#62;T&#60;&#x002F;sub&#62; &#x002B; K&#60;sub&#62;R&#60;&#x002F;sub&#62; M&#60;sub&#62;R&#60;&#x002F;sub&#62;&#x002F;N, which shows that 1) the one-shot sum-DoF scales linearly with the aggregate cache size in the network and 2) it is within a factor of 2 to the information-theoretic optimum. Surprisingly, the identical and near optimal sum-DoF performance can be achieved using the hypercube approach with a much less file subpacketization.