Optimal Coding for the Binary Deletion Channel With Small Deletion Probability
Optimal Coding for the Binary Deletion Channel With Small Deletion Probability
复制标题
DOI：
10.1109/tit.2013.2262020
复制
发表时间：
2013-10
影响因子：
2.5
通讯作者：
Yashodhan Kanoria;A. Montanari
中科院分区：
文献类型：
--
作者：
Yashodhan Kanoria;A. Montanari
二进制删除通道是建模缺乏同步的最简单的点对点通信通道。输入位以概率D独立删除，当未删除时，它们不会受到通道的影响。尽管付出了巨大的努力，但对该渠道的能力的了解知之甚少，甚至不太了解最佳编码方案。在本文中，我们通过证明可以在小型删除概率的系列扩展中计算能力来开发一种新的系统方法。我们计算了这一扩展的三个主要条款，并找到了达到该订单的能力的输入分布。这构成了删除通道的第一个最佳随机编码结果。使用的关键思想是：我们完美地理解了删除概率d = 0的删除通道。它具有容量1，最佳输入分布是IID Bernoulli（1/2）。很自然地期望具有较小的删除概率的通道的能力随D顺利而变化，并且通过平滑扰动IID Bernoulli（1/2）过程来获得最佳输入分布。我们的结果表明确实如此。
The binary deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel and even less about optimal coding schemes. In this paper, we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal random coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is iid Bernoulli (1/2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the iid Bernoulli (1/2) process. Our results show that this is indeed the case.