Deletions in multipermutations
Frédéric Sala, Ryan Gabrys, Lara Dolecek · 2014
Codes based on multiset permutations, or multipermutations, have attracted recent attention due to their applications to non-volatile memories. Most of the literature studying multipermutations is focused on codes capable of correcting errors in the Kendall tau and Ulam metrics. In this work, we make a first effort towards studying synchronization errors over multipermutations. We begin by defining the concept of multipermutation deletions. We characterize the nature and effects of such errors. We provide an expression for the number of multipermutations formed by a single multipermutation deletion. Finally, we introduce code constructions which correct one or more multipermutation deletions.