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 April 2012 | public
Journal Article

Multiple Error-Correcting WOM-Codes

Abstract

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of C, defined by R(C) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zemor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors.

Additional Information

© 2012 IEEE. Manuscript received May 06, 2011; accepted August 29, 2011. Date of publication November 18, 2011; date of current version March 13, 2012. This work was supported in part by the University of California Lab Fees Research Program, Award 09-LR-06-118620-SIEP, the National Science Foundation under Grant CCF-1116739, and the Center for Magnetic Recording Research at the University of California, San Diego. Part of the material in this paper was presented at the 2010 IEEE International Symposium on Information Theory. The authors thank the anonymous reviewer for valuable comments and suggestions.

Additional details

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