Capacity upper bounds for deletion-type channels
File(s)deletion.pdf (1.41 MB)
Accepted version
Author(s)
Cheraghchi Bashi Astaneh, M
Type
Journal Article
Abstract
We develop a systematic approach, based on convex programming and real analysis, for obtaining upper bounds on the capacity of the binary deletion channel and, more generally, channels with i.i.d. insertions and deletions. Other than the classical deletion channel, we give a special attention to the Poisson-repeat channel introduced by Mitzenmacher and Drinea (IEEE Transactions on Information Theory, 2006). Our framework can be applied to obtain capacity upper bounds for any repetition distribution (the deletion and Poisson-repeat channels corresponding to the special cases of Bernoulli and Poisson distributions). Our techniques essentially reduce the task of proving capacity upper bounds to maximizing a univariate, realvalued, and often concave function over a bounded interval. The corresponding univariate function is carefully designed according to the underlying distribution of repetitions and the choices vary depending on the desired strength of the upper bounds as well as the desired simplicity of the function (e.g., being only efficiently computable versus having an explicit closedform expression in terms of elementary, or common special, functions). Among our results, we show the following: 1. The capacity of the binary deletion channel with deletion probability d is at most (1 − d) log ϕ for d ≥ 1/2, and, assuming the capacity function is convex, is at most 1−d log(4/ϕ) for d < 1/2, where ϕ = (1 + √ 5)/2 is the golden ratio. This is the first nontrivial capacity upper bound for any value of d outside the limiting case d → 0 that is fully explicit and proved without computer assistance. 2. We derive the first set of capacity upper bounds for the Poisson-repeat channel. Our results uncover further striking connections between this channel and the deletion channel, and suggest, somewhat counter-intuitively, that the Poisson-repeat channel is actually analytically simpler than the deletion channel and may be of key importance to a complete understanding of the deletion channel. 3. We derive several novel upper bounds on the capacity of the deletion channel. All upper bounds are maximums of efficiently computable, and concave, univariate real functions over a bounded domain. In turn, we upper bound these functions in terms of explicit elementary and standard special functions, whose maximums can be found even more efficiently (and sometimes, analytically, for example for d = 1/2). Along the way, we develop several new techniques of potentially independent interest. For example, we develop systematic techniques to study channels with mean constraints over the reals. Furthermore, we motivate the study of novel probability distributions over non-negative integers as well as novel special functions which could be of interest to mathematical analysis.
Date Issued
2019-04-01
Date Acceptance
2018-10-01
ISSN
0004-5411
Publisher
Association for Computing Machinery
Start Page
1
End Page
17
Journal / Book Title
Journal of the Association for Computing Machinery (ACM)
Volume
66
Issue
2
Copyright Statement
© 2019 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, VOL66, ISS2, (April 2019) https://doi.org/10.1145/3281275.
Source Database
manual-entry
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Computer Science, Information Systems
Computer Science, Software Engineering
Computer Science, Theory & Methods
Computer Science
Information theory
channel coding
error-correcting codes
CODES
Computation Theory & Mathematics
08 Information and Computing Sciences
Publication Status
Published
Article Number
ARTN 9
Date Publish Online
2019-03-19