# Optimal encoding scheme for semi-rewritable memory?

Let's define a "semi-rewritable" memory device as having the following properties:

• The initial blank media is initialised with all zeroes.
• When writing to the media, individual zeroes can be turned into ones.
• Ones can not be turned back into zeroes.

Making a physical interpretation of this is easy. Consider for instance a punch card where new holes can easily be made, but old holes can not be filled.

What makes this different from a "write once, read many" device is that a used device can be rewritten (multiple times), at the cost of reduced capacity for each rewrite.

# Implicit assumptions I would like to make explicit:

1. The memory reader has no information about what was previously written on the device. It can therefore not be relied upon to use a mechanism such as "which symbols have been changed?" to encode data on a device rewrite. That is, the reader is stateless.
2. On the other hand, different "generations" of the device may use different encoding schemes as the available capacity shrinks.
3. The data stored can assumed to be random bits.

# Sample storage scheme, to demonstrate rewrite capability:

Information in this scheme is stored on the device as pairs of binary symbols, each pair encoding one of the three states of a ternary symbol, or [DISCARDED] in the case where both symbols have been written.

The first generation thus stores data at a density of $$\frac{log_2(3)}{2} \approx 0.79$$ times that of simple binary encoding.

When the device is rewritten, the encoder considers each pair of binary symbols in sequence. If the existing state matches the one it desires to write, the encoder considers the data written. If on the other hand the pair doesn't match, it writes the necessary modification to that pair, or in the case where that isn't possible, writes the symbol [DISCARDED] and considers the next pair instead until it has successfully written the ternary symbol.

As such, every rewrite would discard $$\frac{1}{2}$$ of existing capacity.

For a large number of cycles, the device would in sum have stored $$log_2(3) \approx 1.58$$ times the data of a simple one-time binary encoding.

(For a variation of the above, one could also encode the first generation in binary and then apply this scheme on every subsequent generation. The loss from the first generation to the second would be larger, and the total life time capacity reduced, but the initial capacity would be larger).

# Question:

1. Is it possible to have a better life-time capacity than $$log_2(3)$$? I suspect the the real asymptotic capacity is 2.

2. Can a scheme do better than having $$\frac{1}{2}$$ capacity loss between rewrites?

• Writing the second and subsequent cycles is very similar to adding a bunch of elements to a Bloom filter, though IIUC you do not require the ability to also read back previous-cycle writes correctly with high probability. I suspect you can radically decrease the per-cycle capacity loss with a highly redundant encoding -- although this means you start with a much-reduced capacity. – j_random_hacker May 22 '20 at 14:43

The lifetime capacity can be arbitrarily large.

One may change the weight of the ternary symbols from 1/3, 1/3, 1/3 to 1/2, 1/4, 1/4 (favouring the symbol with blank bits). This reduces the entropy of the ternary symbol from $$log_2(3)$$ to $$\frac{3}{2}$$.
What it also does is reducing the capacity loss between generations, to a factor of $$\frac{5}{3}$$

$$\frac{log_2(3)}{2} \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2}\right)^i = log_2(3) \approx 1.58$$

$$\frac{3}{4} \cdot \sum_{i=0}^{\infty}\left(\frac{3}{5}\right)^i = \frac{15}{8}\approx 1.88$$

This can be generalised.

By weighted as $$x$$, $$\frac{1-x}{2}$$, $$\frac{1-x}{2}$$, the loss of capacity for each generation is a factor that can be written as:

$$generation\ loss =\frac{1}{2} - \frac{1}{x - 1}$$

And the entropy of the symbol is:

$$S = - \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)$$

$$\frac{- \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)}{2} \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2} - \frac{1}{x - 1}\right)^i$$
Which grows unbounded when $$x$$ approaches 1, however quite slowly (logarithmic). This makes the capacity per generation very low, but the sparseness of the set bits allows the memory to be reused many many times.