A Caltech Library Service

Codes for Write-Once Memories

Yaakobi, Eitan and Kayser, Scott and Siegel, Paul H. and Vardy, Alexander and Wolf, Jack Keil (2012) Codes for Write-Once Memories. IEEE Transactions on Information Theory, 58 (9). pp. 5985-5999. ISSN 0018-9448. doi:10.1109/TIT.2012.2200291.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Yaakobi, Eitan0000-0002-9851-5234
Siegel, Paul H.0000-0002-2539-4646
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.
Funding AgencyGrant Number
University of California Lab Fees Research Program Award09-LR-06-118620-SIEP
University of California San Diego, Center for Magnetic Recording ResearchUNSPECIFIED
Subject Keywords:Coding theory, flash memories, write-once memories (WOMs), WOM-codes.
Issue or Number:9
Record Number:CaltechAUTHORS:20121008-104940611
Persistent URL:
Official Citation:Yaakobi, E.; Kayser, S.; Siegel, P. H.; Vardy, A.; Wolf, J. K.; , "Codes for Write-Once Memories," Information Theory, IEEE Transactions on , vol.58, no.9, pp.5985-5999, Sept. 2012 doi: 10.1109/TIT.2012.2200291 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34751
Deposited By: Ruth Sustaita
Deposited On:08 Oct 2012 18:33
Last Modified:09 Nov 2021 23:10

Repository Staff Only: item control page