- Title
- Interlinked cycles for index coding: generalizing cycles and cliques
- Creator
- Thapa, Chandra; Ong, Lawrence; Johnson, Sarah J.
- Relation
- Funding BodyARCGrant NumberFT110100195 http://purl.org/au-research/grants/arc/FT110100195
- Relation
- IEEE Transactions on Information Theory Vol. 63, Issue 6, p. 3692-3711
- Publisher Link
- http://dx.doi.org/10.1109/TIT.2017.2662706
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- journal article
- Date
- 2017
- Description
- We consider a graphical approach to index coding. As cycles have been shown to provide coding gain, cycles and cliques (a specific type of overlapping cycles) have been exploited in an existing literature. In this paper, we define a more general form of overlapping cycles, called the interlinked-cycle (IC) structure, that generalizes cycles and cliques. We propose a scheme, called the interlinked-cycle-cover (ICC) scheme, that leverages IC structures in digraphs to construct scalar linear index codes. We characterize a class of infinitely many digraphs where our proposed scheme is optimal over all linear and nonlinear index codes. Consequently, for this class of digraphs, we indirectly prove that scalar linear index codes are optimal. Furthermore, we show that the ICC scheme can outperform all the existing graph-based schemes (including partial-clique-cover and fractional-local-chromatic number schemes), and a random coding scheme (namely, composite coding) for certain graphs.
- Subject
- indexes; receivers; channel coding; integrated circuits; interference; silicon
- Identifier
- http://hdl.handle.net/1959.13/1398665
- Identifier
- uon:34471
- Identifier
- ISSN:0018-9448
- Rights
- © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
- Language
- eng
- Full Text
- Reviewed
- Hits: 1593
- Visitors: 1923
- Downloads: 358
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 697 KB | Adobe Acrobat PDF | View Details Download |