Coding for write-efficient memory

We introduce write-efficient memories (WEM) as a new model for storing and updating information on a rewritable medium. There is a cost ϕ: X × X → R ∞ assigned to changes of letters. A collection of subsets C = {Ci: 1 ≤ i ≤ M} of X n is an (n, M, D) WEM code, if Ci ∩ Cj = ⊘ for all i ≠ j and if D max = max l⩽i, j⩽MxnϵCjYnϵC1 max min ∑ j=1 n ϕ(xt, yt)⩽D. D max is called the maximal correction cost with respect to the given cost function. The performance of a code C can also be measured by two parameters, namely, the maximal cost per letter d C = n −1 D max and the rate of the size r C = n −1 log M. The rate achievable with a maximal per letter cost d is thus R(d)= sup c: dc⩽d rc. This is the most basic quantity (the storage capacity) of a WEM ( X n, ϕ n ) n = 1 ∞. We give a characterization of this and related quantities.

Authors

• R. Ahlswede
• Z. Zhang

Keywords

No keywords are indexed for this paper.