- Title
- Graphical approaches to single-sender and two-sender index coding
- Creator
- Thapa, Chandra
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2018
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- In index coding, a sender broadcasts messages through a noiseless broadcast channel to multiple receivers, each possessing a subset of the messages a priori, known as side-information. The sender knows the side-information available at each receiver, and uses that information to broadcasts coded messages, called an index code, such that all receivers can decode their requested messages using their side-information and the received index code. The aim is to find an index code with the minimum information bits per received message bits, called the optimal broadcast rate. The index-coding problem is applicable in many real-world contexts such as content-distribution networks (e.g., a network providing video-on-demand services), satellite communications, and distributed storage (e.g., data centers). In this dissertation, we investigate unicast-index-coding (UIC) problems, where each message is requested by only one receiver, each receiver requests only one message and each receiver has a subset of messages except its requested messages in side-information. These problems can be modeled by directed graphs. We apply graph-based approaches to the two types of the UIC problems based on the number of senders, namely single-sender unicast-index-coding (SSUIC) and two-sender unicast-index-coding (TSUIC) problems. In SSUIC, we propose a new scheme, called interlinked-cycle-cover (ICC) scheme, that exploits interlinked-cycle (IC) structures (a form of overlapping cycles that generalizes cliques and cycles) in directed graphs. This scheme provides an upper bound on the optimal broadcast rate for any SSUIC instance, and construct a linear index code. We prove that the ICC scheme is optimal over all linear and non-linear index codes for a class of infinitely many digraphs. We show that the ICC scheme can outperform existing schemes for some SSUIC instances with six receivers. Further, we extend the IC structures and the scheme. We find that the ICC scheme (including the extended scheme) provides the optimal broadcast rates for all message alphabet sizes for all SSUIC instances up to five receivers except eight problems. In TSUIC, firstly, we extend the existing SSUIC graph-based schemes, namely clique-cover, cycle-cover, and local-chromatic-number schemes to TSUIC. Then we investigate the TSUIC problems by its structural characterization. By considering three sub-problems of a TSUIC problem based on whether the receivers' requests are available at only one sender or both senders, we formulate its optimal broadcast rate as a function of the optimal broadcast rates of its three sub-problems. Furthermore, for this formulation, we extend the notion of confusion graphs and graph coloring to TSUIC. We characterize a class of infinitely many TSUIC instances where a certain type of side-information can be removed without affecting their optimal broadcast rates.
- Subject
- index coding; broadcast with side-information; graph theory; interlinked cycle cover
- Identifier
- http://hdl.handle.net/1959.13/1388175
- Identifier
- uon:32725
- Rights
- Copyright 2018 Chandra Thapa
- Language
- eng
- Full Text
- Hits: 693
- Visitors: 1489
- Downloads: 733
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Thesis | 1 MB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Abstract | 304 KB | Adobe Acrobat PDF | View Details Download |