TY - GEN
T1 - Codes in permutations and error correction for rank modulation
AU - Barg, Alexander
AU - Mazumdar, Arya
PY - 2010
Y1 - 2010
N2 - Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of n elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of n. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.
AB - Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of n elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of n. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.
UR - http://www.scopus.com/inward/record.url?scp=77955691952&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77955691952&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2010.5513604
DO - 10.1109/ISIT.2010.5513604
M3 - Conference contribution
AN - SCOPUS:77955691952
SN - 9781424469604
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 854
EP - 858
BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010
Y2 - 13 June 2010 through 18 June 2010
ER -