This paper is motivated by the problem of error-free communication through the i.i.d. duplication channel which acts on the transmitted sequence by inserting a random number of duplicates of each symbol next to the original symbol. A construction of optimal codes correcting all patterns of errors of this type is described, and the zero-error capacity of the duplication channel is determined. A generalization of these results to channel models in which blocks of @math consecutive symbols are being duplicated, and which are inspired by DNA-based data storage systems where the stored molecules are subject to tandem-duplication mutations, is also given.
The binary @math - @math -insertion channel was first studied in @cite_16 , where a construction of codes correcting @math such errors was given, and asymptotic bounds on the cardinality of optimal codes derived for any fixed @math and @math . Another construction for same model was later given in @cite_9 . Generalizations of the constructions from @cite_16 and @cite_9 for the @math -duplication channel were given in @cite_22 and @cite_5 , respectively. The best known asymptotic bounds for the @math -duplication channel in the regime of fixed @math and @math , were reported in @cite_22 , where the upper bound from @cite_16 (for @math ) was improved for every @math , and the bounds were also generalized to the case @math .
@cite_5 @cite_9 @cite_16 @cite_22
2858362441 2082173153 2888898008
A (tandem) duplication of length @math is an insertion of an exact copy of a substring of length @math next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshteins construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length @math . Furthermore, we derive bounds on the cardinality of optimal @math -ary codes correcting up to @math duplications of length @math and establish the following corollaries in the asymptotic regime of growing block length: 1) the presented family of codes is optimal for every @math , in the sense of the asymptotic scaling of code redundancy; 2) the upper bound, when specialized to @math , @math , improves upon Levenshteins bound for every @math ; and 3) the bounds coincide for @math , thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes. In this paper, we study codes correcting @math duplications of @math consecutive symbols. These errors are known as tandem duplication errors, where a sequence of symbols is repeated and inserted directly after its original occurrence. Using sphere packing arguments, we derive non-asymptotic upper bounds on the cardinality of codes that correct such errors for any choice of parameters. Based on the fact that a code correcting insertions of @math zero-blocks can be used to correct @math tandem duplications, we construct codes for tandem duplication errors. We compare the cardinalities of these codes with their sphere packing upper bounds. Finally, we discuss the asymptotic behavior of the derived codes and bounds, which yields insights about the tandem duplication channel. In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number @math of repetitions, in the sense that no two strings in the code can give rise to the same string after @math repetitions. We propose explicit number theoretic constructions of such subsets. In the case of @math repetition, the proposed construction is asymptotically optimal. For @math , the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to @math repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number @math of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any @math repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math .