On the capacity and error-correcting codes of write-efficient memories

Write-efficient memories (WEMs) were introduced by Ahlswede and Zhang as a model for storing and updating information on a rewritable medium with cost constraints. We note that the research work of Justesen and Hoholdt on max entropic Markov chains actually provide a method for calculating the capaci ty of WEM. By using this method, we derive a formula for the capacity of WE M with a double-permutation cost matrix, Furthermore, some capacity theorem s are established for a special class of WEM called deterministic WEM. We s how that the capacity of deterministic WEM is equal to the logarithm of the largest eigenvalue of the corresponding connectivity matrix. It is interes ting to note that the deterministic WEM behaves like the discrete noiseless channels of Shannon, By specializing our results, we also obtain some inte resting properties for the maximization problem of information functions,vi th multiple variables which are difficult to obtain otherwise. Finally, we present a method for constructing error-correcting codes for WEM with the H amming distance as the cost function. The covering radius of linear codes p lays an important role in the constructions.