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 X_j^j on an n-cell noisy memory p(y_j |x_j, y_j-1), which stores Y_jⁿ 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 C_sum(t) = max[I(X₁;Y₁)+ Σ_j=2^t(U_j;Y_j)- I(U_j;Y_j-1)], where the maximum is over all pmfs p(x₁) Π_j=2^t p(u_j |y_j-1) and functions x_j(u_j, y_j-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.