Multiset Deletion Codes: Cyclic Constructions, Bounds, and Exact Results

Abstract

We study deletion-correcting codes in the space of length-$n$ multisets over a $q$-ary alphabet. We present an explicit cyclic Sidon-type construction for arbitrary alphabet size $q$ and deletion radius $t$, defined by a single congruence modulo $t(t+1{)}^{q-2}+1$. The construction has redundancy at most ${\log }_q(t(t+1{)}^{q-2}+1)$ and admits linear-time online decoding for fixed $q$ and $t$ after finite preprocessing. We prove that its syndrome classes are asymptotically balanced and compare several general upper bounds. For a single deletion, we show that the natural sum-modulo construction is asymptotically optimal for every fixed $q$. We also obtain exact results for $q=3$ and $q=4$, including uniqueness results for optimal codes in the relevant parameter ranges, and formulate conjectures for prime alphabets.

24 pages

Topics & keywords