Multiple-write WOM-codes

Abstract

A Write Once Memory (WOM) is a storage device that consists of cells that can take on q possible linearly-ordered values, with the added constraint that rewrites can only increase a cell's value. In the binary case, each cell can change from the level zero to the level one only once. Examples of WOMs include punch cards, optical disks, and more recently flash memories. A length-n, t-write WOM-code is a coding scheme that allows t messages to be stored in n cells. If in the i-th write we write one of M <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> messages, then the rate of the i-th write is the ratio of the number of bits written to the WOM to the total number of cells used, i.e., log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (M <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> )/n. The rate of the WOM-code is the sum of all individual rates in all writes. In this paper, we review a recent construction of binary two-write WOM-codes. The construction is generalized for two-write WOM-codes with q levels per cell. Then, we show how to use such a code with ternary cells in order to construct three and four-write WOM-codes. This construction is used recursively in order to generate a family of t-write WOM-codes for all t. Another generalized construction is given which provides us with more ways to construct families of WOM-codes. Finally, we give a comparison between our codes and the best known WOM-codes in order to show that the WOM-codes constructed here outperform all previously known WOM-codes for 3 ≤ t ≤ 10.