IIIT Hyderabad Publications |
|||||||||
|
Index Coding : Rank Invariant ExtensionsAuthor: G Vamsi Krishna Date: 2019-06-20 Report no: IIIT/TH/2019/66 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, peer-to-peer communication, distributed caching, device-to-device 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. Rank Invariant extensions of index coding problems are discussed in this thesis. Any index coding problem can be defined using an associated matrix known as a fitting matrix. An index coding problem Iext is called an extension of another index coding problem I if the fitting matrix of I is a submatrix of the fitting matrix of Iext. We first present a straightforward m-order extension Iext of an index coding problem I for which an index code is obtained by concatenating m copies of an index code of I. The length of the codes is the same for both I and Iext, and if the index code for I has optimal length then so does the extended code for Iext. More generally, an extended index coding problem of I having the same optimal length as I is said to be a rank invariant extension of I. We then focus on 2-order rank-invariant extensions of I, and present constructions of such extensions based on involutory permutation matrices. The second contribution in this thesis is obtaining optimal index codes for a specific subclass of index coding problems. It is known that the single unicast index coding problem can be represented using a side-information graph G (with number of vertices n equal to the number of source symbols). The optimal rate of index coding is known to be lower bounded by the size of maximum acyclic induced subgraph of the side-information graph, denoted by MAIS. 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. |