CaltechAUTHORS
  A Caltech Library Service

High Sum-Rate Three-Write and Nonbinary WOM Codes

Yaakobi, Eitan and Shpilka, Amir (2014) High Sum-Rate Three-Write and Nonbinary WOM Codes. IEEE Transactions on Information Theory, 60 (11). pp. 7006-7015. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20141211-101621598

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20141211-101621598

Abstract

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on q levels. Each cell is initially in level 0 and can only increase its level. A t-write WOM code is a coding scheme, which allows one to store t messages to the WOM such that on consecutive writes every cell's level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the t writes and number of memory cells, is bounded by log(t + 1). Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2014.2352213 DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6883175PublisherArticle
Additional Information:© 2014 IEEE. Manuscript received October 27, 2012; revised February 26, 2014; accepted June 24, 2014. Date of publication August 26, 2014; date of current version October 16, 2014. E. Yaakobi was supported in part by the ISEF Foundation, New York, NY, USA, and in part by the Lester Deutsch Fellowship. A. Shpilka was supported by the Israel Science Foundation under Grant 339/10. This paper was presented at the 2012 IEEE International Symposium on Information Theory. The authors sincerely thank the anonymous reviewers for valuable comments and suggestions in improving the presentation of the paper.
Funders:
Funding AgencyGrant Number
ISEF FoundationUNSPECIFIED
Lester Deutsch FellowshipUNSPECIFIED
Israel Science Foundation (ISF) 339/10
Subject Keywords:Coding theory; write-once memories; flash memories; WOM-codes
Record Number:CaltechAUTHORS:20141211-101621598
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20141211-101621598
Official Citation:Yaakobi, E.; Shpilka, A., "High Sum-Rate Three-Write and Nonbinary WOM Codes," Information Theory, IEEE Transactions on , vol.60, no.11, pp.7006,7015, Nov. 2014 doi: 10.1109/TIT.2014.2352213 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6883175&isnumber=6926896
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:52594
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:11 Dec 2014 21:27
Last Modified:11 Dec 2014 21:27

Repository Staff Only: item control page