Please use this identifier to cite or link to this item:

The channel capacity of read/write isolated memory

Authors Wang, Chuanlong
Yong, Xuerong
Golin, Mordecai View this author's profile
Issue Date 2016
Source Discrete Applied Mathematics , v. 198, January 2016, p. 264-273
Summary A read/write isolated memory is a binary re-writable medium in which (i) two consecutive locations cannot both store 1's and also in which (ii) two consecutive locations cannot both be modified during the same rewriting pass. Its channel capacity C, in bits per symbol per rewrite, is defined as C = lim(k,r ->infinity) log(2) N(k, r)/kr, where k is the size of the memory in binary symbols, r is the lifetime of the memory in rewriting cycles, and N (k, r) is the number of distinct sequences of r-characters that satisfy the constraints. This quantity was originally considered by Cohn (1995) who proved that 0.509 ... <= C <= 0.560297 ... and conjectured that C = 0.537 .... Subsequently, Golin et al. (2004) refined the bounds to 0.53500 ... <= C <= 0.55209 ... and conjectured that C = 0.5350 .... In this paper, we develop a new technique for computing C as a particular type of constrained binary matrix and obtain that C = 0.53501 .... The methods introduced in this note are not specific to this particular problem but can also be used to consider various other computational counting problems. (C) 2015 Published by Elsevier B.V.
ISSN 0166-218X
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus