Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 2014 | public
Journal Article

High Sum-Rate Three-Write and Nonbinary WOM Codes

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.

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.

Additional details

Created:
August 22, 2023
Modified:
October 18, 2023