Back to Search
Start Over
Systematic Error-Correcting Codes for Rank Modulation.
- Source :
- IEEE Transactions on Information Theory; Jan2015, Vol. 61 Issue 1, p17-32, 16p
- Publication Year :
- 2015
-
Abstract
- 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 $\tau $ -metric as well as under the $\ell _\infty $ -metric. In Kendall’s $\tau $ -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. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 61
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 100150892
- Full Text :
- https://doi.org/10.1109/TIT.2014.2365499