A Caltech Library Service

Constant-Weight Gray Codes for Local Rank Modulation

En Gad, Eyal and Langberg, Michael and Schwartz, Moshe and Bruck, Jehoshua (2011) Constant-Weight Gray Codes for Local Rank Modulation. IEEE Transactions on Information Theory, 57 (11). pp. 7431-7442. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We consider the local rank-modulation (LRM) scheme in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. LRM is a generalization of the rank-modulation scheme, which has been recently suggested as a way of storing information in flash memory. We study constant-weight Gray codes for the LRM scheme in order to simulate conventional multilevel flash cells while retaining the benefits of rank modulation. We present a practical construction of codes with asymptotically-optimal rate and weight asymptotically half the length, thus having an asymptotically-optimal charge difference between adjacent cells. Next, we turn to examine the existence of optimal codes by specifically studying codes of weight 2 and 3. In the former case, we upper bound the code efficiency, proving that there are no such asymptotically-optimal cyclic codes. In contrast, for the latter case we construct codes which are asymptotically-optimal. We conclude by providing necessary conditions for the existence of cyclic and cyclic optimal Gray codes.

Item Type:Article
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2011 IEEE. Manuscript received December 29, 2010; revised May 13, 2011; accepted July 07, 2011. Date of current version November 11, 2011. This work was supported in part by the ISF under Grant 134/10 and Grant 480/08, by the Open University of Israel’s research fund under Grant 46114, and by the NSF under Grant NSF-0801795, and under an NSF-NRI award.
Funding AgencyGrant Number
Open University of Israel46114
Subject Keywords:Flash memory, gray code, local rank modulation, permutations, rank modulation
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12356979
Issue or Number:11
Record Number:CaltechAUTHORS:20120420-092834437
Persistent URL:
Official Citation:Gad, E.E.; Langberg, M.; Schwartz, M.; Bruck, J.; , "Constant-Weight Gray Codes for Local Rank Modulation," Information Theory, IEEE Transactions on , vol.57, no.11, pp.7431-7442, Nov. 2011 doi: 10.1109/TIT.2011.2162570 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:30214
Deposited By: Tony Diaz
Deposited On:23 Apr 2012 21:46
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page