How to Reuse a "Write-Once" Memory (Preliminary Version)

Storage media such as digital optical disks, PROMS, or paper tape consist of a number of “write-once” bit positions ( wits ); each wit initially contains a “0” that may later be irreversibly overwritten with a “I”. We demonstrate that such “write-once memories” ( woms ) can be “rewritten” to a surprising degree. For example, only 3 wits suffice to represent any 2-bit value in a way that can later be updated to represent any other 2-bit value. For large k, 1.29... k wits suffice to represent a k -bit value in a way that can be similarly updated. Most surprising, allowing t writes of a k -bit value requires only t + o ( t ) wits, for any fixed k . For fixed t, approximately k.t /log( t ) wits are required as k → @@@@. An n -wit WOM is shown to have a “capacity” (i.e. k.t when writing a k -bit value t times) of up to n .log( n ) bits.

Authors

• Ronald L. Rivest
• Adi Shamir

Keywords

No keywords are indexed for this paper.