Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels
Authors:
Top Cited Papers
- 23 July 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 53 (8) , 2693-2714
Abstract
This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability d. It improves significantly upon the best previous framework used to obtain provable lower bounds on this capacity by utilizing a stronger definition of a typical output from the channel. The new results give the best known provable bounds on the capacity for all values of d. Moreover, the techniques presented here extend to yield lower bounds for channels with certain types of random insertions, namely, duplications, or combinations of duplications and deletions. To demonstrate these techniques in this context, two binary channels are analyzed: a channel where each transmitted bit is copied with probability nu and a channel where each transmitted bit is copied a geometrically distributed number of times.Keywords
This publication has 7 references indexed in Scilit:
- Directly Lower Bounding the Information Capacity for Channels with I.I.D. Deletions and Duplications2007
- On Lower Bounds for the Capacity of Deletion ChannelsIEEE Transactions on Information Theory, 2006
- 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
- Elements of Information Theory2001
- Randomized Algorithms1995
- On the capabilities of codes to correct synchronization errorsIEEE Transactions on Information Theory, 1967