Codes for Write-Once Memories
Abstract
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 ith 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 Cohen and 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 ≤ t ≤ 10 for both the fixed- and unrestricted-rate WOM-code problems.
Additional Information
© 2012 IEEE. Manuscript received August 23, 2011; accepted February 15, 2012. Date of publication May 19, 2012; date of current version August 14, 2012. The authors thank the anonymous reviewer for valuable comments and suggestions. This work was supported in part by the University of California Lab Fees Research Program under Award 09-LR-06-118620-SIEP, in part by the National Science Foundation under Grant CCF-1116739, and in part by the Center for Magnetic Recording Research at the University of California, San Diego. This paper was presented in part at the 2010 IEEE Information Theory Workshop and in part at the 48th Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL, September 29–October 3, 2010.Additional details
- Eprint ID
- 34751
- DOI
- 10.1109/TIT.2012.2200291
- Resolver ID
- CaltechAUTHORS:20121008-104940611
- 09-LR-06-118620-SIEP
- University of California Lab Fees Research Program Award
- CCF-1116739
- NSF
- University of California San Diego, Center for Magnetic Recording Research
- Created
-
2012-10-08Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field