On the capacity of write-unidirectional memories with nonperiodic codes

Abstract

Write-unidirectional memories (WUMs) were introduced by Willems, Vinck, and Borden as an information-theoretic model for storing and updating information on a rewritable medium with the writing constraints: During the odd (resp., even) cycles of updating information, the encoder can only write 1 's (resp., 0's) in selected bit positions of WUMs, and not change the contents of other positions. In this correspondence, motivated by the research works of Wolf, Wyner, Ziv, and Korner on write-once memories (WOMs), we study the problem of how to reuse a WUM for fixed T successive cycles with nonperiodic codes (i.e., all coding strategies are permitted for every cycle). For the situation where the encoder knows and the decoder does not know the previous content of the memory, we determine the zero-error capacity region, the average capacity, and the maximum total number of information bits stored in the WUM for fixed T successive cycles. Motivated by the research works of Heegard on WOMs with symmetric input noise, we introduce two models of WUMs with symmetric or asymmetric input noise. By using ε-error as performance criterion, we extend the above results for WUMs to the two models of WUMs with symmetric or asymmetric input noise.