Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation ball sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing upper and lower bounds on multipermutation Ulam ball sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric.

This paper introduces descent moment distributions for analysis of single and multi permutation codes defined via Levenshtein (VT) codes. Originally this work is motivated by computer experiments of deletion spheres for contant weight codes and the authors proved properties in a theoretical manner.

Formalization deals with expressing definitions or theorems and proofs at the level of fundamental logic, which allows for automatic verification by computer programs. We report on work done formalizing definitions and theorems in coding theory using the Lean theorem prover, released by Microsoft Research and Carnegie Mellon University in 2015. We formalize fundamental concepts regarding error-correcting codes capable of correcting insertions, deletions, or combinations of insertions and deletions. In particular, we formalize definitions and theorems about subsequences and supersequences, the Levenshtein distance, insertion/deletion spheres, and insertion/deletion codes.

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. Multipermutation codes have also been proposed as a generalization of permutation codes that would improve code size. In this paper we analyze the Ulam metric in the context of multipermutations, noting similarities and differences with the Ulam metric in the context of permutations. We then consider sphere sizes for multipermutations under the Ulam metric and resulting bounds on code size.