An Explicit Construction of a Coded Caching Scheme with Heterogeneous Cache Sizes
Akihito Nagaya, Hiroki Koga · 2024
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 arbitrary one of$N$files to a server. The server broadcasts a signal to the$K$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$K$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$N$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$K$users can reduce the rate of the transmitted signal.