Error-correction in flash memories via codes in the ulam metric

Farzad Hassanzadeh Farnoud, Vitaly Skachek, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review


We consider rank modulation codes for flash memories that allow for handling arbitrary charge-drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation rank codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include derivation of the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes for permutations, and permutation codes in the Hamming distance.

Original languageEnglish (US)
Article number6410424
Pages (from-to)3003-3020
Number of pages18
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - 2013


  • Data storage systems
  • Hamming distance
  • Ulam distance
  • error-correction codes
  • flash memory
  • translocation errors

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Error-correction in flash memories via codes in the ulam metric'. Together they form a unique fingerprint.

Cite this