Multi-sender index coding for collaborative broadcasting: a rank-minimization approach

Min Li*, Lawrence Ong, Sarah J. Johnson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


We consider a Multi-Sender Unicast Index-Coding (MSUIC) problem, where in a broadcast network, multiple senders collaboratively send distinct messages to multiple receivers, each having some subset of the messages a priori. The aim is to find the shortest index code that minimizes the total number of coded bits sent by the senders. In this paper, built on the classic single-sender minrank concept, we develop a new rank-minimization framework for MSUIC that explicitly takes into account the sender message constraints and minimizes the sum of the ranks of encoding matrices subject to the receiver decoding requirements. This framework provides a systematic way to construct multi-sender linear index codes and to study their capability in achieving the shortest index codelength per message length (i.e., the optimal broadcast rate). In particular, we establish the optimal broadcast rate for all critical MSUIC instances with up to four receivers and show that a binary linear index code is optimal for all, except 15 instances with four receivers. We also propose a heuristic algorithm (in lieu of exhaustive search) to solve the rank-minimization problem. The effectiveness of the algorithm is validated by numerical studies of MSUIC instances with four or more receivers.

Original languageEnglish
Pages (from-to)1452-1466
Number of pages15
JournalIEEE Transactions on Communications
Issue number2
Publication statusPublished - Feb 2019


Dive into the research topics of 'Multi-sender index coding for collaborative broadcasting: a rank-minimization approach'. Together they form a unique fingerprint.

Cite this