Abstract | ||
---|---|---|
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/\\epsilon)^{O(t/(\\delta\\epsilon))}$ when $\\epsilon$ is the gap to capacity and encoding and decoding run in time $N^{1+\\delta}$. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/TIT.2013.2294464 | Information Theory, IEEE Transactions |
Keywords | DocType | Volume |
codes,decoding,alphabets,capacity-achieving binary t-write WOM codes,capacity-achieving multiwrite WOM codes,decoding algorithms,polynomial time encoding,Coding theory,WOM-codes,flash memories,hash-functions,write-once memories | Journal | 60 |
Issue | ISSN | Citations |
3 | 0018-9448 | 3 |
PageRank | References | Authors |
0.49 | 7 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amir Shpilka | 1 | 1095 | 64.27 |