New Constructions of WOM Codes Using the Wozencraft Ensemble

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 ϵ > 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 max_p (H(p)+1-p), we get a code that is ϵ-close to capacity. Furthermore, encoding and decoding can be done in time O(n² ·poly (logn)) and time O(n ·poly (logn)), 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/ϵ (again, ϵ 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-ϵ, 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(logn) 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.