EXPLORING EFFICIENT CODING SCHEMES FOR STORING ARBITRARY TREE DATA STRUCTURES IN FLASH MEMORIES

摘要

Flash memory usage is becoming ever more prevalent in society today. It is being usedin everything from portable data storage devices, portable music players, cell phones,and even solid-state (non-mechanical) computer hard drives. Despite their widespreaduse, there are still many problems inherent to flash memories. Three examples ofproblems with flash memory are as follows: (1) Block erasures. In flash memories likeother memory architectures, cells are organized into large blocks. These cells havecharge injected into them individually in order to program the cell. Cells that havecharge are then read as ?1?, while cells with absence of charge are a ?0?. This schemeworks well for reading data and writing data once; however, when a cell must be broughtback to ?0? from ?1? the entire large block must be erased and reprogrammed. Thisreprogramming process is very costly, especially in high write environments (i.e. solidstate PC hard drives). (2) Over injection. When charge is injected into a cell to raise itsvalue, it is possible that too much charge will be injected. Over injection can only besolved by block erasure, which as mentioned before is very costly. (3) Reliability andlongevity problems. Block erasures, over injection, and other problems can cause errorsin data stored in the memory. In addition, the average flash memory can only endureabout 10,000 rewrites before it breaks down. If block erasures are common and notaccounted for in some way, flash memory is not a very reliable storage medium. In thisresearch project, we examine and develop novel coding techniques that work tosolve the problem of block erasure. If block erasures can be minimized, not only willthere be an increase in memory speed, but reliability and longevity of the device willincrease. We have focused on developing coding techniques for tree data structuresbecause of their wide applicability to computing problems, as well as then using thedeveloped codes as a foundation to generalize to other data structures.