Sum-capacity of multiple-write noisy memory

Motivated by the emerging interests in non-volatile solid-state computer memories such as flash memories, this paper studies the problem of repeatedly storing information on memory cells with noise and state. The goal is to reliably convey t messages by writing Xjj on an n-cell noisy memory p(yj |xj, yj-1), which stores Yjn at the j-th write. We model this problem as a channel with state and introduce the multiple-write noisy memory model, which includes the write-once memory and flash memory models as special cases. The t-write sum-capacity for the multiple-write noisy memory is established as Csum(t) = max[I(X1;Y1)+ Σj=2t(Uj;Yj)- I(Uj;Yj-1)], where the maximum is over all pmfs p(x1) Πj=2t p(uj |yj-1) and functions xj(uj, yj-1), j = 2, ..., t. We derive three outer bounds on the capacity region and discuss their extension to other classes of memory models. These results extend Wolf, Wyner, Ziv, and Körner's work on the binary write-once memory and Fu and Vinck's work on the generalized write-once memory to noisy memories