Capacity Achieving Two-Write WOM Codes
From MaRDI portal
Publication:2894504
DOI10.1007/978-3-642-29344-3_53zbMATH Open1353.68076arXiv1209.1128OpenAlexW1946201905MaRDI QIDQ2894504
Publication date: 29 June 2012
Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)
Abstract: In this paper we give an explicit construction of a capacity achieving family of binary t-write WOM codes for any number of writes t, that have a polynomial time encoding and decoding algorithms. The block length of our construction is N=(t/epsilon)^{O(t/(deltaepsilon))} 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.
Full work available at URL: https://arxiv.org/abs/1209.1128
Linear codes (general theory) (94B05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items (1)
This page was built for publication: Capacity Achieving Two-Write WOM Codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894504)
