Multipermutation codes in the Ulam metric for nonvolatile memories

Farzad Farnoud Hassanzadeh, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review


We address the problem of multipermutation code design in the Ulam metric for novel storage applications. Multipermutation codes are suitable for flash memory where cell charges may share the same rank. Changes in the charges of cells manifest themselves as errors whose effects on the retrieved signal may be measured via the Ulam distance. As part of our analysis, we study multipermutation codes in the Hamming metric, known as constant composition codes. We then present bounds on the size of multipermutation codes and their capacity, for both the Ulam and the Hamming metrics. Finally, we present constructions and accompanying decoders for multipermutation codes in the Ulam metric.

Original languageEnglish (US)
Article number6804937
Pages (from-to)919-932
Number of pages14
JournalIEEE Journal on Selected Areas in Communications
Issue number5
StatePublished - May 2014


  • Constant composition code
  • Hamming metric
  • Ulam metric
  • deletion
  • flash memory
  • frequency permutation array
  • multipermutation code
  • permutation code
  • rank modulation
  • re-writing code
  • translocation

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Multipermutation codes in the Ulam metric for nonvolatile memories'. Together they form a unique fingerprint.

Cite this