On the capacity of non-binary write-once memory
Michal Horovitz, Eitan Yaakobi · 2016
Write-once memory (WOM) is a storage device consisting of q-ary cells that can only increase their values. A WOM code is a scheme to write messages to the memory without decreasing the cells' levels. There are four models of WOM which depend on whether the encoder and decoder are informed or uninformed with the previous state of the memory. The WOM capacity of the four models was extensively studied by Wolf et al. for the binary case, however in the non-binary setup only the model, in which the encoder is informed and the decoder is not, was studied by Fu and Han Vinck. In this paper we study the capacity regions and maximum sum-rates of non-binary WOM codes for these four models. We extend the results by Wolf et al. and show that for the models in which the encoder is informed and the decoder is informed or uninformed the capacity region is the same both for the ε-error and the zero-error cases. We also find the ε-error capacity region in case the encoder is uninformed and the decoder is informed and show that, in contrary to the binary case, it is a proper subset of the capacity region in the first two models. Several more results on the maximum sum-rate are presented as well.