logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 100305(2018) https://doi.org/10.1007/s11432-018-9509-y

Gray codes over certain run-length sequences for local rank modulation$^\dagger$

More info
  • ReceivedMar 9, 2018
  • AcceptedJun 28, 2018
  • PublishedAug 21, 2018

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.


Acknowledgment

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).


References

[1] Jiang A X, Mateescu R, Schwartz M. Rank modulation for flash memories. IEEE Trans Inform Theor, 2009, 55: 2659-2673 CrossRef Google Scholar

[2] Jiang A X, Schwartz M, Bruck J. Correcting charge-constrained errors in the rank-modulation scheme. IEEE Trans Inform Theor, 2010, 56: 2112-2120 CrossRef Google Scholar

[3] Tamo I, Schwartz M. Correcting limited-magnitude errors in the rank-modulation scheme. IEEE Trans Inform Theor, 2010, 56: 2551-2560 CrossRef Google Scholar

[4] 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. Google Scholar

[5] Gray F. Pulse Code Communication. U. S. Patent, 2632058, 1953, 17. Google Scholar

[6] 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 CrossRef Google Scholar

[7] Chen M S, Shin K G. Subcube allocation and task migration in hypercube multiprocessors. IEEE Trans Comput, 1990, 39: 1146-1155 CrossRef Google Scholar

[8] Ludman J. Gray code generation for MPSK signals. IEEE Trans Commun, 1981, 29: 1519-1522 CrossRef Google Scholar

[9] Richards D. Data compression and gray-code sorting. Inf Processing Lett, 1986, 22: 201-205 CrossRef Google Scholar

[10] Savage C. A survey of combinatorial Gray codes. SIAM Rev, 1997, 39: 605-629 CrossRef ADS Google Scholar

[11] En Gad E, Langberg M, Schwartz M. Generalized Gray codes for local rank modulation. IEEE Trans Inform Theor, 2013, 59: 6664-6673 CrossRef Google Scholar

[12] Gad E, Langberg M, Schwartz M. Constant-weight Gray codes for local rank modulation. IEEE Trans Inform Theor, 2011, 57: 7431-7442 CrossRef Google Scholar

[13] 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 CrossRef Google Scholar

[14] Horovitz M, Etzion T. Constructions of snake-in-the-box codes for rank modulation. IEEE Trans Inform Theor, 2014, 60: 7016-7025 CrossRef Google Scholar

[15] Zhang Y, Ge G. Snake-in-the-box codes for rank modulation under Kendall's $\tau~$ -metric. IEEE Trans Inform Theor, 2016, 62: 151-158 CrossRef Google Scholar

[16] Yehezkeally Y, Schwartz M. Snake-in-the-box codes for rank modulation. IEEE Trans Inform Theor, 2012, 58: 5471-5483 CrossRef Google Scholar

[17] Laisant C A. Sur la numération factorielle, application aux permutations. Bull de la Société Mathématiq. de France, 1888, 16: 176--183. Google Scholar

[18] Ferreira H C, Vinck A J H, Swart T G. Permutation trellis codes. IEEE Trans Commun, 2005, 53: 1782-1789 CrossRef Google Scholar

[19] Blake I F. The enumeration of certain run length sequences. Inf Control, 1982, 55: 222-237 CrossRef Google Scholar

[20] Kautz W. Fibonacci codes for synchronization control. IEEE Trans Inform Theor, 1965, 11: 284-292 CrossRef Google Scholar

[21] Golomb S W. Shift Register Sequences. San Francisco: Holden-Day, 1967. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1