Parallel Programming of Rank Modulation Conference Paper uri icon


  • Rank modulation is a technique for representing stored information in an ordered set of flash memory cells by a permutation that reflects the ranking of their voltage levels. In this paper, we consider two figures of merit that can be used to compare parallel programming algorithms for rank modulation. These two criteria represent different tradeoffs between the programming speed and the lifetime of flash memory cells. In the first scenario, we want to find the minimum number of programming rounds required to increase a specified cell-level vector 0 to a cell-level vector corresponding to a target rank permutation , with no restriction on the maximum allowable cell level. We derive lower and upper bounds on this number, denoted by t1(, 0). In the second scenario, we seek an efficient programming strategy to achieve a cell-level vector () consistent with the target permutation , such that the maximum cell level after programming is minimized. Equivalently, this strategy maximizes the number of information update cycles supported by the device before requiring a block erasure. We derive upper bounds on the minimum number of programming rounds required to achieve cell-level vector (), denoted by t1(, 0), and propose a programming algorithm for which the resultant number of programming rounds is close to t2(, 0). 2013 IEEE.

name of conference

  • 2013 IEEE International Symposium on Information Theory

published proceedings


author list (cited authors)

  • Qin, M., Jiang, A. A., & Siegel, P. H.

citation count

  • 6

complete list of authors

  • Qin, Minghai||Jiang, Anxiao Andrew||Siegel, Paul H

publication date

  • July 2013