Motivated by communication channels in which the transmitted sequences are subject to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any “error radius” and any alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.

A (tandem) duplication of length k is an insertion of an exact copy of a substring of length k 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 Levenshtein’s 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 k. Furthermore, we derive bounds on the cardinality of optimal q-ary codes correcting up to t duplications of length k, and establish the following corollaries in the asymptotic regime of growing block-length: 1) the presented family of codes is optimal for every q, t, k, in the sense of the asymptotic scaling of code redundancy; 2) the upper bound, when specialized to q = 2, k = 1, improves upon Levenshtein’s bound for every t ≥ 3; 3) the bounds coincide for t = 1, thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes.

We analyze the problem of zero-error communication through timing channels that can be interpreted as discrete-time queues with bounded waiting times. The channel model includes the following assumptions: 1) Time is slotted, 2) at most $ N $ "particles" are sent in each time slot, 3) every particle is delayed in the channel for a number of slots chosen randomly from the set $ \{0, 1, \ldots, K\} $, and 4) the particles are identical. It is shown that the zero-error capacity of this channel is $ \log r $, where $ r $ is the unique positive real root of the polynomial $ x^{K+1} - x^{K} - N $. Capacity-achieving codes are explicitly constructed, and a linear-time decoding algorithm for these codes devised. In the particular case $ N = 1 $, $ K = 1 $, the capacity is equal to $ \log \phi $, where $ \phi = (1 + \sqrt{5}) / 2 $ is the golden ratio, and the constructed codes give another interpretation of the Fibonacci sequence.Comment: 5 pages (double-column), 3 figures. v3: Section IV.1 from v2 is replaced with Remark 1, and Section IV.2 is removed. Accepted for publication in IEEE Transactions on Information Theor

This paper is concerned with the problem of error-free communication over the i.i.d. duplication channel which acts on a transmitted sequence x1...xn by inserting a random number of copies of each symbol xi next to the original symbol. The random variables representing the numbers of inserted copies at each position i are independent and take values in {0,1,...,r}, where r is a fixed parameter. A more general model in which blocks of ℓ consecutive symbols are being duplicated, and which is inspired by DNA-based data storage systems wherein the stored molecules are subject to tandem-duplication mutations, is also analyzed. A construction of optimal codes correcting all patterns of errors of this type is described, and the zero-error capacity of the duplication channel—the largest rate at which information can be transmitted through it in an error-free manner—is determined for each ℓ and r.