  Flash memory is a non-volatile computer memory comprised of blocks of cells,
wherein each cell is implemented as either NAND or NOR floating gate. NAND
flash is currently the most widely used type of flash memory. In a NAND flash
memory, every block of cells consists of numerous pages; rewriting even a
single page requires the whole block to be erased and reprogrammed. Block
erasures determine both the longevity and the efficiency of a flash memory.
Therefore, when data in a NAND flash memory are reorganized, minimizing the
total number of block erasures required to achieve the desired data movement is
an important goal. This leads to the flash data movement problem studied in
this paper. We show that coding can significantly reduce the number of block
erasures required for data movement, and present several optimal or nearly
optimal data-movement algorithms based upon ideas from coding theory and
combinatorics. In particular, we show that the sorting-based (non-coding)
schemes require at least O(nlogn) erasures to move data among n blocks, whereas
coding-based schemes require only O(n) erasures. Furthermore, coding-based
schemes use only one auxiliary block, which is the best possible, and achieve a
good balance between the number of erasures in each of the n+1 blocks.
