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.
@cite_26: We present a simple proof that the capacity of the binary independent and identically distributed (i.i.d.) deletion channel, where each bit is deleted independently with probability d, is at least (1-d) 9, by developing a correspondence between the deletion channel and an insertion deletion channel that we call a Poisson-repeat channel
@cite_22: We study memoryless channels with synchronization errors as defined by a stochastic channel matrix allowing for symbol drop-outs or symbol insertions with particular emphasis on the binary and non-binary deletion channels. We offer a different look at these channels by considering equivalent models by fragmenting the input sequence where different subsequences travel through different channels. The resulting output symbols are combined appropriately to come up with an equivalent input-output representation of the original channel which allows for derivation of new upper bounds on the channel capacity. We consider both random and deterministic types of fragmentation processes applied to binary and nonbinary deletion channels. With two specific applications of this idea, a random fragmentation applied to a binary deletion channel and a deterministic fragmentation process applied to a nonbinary deletion channel, we prove certain inequality relations among the capacities of the original channels and those of the introduced subchannels. The resulting inequalities prove useful in deriving tighter capacity upper bounds for: 1) independent identically distributed (i.i.d.) deletion channels when the deletion probability exceeds 0.65 and 2) nonbinary deletion channels. Some extensions of these results, for instance, to the case of deletion substitution channels are also explored.
@cite_7: 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.
@cite_8: The problem of reconstructing a source sequence with the presence of decoder side-information that is mis-synchronized to the source due to deletions is studied in a distributed source coding framework. Motivated by practical applications, the deletion process is assumed to be bursty and is modeled by a Markov chain. The minimum rate needed to reconstruct the source sequence with high probability is characterized in terms of an information theoretic expression, which is interpreted as the amount of information of the deleted content and the locations of deletions, subtracting “nature's secret”, that is, the uncertainty of the locations given the source and side-information. For small bursty deletion probability, the asymptotic expansion of the minimum rate is computed.
@cite_6: This correspondence considers binary deletion channels, where bits are deleted independently with probability d; it improves upon the framework used to analyze the capacity of binary deletion channels established by Diggavi and Grossglauser, improving on their lower bounds. Diggavi and Grossglauser considered codebooks with codewords generated by a first-order Markov chain. They only consider typical outputs, where an output is typical if an N bit input gives an N(1-d)(1-epsi) bit output. The improvements in this correspondence arise from two considerations. First, a stronger notion of a typical output from the channel is used, which yields better bounds even for the codebooks studied by Diggavi and Grossglauser. Second, codewords generated by more general processes than first-order Markov chains are considered
@cite_24: 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.
@cite_16: 
@cite_13: This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit is added after it with probability i, or it is transmitted unmodified with probability 1-d-i. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter longer, some runs get deleted, and some new runs are added. It is difficult for the decoder to synchronize the channel output sequence to the transmitted codeword mainly due to deleted runs and new inserted runs. The main idea is a mutual information decomposition in terms of the rate achieved by a suboptimal decoder that determines the positions of the deleted and inserted runs in addition to decoding the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its suboptimality. Obtaining computable lower bounds on each of these quantities yields a lower bound on the capacity. The bounds proposed in this paper provide the first characterization of achievable rates for channels with general insertions, and for channels with both deletions and insertions. For the special case of the deletion channel, the proposed bound improves on the previous best lower bound for deletion probabilities up to 0.3.
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.