Capacity-Achieving Multiwrite WOM Codes
Amir Shpilka · IEEE Transactions on Information Theory · 2014
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/ε)O(t/(δε))when ε is the gap to capacity and encoding and decoding run in time N1+δ. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets.