| dc.description.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. | en_US |
