In the early 1980s, digital optical disks were an "exciting new storage medium," according to an article by Rivest and Shamir (referenced at the end of this page). They wrote: "A single 12-in. disk costing $100 can be used to store over 10¹¹ bits of data [that is, 12.5 gigabytes] ... an order-of-magnitude improvement in the cost-performance of memory technology." However, with this technology, "the writing process was irreversible," that is, it was write-once-memory.

For now picture this memory as a large array of cells each holding a single bit. These are smooth (unaltered or unburned) cells initially, indicating a "0" bit. To change the state, the hardware burns a pit into the cell, to make it a "1" bit. Once a cell has been burned, it's burned for good. However, a "0" bit can always be burned at some later time, converting it permanently to a "1" bit.

Rivest and Shamir discovered a clever scheme to simulate write-twice-memory within this write-once-memory. Their approach represents each 2 bits of information with 3 bits of write-once storage. After initially burning information into memory as shown below in the middle column of the table below, each 3-bit storage unit can be left alone or further burned to represent any of the four 2-bit possibilities, as shown in the right hand column.

In the table below, bits with value "1" are shown in red if they were newly burned at that stage. You can overwrite any 2 bits of information, stored physically as 3 bits, with any of the 4 possibilities for 2 bits, again stored as 3 bits. Columns 1 and 3 show the raw 2-bit information, while columns 2 and 4 show how the information is represented by 3 bits, in the first and the second write generations.

For example, suppose you have 3 terabits (tb) of optical storage. Using 3 bits for each pair of information bits means that you have the same capacity as 2 tb of ordinary storage. However, this entire storage can be written a second time, to give a total of 4 tb of storage. Thus this scheme magnifies the storage by a factor of 133%. There might be other uses for storage that can be written twice. I don't know of any use of this scheme.

Notice that in the above illustration, we only have access to 2 tb of memory at a time, either the first generation or the second generation. We only get 4 tb of storage by managing to reuse the first 2 tb.

Rivest and Shamir also give a simple way to decode the 3-bit representation, whether first or second generation:

Notice that this formula and the above coding scheme differs slightly from the Rivest/Shamir article below.