IIIT Hyderabad Publications 


Optimal Index Codes via a Duality between Index Coding and Network CodingAuthor: Ashok Choudhary Date: 20190619 Report no: IIIT/TH/2019/67 Advisor:Prasad Krishnan AbstractOne of the major challenges for information theorists is to build such communication schemes which allow participants to communicate efficiently . Index Coding , which was first introduced by Birk and Kol in 1998 [1] as Coding on Demand by an Informed Source is a communication scheme dealing with a broadcast channel in which receivers have prior side information about the messages to be broadcast. Exploiting the knowledge about the side information, the sender may significantly reduce the number of required transmissions , in turn improve the efficiency of the communication over this type of broadcast channels. 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 oppoturnistic 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 graph theoretic methods, algebraic methods, matrix completion, linear programming, interference alignment, etc. It is known that the index coding problem can be represented using a sideinformation graph G (with number of vertices n equal to the number of source symbols). The size of the maximum acyclic induced subgraph of side information graph, denoted by MAIS is a lower bound on the broadcast rate. For index coding problems with MAIS = n ā 1 and MAIS = n ā 2, prior work has shown that binary (over F2) linear index codes achieve the MAIS lower bound for the broadcast rate and thus are optimal. In this thesis, we use the the duality relationship between network coding and index coding to show that for a class of index coding problems with MAIS = n ā 3, binary linear index codes achieve the MAIS lower bound on the broadcast rate. In contrast, it is known that there exists index coding problems with MAIS = nā3 and optimal broadcast rate strictly greater than MAIS. Relevant figures has been included for clear understating of reader. Full thesis: pdf Centre for Others 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 