An Explicit Construction of a Coded Caching Scheme with Heterogeneous Cache Sizes and Its Extension via Optimization

In the coded caching scheme proposed by Maddah-Ali and Niesen, we usually consider the setup where K users have respective cache memories of equal size and request an arbitrary one of N files to a server. The server multicasts a signal to all the users so that all the users can reproduce the files of their requests from the transmitted signal using the contents in their respective cache memories. Finding the memory-rate tradeoff is one of the fundamental problems in coded caching. In this paper, we consider the problem of centralized coded caching where K users have cache memories of heterogeneous sizes. We first give a new explicit construction of the coded caching scheme under a certain assumption on the cache sizes. The validity of the scheme is established theoretically. Next, we consider an extension of the scheme so that we can apply the scheme to general heterogeneous cache memories. We divide the N files into K + 1 portions and apply the proposed scheme to each portion in the most efficient way by solving a certain linear programming problem. We compare the memory-rate tradeoff of this optimized scheme with existing coded caching schemes.