Systematic Error-Correcting Codes for Rank Modulation
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
The rank modulation scheme has been proposed recently for efficiently writing and storing data in nonvolatile memories. Error-correcting codes are very important for rank modulation, and they have attracted interest among researchers. In this work, we explore a new approach, systematic error-correcting codes for rank modulation. In an (n, k) systematic code, we use the permutation induced by the levels of n cells to store data, and the permutation induced by the first k cells (k < n) has a one-to-one mapping to information bits. Systematic codes have the benefits of enabling efficient information retrieval and potentially supporting more efficient encoding and decoding procedures. We study systematic codes for rank modulation equipped with the Kendall's -distance. We present (k + 2, k) systematic codes for correcting one error, which have optimal sizes unless perfect codes exist. We also study the design of multi-error-correcting codes, and prove that for any 2 k < n, there always exists an (n, k) systematic code of minimum distance n-k. Furthermore, we prove that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes. 2012 IEEE.
name of conference
2012 IEEE International Symposium on Information Theory Proceedings
