Codes in Permutations and Error Correction for Rank Modulation

Abstract

Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of $n$ elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of $n$. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.

Some typos corrected from the published journal version

Cited by in corpus (36)

• Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
• Snake-in-the-Box Codes for Rank Modulation
• Product Constructions for Perfect Lee Codes
• Secure Index Coding: Existence and Construction
• Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation
• Compression in the Space of Permutations
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Constructions of Rank Modulation Codes
• Rate-Distortion for Ranking with Incomplete Information
• Codes for DNA Sequence Profiles
• Partial-MDS Codes and their Application to RAID Type of Architectures
• Constructions of Snake-in-the-Box Codes under ${\ell }_{\infty }$-metric for Rank Modulation
• On ML-Certificate Linear Constraints for Rank Modulation with Linear Programming Decoding and its Application to Compact Graphs
• New Bounds for Permutation Codes in Ulam Metric
• LP Decodable Permutation Codes based on Linearly Constrained Permutation Matrices
• Snake-in-the-Box Codes for Rank Modulation under Kendall's $\tau$-Metric
• Rank Modulated Composite Encoding for Data Storage in DNA
• Quantum error correction beyond $SU(2)$: spin, bosonic, and permutation-invariant codes from convex geometry
• Optimal codes with small constant weight in ${\ell }_1$-metric
• Proof of a conjecture of Kløve on permutation codes under the Chebychev distance
• LP-decodable multipermutation codes
• Rank-Modulation Rewrite Coding for Flash Memories
• Some Enumeration Problems in the Duplication-Loss Model of Genome Rearrangement
• On the Labeling Problem of Permutation Group Codes under the Infinity Metric
• Sidon Sets, Difference Sets, and Codes in $A_n$ Lattices
• Bounds on MLDR Codes Over ${\mathbb{Z}}_{p^t}$
• Nonexistence of perfect permutation codes under the Kendall τ-metric
• Sidon Sequences and Doubly Periodic Two-Dimensional Synchronization Patterns
• Systematic Error-Correcting Codes for Rank Modulation
• Optimal Ternary Codes with Weight $w$ and Distance $2w-2$ in ${\ell }_1$-Metric
• Error-Correction in Flash Memories via Codes in the Ulam Metric
• New bounds of permutation codes under Hamming metric and Kendall's $\tau$-metric
• Multipermutation Ulam Sphere Analysis Toward Characterizing Maximal Code Size
• Infinity-Norm Permutation Covering Codes from Cyclic Groups
• Permutation codes, source coding and a generalisation of Bollobás-Lubell-Yamamoto-Meshalkin and Kraft inequalities
• Ulam Sphere Size Analysis for Permutation and Multipermutation Codes Correcting Translocation Errors