Coding for a write-once memory

• Published in: AT & T Bell Laboratories technical journal 1984-07, Vol.63 (6), p.1089-1112
• Main Authors: Wolf, J. K., Wyner, A. D., Ziv, J., Körner, J.
• Format: Article
• Language: English
• ISSN: 0748-612X; 2376-7162; 1538-7305
• DOI: 10.1002/j.1538-7305.1984.tb00115.x

A write-once memory (WOM) is a binary storage medium in which the individual bit positions can be changed from the 0 state to the 1 state only once. Examples of WOMs are paper tapes, punched cards, and, most importantly, optical disks. For the latter storage medium, the l's are marked by a laser that burns away a portion of the disk. In a recent paper, Rivest and Shamir showed that it is possible to update or rewrite a WOM to a surprising degree, and that the total amount of information which can be stored in an JV-position WOM in many write/read "generations" or "stages" can be much larger than N. 1 In this paper we extend their results in several directions. Let C(T, N) be the total number of bits of information that can be stored in an N-position WOM using T write/read generations. We consider the four cases that result when the writer (encoder) and/or reader (decoder) know the state of the memory at the previous generation. For three of these cases, when either the encoder and/or decoder knows the previous state, we show that C(T, N) ∼ N log(T + 1), with T held fixed, as A→∞. For the remaining case, when neither the encoder nor the decoder knows the previous state, we show that C(T, N) < N Π 2 (6 In 2) ≈AT (2.37) and that this bound can be approached arbitrarily closely with T, N sufficiently large.