New Constructions of WOM Codes Using the Wozencraft Ensemble
From MaRDI portal
Publication:5346471
DOI10.1109/TIT.2013.2251455zbMATH Open1364.94628arXiv1110.6590MaRDI QIDQ5346471FDOQ5346471
Authors: Amir Shpilka 
Publication date: 8 June 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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 epsilon>0, 0<p<1 and n =(1/epsilon)^{O(1/pepsilon)} 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.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-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 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.
Full work available at URL: https://arxiv.org/abs/1110.6590
Cited In (2)
This page was built for publication: New Constructions of WOM Codes Using the Wozencraft Ensemble
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346471)
