Place
and Time: Monday, Feb 23, 2009, Piece Hall 320
Refreshments
at 2:30pm, talk at 2:45
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,\ldots,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 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 our work, we introduce the problem of
maximizing the {\em 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.
This is a joint work with Flavio Chierichetti, Hilary
Finucane, and Michael Mitzenmacher