Capacity of write-unidirectional memory in variable rate code case (Q1320587)

A write-unidirectional memory (WUM), as it was introduced by \textit{F. M. Willems} and \textit{A. J. Vinck} [Proc. 7th Sympos. Information Theory in the Benelux (ed. D. E. Boekee), Delft Univ. Press 1986, 49-53 (1986)], is a binary reusable information storage medium. During the odd (resp. even) cycle of updating information, we could only write 1's (resp. 0's) in selected bit positions of WUM, and not change other positions. WUM is a mathematical model of a class of reusable digital discs. The writing constraints are due to the storage technology of this class of reusable digital discs. During the storing and updating process, the storage speed of writing both of 0's and 1's is much slower than that of only writing 0's or 1's. In the case when the encoder knows the previous content of the WUM, and the decoder does not know it, Borden proved that the capacity of WUM for period-1 code (use same code for each cycle) is \(\log_ 2{{\sqrt{5}+1}\over 2}\). Van Overfeld determined the capacity region of WUM for period-2 code (use two codes alternately for even and odd cycles). In this paper, the author considers the non-periodic codes of WUM, which allows the use of different codes for different cycles. For fixed \(T\) cycles, it is shown that the capacity region \({\mathcal R}_ T\) is equal to \(\{(R_ 1,\dots, R_ T)\mid\) there exist \(0\leq p_ 1,\dots,p_ T\leq 1\), denote \(q_ 0= 1\), \(q_ t= p_ t q_{t-1}+ 1-q_{t-1}\), \(t=1,\dots, T\), such that \(R_ i\leq q_{t-1} h(p_ t)\), \(1\leq t\leq T\}\). Denote \(C(T)= \max\{ \sum_{t=1}^ T R_ t\mid (R_ 1,\dots, R_ T)\in {\mathcal R}_ T\}\), \(C(T)\) is the total information bits stored in one bit position in WUM for \(T\) cycles. \(C=\lim_{n\to\infty} {{C(T)} \over T}\) is called the average capacity of WUM. He shows that \(C(T)\) is equal to \(\log_ 2 f_ T\), where \(f_ T\) is the \(T\)-th Fibonacci number, \(f_ 0=1\), \(f_ 1=2\), \(f_ i= f_{i-1}+ f_{i-2}\), \(i\geq 2\), and \(C\) is equal to \(\log_ 2 {{\sqrt{5}+1} \over 2}\).