Abstract-Motivated by communication channels in which the transmitted sequences are subject to random permutations, as well as by 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 errorcorrecting 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 minimal asymptotic code redundancy, for any "error radius" and any alphabet size. It is also shown to be optimal in the sense of maximal code cardinality in various cases.
Permutation channel with impairments was considered in REF , where the input and output are multi-sets, rather than vectors, of symbols from a finite alphabet.
Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
IEEE Trans. Inform. Theory, vol. 64, no. 7, pp. 5156--5169, Jul. 2018
Computer Science Mathematics