...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Shannon Meets von Neumann: A Minimax Theorem for Channel Coding in the Presence of a Jammer
【24h】

Shannon Meets von Neumann: A Minimax Theorem for Channel Coding in the Presence of a Jammer

机译：Shannon遇到von neumann：在混血器存在下的频道编码的最低限度定理

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

摘要

We study the setting of channel coding over a family of channels whose state is controlled by an adversarial jammer by viewing it as a zero-sum game between a finite blocklength encoder-decoder team, and the jammer. The encoder-decoder team choose stochastic encoding and decoding strategies to minimize the average probability of error in transmission, while the jammer chooses a distribution on the state-space to maximize this probability. The min-max value of the game is equivalent to channel coding for a compound channel - we call this the Shannon solution of the problem. The max-min value corresponds to finding a mixed channel with the largest value of the minimum achievable probability of error. When the min-max and max-min values are equal, the problem is said to admit a saddle-point or von Neumann solution. While a Shannon solution always exists, the communicating team's problem is nonconvex for finite blocklengths, whereby a von Neumann solution may not exist. Despite this, we show that the min-max and max-min values become equal asymptotically in the large blocklength limit, for all but finitely many rates. We explicitly characterize this limiting value as a function of the rate and obtain tight finite blocklength bounds on the min-max and max-min value. As a corollary we get an explicit expression for the $epsilon $ -capacity of a compound channel under stochastic codes - the first such result, to the best of our knowledge. Our results demonstrate a deeper relation between the compound channel and mixed channel than was previously known. They also show that the conventional information-theoretic viewpoint, articulated via the Shannon solution, coincides asymptotically with the game-theoretic one articulated via the von Neumann solution. Key to our results is the derivation of new finite blocklength upper bounds on the min-max value of the game via a novel achievability scheme, and lower bounds on the max-min value obtained via the linear programming relaxation based approach we introduced in [2].
机译：我们研究了通过在有限BloctLenceCer-解码器团队和Jammer之间将其视为零和游戏的频道由对抗性干扰控制的通道编码的信道编码的频道编码的设置。编码器 - 解码器团队选择随机编码和解码策略，以最小化传输中误差的平均概率，而干扰器在状态空间上选择分布以最大化此概率。游戏的最小值相当于复合频道的信道编码 - 我们称之为问题的香农解决方案。 MAX-MIN值对应于找到具有最小误差概率的最大值的混合通道。当MIN-MAX和MAX-MIN值相等时，据说该问题允许鞍点或von neumann解决方案。虽然Shannon解决方案始终存在，但通信团队的问题是有限块长度的非谐波，从而可能不存在von neumann解决方案。尽管如此，我们表明min-max和max-min的值在大块长度限制中变得相等，但除了有限的许多费率。我们将该限制值明确地表征为速率的函数，并在最大MAX和MAX-MIN值上获取紧密有限块长度。作为一项必要性，我们在随机代码下的复合渠道的$ epsilon $ -capacity的明确表达式 - 这是我们的知识中的第一个这样的结果。我们的结果表明了复合通道和混合通道之间的更深关系而不是先前已知的。他们还表明，通过香农溶液铰接的传统信息理论观点，与通过von neumann解决方案铰接的游戏理论物渐近渐近。我们的结果的关键是通过新颖的可实现性方案来推导新的有限块体长上限，通过新颖的可实现性方案，并通过我们在[2中的基于线性编程放松的方法获得的MAX-MIN值下限]。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号