Codes for Write-Once Memories
Eitan Yaakobi, Scott Kayser, Paul H. Siegel, Alexander Vardy, Jack Keil Wolf · IEEE Transactions on Information Theory · 2012
A write-once memory (WOM) is a storage device that consists of cells that can take on$q$values, with the added constraint that rewrites can only increase a cell's value. A length-$n$,$t$-write WOM-code is a coding scheme that allows$t$messages to be stored in$n$cells. If on the$i$th write we write one of$M_{i}$messages, then the rate of this write is the ratio of the number of written bits to the total number of cells, i.e.,$\log_{2}M_{i}/n$. The sum-rate of the WOM-code is the sum of all individual rates on all writes. A WOM-code is called a fixed-rate WOM-code if the rates on all writes are the same, and otherwise, it is called a variable-rate WOM-code. We address two different problems when analyzing the sum-rate of WOM-codes. In the first one, called the fixed-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate WOM-codes, and in the second problem, called the unrestricted-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate and variable-rate WOM-codes. In this paper, we first present a family of two-write WOM-codes. The construction is inspired by the coset coding scheme, which was used to construct multiple-write WOM-codes by Cohenand recently by Wu, in order to construct from each linear code a two-write WOM-code. This construction improves the best known sum-rates for the fixed- and unrestricted-rate WOM-code problems. We also show how to take advantage of two-write WOM-codes in order to construct codes for the Blackwell channel. The two-write construction is generalized for two-write WOM-codes with$q$levels per cell, which is used with ternary cells to construct three- and four-write binary WOM-codes. This construction is used recursively in order to generate a family of$t$-write WOM-codes for all$t$. A further generalization of these$t$-write WOM-codes yields additional families of efficient WOM-codes. Finally, we show a recursive method that uses the previously constructed WOM-codes in order to construct fixed-rate WOM-codes. We conclude and show that the WOM-codes constructed here outperform all previously known WOM-codes for$2\leqslant t\leqslant 10$for both the fixed- and unrestricted-rate WOM-code problems.