Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2012 | Submitted
Book Section - Chapter Open

Systematic Error-Correcting Codes for Rank Modulation


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.

Additional Information

© 2012 IEEE. Date of Current Version: 27 August 2012. This work was supported in part by an NSF grant ECCS-0801795 and by a BSF grant 2010075.

Attached Files

Submitted - 1310.6817.pdf


Files (216.9 kB)
Name Size Download all
216.9 kB Preview Download

Additional details

August 19, 2023
January 13, 2024