New Constructions of WOM Codes Using the Wozencraft Ensemble

作     者：Shpilka, Amir 

作者机构：Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：2013年第59卷第7期

页      面：4520-4529页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Israel Science Foundation [339/10] 

主　　题：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 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) . 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.