Yaakobi, Eitan and Siegel, Paul H. and Vardy, Alexander and Wolf, Jack K. (2012) Multiple Error-Correcting WOM-Codes. IEEE Transactions on Information Theory, 58 (4). pp. 2220-2230. ISSN 0018-9448 http://resolver.caltech.edu/CaltechAUTHORS:20120502-145544314
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120502-145544314
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.|
|Subject Keywords:||Almost perfect nonlinear mapping; coding theory; error-correcting WOM-codes; flash memories; write once memory (WOM)-codes; write-once memories|
|Other Numbering System:|
|Official Citation:||Yaakobi, E.; Siegel, P.H.; Vardy, A.; Wolf, J.K.; , "Multiple Error-Correcting WOM-Codes," Information Theory, IEEE Transactions on , vol.58, no.4, pp.2220-2230, April 2012 doi: 10.1109/TIT.2011.2176465|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Jason Perez|
|Deposited On:||02 May 2012 22:26|
|Last Modified:||02 May 2012 22:26|
Repository Staff Only: item control page