Error-correcting codes for multipermutations

Multipermutations appear in various applications in information theory. New applications such as rank modulation for flash memories and voting have suggested the need to consider error-correcting codes for multipermutations. The construction of codes is challenging when permutations are considered and it becomes even a harder problem for multipermutations. In this paper we discuss the general problem of error-correcting codes for multipermutations. We present some tight bounds on the size of error-correcting codes for several families of multipermutations. We find the capacity of the channels of multipermutations and characterize families of perfect codes in this metric which we believe are the only such perfect codes.