Title: Multipermutation Ulam Sphere Analysis Toward Characterizing Maximal Code Size,
Abstract: Permutation codes, in the form of rank modulation, have shown promise for
applications such as flash memory. One of the metrics recently suggested as
appropriate for rank modulation is the Ulam metric, which measures the minimum
translocation distance between permutations. Multipermutation codes have also
been proposed as a generalization of permutation codes that would improve code
size (and consequently the code rate). In this paper we analyze the Ulam metric
in the context of multipermutations, noting some similarities and differences
between the Ulam metric in the context of permutations. We also consider sphere
sizes for multipermutations under the Ulam metric and resulting bounds on code
size.