On the capacity of permanent memory
On the capacity of permanent memory
复制标题
关于永久记忆的容量
DOI：
--
复制
发表时间：
1985
影响因子：
2.5
通讯作者：
C. Heegard
中科院分区：
文献类型：
--
作者：
C. Heegard
已经开发出多种形式的数字存储器来永久存储信息。其中包括按键卡、纸带、PROM、照相胶片以及最近的数字光盘。所有这些“一次写入”存储器都具有这样的特性：一旦在特定单元中写入“1”，该单元就会不可逆地设置为1。因此，在存储器中重写信息的能力受到先前写入信息的存在的阻碍。这里研究在永久存储器中存储临时数据的问题。考虑在这样的设备中存储 t 条消息 W_{1}, W_{2}, \cdots , W_{t} 的序列。令每条消息 W_{i} 由 k_{i} 位组成，并让存储器包含 n 个单元。我们说，如果我们能够以这些速率存储一些 n 的消息序列，则速率 t 元组 (R_{1} = k_{1} / n, R_{2} = k_{2} / n, \cdots , R_{t} = k_{t} / n) 是可以实现的。容量 C_{t}^{\ast} \subset R_{+}^{t} 是可实现速率集合的闭包。确定光盘型存储器的容量C_{t}^{\ast}。这一结果与 Rivest 和 Shamir 的工作有关。引入了更通用的永久存储器模型。该模型允许出现随机干扰（噪声）、更大的输入和输出字母表、更多可能的单元状态以及更灵活的状态转换集。给出了该模型的容量区域 C_{t}^{\ast} 的内界。结果表明，该界限在多个实例中描述了 C_{t}^{\ast}。
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 t messages W_{1}, W_{2}, \cdots , W_{t} in such a device. Let each message W_{i} consist of k_{i} bits and let the memory contain n cells. We say that a rate t -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 some n . The capacity C_{t}^{\ast} \subset R_{+}^{t} is the closure of the set of achievable rates. The capacity C_{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 region C_{t}^{\ast} for this model is presented. It is shown that this bound describes C_{t}^{\ast} in several instances.