• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >On the Combinatorial Version of the Slepian–Wolf Problem
【24h】

On the Combinatorial Version of the Slepian–Wolf Problem

机译：关于Slepian-Wolf问题的组合版本

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

摘要

We study the following combinatorial version of the Slepian–Wolf coding scheme. Two isolated Senders are given binary stringsn$X$nandn$Y$n, respectively; the length of each string is equal ton$n$n, and the Hamming distance between the strings is at mostn$alpha n$n. The Senders compress their strings and communicate the results to the Receiver. Then, the Receiver must reconstruct both the stringsn$X$nandn$Y$n. The aim is to minimize the lengths of the transmitted messages. For an asymmetric variant of this problem (where one of the Senders transmits the input string to the Receiver without compression) with deterministic encoding, a nontrivial bound was found by Orlitsky and Viswanathany. In this paper, we prove a new lower bound for the schemes with syndrome coding, where at least one of the Senders uses linear encoding of the input string. For the combinatorial Slepian–Wolf problem with randomized encoding, the theoretical optimum of communication complexity was known earlier, even though effective protocols with optimal lengths of messages remained unknown. We close this gap and present a polynomial-time-randomized protocol that achieves the optimal communication complexity.
机译：我们研究了Slepian-Wolf编码方案的以下组合版本。两个孤立的发件人被赋予二进制字符串n $ X $ nandn $ Y $ n，分别;每个字符串的长度等于ton $ n $ n，字符串之间的汉明距离最多为n $ alpha n $ < / tex-math> n。发送方压缩其字符串并将结果传达给接收方。然后，接收方必须重构两个字符串n $ X $ nandn $ Y $ 。目的是使传输的消息的长度最小化。对于此问题的非对称变体（其中发件人之一将输入字符串无需压缩即可发送到接收器），使用确定性编码，Orlitsky和Viswanathany发现了一个平凡的界限。在本文中，我们证明了带有校正子编码的方案的新下界，其中至少有一个发件人使用输入字符串的线性编码。对于带有随机编码的组合Slepian-Wolf问题，尽管复杂的消息有效长度的有效协议仍然未知，但通信复杂度的理论最优值较早就知道了。我们缩小了差距，并提出了实现最佳通信复杂度的多项式时间随机协议。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号