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.
So far, several coded caching schemes with reduced file size have been constructed, all with the sacrifice of increasing the rate. In @cite_2 , a class of coded caching schemes with linear file size @math i.e., @math were constructed from Ruzsa-Szem @math redi graphs. A very interesting framework for constructing centralized coded caching scheme, named design (or PDA design for simplicity), was introduced in @cite_14 , and some new classes of coded caching schemes were constructed by PDA design in references @cite_14 and @cite_6 . In @cite_5 , two classes of constant rate caching schemes with sub-exponential subpacketization were obtained from @math -free @math -partite hypergraphs. A more general class of coded caching schemes were constructed in @cite_7 from strong edge colored bipartite graphs. References @cite_1 and @cite_0 constructed some coded caching schemes using projective geometries over finite fields, and reference @cite_18 constructed some schemes based on resolvable combinatorial designs from certain linear block codes. Some classes of coded caching schemes from some other block designs, including balanced incomplete block designs (BIBDs), @math -designs and transversal designs (TDs), are obtained in @cite_17 . Summaries of known centralized coded caching schemes can be found in @cite_6 @cite_5 and @cite_1 .
@cite_18 @cite_14 @cite_7 @cite_1 @cite_6 @cite_0 @cite_2 @cite_5 @cite_17
2793858273 2975151417 2539811847 2915582513 2946479852 2963720294
Coded caching is a technique that generalizes conventional caching and promises significant reductions in traffic over caching networks. However, the basic coded caching scheme requires that each file hosted in the server be partitioned into a large number (i.e., the subpacketization level) of non-overlapping subfiles. From a practical perspective, this is problematic as it means that prior schemes are only applicable when the size of the files is extremely large. In this paper, we propose coded caching schemes based on combinatorial structures called resolvable designs. These structures can be obtained in a natural manner from linear block codes whose generator matrices possess certain rank properties. We obtain several schemes with subpacketization levels substantially lower than the basic scheme at the cost of an increased rate. Depending on the system parameters, our approach allows us to operate at various points on the subpacketization level vs. rate tradeoff. 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. The technique of coded caching proposed by Madddah-Ali and Niesen is a promising approach to alleviate the load of networks during peak-traffic times. Recently, placement delivery array (PDA) was presented to characterize both the placement and delivery phase in a single array for the centralized coded caching algorithm. In this letter, we reinterpret PDA from a new perspective, i.e., the strong edge coloring of bipartite graph (bigraph). We prove that, a PDA is equivalent to a strong edge colored bigraph. Thus, we can construct a class of PDAs from existing structures in bigraphs. The class subsumes the scheme proposed by Maddah- and a more general class of PDAs proposed by as special cases. 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 . Coded caching scheme, which is an effective technique to increase the transmission efficiency during peak traffic times, has recently become quite popular among the coding community. Generally rate can be measured to the transmission in the peak traffic times, i.e., this efficiency increases with the decreasing of rate. In order to implement a coded caching scheme, each file in the library must be split in a certain number of packets. And this number directly reflects the complexity of a coded caching scheme, i.e., the complexity increases with the increasing of the packet number. However there exists a tradeoff between the rate and packet number. So it is meaningful to characterize this tradeoff and design the related Pareto-optimal coded caching schemes with respect to both parameters. Recently, a new concept called placement delivery array (PDA) was proposed to characterize the coded caching scheme. However as far as we know no one has yet proved that one of the previously known PDAs is Pareto-optimal. In this paper, we first derive two lower bounds on the rate under the framework of PDA. Consequently, the PDA proposed by Maddah-Ali and Niesen is Pareto-optimal, and a tradeoff between rate and packet number is obtained for some parameters. Then, from the above observations and the view point of combinatorial design, two new classes of Pareto-optimal PDAs are obtained. Based on these PDAs, the schemes with low rate and packet number are obtained. Finally the performance of some previously known PDAs are estimated by comparing with these two classes of schemes. The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into @math pieces, where @math grows exponentially with the number of users @math . Such a constraint is obviously infeasible in the practical setting, especially when @math is large. Thus, it is desirable to design caching schemes with constant rate @math (independent of @math ) as well as smaller @math . In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with @math growing linearly with @math do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with @math growing sub-exponentially with @math do exist.