IIIT Hyderabad Publications 


Uniprior Index CodingAuthor: Vijaya Kumar Mareedu Date: 20190617 Report no: IIIT/TH/2019/68 Advisor:Prasad Krishnan AbstractThe problem of source coding is one of the central areas of information theory and coding. Designing source codes for the broadcast applications, where the receivers may have some prior information about the source, before it was sent is the key idea in this thesis. The challenge is to come with encoding schemes that exploit the sideinformation from the receivers in order to reduce the length of the code. This problem of source coding with sideinformation is called as index coding, first introduced by Birk and Kol [1] as coding on demand by an informed source. The index coding problem provides a simple yet rich model for several important engineering problems in network communication, such as content broadcasting, peertopeer communication, distributed caching, devicetodevice relaying, interference management and opportunistic wireless networks. It also has close relationships to network coding, distributed storage, and guessing games.The Index Coding problem is to identify the minimum number of transmissions (optimal length) to be made so that all receivers can decode their wanted messages using the transmitted symbols and their respective prior information and also the codes with optimal length. Optimal Index codes can be constructed using different methods which include graph theoretic methods, algebraic methods, matrix completion, linear programming, interference alignment,etc. An index coding problem can be represented using a demand graph (with number of edges equal to the demands at receivers and number of vertices n equal to the number of source symbols). Various graph theoretic bounds were well studied in the literature. Uniprior index coding problem is studied in this thesis. For single uniprior index coding problem , in which each receiver has a single unique sideinformation symbol, a polynomial complexity construction of an optimal index code is known from prior work. In this thesis we model the uniprior index coding problem as a supergraph G S , and focus on a class of uniprior problems defined on special supergraphs known as generalized cycles G gc , in which the sizes of demand set and the sideinformation set are equal at every receiver. For such problems, we prove upper and lower bounds on the optimal broadcast rate. Using a connection with Eulerian directed graphs, we also show that the upper and lower bounds are equal for a subclass of uniprior problems. We show the NPhardness of finding the lower bound for uniprior problems on generalized cycles, hence contrasting such uniprior problems with single uniprior problems. Finally we look at a simple extension of the generalized cycle uniprior class for which we give bounds on the optimal rate and show an explicit scheme which achieves the upper bound. Full thesis: pdf Centre for Others 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 