Floating codes are codes designed to store multiple values in a Write Asymmetric Memory, with applications to flash memory. In this model, a memory consists of a block of n cells, with each cell in one of Q states {0̇1⋯q-1}. The cells are used to represent k variable values from an &ell-ary alphabet. Cells can move from lower values to higher values easily, but moving any cell from a higher value to a lower value requires first resetting the entire block to an all 0 state. Reset operations are to be avoided; generally a block can only experience a large but finite number of resets before wearing out entirely. A code here corresponds to a mapping from cell states to variable values, and a transition function that gives how to rewrite cell states when a variable is changed. Previous work has focused on developing codes that maximize the worst-case number of variable changes, or equivalently cell rewrites, that can be experienced before resetting. In this paper, we introduce the problem of maximizing the expected number of variable changes before resetting, given an underlying Markov chain that models variable changes. We demonstrate that codes designed for expected performance can differ substantially from optimal worst-case codes, and suggest constructions for some simple cases. We then study the related question of the performance of random codes, again focusing on the issue of expected behavior. © 2006 IEEE.

Designing floating codes for expected performance / Chierichetti, Flavio; Hilary, Finucane; Zhenming, Liu; Michael, Mitzenmacher. - In: IEEE TRANSACTIONS ON INFORMATION THEORY. - ISSN 0018-9448. - 56:3(2010), pp. 968-978. [10.1109/tit.2009.2039040]

Designing floating codes for expected performance

CHIERICHETTI, FLAVIO;
2010

Abstract

Floating codes are codes designed to store multiple values in a Write Asymmetric Memory, with applications to flash memory. In this model, a memory consists of a block of n cells, with each cell in one of Q states {0̇1⋯q-1}. The cells are used to represent k variable values from an &ell-ary alphabet. Cells can move from lower values to higher values easily, but moving any cell from a higher value to a lower value requires first resetting the entire block to an all 0 state. Reset operations are to be avoided; generally a block can only experience a large but finite number of resets before wearing out entirely. A code here corresponds to a mapping from cell states to variable values, and a transition function that gives how to rewrite cell states when a variable is changed. Previous work has focused on developing codes that maximize the worst-case number of variable changes, or equivalently cell rewrites, that can be experienced before resetting. In this paper, we introduce the problem of maximizing the expected number of variable changes before resetting, given an underlying Markov chain that models variable changes. We demonstrate that codes designed for expected performance can differ substantially from optimal worst-case codes, and suggest constructions for some simple cases. We then study the related question of the performance of random codes, again focusing on the issue of expected behavior. © 2006 IEEE.
2010
average-case analysis; floating codes; random floating codes; write asymmetric memory
01 Pubblicazione su rivista::01a Articolo in rivista
Designing floating codes for expected performance / Chierichetti, Flavio; Hilary, Finucane; Zhenming, Liu; Michael, Mitzenmacher. - In: IEEE TRANSACTIONS ON INFORMATION THEORY. - ISSN 0018-9448. - 56:3(2010), pp. 968-978. [10.1109/tit.2009.2039040]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/497802
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact