Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation

DOI10.1109/TIT.2017.2719710zbMATH Open1374.94837arXiv1601.05218WikidataQ59902635 ScholiaQ59902635MaRDI QIDQ4589406FDOQ4589406

Authors: Yonatan Yehezkeally, Moshe Schwartz 

Publication date: 10 November 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We construct Gray codes over permutations for the rank-modulation scheme, which are also capable of correcting errors under the infinity-metric. 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 (snake-in-the-box codes) under a different metric, the Kendall $au$-metric, in the group of permutations over an even number of elements $S_{2n}$, where we provide asymptotically optimal codes.

Full work available at URL: https://arxiv.org/abs/1601.05218

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Modulation and demodulation in information and communication theory (94A14)

Cited In (3)

• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Covering radius of permutation groups with infinity-norm
• Capacity and Codes for Embedding Information in Gray-Scale Signals

This page was built for publication: Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589406)