Error Correction in Index Coding And Coded Caching

Abstract

In an index coding problem, there is a sender which has a set of messages and there are multiple receivers demanding possibly different subsets of these messages and possessing some other subsets of these messages as side-information. The goal for the sender is to meet the demands of the receivers in minimum number of transmissions using which along with the side-information every receiver can get what it demands. There have been many extensions and generalizations to the index coding prob- lem in the literature. One such generalization is to the case when the transmissions are subject to errors. Lower and upper bounds on the optimal number of transmis- sions required to correct a speci ed number of errors have been established. In this work, optimal linear error correcting index codes are obtained for three classes of index coding problems namely single-prior index coding problems, single unicast index coding problems with symmetric neighboring consecutive side-information and index coding problems with min-rank at most two. In another generalization of index coding problem, namely Generalized Index Coding (GIC) problem, linear combination of the messages can be demanded and the side-information at the receivers may also be some linear combinations of messages. For a particular class of GIC problems we discuss a construction of the optimal scalar linear index codes. For this class of GIC problems, the optimal linear error correcting index codes are also constructed. In a coded caching problem, a single server is connected to a set of users through a shared bottleneck link, which is assumed to be error-free. A coded caching problem involves two phases. The placement or prefetching phase is done during non-peak hours during which all the users ll their local cache with the portions of the les available. During the delivery phase, each user requests a le and the server delivers coded transmissions to meet the demands. During the placement, if the parts of the les are stored in the cache without coding, the prefetching is termed as uncoded prefetching. If coding is done among the parts of the les during the placement, then the prefetching is referred to as coded prefetching. When multiple users share a common cache, the scheme is referred to as the shared cache scheme. The centralized schemes involve a central coordi- nation during the placement phase. The schemes for which a central coordination is not required during the placement phase are called the decentralized schemes. In our work, the links between the server and the users are assumed to be error prone. A new delivery scheme is required to meet the demands of each user even after receiving a nite number of transmissions in error in the presence of erro- neous portions of les in the cache. The minimum average rate and the minimum peak rate for this problem are characterized. The optimal linear error correcting delivery schemes are proposed for various classes of coded caching problems in the absence of prefetching errors. The classes of problems which we considered include centralized schemes like the symmetric batch prefetching and the shared cache scheme, which involve uncoded prefetching, the Chen, Fan, Letaif scheme and the Jesus Vilardebo scheme, which involve coded prefetching. We have also considered decentralized schemes like the Ali-Niesen decentralized Scheme and the Least Recently Sent (LRS) online coded caching scheme. We also prove the optimality of the LRS online coded caching scheme using results from index cod- ing. Furthermore, alternate proofs for the optimality are given for coded caching problems with the symmetric batch prefetching and the Ali-Niesen decentralized prefetching. In addition to this, lower bounds are established for the optimal rate required when there are prefetching errors in the symmetric batch prefetching.