We consider the problem of constructing codes that can correct @math deletions occurring in an arbitrary binary string of length @math bits. Varshamov–Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion @math correcting codes and have an asymptotically optimal redundancy. Finding similar codes for @math deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the @math deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of @math deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization.
The capacity of the deletion channel has been studied in the probabilistic model. In the model where the deletions are iid and occur with a fixed probability @math , an immediate upper bound on the channel capacity is given by the capacity of the erasure channel @math . Mitzenmacher and Drinea showed in @cite_26 that the capacity of the deletion channel in the iid model is at least @math . Extensive work in the literature has focused on determining lower and upper bounds on the capacity @cite_26 @cite_6 @cite_24 @cite_13 @cite_7 @cite_22 . We refer interested readers to the comprehensive survey by Mitzenmacher @cite_16 . Ma @cite_8 also studied the capacity in the bursty model of the deletion channel, where the deletion process is modeled by a Markov chain.
@cite_26 @cite_22 @cite_7 @cite_8 @cite_6 @cite_24 @cite_16 @cite_13
2119486537 2034381439 2767293093 2079814843
We present two upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. The first can be numerically evaluated for any fixed d. The second provides an asymptotic upper bound as d goes to 1. These appear to be the first nontrivial upper bounds for this probabilistic deletion channel. 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. 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, real-valued, 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 closed-form expression in terms of elementary, or common special, functions). Among our results, we show that 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 Furthermore, 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. Finally, 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. We develop several analytical lower bounds on the capacity of binary insertion and deletion channels by considering independent uniformly distributed (i.u.d.) inputs and computing lower bounds on the mutual information between the input and output sequences. For the deletion channel, we consider two different models: i.i.d. deletion-substitution channel and i.i.d. deletion channel with additive white Gaussian noise (AWGN). These two models are considered to incorporate effects of the channel noise along with the synchronization errors. For the insertion channel case, we consider Gallager's model in which the transmitted bits are replaced with two random bits and uniform over the four possibilities independently of any other insertion events. The general approach taken is similar in all cases, however the specific computations differ. Furthermore, the approach yields a useful lower bound on the capacity for a wide range of deletion probabilities of the deletion channels, while it provides a beneficial bound only for small insertion probabilities (less than 0.25) of the insertion model adopted. We emphasize the importance of these results by noting that: 1) our results are the first analytical bounds on the capacity of deletion-AWGN channels, 2) the results developed are the best available analytical lower bounds on the deletion-substitution case, 3) for the Gallager insertion channel model, the new lower bound improves the existing results for small insertion probabilities.