Systematic Error-Correcting Codes for Rank Modulation
- Additional Document Info
- View All
1963-2012 IEEE. The rank-modulation scheme has been recently proposed for efficiently storing data in nonvolatile memories. In this paper, we explore [n,k,d] systematic error-correcting codes for rank modulation. Such codes have length n, k information symbols, and minimum distance d. Systematic codes have the benefits of enabling efficient information retrieval in conjunction with memory-scrubbing schemes. We study systematic codes for rank modulation under Kendall's $ au $ -metric as well as under the $ell -infty $ -metric. In Kendall's $ au $ -metric, we present [k+2,k,3] systematic codes for correcting a single error, which have optimal rates, unless systematic perfect codes exist. We also study the design of multierror-correcting codes, and provide a construction of [k+t+1,k,2t+1] systematic codes, for large-enough k. We use nonconstructive arguments to show that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes. Finally, in the $ell -infty $ -metric, we construct two [n,k,d] systematic multierror-correcting codes, the first for the case of d=O(1) and the second for d=Theta (n). In the latter case, the codes have the same asymptotic rate as the best codes currently known in this metric.
IEEE Transactions on Information Theory
author list (cited authors)
Hongchao Zhou, .., Schwartz, M., Jiang, A. A., & Bruck, J.
complete list of authors
Schwartz, Moshe||Jiang, Anxiao Andrew||Bruck, Jehoshua