Enhancing the Expected Lifetime of NAND Flash by Short q-Ary WOM Codes

Write-once memory (WOM) codes can be used to enhance the lifetime of multi-level flash memories by constraining unidirectional changes of cell levels. A q-ary WOM code on integer lattices can be defined by a message decoding function and an updating function. Instead of focusing on the worst-case performance, i.e., the guaranteed number of writes of WOM codes, we study the average number of writes that can be successfully performed, assuming that the input alphabet is the same on each write. We model the updating of messages in a WOM as a Markov process on lattices, and present techniques to evaluate the average number of writes. Several code constructions are compared. A greedy algorithm is presented to obtain the optimal updating function of a given decoding function.