Sarit Buzaglo – Constrained codes for rank modulation


Event Details

  • Date:

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 σ ∈ Sn satisfies the two-neighbor k-constraint if for all 2 ≤ i ≤ n – 1 either |σ(i – 1) – σ(i)| ≤ k or |σ(i) – σ(i + 1)| ≤ k, and it satisfies the asymmetric two-neighbor k-constraint if for all 2 ≤ i ≤ 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.