Context Sensitive Rewriting Codes for Flash Memory

Abstract

Writing data on flash memory is asymmetric in the sense that it is possible to change a 0 into a 1-bit, but erasing a 1 back to value 0 is much more expensive and can only be done in blocks. This has triggered the development of rewriting codes in which new data can overwrite the old one, subject to the constraint of never changing a 1 into a 0. The notion of context-sensitive rewriting codes is introduced and we bring here the analysis of the compression performance of a family of such codes, based on generalizations of the Fibonacci sequence. This is then compared with experimental results.