On the capacity of Write-Constrained Memories

摘要

Rivest and Shamir introduced Write-Once Memory (WOM), a model of storage devices whose storage elements have restrictions on state transitions, and they presented some coding methods to reuse WOM. An interesting question about WOM is how efficiently we can reuse it with the best coding method, and as an answer to the question, Fu and Han Vinck determined the capacity of Fiat and Shamir's generalized WOM. In this paper, we extend their results, introducing Write-Constrained Memory (WCM) that considers state transition cost, and determining the capacity of WCM under a certain type of cost constraints.