Source author record

Sarit Buzaglo

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

7works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Bounds on the Size of Permutation Codes with the Kendall $τ$ -Metric

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. Error-correction in the rank modulation scheme is done by considering permutation codes. In this paper we consider codes in the set of all permutations on $n$ elements, $S_n$ , using the Kendall $τ$ -metric. The main goal of this paper is to derive new bounds on the size of such codes. For this purpose we also consider perfect codes, diameter perfect codes, and the size of optimal anticodes in the Kendall $τ$ -metric, structures which have their own considerable interest. We prove that there are no perfect single-error-correcting codes in $S_n$ , where $n>4$ is a prime or $4\leq n\leq 10$ . We present lower bounds on the size of optimal anticodes with odd diameter. As a consequence we obtain a new upper bound on the size of codes in $S_n$ with even minimum Kendall $τ$ -distance. We present larger single-error-correcting codes than the known ones in $S_5$ and $S_7$ .

preprint2014arXiv

Constrained Codes for Rank Modulation

Motivated by the rank modulation scheme, a recent work by Sala and Dolecek explored the study of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. In this paper, the model studied by Sala and Dolecek is extended into two constraints. A permutation $σ\in S_n$ satisfies the \emph{two-neighbor $k$ -constraint} if for all $2 \leq i \leq n-1$ either $|σ(i-1)-σ(i)|\leq k$ or $|σ(i)-σ(i+1)|\leq k$ , and it satisfies the \emph{asymmetric two-neighbor $k$ -constraint} if for all $2 \leq i \leq n-1$ , either $σ(i-1)-σ(i) < k$ or $σ(i+1)-σ(i) < k$ . We show that the capacity of the first constraint is $(1+ε)/2$ in case that $k=Θ(n^ε)$ and the capacity of the second constraint is 1 regardless to the value of $k$ . We also extend our results and study the capacity of these two constraints combined with error-correction codes in the Kendall's $τ$ metric.

preprint2014arXiv

Perfect Permutation Codes with the Kendall's $τ$ -Metric

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. Error-correction in the rank modulation scheme is done by considering permutation codes. In this paper we consider codes in the set of all permutations on $n$ elements, $S_n$ , using the Kendall's $τ$ -metric. We prove that there are no perfect single-error-correcting codes in $S_n$ , where $n>4$ is a prime or $4\leq n\leq 10$ . We also prove that if such a code exists for $n$ which is not a prime then the code should have some uniform structure. We define some variations of the Kendall's $τ$ -metric and consider the related codes and specifically we prove the existence of a perfect single-error-correcting code in $S_5$ . Finally, we examine the existence problem of diameter perfect codes in $S_n$ and obtain a new upper bound on the size of a code in $S_n$ with even minimum Kendall's $τ$ -distance.

preprint2014arXiv

Systematic Codes for Rank Modulation

The goal of this paper is to construct systematic error-correcting codes for permutations and multi-permutations in the Kendall's $τ$ -metric. These codes are important in new applications such as rank modulation for flash memories. The construction is based on error-correcting codes for multi-permutations and a partition of the set of permutations into error-correcting codes. For a given large enough number of information symbols $k$ , and for any integer $t$ , we present a construction for ${(k+r,k)}$ systematic $t$ -error-correcting codes, for permutations from $S_{k+r}$ , with less redundancy symbols than the number of redundancy symbols in the codes of the known constructions. In particular, for a given $t$ and for sufficiently large $k$ we can obtain $r=t+1$ . The same construction is also applied to obtain related systematic error-correcting codes for multi-permutations.

preprint2012arXiv

Tilings by $(0.5,n)$ -Crosses and Perfect Codes

The existence question for tiling of the $n$ -dimensional Euclidian space by crosses is well known. A few existence and nonexistence results are known in the literature. Of special interest are tilings of the Euclidian space by crosses with arms of length one, known also as Lee spheres with radius one. Such a tiling forms a perfect code. In this paper crosses with arms of length half are considered. These crosses are scaled by two to form a discrete shape. We prove that an integer tiling for such a shape exists if and only if $n=2^t-1$ or $n=3^t-1$ , $t>0$ . A strong connection of these tilings to binary and ternary perfect codes in the Hamming scheme is shown.

preprint2012arXiv

Tilings with $n$ -Dimensional Chairs and their Applications to Asymmetric Codes

An $n$ -dimensional chair consists of an $n$ -dimensional box from which a smaller $n$ -dimensional box is removed. A tiling of an $n$ -dimensional chair has two nice applications in coding for write-once memories. The first one is in the design of codes which correct asymmetric errors with limited-magnitude. The second one is in the design of $n$ cells $q$ -ary write-once memory codes. We show an equivalence between the design of a tiling with an integer lattice and the design of a tiling from a generalization of splitting (or of Sidon sequences). A tiling of an $n$ -dimensional chair can define a perfect code for correcting asymmetric errors with limited-magnitude. We present constructions for such tilings and prove cases where perfect codes for these type of errors do not exist.

preprint2011arXiv

On the Existence of Perfect Codes for Asymmetric Limited-Magnitude Errors

Block codes, which correct asymmetric errors with limited-magnitude, are studied. These codes have been applied recently for error correction in flash memories. The codes will be represented by lattices and the constructions will be based on a generalization of Sidon sequences. In particular we will consider perfect codes for these type of errors.

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.

Sarit Buzaglo

Research overview

Is this your work?

7 publications

Bounds on the Size of Permutation Codes with the Kendall $τ$ -Metric

Constrained Codes for Rank Modulation

Perfect Permutation Codes with the Kendall's $τ$ -Metric

Systematic Codes for Rank Modulation

Tilings by $(0.5,n)$ -Crosses and Perfect Codes

Tilings with $n$ -Dimensional Chairs and their Applications to Asymmetric Codes

On the Existence of Perfect Codes for Asymmetric Limited-Magnitude Errors

See the researcher in context

Building this map preview

Sarit Buzaglo

Research overview

Is this your work?

7 publications

Bounds on the Size of Permutation Codes with the Kendall τττ-Metric

Constrained Codes for Rank Modulation

Perfect Permutation Codes with the Kendall's τττ-Metric

Systematic Codes for Rank Modulation

Tilings by (0.5,n)(0.5,n)(0.5,n)-Crosses and Perfect Codes

Tilings with nnn-Dimensional Chairs and their Applications to Asymmetric Codes

On the Existence of Perfect Codes for Asymmetric Limited-Magnitude Errors

See the researcher in context

Building this map preview

Bounds on the Size of Permutation Codes with the Kendall $τ$ -Metric

Perfect Permutation Codes with the Kendall's $τ$ -Metric

Tilings by $(0.5,n)$ -Crosses and Perfect Codes

Tilings with $n$ -Dimensional Chairs and their Applications to Asymmetric Codes