Index Coding Capacity: How Far Can One Go With Only Shannon Inequalities?
Index Coding Capacity: How Far Can One Go With Only Shannon Inequalities?
复制标题
指数编码能力：仅用香农不等式能走多远？
DOI：
10.1109/tit.2015.2418289
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
S. Jafar
中科院分区：
文献类型：
--
作者：
Hua Sun;S. Jafar
干涉对齐的角度用于识别索引编码问题的最简单实例（对齐图中最小可能的边缘数量，在任何目的地上的边缘数量不超过2个干扰消息），在这些问题中，非香农信息不等式对于容量表征是必要的。特别是，这包括一个已知的单播（每个消息目的地）索引编码问题的第一个已知示例，在该问题中表明非香农信息不等式是必要的。最简单的多个单播示例在对齐图中具有7个边缘和11条消息。最简单的多个组cast（每个消息多个目的地）示例在对齐图中有6个边缘，6个消息和10个接收器。对于最简单的多个单播和多个集体广播实例，仅基于香农不平等的最佳外部界限是2/5，通过使用Zhang-Yeung Non-Shannon类型信息不平等，将其拧紧至11/28使用Ingleton不等式显示容量为5/13。相反，确定索引编码问题的最小挑战性方面，可以扩展已解决的索引编码问题，直到（但不包括）这些实例。
An interference alignment perspective is used to identify the simplest instances (minimum possible number of edges in the alignment graph, not more than 2 interfering messages at any destination) of index coding problems where non-Shannon information inequalities are necessary for capacity characterization. In particular, this includes the first known example of a multiple unicast (one destination per message) index coding problem where non-Shannon information inequalities are shown to be necessary. The simplest multiple unicast example has 7 edges in the alignment graph and 11 messages. The simplest multiple groupcast (multiple destinations per message) example has 6 edges in the alignment graph, 6 messages, and 10 receivers. For both the simplest multiple unicast and multiple groupcast instances, the best outer bound based on only Shannon inequalities is 2/5, which is tightened to 11/28 by the use of the Zhang-Yeung non-Shannon type information inequality, and the linear capacity is shown to be 5/13 using the Ingleton inequality. Conversely, identifying the minimal challenging aspects of the index coding problem allows an expansion of the class of solved index coding problems up to (but not including) these instances.
DOI：
10.1109/netcod.2013.6570823
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Baber R
通讯作者：
Baber R