Worst-Case and Average-Case Floating Codes for Flash Memory

Abstract

Flash memory is used in portable electronic devices like cell phones, mp3 players, digital cameras, and PDAs. The question of how to code information in flash memory is a difficult one whose answer can have effects on the speed and lifespan of a chip of flash memory. The main factor to be taken into account when designing codes for flash memory is the difference in cost between decreasing and increasing the state of a cell; decreasing the state of a cell requires first the resetting of an entire section of cells. Codes that focus on maximizing the number of updates between these reset operations are called floating codes. Worst-case floating codes focus on maximizing the lower bound on the number of updates between resets, and average-case floating codes focus on maximizing the average number of updates between resets. In this thesis, we review the work done on both worst-case and average-case floating codes. We also introduce a new code which performs as well as the previous best worst-case floating code but is significantly simpler, and a second code which performs asymptotically better.