Source author record

Michal Horovitz

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.CO

Catalog footprint

Research overview

3works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Constructions of Snake-in-the-Box Codes for Rank Modulation

Snake-in-the-box code is a Gray code which is capable of detecting a single error. Gray codes are important in the context of the rank modulation scheme which was suggested recently for representing information in flash memories. For a Gray code in this scheme the codewords are permutations, two consecutive codewords are obtained by using the "push-to-the-top" operation, and the distance measure is defined on permutations. In this paper the Kendall's $τ$ -metric is used as the distance measure. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length $M_{2n+1}=((2n+1)(2n)-1)M_{2n-1}$ for permutations of $S_{2n+1}$ , from a snake of length $M_{2n-1}$ for permutations of~ $S_{2n-1}$ . Thus, we have $\lim\limits_{n\to \infty} \frac{M_{2n+1}}{S_{2n+1}}\approx 0.4338$ , improving on the previous known ratio of $\lim\limits_{n\to \infty} \frac{1}{\sqrt{πn}}$ . By using the general method we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length $\frac{(2n+1)!}{2} -2n+1$ for permutations of $S_{2n+1}$ . The direct construction was applied successfully for $S_7$ and $S_9$ , and hence $\lim\limits_{n\to \infty} \frac{M_{2n+1}}{S_{2n+1}}\approx 0.4743$ .

preprint2014arXiv

Local Rank Modulation for Flash Memories II

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For $0 < s\leq t\leq n$ with $s$ divides $n$ , an $(s,t,n)$ -LRM scheme is a local rank modulation scheme where the $n$ cells are locally viewed cyclically through a sliding window of size $t$ resulting in a sequence of small permutations which requires less comparisons and less distinct values. The gap between two such windows equals to $s$ . In this work, encoding, decoding, and asymptotic enumeration of the $(1,3,n)$ -LRM scheme is studied. The techniques which are suggested have some generalizations for $(1,t,n)$ -LRM, $t > 3$ , but the proofs will become more complicated. The enumeration problem is presented also as a purely combinatorial problem. Finally, we prove the conjecture that the size of a constant weight $(1,2,n)$ -LRM Gray code with weight two is at most $2n$ .

preprint2013arXiv

Local Rank Modulation for Flash Memories

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For $s\leq t\leq n$ with $s|n$ , $(s,t,n)$ -LRM scheme is a local rank modulation scheme where the $n$ cells are locally viewed through a sliding window of size $t$ resulting in a sequence of small permutations which requires less comparisons and less distinct values. The distance between two windows equals to $s$ . To get the simplest hardware implementation the case of sliding window of size two was presented. Gray codes and constant weight Gray codes were presented in order to exploit the full representational power of the scheme. In this work, a tight upper-bound for cyclic constant weight Gray code in $(1,2,n)$ -LRM scheme where the weight equals to $2$ is given. Encoding, decoding and enumeration of $(1,3,n)$ -LRM scheme is studied.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.