Index coding, the problem of efficient broadcast to many receivers with side-infomation, is a rich and active research area. It has applications to a range of multi-user broadcast scenarios such as video-on-demand and satellite communications. It has attracted significant theoretical interest both as a hard problem in its own right and due to its connections to other network capacity problems. The central problem of index coding, that of determining the optimal rate of an index code, is still open. We describe recent advances on the index coding problem and its generalizations in the context of broadcast with side-information. The two main approaches to bounding the optimal rate of an index code, namely rank-minimization methods and linear programming models, are discussed in detail. The latter of these, based on graph-theoretical ideas in the classical case, can be extended even to generalizations of the index coding problem for which there is no associated side-information hypergraph. We discuss error-correction in the index coding problem, the corresponding bounds on the optimal transmission rate and decoding algorithms. We also illustrate the connections to network coding, interference alignment and coded caching.

Index Coding, Network Coding and Broadcast with Side-Information / Byrne, E.; Calderini, M.. - (2018), pp. 247-293. [10.1007/978-3-319-70293-3_10]

Index Coding, Network Coding and Broadcast with Side-Information

Calderini M.
2018-01-01

Abstract

Index coding, the problem of efficient broadcast to many receivers with side-infomation, is a rich and active research area. It has applications to a range of multi-user broadcast scenarios such as video-on-demand and satellite communications. It has attracted significant theoretical interest both as a hard problem in its own right and due to its connections to other network capacity problems. The central problem of index coding, that of determining the optimal rate of an index code, is still open. We describe recent advances on the index coding problem and its generalizations in the context of broadcast with side-information. The two main approaches to bounding the optimal rate of an index code, namely rank-minimization methods and linear programming models, are discussed in detail. The latter of these, based on graph-theoretical ideas in the classical case, can be extended even to generalizations of the index coding problem for which there is no associated side-information hypergraph. We discuss error-correction in the index coding problem, the corresponding bounds on the optimal transmission rate and decoding algorithms. We also illustrate the connections to network coding, interference alignment and coded caching.
2018
Network Coding and Subspace Designs
Cham, Svizzera
Springer Science and Business Media Deutschland GmbH
978-3-319-70292-6
978-3-319-70293-3
Byrne, E.; Calderini, M.
Index Coding, Network Coding and Broadcast with Side-Information / Byrne, E.; Calderini, M.. - (2018), pp. 247-293. [10.1007/978-3-319-70293-3_10]
File in questo prodotto:
File Dimensione Formato  
indexbook.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 782.24 kB
Formato Adobe PDF
782.24 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/339487
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact