On the Placement Delivery Array Design for Centralized Coded Caching Scheme

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 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 F. Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size M at each user (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 = 2). The new construction can decrease the required F from the order O(e(K.((M/N) ln(N/M)+(1-(M/N)) ln (N/(N-M)))) of Ali-Niesen scheme to O(e(K.(M/N) ln(N/M))) or O(e(K.(1-(M/N)) ln(N/(N-M)))), respectively, while the coding gain loss is only 1.