Capacity achieving two-write WOM codes

DOI10.1007/978-3-642-29344-3_53MaRDI QIDQ2894504zbMATH OpenOpenAlexFDO

Authors Amir Shpilka

Publication date 29 June 2012

Published in LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.1128

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Linear codes (general theory) (94B05)

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.

Recommendations

• WOM-codes construits à partir des codes de Hamming
• Coding for a Write-Once Memory
• scientific article; zbMATH DE number 4012489
• Linear binary code for write-once memories (Corresp.)
• scientific article; zbMATH DE number 4211967

Cited in

(4)

• Geometric WOM codes and coding strategies for multilevel flash memories
• High Sum-Rate Three-Write and Nonbinary WOM Codes
• Short <inline-formula> <tex-math notation="TeX">\(Q\) </tex-math></inline-formula>-Ary Fixed-Rate WOM Codes for Guaranteed Rewrites and With Hot/Cold Write Differentiation
• scientific article; zbMATH DE number 4211967 (Why is no real title available?)

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)