On the Channel Capacity of Read/Write Isolated Memory

We apply graph theory to find upper and lower bounds on the channel capacity of a serial, binary, rewritable medium in which consecutive locations may not store 1's, and consecutive locations may not be altered during a single rewriting pass. If the true capacity is close to the upper bound, then a trivial code is nearly optimal. 1 Introduction A serial, binary (0,1) memory is said to be read isolated if no two consecutive positions may store 1's; it is said to be write isolated if no two consecutive positions may be changed during rewriting. A read/write isolated memory (RWIM) is a binary, linearly ordered, rewritable storage medium obeying both restrictions. 1.1 Origin of the Problem The first restriction alone, no consecutive 1's, is typical of magnetic recording and has recurred in optical recording. The problem was first studied by Freiman and Wyner [1], and a subcase by Kautz [2]; they showed that the capacity was 0:694 . . . = log 2 OE bits per symbol, where OE is the larger..