Paper Info
Title
New Constructions of WOM Codes Using the Wozencraft Ensemble
Abstract
In this paper, we give several new constructions of write-once-memory (WOM) codes. The novelty in our constructions is the use of the so-called Wozencraft ensemble of linear codes. Specifically, we obtain the following results. We give an explicit construction of a two-write WOM code that approaches capacity, over the binary alphabet. More formally, for every $\\epsilon 0$, $0 < p < 1$, and $n=(1/\\epsilon)^{O(1/p\\epsilon)}$ , we give a construction of a two-write WOM code of length $n$ and capacity $H(p)+1-p-\\epsilon$. Since the capacity of a two-write WOM code is $\\max_{p} (H(p)+1-p)$, we get a code that is $\\epsilon$-close to capacity. Furthermore, encoding and decoding can be done in time $O(n^{2} \\cdot {\\rm poly} (\\log n))$ and time $O(n \\cdot {\\rm poly} (\\log n))$, respectively, and in logarithmic space. In addition, we exhibit an explicit randomized encoding scheme of a two-write capacity-achieving WOM code of block length polynomial in $1/\\epsilon$ (again, $\\epsilon$ is the gap to capacity), with a polynomial time encoding and decoding. We obtain a new encoding scheme for three-write WOM codes over the binary alphabet. Our scheme achieves rate $1.809-\\epsilon$, when the block length is $\\exp (1/\\epsilon)$. This gives a better rate than what could be achieved using previous techniques. We highlight a connection to linear seeded extractors for bit-fixing sources. In particular, we show that obtaining such an extractor with seed length $O(\\log n)$ can lead to improved parameters for two-write WOM codes. We then give an application of existing constructions of extractors to the problem of designing encoding schemes for memory with defects.
Year
DOI
Venue
2011
10.1109/TIT.2013.2251455
IEEE Transactions on Information Theory
Keywords
DocType
Volume
linear codes,polynomials,write-once storage,WOM codes,Wozencraft ensemble,binary alphabet,block length polynomial,linear codes,logarithmic space,polynomial time encoding,write once memory codes,Coding theory,Wozencraft ensemble,extractors,flash memories,memories with defect,write-once-memory (WOM) codes
Journal
59
Issue
ISSN
Citations 
7
0018-9448
15
PageRank 
References 
Authors
0.84
11
1
Name
Order
Citations
PageRank
Amir Shpilka1109564.27