  In this paper, we introduce a new way of constructing and decoding
multipermutation codes. Multipermutations are permutations of a multiset that
generally consist of duplicate entries. We first introduce a class of binary
matrices called multipermutation matrices, each of which corresponds to a
unique and distinct multipermutation. By enforcing a set of linear constraints
on these matrices, we define a new class of codes that we term LP-decodable
multipermutation codes. In order to decode these codes using a linear program
(LP), thereby enabling soft decoding, we characterize the convex hull of
multipermutation matrices. This characterization allows us to relax the coding
constraints to a polytope and to derive two LP decoding problems. These two
problems are respectively formulated by relaxing the maximum likelihood
decoding problem and the minimum Chebyshev distance decoding problem.
  Because these codes are non-linear, we also study efficient encoding and
decoding algorithms. We first describe an algorithm that maps consecutive
integers, one by one, to an ordered list of multipermutations. Based on this
algorithm, we develop an encoding algorithm for a code proposed by Shieh and
Tsai, a code that falls into our class of LP-decodable multipermutation codes.
Regarding decoding algorithms, we propose an efficient distributed decoding
algorithm based on the alternating direction method of multipliers (ADMM).
Finally, we observe from simulation results that the soft decoding techniques
we introduce can significantly outperform hard decoding techniques that are
based on quantized channel outputs.
