An Equivalence Between Network Coding and Index Coding

作者：Effros Michelle^*; El Rouayheb Salim; Langberg Michael

来源：IEEE Transactions on Information Theory, 2015, 61(5): 2478-2487.

DOI：10.1109/TIT.2015.2414926

• Communication networks
• network coding

We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and nonlinear codes. Specifically, we present a reduction that maps a network coding instance to an index coding instance while preserving feasibility, i.e., the network coding instance has a feasible solution if and only if the corresponding index coding instance is feasible. In addition, we show that one can determine the capacity region of a given network coding instance with colocated sources by studying the capacity region of a corresponding index coding instance. Previous connections between network and index coding were restricted to the linear case.

• 出版日期2015-5