Abstract
In the local rank modulation (LRM) scheme, a sliding window produces a sequence of permutations by moving over a sequence of variables. LRM has been presented as a method of storing data in flash memory, which represents a natural generalization of the classical rank modulation scheme. In this paper, we present a study on Gray codes over certain run-length sequences for the (1, 2, n)-LRM scheme to simulate virtual multilevel flash memory cells while maintaining the advantages of LRM. Unlike previous studies on the LRM scheme, we present Gray codes over certain run-length sequences in the (1, 2, n)-LRM scheme. This class of Gray codes can overcome the drawback of the many distinct charge levels required in the rank modulation scheme and in certain Gray codes for LRM. Furthermore, we demonstrate that the proposed codes have an asymptotically optimal rate.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Jiang A X, Mateescu R, Schwartz M, et al. Rank modulation for flash memories. IEEE Trans Inform Theor, 2009, 55: 2659–2673
Jiang A X, Schwartz M, Bruck J. Correcting charge-constrained errors in the rank-modulation scheme. IEEE Trans Inform Theor, 2010, 56: 2112–2120
Tamo I, Schwartz M. Correcting limited-magnitude errors in the rank-modulation scheme. IEEE Trans Inform Theor, 2010, 56: 2551–2560
Wang Z Y, Jiang A X, Bruck J. On the capacity of bounded rank modulation for flash memories. In: Proceedings of IEEE International Symposium Information Theory, Seoul, 2009. 1234–1238
Gray F. Pulse Code Communication. U. S. Patent, 2632058, 1953, 17
Chang C C, Chen H Y, Chen C Y. Symbolic gray code as a data allocation scheme for two-disc systems. Comput J, 1992, 35: 299–305
Chen M S, Shin K G. Subcube allocation and task migration in hypercube multiprocessors. IEEE Trans Comput, 1990, 39: 1146–1155
Ludman J. Gray code generation for MPSK signals. IEEE Trans Commun, 1981, 29: 1519–1522
Richards D. Data compression and Gray-code sorting. Inf Process Lett, 1986, 22: 201–205
Savage C D. A survey of combinatorial Gray codes. SIAM Rev, 1997, 39: 605–629
En Gad E, Langberg M, Schwartz M, et al. Generalized Gray codes for local rank modulation. IEEE Trans Inform Theor, 2013, 59: 6664–6673
En Gad E, Langberg M, Schwartz M, et al. Constant-weight Gray codes for local rank modulation. IEEE Trans Inform Theor, 2011, 57: 7431–7442
Farnoud F, Skachek V, Milenkovic O. Error-correction in flash memories via codes in the Ulam metric. IEEE Trans Inform Theor, 2013, 59: 3003–3020
Horovitz M, Etzion T. Constructions of snake-in-the-box codes for rank modulation. IEEE Trans Inform Theor, 2014, 60: 7016–7025
Ge G N, Zhang Y W. Snake-in-the-box codes for rank modulation under Kendall’s-metric. IEEE Trans Inform Theor, 2016, 62: 151–158
Yehezkeally Y, Schwartz M. Snake-in-the-box codes for rank modulation. IEEE Trans Inform Theor, 2012, 58: 5471–5483
Laisant C A. Sur la numération factorielle, application aux permutations. Bull de la Société Mathématiq. de France, 1888, 16: 176–183
Ferreira H C, Vinck A J H, Swart T G, et al. Permutation trellis codes. IEEE Trans Commun, 2005, 53: 1782–1789
Blake I F. The enumeration of certain run length sequences. Inf Control, 1982, 55: 222–237
Kautz W H. Fibonacci codes for synchronization control. IEEE Trans Inform Theor, 1965, 11: 284–292
Golomb S W. Shift Register Sequences. San Francisco: Holden-Day, 1967
Acknowledgements
This work was supported by National Basic Research Program of China (973) (Grant No. 2013CB834204) and National Natural Science Foundation of China (Grant No. 61571243).
Author information
Authors and Affiliations
Corresponding author
Additional information
Invited article
Rights and permissions
About this article
Cite this article
Wang, X., Fu, FW. Gray codes over certain run-length sequences for local rank modulation. Sci. China Inf. Sci. 61, 100305 (2018). https://doi.org/10.1007/s11432-018-9509-y
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-018-9509-y