• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Electrical Communication Engineering (ECE)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Electrical Communication Engineering (ECE)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Index Coding, Error Correcting Index Codes And Matroids

    View/Open
    Thesis full text (1.176Mb)
    Author
    Thomas, Anoop
    Metadata
    Show full item record
    Abstract
    In the problem of index coding, there is a central source sending messages to a set of receivers which demand messages over a noiseless broadcast channel. Each receiver knows a subset of messages which is referred to as side-information. A backward channel exists between each of the receivers and the source. Receivers use the reverse channel to communicate the side-information back to the source. The source uses this side-information to develop encoding schemes so that all the receivers are satisfied with minimum number of transmissions. In this work, we consider few problems related to index coding. First, we consider the informed source coding problem in which the receiver communicates only the cardinality of the side-information available to it and not the messages that constitute the side-information. We use l-th Near Maximum Distance Sep- arable (Near-MDS) codes to construct encoding schemes for the informed source coding problem. The advantage of using l-th Near-MDS codes is the reduction of required field size. For certain class of informed source coding problems, we show that the codes constructed from l`-th Near-MDS codes are optimal under some field size restrictions. Links between matroid theory, network coding and index coding problems have been an active area of research. The generalized index coding problem is a general version of the conventional index coding problem in which both the source and receivers possess linear functions of messages. We establish connections between representation of discrete polymatroids and generalized index coding. We show that the generalized index coding problem has a vector linear solution if and only if there exists a representable discrete polymatroid satisfying certain conditions. Further, from a discrete polymatroid a generalized index coding problem is con- structed. It is shown that if the generalized index coding problem has a vector linear solution over the binary eld then an associated discrete polymatroid is representable over the binary eld. For generalized index coding problems con- structed from matroids, we show that a scalar linear solution to the constructed problem exists if and only if the matroid is binary representable. We also consider the index coding with restricted information (ICRI) problem in which the source must ensure that each receiver will not be able to decode a certain subset of messages. Interference alignment techniques are used to obtain results on the ICRI problem. Necessary conditions for the existence of a solution to the ICRI problem is found. A technique to obtain solutions to the ICRI problem using contractions corresponding to restrictions is obtained. Index coding over noisy channels is also considered. Error correcting index codes are encoding schemes which enable every receiver to correct up to a certain number of errors in the received message. We allow each receiver to have a di erent error correcting capability and introduce di erential error correcting index codes to achieve this. A set of necessary and su cient conditions for a matrix to correspond to a vector linear di erential index code is found. We establish the link between vector linear di erential error correcting index codes and discrete polymatroids. It is shown that a vector linear di erential error correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Lastly, index coding problem over binary symmetric channels is studied. It is observed that the probability of error at each receiver depends on the index code used. A condition on the optimal index codes which minimize the maximum error probability among all the receivers is derived. For a special class of index coding problems, an algorithm to identify an optimal index code which gives the best performance in terms of minimal maximum error probability across all the receivers is provided.
    URI
    https://etd.iisc.ac.in/handle/2005/5326
    Collections
    • Electrical Communication Engineering (ECE) [402]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV