New Constructions of WOM Codes Using the Wozencraft Ensemble
New Constructions of WOM Codes Using the Wozencraft Ensemble
复制标题
使用 Wozencraft 集成的 WOM 代码的新构造
DOI：
--
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
Amir Shpilka
中科院分区：
文献类型：
--
作者：
Amir Shpilka
在本文中，我们给出了一次性写入内存（WOM）代码的几种新结构。我们构造的新颖之处在于使用了所谓的 Wozencraft 线性码系综。具体来说，我们得到以下结果。我们给出了在二进制字母表上接近容量的两次写入 WOM 代码的显式构造。更正式地说，对于每个 ϵ > 0, 0 <; <i>p</i> <; 1，和<i>n</i>=(1/ϵ)<sup>O(1/pϵ)</sup>，我们给出了长度<i>n</i>和容量<i>H</i>(<i>p</i>)+1-<i>p</i>-ϵ的两次写入WOM代码的构造。由于两次写入的 WOM 代码的容量为 max<sub>p</sub> (<i>H</i>(<i>p</i>)+1-<i>p</i>)，因此我们得到一个接近容量的代码。此外，编码和解码可以分别在时间 <i>O</i>(<i>n</i><sup>2</sup> ·poly (log<i>n</i>)) 和时间 <i>O</i>(<i>n</i> ·poly (log<i>n</i>)) 和对数空间中完成。此外，我们展示了一种显式随机编码方案，该方案具有 1/ε 中的块长度多项式（再次，ε 是容量差距）的两次写入容量实现 WOM 代码，并具有多项式时间编码和解码。我们获得了一种新的二进制字母表上三写WOM代码的编码方案。当块长度为 exp(1/ϵ) 时，我们的方案达到了 1.809-ϵ 的速率。与使用以前的技术相比，这提供了更好的速率。我们重点介绍了与用于位固定源的线性种子提取器的连接。特别是，我们表明，获得这样一个种子长度为 <i>O</i>(log<i>n</i>) 的提取器可以改善两次写入 WOM 代码的参数。然后，我们将现有的提取器结构应用于为有缺陷的内存设计编码方案的问题。
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 <; <i>p</i> <; 1, and <i>n</i>=(1/ϵ)<sup>O(1/pϵ)</sup>, we give a construction of a two-write WOM code of length <i>n</i> and capacity <i>H</i>(<i>p</i>)+1-<i>p</i>-ϵ. Since the capacity of a two-write WOM code is max<sub>p</sub> (<i>H</i>(<i>p</i>)+1-<i>p</i>), we get a code that is ϵ-close to capacity. Furthermore, encoding and decoding can be done in time <i>O</i>(<i>n</i><sup>2</sup> ·poly (log<i>n</i>)) and time <i>O</i>(<i>n</i> ·poly (log<i>n</i>)), 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 <i>O</i>(log<i>n</i>) 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.