TY - GEN
T1 - Multipermutation codes in the Ulam metric
AU - Farnoud, Farzad
AU - Milenkovic, Olgica
PY - 2014
Y1 - 2014
N2 - We present a multiset rank modulation scheme capable of correcting translocation errors, motivated by the fact that compared to permutation codes, multipermutation codes offer higher rates and longer block lengths. We show that the appropriate distance measure for code construction is the Ulam metric applied to equivalence classes of permutations, where each permutation class corresponds to a multipermutation. The paper includes a study of multipermutation codes in the Hamming metric, also known as constant composition codes, due to their use in constructing multipermutation codes in the Ulam metric. We derive bounds on the size of multipermutation codes in both the Ulam metric and the Hamming metric, compute their capacity, and present constructions for codes in the Ulam metric based on permutation interleaving, semi-Latin squares, and resolvable Steiner systems.
AB - We present a multiset rank modulation scheme capable of correcting translocation errors, motivated by the fact that compared to permutation codes, multipermutation codes offer higher rates and longer block lengths. We show that the appropriate distance measure for code construction is the Ulam metric applied to equivalence classes of permutations, where each permutation class corresponds to a multipermutation. The paper includes a study of multipermutation codes in the Hamming metric, also known as constant composition codes, due to their use in constructing multipermutation codes in the Ulam metric. We derive bounds on the size of multipermutation codes in both the Ulam metric and the Hamming metric, compute their capacity, and present constructions for codes in the Ulam metric based on permutation interleaving, semi-Latin squares, and resolvable Steiner systems.
UR - http://www.scopus.com/inward/record.url?scp=84906537003&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906537003&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2014.6875335
DO - 10.1109/ISIT.2014.6875335
M3 - Conference contribution
AN - SCOPUS:84906537003
SN - 9781479951864
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2754
EP - 2758
BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014
Y2 - 29 June 2014 through 4 July 2014
ER -