Abstract

Coded caching was introduced as a technique of systematically exploiting locally available storage at the clients to increase the channel throughput via coded transmissions. Most known coded caching schemes in literature enable large gains in terms of the rate, however at the cost of subpacketization that is exponential in ( being the number of clients, some positive integer). Building upon recent prior work for coded caching design via line graphs and finite-field projective geometries, we present a new scheme in this work which achieves a subexponential (in ) subpacketization of and rate , for large , and the cached fraction being upper bounded by a constant (for some prime power and constant ). Apart from this asymptotic improvement, we show that through some numerical comparisons that our present scheme has much lower subpacketization than previous comparable …

Abstract

Consider an interference channel consisting of transmitters and receivers with AWGN noise and complex channel gains, and with files in the system. The one-shot for this channel is the maximum number of receivers which can be served simultaneously with vanishing probability of error as the grows large, under a class of schemes known as\textit {one-shot} schemes. Consider that there exists transmitter and receiver side caches which can store fractions and of the library respectively. Recent work for this cache-aided interference channel setup shows that, using a carefully designed prefetching (caching) phase, and a one-shot coded delivery scheme combined with a proper choice of beamforming coefficients at the transmitters, we can achieve a of , where and which was shown to be almost optimal. The existing scheme involves splitting the file into subfiles (the parameter is called the\textit {subpacketization}), where can be extremely large (in fact, with constant cache fractions, it becomes exponential in , for large ). In this work, our first contribution is a scheme which achieves the same of with a smaller subpacketization than prior schemes. Our second contribution is a new coded caching scheme for the interference channel based on projective geometries over finite fields which achieves a one-shot of , with a subpacketization (for some prime power ) that is\textit {subexponential} in , for small constant cache fraction at the receivers. To the best of our knowledge, this is the first coded caching scheme with subpacketization …

Abstract

An index code is said to be locally decodable if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The locality of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off …

Abstract

We consider the standard broadcast setup with a single server broadcasting information to a number of clients, each of which contains local storage (called cache) of some size, which can store some parts of the available files at the server. The centralized coded caching framework, consists of a caching phase and a delivery phase, both of which are carefully designed in order to use the cache and the channel together optimally. In prior literature, various combinatorial structures have been used to construct coded caching schemes. In this work, we propose a binary matrix model to construct the coded caching scheme. The ones in such a caching matrix indicate uncached subfiles at the users. Identity submatrices of the caching matrix represent transmissions in the delivery phase. Using this model, we then propose several novel constructions for coded caching based on the various types of combinatorial designs …

Abstract

Coded Caching is a promising solution to reduce the peak traffic in broadcast networks by prefetching the popular content close to end users and using coded transmissions. One of the chief issues of most coded caching schemes in literature is the issue of large subpacketization, i.e., they require each file to be divided into a large number of subfiles. In this work, we present a coded caching scheme using line graphs of bipartite graphs in conjunction with projective geometries over finite fields. The presented scheme achieves a rate Θ(K/log q K) (K being the number of users, q is some prime power) with subexponential subpacketization q O((logq K)^2) when cached fraction is upper bounded by a constant (M/N ≤ 1/q α , for some positive integer α). Compared to earlier schemes, the presented scheme has a lower subpacketization (albeit possessing a higher rate). We also present a new subpacketization …

Abstract

Coded Caching is a recent technique that optimizes the use of a multi-client broadcast channel by the use of local storage available at the clients and by using coded transmissions to serve multiple clients at once. While large gains in the rate of communication are obtained using coded caching, most existing schemes require that the files at the server be divisible into a large number of parts. In particular, most known coded caching schemes require subpacketization $ F={e^{Oleft ({{K^{frac {1}{r}}}}right)}} $, where K is the number of clients and r is some constant positive integer. While few schemes having subpacketization linear in K are known in literature, unfortunately such schemes require large number of users to exist or offer little gain in rate. In this work, we propose a class of coded caching schemes based on projective geometries over finite fields, generalizing recent results. Our construction achieves subexponential (in K) subpacketization, ie, $ F={q^{O …

Abstract

Coded caching was introduced as a technique of systematically exploiting locally available storage at the clients to increase the channel throughput via coded transmissions. Most known coded caching schemes in literature enable large gains in terms of the rate, however at the cost of subpacketization that is exponential in ( being the number of clients, some positive integer). Building upon recent prior work for coded caching design via line graphs and finite-field projective geometries, we present a new scheme in this work which achieves a subexponential (in ) subpacketization of and rate , for large , and the cached fraction being upper bounded by a constant (for some prime power and constant ) . Apart from this asymptotic improvement, we show that through some numerical comparisons that our present scheme has much lower subpacketization than previous comparable …

Abstract

An index coding (IC) problem consisting of a server and multiple receivers with different side-information and demand sets can be equivalently represented using a fitting matrix. A scalar linear index code to a given IC problem is a matrix representing the transmitted linear combinations of the message symbols. The length of an index code is then the number of transmissions (or equivalently, the number of rows in the index code). An IC problem Iext is called an extension of another IC problem I if the fitting matrix of I is a submatrix of the fitting matrix of Iext. We first present a straightforward m-order extension Iext of an IC problem I for which an index code is obtained by concatenating m copies of an index code of I. The length of the codes is the same for both I and Iext, and if the index code for I has optimal length then so does the extended code for Iext. More generally, an extended IC problem of I having the same …

Abstract

n Index Coding, the goal is to use a broadcast channel as efficiently as possible to communicate information from a source to multiple receivers which can possess some of the information symbols at the source as side-information. In this work, we present a duality relationship between index coding (IC) and multiple-unicast network coding (NC). It is known that the IC problem can be represented using a side-information graph G (with number of vertices n equal to the number of source symbols). The size of the maximum acyclic induced subgraph, denoted by MAI S is a lower bound on the broadcast rate. For IC problems with MAIS = n - 1 and MAI S = n - 2, prior work has shown that binary (over F 2) linear index codes achieve the MAI S lower bound for the broadcast rate and thus are optimal. In this work, we use the the duality relationship between NC and IC to show that for a class of IC problems with MAIS = n - 3 …

Abstract

Index coding for broadcast channels allows each receiver or client to retrieve its demanded message from its side information and the transmitted codeword. In general, a client may have to observe the entire codeword to decode its demanded message. However, downloading or querying the codeword symbols might involve costs at a client - such as network utilization costs and storage. Traditional index coding does not consider this client perspective, and as a result, for these codes the number of codeword symbols queried by a client per decoded message symbol, which we refer to as locality, could be large. In this paper we study a `client aware' approach to index coding by viewing the problem as a trade-off between the achievable broadcast rate and locality, where the objective is to minimize the rate for a given value of locality and vice versa. We first consider the minimum possible locality 1 and show that the …