On the Capacity of Generalized Write-Once Memory with State Transitions Described by an Arbitrary Directed Acyclic Graph
On the Capacity of Generalized Write-Once Memory with State Transitions Described by an Arbitrary Directed Acyclic Graph
复制标题
任意有向无环图描述的广义一次性写入存储器的状态转换容量
DOI：
--
复制
发表时间：
1999
影响因子：
2.5
通讯作者：
Han Vinck
中科院分区：
文献类型：
--
作者：
Fang;Han Vinck
Fiat和Shamir(1984)提出的广义一次写入存储器是一种Q元信息存储介质。每个存储单元期望存储Q个符号中的一个，并且合法状态转换由任意有向无环图来描述。这种记忆模型可以理解为Rivest和Shamir(1982)提出的二进制一次写入记忆的推广。在更新信息的过程中，单元格的内容可以从0状态更改为1状态，但反之亦然。我们研究了广义一次写入存储器连续T个循环(代)的重用问题。对于编码器知道而解码器不知道存储器的先前状态的情况，我们确定在T个连续周期内存储在存储器中的零错误容量区域和最大信息命中总数。这些结果推广了Wolf，Wyner，Ziv和Korner(1984)关于二进制一次写入记忆的结果。
The generalized write-once memory introduced by Fiat and Shamir (1984) is a q-ary information storage medium. Each storage cell is expected to store one of q symbols, and the legal state transitions are described by an arbitrary directed acyclic graph. This memory model can be understood as a generalization of the binary write-once memory which was introduced by Rivest and Shamir (1982). During the process of updating information, the contents of a cell can be changed from a 0-state to a 1-state but not vice versa. We study the problem of reusing a generalized write-once memory for T successive cycles (generations). We determine the zero-error capacity region and the maximum total number of information hits stored in the memory for T consecutive cycles for the situation where the encoder knows and the decoder does not know the previous state of the memory. These results extend the results of Wolf, Wyner, Ziv, and Korner (1984) for the binary write-once memory.