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 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

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

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

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

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

Circular perfect graphs are those undirected graphs such that the circular clique number is equal to the circular chromatic number for each induced subgraph. They form a strict superclass of the perfect graphs, whose index coding broadcast rates are well known. We present the broadcast rate of index coding for side-information graphs whose complements are circular perfect, along with an optimal achievable scheme. We thus enlarge the known classes of graphs for which the broadcast rate is exactly characterized. In an attempt to understand the broadcast rate of a graph given that of its complement, we obtain upper and lower bounds for the product and sum of the vector linear broadcast rates of a graph and its complement. We show that these bounds are satisfied with equality even for some perfect graphs. Curating prior results, we show that there are circular perfect but imperfect graphs which satisfy the lower bound on the product of the broadcast rate of the complementary graphs with equality.

Abstract

We present a coded caching framework using line graphs of bipartite graphs. A clique cover of the line graph describes the uncached subfiles at users. A clique cover of the complement of the square of the line graph gives a transmission scheme that satisfies user demands. We then define a specific class of such caching line graphs, for which the subpacketization, rate, and uncached fraction of the coded caching problem can be captured via its graph theoretic parameters. We present a construction of such caching line graphs using projective geometry. The presented scheme has a rate bounded from above by a constant with subpacketization level q O((IogqK)^2) and uncached fraction Θ(1/√K), where K is the number of users and q is a prime power. We also present a subpacketization-dependent lower bound on the rate of coded caching schemes for a given broadcast setup.

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 …

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 …