Index coding and network coding via rank minimization

Xiao Huang, Salim El Rouayheb

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

16 Citations (Scopus)

Abstract

Index codes reduce the number of bits broadcast by a wireless transmitter to a number of receivers with different demands and with side information. It is known that the problem of finding optimal linear index codes is NP-hard. We investigate the performance of different heuristics based on rank minimization and matrix completion methods for constructing linear index codes over the reals. As a summary of our results, the alternating projections method gives the best results in terms of minimizing the number of broadcast bits and convergence rate and leads to up to 13% savings in communication cost compared to graph coloring algorithms studied in the literature. Moreover, we describe how the proposed methods can be used to construct linear network codes for non-multicast networks.

Original languageEnglish
Title of host publicationITW 2015 - 2015 IEEE Information Theory Workshop
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages14-18
Number of pages5
ISBN (Electronic)9781467378529
DOIs
Publication statusPublished - 17 Dec 2015
Externally publishedYes
EventIEEE Information Theory Workshop, ITW 2015 - Jeju Island, Korea, Republic of
Duration: 11 Oct 201515 Oct 2015

Publication series

NameITW 2015 - 2015 IEEE Information Theory Workshop

Conference

ConferenceIEEE Information Theory Workshop, ITW 2015
CountryKorea, Republic of
CityJeju Island
Period11/10/1515/10/15

ASJC Scopus subject areas

  • Information Systems

Cite this