On the capacity of permanent memory
Chris Heegard · IEEE Transactions on Information Theory · 1985
Many forms of digital memory have been developed for the permanent storage of information. These include keypunch cards, paper tapes, PROMs, photographic film and, more recently, digital optical disks. All these "write-once" memories have the property that once a "one" is written in a particular cell, this cell becomes irreversibly set at one. Thus, the ability to rewrite information in the memory is hampered by the existence of previously written ones. The problem of storing temporary data in permanent memory is examined here. Consider storing a sequence oftmessagesW_{1}, W_{2}, \cdots , W_{t}in such a device. Let each messageW_{i}consist ofk_{i}bits and let the memory contain n cells. We say that a ratet-tuple(R_{1} = k_{1} / n, R_{2} = k_{2} / n, \cdots , R_{t} = k_{t} / n)is achievable if we can store a sequence of messages at these rates for somen. The capacityC_{t}^{\ast} \subset R_{+}^{t}is the closure of the set of achievable rates. The capacityC_{t}^{\ast}for an optical disk-type memory is determined. This result is related to the work of Rivest and Shamir. A more general model for permanent memory is introduced. This model allows for the possibility of random disturbances (noise), larger input and output alphabets, more possible cell states, and a more flexible set of state transitions. An inner bound on the capacity regionC_{t}^{\ast}for this model is presented. It is shown that this bound describesC_{t}^{\ast}in several instances.