A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once, except, in some types of memory, upon a block erase. WOM codes were originally designed for memories that consist of binary memory elements that could physically only be changed from a zero state to a one state. Examples of such memories are punch cards and optical disks. More recently, WOM codes have been designed for general usage in different types of memories, including flash memories. See, e.g., A. Jiang, “On the Generalization of Error-Correcting WOM codes,” in Proc. IEEE Int. Symp. Inform. Theory, pp. 1391-1395, Nice, France (2007); A. Jiang and J. Bruck, “Joint coding for flash memory storage,” in Proc. IEEE Int. Symp. Inform. Theory, pp. 1741-1745, Toronto, Canada, (July 2008); H. Mandavifar, P. H. Siegel, A. Vardy, J. K. Wolf, and E. Yaakobi, “A Nearly Optimal Construction of Flash Codes,” in Proc. IEEE Int. Symp. Inform. Theory, pp. 1239-1243, Seoul, Korea, (July 2009).
WOM codes provide advantages in limiting the write-stress on multiple write memories to increase lifetime. The atomic memory element in flash memories is a floating gate cell. The cell is electrically charged with electrons and can have multiple levels corresponding to a different numbers of electrons in the cell. A typical cell is a binary cell that takes on two levels. A group of cells, typically 220 cells, constitutes of a block. While it is possible to increase an individual cell level in the block, it is impossible to reduce its level, unless the entire block is erased and then reprogrammed. Considering rows with an “all-zero” state, information is recorded in the blocks on a row-by-row basis. However, in order to rewrite a row in a previously written block, the entire block must first be erased, returning it to the “all-zero” state. See, e.g., “Algorithms and data structures for flash memories,” ACM Computing Surveys, vol. 37, pp. 138-163, (June 2005). This block erase operation introduces a significant delay and also has a detrimental effect on the lifetime of the memory. WOM codes offer a way to reduce the number of such block erasures.
WOM codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. See, R. L. Rivest and A. Shamir, “How to Reuse a Write-Once Memory,” Inform. and Control, vol. 55, nos. 1-3, pp. 1-19, (1982). A WOM-Code CW[n,k,t] is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The WOM-Rate of CW, defined to be Rt(CW)=kt/n, indicates the total amount of information that is possible to store in a cell in t writes.
Two constructions of practical error correcting WOM codes were first given by Zémor and Cohen. See, G. Zémor and G. D. Cohen, “Error-correcting WOM codes,” IEEE Trans. Inform. Theory, vol. 37, no. 3, pp. 730-734, (May 1991). Both constructions correct a single cell-error during the writes. The first construction, based on a double error correcting BCH code, enables one to write k bits using n=2k-1 cells t≈n/15.42 times. The second construction, which uses the same number of cells, is based on a triple error correcting BCH code and stores 2k bits t≈n/26.9 times.
A simple error correcting WOM code replicates each of n cells 2e+1 times to correct e or fewer errors. The error correction reduces the rate of the general WOM code by 2e+1, thus, if the rate were Rt(CW)=ken for the code, then the error corrected rate is Rt(CW)/(2e+1)=kt/n(2e+1).