Back to Search
Start Over
Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation.
- Source :
-
IEEE Transactions on Information Theory . Sep2017, Vol. 63 Issue 9, p5774-5792. 19p. - Publication Year :
- 2017
-
Abstract
- We construct error-correcting codes over permutations under the infinity-metric, which are also Gray codes in the context of rank modulation, i.e., are generated as simple circuits in the rotator graph. These errors model limited-magnitude or spike errors, for which only single-error-detecting Gray codes are currently known. Surprisingly, the error-correcting codes we construct achieve a better asymptotic rate than that of presently known constructions not having the Gray property, and exceed the Gilbert-Varshamov bound. Additionally, we present efficient ranking and unranking procedures, as well as a decoding procedure that runs in linear time. Finally, we also apply our methods to solve an outstanding issue with error-detecting rank-modulation Gray codes (also known in this context as snake-in-the-box codes) under a different metric, the Kendall $\tau $ -metric, in the group of permutations over an even number of elements S_{2n} , where we provide asymptotically optimal codes. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 63
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 124750446
- Full Text :
- https://doi.org/10.1109/TIT.2017.2719710