Capacity-Achieving Multiwrite WOM Codes
Capacity-Achieving Multiwrite WOM Codes
复制标题
实现多写WOM代码的容量
DOI：
--
复制
发表时间：
2012
影响因子：
2.5
通讯作者：
Amir Shpilka
中科院分区：
文献类型：
--
作者：
Amir Shpilka
在本文中，我们给出了一个显式构造的一个家庭的容量实现的二进制t-写WOM码的任何数量的写入t，它具有多项式时间的编码和解码算法。当ε为容量的差距时，该结构的块长为N=（t/ε）<sup>O（t/（δε）），</sup>编解码时间<sup>为N1 +δ</sup>.这是实现这些参数的第一个确定性构造。我们的技术也适用于较大的字母表。
In this paper, we give an explicit construction of a family of capacity-achieving binary t-write WOM codes for any number of writes t, which have polynomial time encoding and decoding algorithms. The block length of our construction is N=(t/ε)<sup>O(t/(δε))</sup> when ε is the gap to capacity and encoding and decoding run in time N<sup>1+δ</sup>. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets.