• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Index Coding With Side Information
【24h】

Index Coding With Side Information

机译：附带信息的索引编码

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

摘要

Motivated by a problem of transmitting supplemental data over broadcast channels (Birk and Kol, INFOCOM 1998), we study the following coding problem: a sender communicates with $n$ receivers $R_{1},ldots ,R_{n}$. He holds an input $x in { 0,1 } ^{n}$ and wishes to broadcast a single message so that each receiver $R_{i}$ can recover the bit $x_{i}$. Each $R_{i}$ has prior side information about $x$ , induced by a directed graph $G$ on $n$ nodes; $R_{i}$ knows the bits of $x$ in the positions ${j mid (i,j) ~{rm is~an~edge~of~} G}$. $G$ is known to the sender and to the receivers. We call encoding schemes that achieve this goal indexcodes for $ { 0,1 }^{n}$ with side information graph $G$ . In this paper we identify a measure on graphs, the minrank, which exactly characterizes the minimum length of linear and certain types of nonlinear index codes. We show that for natural classes of side information graphs, including directed acyclic graphs, perfect graphs, odd holes, and odd anti--n-nholes, minrank is the optimal length of arbitrary index codes. For arbitrary index codes and arbitrary graphs, we obtain a lower bound in terms of the size of the maximum acyclic induced subgraph. This bound holds even for randomized codes, but has been shown not to be tight.
机译：出于在广播信道上传输补充数据的问题（Birk和Kol，INFOCOM 1998）的动机，我们研究了以下编码问题：发送方与$ n $接收方$ R_ {1}，ldots，R_ {n} $通信。他在{0,1} ^ {n} $中持有输入$ x，并希望广播一条消息，以便每个接收者$ R_ {i} $都可以恢复比特$ x_ {i} $。每个$ R_ {i} $都有关于$ x $的先前辅助信息，该信息由$ n $节点上的有向图$ G $引起； $ R_ {i} $知道位置$ {j mid（i，j）〜{rm is〜an〜edge〜of〜} G} $中$ x $的位。 $ G $对发送者和接收者都是已知的。我们称编码方案为$ {0,1} ^ {n} $并带有辅助信息图$ G $来实现该目标。在本文中，我们在图形上确定了一个度量，即最小秩，它精确地描述了线性和某些类型的非线性索引代码的最小长度。我们表明，对于附带信息图的自然类（包括有向无环图，完美图，奇数孔和奇数反n孔），minrank是任意索引代码的最佳长度。对于任意索引代码和任意图，我们在最大非循环诱导子图的大小方面获得了一个下限。该界限甚至适用于随机码，但已证明并非严格。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号