We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining @math , the zero-rate threshold of adversarial deletions, defined to be the supremum of all @math for which there exists a code family with rate bounded away from 0 capable of correcting a fraction @math of adversarial deletions. A recent construction of deletion-correcting codes [ 17] shows that @math , and the trivial upper bound, @math , is the best known. Perhaps surprisingly, we do not know whether or not @math . In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of @math deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction @math of oblivious deletions, establishing that the associated zero-rate threshold @math equals @math . For online deletions, where the channel decides whether to delete bit @math based only on knowledge of bits @math , define the deterministic zero-rate threshold for online deletions @math to be the supremum of @math for which there exist deterministic codes against an online channel causing @math deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove @math if and only if @math .
The model of oblivious errors (such as bit flips) has has been studied in the information-theory literature as a particular case of arbitrarily varying channels with state constraints @cite_22 (see the related work section of @cite_20 for more background on this connection). In particular, for the case of bit flips, the capacity against the model of @math oblivious bit flips (for @math ) equals @math , matching the Shannon capacity of the binary symmetric channel that flips each bit independently with probability @math . (This special case was re-proved in @cite_15 by a different simpler random coding argument compared to the original works @cite_17 @cite_13 .) Similarly, the capacity against the model of @math oblivious erasures is @math , matching the Shannon capacity of the binary erasure channel. Explicit codes of rate approaching @math to correct @math oblivious bit flips (in the sense of Theorem , with randomized encoding) were given in @cite_20 . This work also considered computationally bounded noise models, such as channels with bounded memory or with small circuits, and gave optimal rate codes for decoding against those models. These models are more general than oblivious errors, but still not as pessimistic as adversarial noise.
@cite_22 @cite_15 @cite_13 @cite_20 @cite_17
2139194398 2076613277 2963279554 2015204845
Let be C= x1,...,xn sub 0,1 n be an [n,N] binary error correcting code (not necessarily linear). Let e 0,1 n be an error vector. A codeword xepsiC is said to be disturbed by the error e if the closest codeword to xopluse is no longer x. Let Ae be the subset of codewords in C that are disturbed by e. In this work, we study the size of Ae in random codes C (i.e., codes in which each codeword is chosen uniformly and independently at random from 0,1 n ). Using recent results of Vu [Random Structures and Algorithms, vol. 20, no. 3, pp. 262-316, 2002] on the concentration of non-Lipschitz functions, we show that |Ae| is strongly concentrated for a wide range of values of N and ||e||. We apply this result in the study of communication channels we refer to as oblivious. Roughly speaking, a channel W(y|x) is said to be oblivious if the error distribution imposed by the channel is independent of the transmitted codeword x. A family of channels Psi is said to be oblivious if every member W of the family is oblivious. In this work, we define oblivious and partially oblivious families of (not necessarily memoryless) channels and analyze their capacity. When considering the capacity of a family of channels Psi, one must address the design of error correcting codes which allow communication under the uncertainty of which channel WepsiPsi is actually used. The oblivious channels we define have connections to arbitrarily varying channels with state constraints. The capacity of an arbitrarily varying channel (AVC) is considered for deterministic codes with the average probability of error criterion and, typically, subject to at state constraint. First, sufficient conditions are provided that enable relatively simple decoding rules such as typicality, maximum mutual information, and minimum distance, to attain capacity. Then the (possibly noisy) OR channels and group adder channels are studied in detail. For the former the capacity is explicitly determined and shown to be attainable by minimum-distance decoding. Next, for a large class of addictive AVCs, in addition to providing an intuitively suggestive simplification of the general AVC capacity formula, it is proven that capacity can be attained by a universal decoding rule. Finally, the effect of random state selections on capacity is studied. The merits and limitations of a previous mutual information game approach are also discussed. > We consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process that adds the errors can be described by a sufficiently “simple” circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For two classes of channels, we provide explicit, efficiently encodable decodable codes of optimal rate where only inefficiently decodable codes were previously known. In each case, we provide one encoder decoder that works for every channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel. Unique decoding for additive errors: We give the first construction of a polynomial-time encodable decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1 − H(p). These are channels that add an arbitrary error vector e ∈ 0, 1 N of weight at most pN to the transmitted word; the vector e can depend on the code but not on the randomness of the encoder or the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases. List decoding for polynomial-time channels: For every constant c > 0, we construct codes with optimal rate (arbitrarily close to 1 − H(p)) that efficiently recover a short list containing the correct message with high probability for channels describable by circuits of size at most Nc. Our construction is not fully explicit but rather Monte Carlo (we give an algorithm that, with high probability, produces an encoder decoder pair that works for all time Nc channels). We are not aware of any channel models considered in the information theory literature other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list decoding with an impossibility result showing that, in a large range of parameters (p > 1 4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate. Random coding theorems are proved for discrete memoryless arbitrarily varying channels (AVCs) with constraints on the transmitted codewords and channel state sequences. Two types of constraints are considered: peak (i.e. required for each n-length sequence almost surely) and average (over the message set or over an ensemble). For peak constraints on the codewords and on the channel state sequences, the AVC is shown to have a (strong) random coding capacity. If the codewords and or the channel state sequences are constrained in the average sense, the AVCs do not possess (strong) capacities; only epsilon -capacities are shown to exist. >