Tight asymptotic bounds for the deletion channel with small deletion probabilities
Authors:
- 1 June 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 997-1001
Abstract
In this paper, we consider the capacity C of the binary deletion channel for the limiting case where the deletion probability p goes to 0. It is known that for any p <; 1/2, the capacity satisfies C ≥ 1-H(p), where H is the standard binary entropy. We show that this lower bound is essentially tight in the limit, by providing an upper bound C ≤ 1-(1-o(1))H(p), where the o(1) term is understood to be vanishing as p goes to 0. Our proof utilizes a natural counting argument that should prove helpful in analyzing related channels.Keywords
This publication has 7 references indexed in Scilit:
- On the deletion channel with small deletion probability2010
- Novel bounds on the capacity of binary channels with deletions and substitutions2009
- A survey of results for deletion channels and related synchronization channelsProbability Surveys, 2009
- Capacity Upper Bounds for the Deletion Channel2007
- A Simple Lower Bound for the Capacity of the Deletion ChannelIEEE Transactions on Information Theory, 2006
- On information transmission over a finite buffer channelIEEE Transactions on Information Theory, 2006
- Probability and Computing2005