EXPLORING EFFICIENT CODING SCHEMES FOR STORING ARBITRARY TREE DATA STRUCTURES IN FLASH MEMORIES
Abstract
Flash memory usage is becoming ever more prevalent in society today. It is being used
in everything from portable data storage devices, portable music players, cell phones,
and even solid-state (non-mechanical) computer hard drives. Despite their widespread
use, there are still many problems inherent to flash memories. Three examples of
problems with flash memory are as follows: (1) Block erasures. In flash memories like
other memory architectures, cells are organized into large blocks. These cells have
charge injected into them individually in order to program the cell. Cells that have
charge are then read as “1”, while cells with absence of charge are a “0”. This scheme
works well for reading data and writing data once; however, when a cell must be brought
back to “0” from “1” the entire large block must be erased and reprogrammed. This
reprogramming process is very costly, especially in high write environments (i.e. solid
state PC hard drives). (2) Over injection. When charge is injected into a cell to raise its
value, it is possible that too much charge will be injected. Over injection can only be
solved by block erasure, which as mentioned before is very costly. (3) Reliability and
longevity problems. Block erasures, over injection, and other problems can cause errors
in data stored in the memory. In addition, the average flash memory can only endure
about 10,000 rewrites before it breaks down. If block erasures are common and not
accounted for in some way, flash memory is not a very reliable storage medium. In this
research project, we examine and develop novel coding techniques that work to
solve the problem of block erasure. If block erasures can be minimized, not only will
there be an increase in memory speed, but reliability and longevity of the device will
increase. We have focused on developing coding techniques for tree data structures
because of their wide applicability to computing problems, as well as then using the
developed codes as a foundation to generalize to other data structures.
Citation
Falck, Justin (2009). EXPLORING EFFICIENT CODING SCHEMES FOR STORING ARBITRARY TREE DATA STRUCTURES IN FLASH MEMORIES. Available electronically from https : / /hdl .handle .net /1969 .1 /86501.