• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
【24h】

On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory

机译：索引编码问题及其与网络编码和拟阵理论的关系

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages $X={x_1,ldots,x_k}$ and a set of receivers $R$. Each receiver $rho=(x,H)$ in $R$ needs to obtain a message $xin X$ and has prior side information consisting of a subset $H$ of $X$ . The sender uses a noiseless communication channel to broadcast encoding of messages in $X$ to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an -n-ninstance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.
机译：索引编码问题由于其理论意义和在无线自组织网络中的应用，最近引起了研究界的广泛关注。索引编码问题的一个实例包括持有一组信息消息$ X = {x_1，ldots，x_k} $的发送者和一组接收者$ R $。 $ R $中的每个接收者$ rho =（x，H）$需要获取消息$ xin X $并具有由$ X $的子集$ H $组成的先前辅助信息。发件人使用无噪音的通信信道向所有客户端广播$ X $消息的编码。目的是找到一种编码方案，该方案使满足所有接收机的需求所需的传输次数最小化。在本文中，我们分析了索引编码问题，更一般的网络编码问题和寻找拟阵线的线性表示问题之间的关系。特别是，我们表明，网络编码和拟阵表示问题的任何实例都可以有效地减少到索引编码问题的-n-n-instance。我们的减少意味着网络编码和拟阵表示问题的许多重要性质会延续到索引编码问题。具体来说，我们表明向量线性码的性能优于标量线性索引码，并且向量线性码不足以实现最佳传输次数。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号