Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2010 | Published + Submitted
Journal Article Open

Storage Coding for Wear Leveling in Flash Memories

Abstract

Flash memory is a nonvolatile 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 (noncoding) schemes require O(n log n) 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.

Additional Information

© 2010 IEEE. Manuscript received November 18, 2009; revised June 11, 2010. Date of current version September 15, 2010. This work was supported in part by the NSF CAREER Award CCF-0747415, in part by NSF grants ECCS-0802107 and CCF-0830752, in part by the Caltech Lee Center for Advanced Networking, and in part by the Center for Magnetic Recording Research at the University of California, San Diego. This paper was presented in part at the IEEE International Symposium on Information Theory, Seoul, Korea, June 28–July 3, 2009. Communicated by M. Blaum, Associate Editor for Coding Theory.

Attached Files

Published - 05571896.pdf

Submitted - 0911.3992.pdf

Files

05571896.pdf
Files (475.2 kB)
Name Size Download all
md5:a005bb8b544bd412dec5165aaf13ce27
293.2 kB Preview Download
md5:06e1358440f6a5f5e002aba0234d60ed
182.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 25, 2023