An Explicit Construction of a Coded Caching Scheme with Heterogeneous Cache Sizes

In the coded caching scheme proposed by Maddah-Ali and Niesen, we usually consider the setup where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> users have respective cache memories of equal size and request arbitrary one of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> files to a server. The server broadcasts a signal to the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> users so that each user can reproduce the requested file from the transmitted signal together with the contents in their cache memory. Finding the memory-rate tradeoff is one of the fundamental problems in the coded caching problem. In this paper, we extend the coded caching problem to the case where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> users have cache memories of unequal sizes. We succeed in giving a new upper bound of the memory-rate tradeoff under a certain assumption. We establish the upper bound by developing a new scheme in which <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> files are divided into sub files of unequal sizes according to the sizes of cache memories. The validity of this scheme is established by using combinatoric arguments. We also show that adding new users with no cache memory to the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> users can reduce the rate of the transmitted signal.