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.
Notice that, in all of the above-mentioned works with the exception of @cite_3 , no upper bound on the number of inserted duplicates at each position was assumed, i.e., @math is taken to be @math . We find the assumption @math realistic, especially in the context of the model with synchronization errors that inspired introducing the duplication channel in the first place. Our main results here are a construction of optimal zero-error codes and a characterization of the zero-error capacity of the @math -duplication channel, for any fixed @math and @math . We recover the mentioned results from @cite_7 as a special case when @math , and we also obtain the discrete-time analogs of the results from @cite_3 as a special case when @math . Moreover, and further generalizing our results, we obtain a characterization of the zero-error capacity of the @math - @math -insertion channel.
@cite_7 @cite_3
2601746657 2115885621
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.