On the capacity of permanent memory

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 of messages in such a device. Let each message consist of bits and let the memory contain n cells. We say that a rate -tuple is achievable if we can store a sequence of messages at these rates for some . The capacity is the closure of the set of achievable rates. The capacity 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 region for this model is presented. It is shown that this bound describes in several instances.