2011/10/30 by Amir Shpilka, Shpilka, Amir · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Data Storage Technologies #Coding theory and cryptography #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1110.6590
19 pages
arxiv created 2011/10/30 · openalex publication_date 2011/10/30 · arxiv updated 2011/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we give several new constructions of 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 Write-Once-Memory (WOM for short) code that approaches capacity, over the binary alphabet. More formally, for every ε>0, 0<p<1 and n =(1/ε)O(1/pε) we give a construction of a two-write WOM code of length n and capacity H(p)+1-p-ε. Since the capacity of a two-write WOM code is maxp (H(p)+1-p), we get a code that is ε-close to capacity. Furthermore, encoding and decoding can be done in time O(n2.poly(log n)) and time O(n.poly(log n)), respectively, and in logarithmic space. We obtain a new encoding scheme for 3-write WOM codes over the binary alphabet. Our scheme achieves rate 1.809-ε, when the block length is exp(1/ε). 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 2-write WOM codes. We then give an application of existing constructions of extractors to the problem of designing encoding schemes for memory with defects.