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

  • Table 1   Parameters of $G,G_1,$ and $G_2$
    Gray code $n$ $N$ $\Psi$($\cdot$) Parameter constraint
    $G_1$ [12] $m^2$ $\mathrm{lcm}({\binom{m}{w}}^{m-2},m)\cdot(w+2)\cdot~m$ $\geq~m$ $m\geq~w,~w~~\text{is~a~positive~integer}$
    $G_2$ [11] $m^2$ $O(2^{(m-1)(m-3)})$ $\geq~m$ $m\geq~4$
    $G$ $m^2$ $O(2^{m^2\cdot~{\log_2\alpha}_d})$ $d$ $d=2d_1+3,~d_1\geq~3,~m\geq~2d_1+4,~~\alpha_d~~~\text{is~defined~in~Lemma~2}$
  •   
    Algorithm $1$ Set the initial cell charge levels $\boldsymbol{c}_{(0,0)}=(c_{(0,0)}^1,c_{(0,0)}^2,\ldots,c_{(0,0)}^n)$ such that$\boldsymbol{f}_{{\boldsymbol{c}_{(0,0)}}}=\boldsymbol{g}_{0}^{0}$ and $\boldsymbol{c}_{(0,0)}\in~$
    $(0,\frac{d+1}{2}]^{n}$
    Input: current cell configuration $0^n$, the initial value $\boldsymbol{g}_{0}=\boldsymbol{v}_{s_{m-1}}\boldsymbol{v}_{s_{m-2}}\cdot\cdot\cdot\boldsymbol{v}_{s_1}\underline{\boldsymbol{v}_{s_{0}}}$.
    Output: new cell configuration $\boldsymbol{c}_{(0,0)}=(c_{(0,0)}^1,c_{(0,0)}^2,\ldots,c_{(0,0)}^n)$.
    $k\Leftarrow~0,~T\Leftarrow\emptyset,~i\Leftarrow~3,~s\Leftarrow~0,~t\Leftarrow~0,j~\Leftarrow~0$
    repeat
    $c_{(0,0)}^{kn_1+2}\Leftarrow~1$ (let the lowest charge level be $1$).
    while $(3\leq~i\leq~n_1)\{$
    case 1: $(s=0~\text{and}~\boldsymbol{g}_{0}^{0}(kn_1+i)=0)$
    $c_{(0,0)}^{kn_1+i}\Leftarrow~c_{(0,0)}^{kn_1+i-1}+1$ ($\delta=1$ is the minimum charge difference required to distinguish
    two distinct charge levels and this cell corresponds the bit $0$).
    case 2: $(s=0~\text{and}~\boldsymbol{g}_{0}^{0}(kn_1+i)=1)$
    $s\Leftarrow~i,T\Leftarrow~T\cup\{i\}$ ($T$ is the set of cells with the highest level).
    case 3: $(s\neq0~\text{and}~\boldsymbol{g}_{0}^{0}(kn_1+i)=0)$
    $t\Leftarrow~i,j\Leftarrow~(t-1),c_{(0,0)}^{kn_1+i}\Leftarrow~1$ (this cell has the lowest level);
    while ($s+1\leq~j\leq~t-1$)
    $c_{(0,0)}^{kn_1+j}\Leftarrow~c_{(0,0)}^{kn_1+j+1}+1,j\Leftarrow~j-1$ (this cell corresponds to the bit $1$).
    $s\Leftarrow0$.
    $i\Leftarrow~i+1$.
    $c_{(0,0)}^{kn_1+1}\Leftarrow~c_{(0,0)}^{kn_1+1+d_1}+1$ (push first cell in each block to the next-highest level);
    while $(l\in~T)\{$
    $c_{(0,0)}^{kn_1+l}\Leftarrow\max\{c_{(0,0)}^{kn_1+1},c_{(0,0)}^{kn_1+l-1},c_{(0,0)}^{kn_1+l+1}\}+1$ (push this cell to the highest level);
    $T\Leftarrow~T\setminus\{l\}$$\}$.
    $i\Leftarrow3,T\Leftarrow\emptyset,s\Leftarrow0,k\Leftarrow~k+1$ (initially, set some parameters for block $k+1$).
    until $k=m-1$.
  •   
    Algorithm $2$ Transform the cell configuration $\boldsymbol{c}_{{s_{i}}}$ into another cell configuration $\boldsymbol{c}_{{s_{i+m}}}$ such that $\boldsymbol{f}_{\boldsymbol{c}_{{s_{i}}}}=\boldsymbol{v}_{s_{i}}$ and
    $\boldsymbol{f}_{{\boldsymbol{c}_{s_{i+m}}}}=\boldsymbol{v}_{s_{i+m}}$
    Input: Current cell configuration $\boldsymbol{c}_{{s_{i}}}$, the initial value $\boldsymbol{v}_{s_{i}}$, new block value $\boldsymbol{v}_{s_{i+m}}$.
    Output: New cell configuration $\boldsymbol{c}_{{s_{i+m}}}$.
    $k\Leftarrow~0,~T\Leftarrow\emptyset,~H_1\Leftarrow~\emptyset,~H_2\Leftarrow~\emptyset,~j\Leftarrow~3,~s\Leftarrow~0,~t\Leftarrow~0$
    $\boldsymbol{c}_{{s_{i+m}}}(2)\Leftarrow\max\{\boldsymbol{c}_{{s_{i}}}(1),\boldsymbol{c}_{{s_{i}}}(3)\}+1$ (push the $2$nd cell to the highest level in $\boldsymbol{c}_{{s_{i}}}$).
    while $(3\leq~j\leq~n_1)\{$
    case 1: $(j\leq~d_1+2)$
    $\boldsymbol{c}_{{s_{i+m}}}(j)\Leftarrow\max\{\boldsymbol{c}_{{s_{i+m}}}(j-1),\boldsymbol{c}_{{s_{i}}}(j+1)\}+1$ (push the $j$th cell in a run of $0$s).
    case 2: $(s=0~\text{and}~\boldsymbol{v}_{s_{i+m}}(j)=1)$
    $s\Leftarrow~j,T\Leftarrow~T\cup\{j\}$ (this cell is the highest in $\boldsymbol{c}_{{s_{i+m}}}$).
    if $t\neq~0$ then
    $H_2\Leftarrow~H_2\cup\{(t,s)\}$ ($H_2$ is a set of runs of $0$s).
    case 3: $(s\neq0~\text{and}~\boldsymbol{v}_{s_{i+m}}(j)=0)$
    $t\Leftarrow~j$ ($t$ represents the position of the lowest cell in $\boldsymbol{v}_{s_{i+m}}$).
    $H_1\Leftarrow~H_1\cup\{(s,t)\}$ ($H_1$ is a set of runs of $1$s).
    if $\boldsymbol{v}_{s_{i}}(j-1)=0~\text{and}~\boldsymbol{v}_{s_{i}}(j)=1$ then
    $\boldsymbol{c}_{{s_{i+m}}}(j)\Leftarrow\boldsymbol{c}_{{s_{i}}}(j)$ (this is the highest cell in $\boldsymbol{c}_{s_i}$. Let the charge level of this
    cell remain unchanged);
    else
    $\boldsymbol{c}_{{s_{i+m}}}(j)\Leftarrow\max\{\boldsymbol{c}_{{s_{i}}}(1),\boldsymbol{c}_{{s_{i}}}(j-1),\boldsymbol{c}_{{s_{i}}}(j+1)\}+1$.
    $s\Leftarrow0$.
    $j\Leftarrow~j+1$.
    $\boldsymbol{c}_{{s_{i+m}}}(1)\Leftarrow\boldsymbol{c}_{{s_{i+m}}}(1+d_1)+1$ (push the first cell to next-highest level in the changed block);
    while big($A=(s_1,t_1)\in~H_1$big)
    $k\Leftarrow~(t_1-1)$
    if ($s_1+1\leq~k\leq~t_1-1$)
    $\boldsymbol{c}_{{s_{i+m}}}(k)\Leftarrow\max\{\boldsymbol{c}_{{s_{i}}}(k-1),\boldsymbol{c}_{{s_{i+m}}}(k+1)\}+1, k\Leftarrow~(k-1)$; $H_1\Leftarrow~H_1\setminus\{A\}$.
    while big($B=(t_1,s_1\big)\in~H_2$)
    $k\Leftarrow~(t_1+1)$;
    if ($t_1+1\leq~k\leq~s_1-1$)
    $\boldsymbol{c}_{{s_{i+m}}}(k)\Leftarrow\max\{\boldsymbol{c}_{{s_{i+m}}}(k-1),\boldsymbol{c}_{{s_i}}(k+1)\}+1, k\Leftarrow~(k+1)$; $H_2\Leftarrow~H_2\setminus\{B\}$.
    while $(l\in~T)\{$
    $\boldsymbol{c}_{{s_{i+m}}}(l)\Leftarrow\max\{\boldsymbol{c}_{{s_{i+m}}}(1),\boldsymbol{c}_{{s_{i+m}}}(1-1),\boldsymbol{c}_{{s_{i+m}}}(1+1)\}+1$(let the charge level of this cell be the highest in
    the changed block); $T\Leftarrow~T\setminus\{l\}$$\}$.
  • Table 2   Rates of our Gray code $G$ with respect to $d$
    $d$ $R=~\frac{{\log}_{2}N}{n}$
    $13$ $\log_2\alpha_3=0.8543$
    $15$ $\log_2\alpha_4=0.9468$
    $17$ $\log_2\alpha_5=0.9752$
    $d\rightarrow\infty$ $1$

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

京ICP备18024590号-1