Memory-Rate Tradeoff for Caching with Uncoded Placement under Nonuniform File Popularity

For caching with nonuniform file popularity, we aim to characterize the memory-rate tradeoff under uncoded cache placement. We consider the recently proposed Modified Coded Caching Scheme (MCCS) with the optimized cache placement based on the popularity-first approach to minimize the average delivery rate. We introduce two information-theoretic lower bounds on the average rate for caching under uncoded placement. For K = 2 users, we show that the optimized MCCS attains the lower bound and is optimal for caching with uncoded placement. For general K users with distinct file requests, the optimized MCCS attains the popularity-first-based lower bound. When there are redundant file requests among K users, we show a possible gap between the optimized MCCS and the lower bounds, which is attributed to zero-padding commonly used for coded delivery. We analyze the impact of zero-padding and its limitation. Simulation study shows that the loss is very small in general and only exists in some limited cases.