On the zero-error capacity threshold for deletion channels
On the zero-error capacity threshold for deletion channels
复制标题
关于删除通道的零错误容量阈值
DOI：
10.1109/ita.2011.5743594
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Ian A. Kash;M. Mitzenmacher;J. Thaler;Jonathan Ullman
我们考虑删除通道的零错误容量。具体来说，我们考虑的设置，我们选择一个码本C组成的字符串的n位，和我们的信道模型对应于一个对手谁可以删除这些位的pn为常数p。我们的目标是正确解码没有错误，无论对手的行动。我们考虑在此设置中，p的值允许非零容量。我们提出了多种方法，其中之一是利用这个问题和寻找两个随机序列的最长公共子序列的预期长度的问题之间的自然联系。
We consider the zero-error capacity of deletion channels. Specifically, we consider the setting where we choose a codebook C consisting of strings of n bits, and our model of the channel corresponds to an adversary who may delete up to pn of these bits for a constant p. Our goal is to decode correctly without error regardless of the actions of the adversary. We consider what values of p allow non-zero capacity in this setting. We suggest multiple approaches, one of which makes use of the natural connection between this problem and the problem of finding the expected length of the longest common subsequence of two random sequences.