Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme

DOI10.1109/TIT.2010.2046241zbMATH Open1366.94672arXiv0907.3387WikidataQ59903027 ScholiaQ59903027MaRDI QIDQ5281432FDOQ5281432

Authors: Itzhak Tamo, Moshe Schwartz 

Publication date: 27 July 2017

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

Abstract: We study error-correcting codes for permutations under the infinity norm, motivated by a novel storage scheme for flash memories call rank modulation. In this scheme, a set of $n$ flash cells are combined to create a single virtual multi-level cell. Information is stored in the permutation induced by the cell charge levels. Spike errors, which are characterized by a limited-magnitude change in cell charge levels, correspond to a low-distance change under the infinity norm. We define codes protecting against spike errors, called limited-magnitude rank-modulation codes (LMRM codes), and present several constructions for these codes, some resulting in optimal codes. These codes admit simple recursive, and sometimes direct, encoding and decoding procedures. We also provide lower and upper bounds on the maximal size of LMRM codes both in the general case, and in the case where the codes form a subgroup of the symmetric group. In the asymptotic analysis, the codes we construct out-perform the Gilbert-Varshamov-like bound estimate.

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

Mathematics Subject Classification ID

Combinatorial codes (94B25) Mathematical problems of computer architecture (68M07) Burst-correcting codes (94B20) Modulation and demodulation in information and communication theory (94A14)

Cited In (13)

• Optimal permutation anticodes with the infinity norm via permanents of \((0,1)\)-matrices
• Constructions and invariants of optimal codes in the Lee metric
• Computing the ball size of frequency permutations under Chebyshev distance
• Coding for locality in reconstructing permutations
• Title not available (Why is that?)
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Covering radius of permutation groups with infinity-norm
• Lower bounds on the size of spheres of permutations under the Chebychev distance
• Increasing the minimum distance of codes by twisting
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric
• Error-correcting codes from \(k\)-resolving sets
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric

This page was built for publication: Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme

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