- Title
- The single-uniprior index-coding problem: the single-sender case and the multi-sender extension
- Creator
- Ong, Lawrence; Ho, Chin Keong; Lim, Fabian
- Relation
- ARC.FT140100219
- Relation
- IEEE Transactions on Information Theory Vol. 62, Issue 6, p. 3165-3182
- Publisher Link
- http://dx.doi.org/10.1109/TIT.2016.2555950
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- journal article
- Date
- 2016
- Description
- Index coding studies multiterminal source-coding problems where a set of receivers are required to decode multiple (possibly different) messages from a common broadcast, and they each know some messages a priori. In this paper, at the receiver end, we consider a special setting where each receiver knows only one message a priori, and each message is known to only one receiver. At the broadcasting end, we consider a generalized setting where there could be multiple senders, and each sender knows a subset of the messages. The senders collaborate to transmit an index code. This paper looks at minimizing the number of total coded bits the senders are required to transmit. When there is only one sender, we propose a pruning algorithm to find a lower bound on the optimal (i.e., the shortest) index codelength, and show that it is achievable by linear index codes. When there are two or more senders, we propose an appending technique to be used in conjunction with the pruning technique to give a lower bound on the optimal index codelength; we also derive an upper bound based on cyclic codes. While the two bounds do not match in general, for the special case where no two distinct senders know any message in common, the bounds match, giving the optimal index codelength. The results are expressed in terms of strongly connected components in directed graphs that represent the index-coding problems.
- Subject
- source coding; directed graphs; encoding; linear codes
- Identifier
- http://hdl.handle.net/1959.13/1323828
- Identifier
- uon:24899
- Identifier
- ISSN:0018-9448
- Rights
- © © 2016 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: 1738
- Visitors: 2214
- Downloads: 582
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 505 KB | Adobe Acrobat PDF | View Details Download |