New Constructions of WOM Codes Using the Wozencraft Ensemble

作者：Shpilka Amir^*

来源：IEEE Transactions on Information Theory, 2013, 59(7): 4520-4529.

DOI：10.1109/TIT.2013.2251455

• Coding theory
• extractors
• flash memories
• memories with defect
• Wozencraft ensemble
• write-once-memory (WOM) codes

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 %26gt; 0, 0 %26lt; p %26lt; 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) . poly(log n)) and time O(n . 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.

• 出版日期2013-7