Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. High Sum-Rate Three-Write and Nonbinary WOM Codes
 
research article

High Sum-Rate Three-Write and Nonbinary WOM Codes

Yaakobi, Eitan
•
Shpilka, Amir
2014
Ieee Transactions On Information Theory

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on q levels. Each cell is initially in level 0 and can only increase its level. A t-write WOM code is a coding scheme, which allows one to store t messages to the WOM such that on consecutive writes every cell's level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the t writes and number of memory cells, is bounded by log(t + 1). Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates.

  • Details
  • Metrics
Type
research article
DOI
10.1109/Tit.2014.2352213
Web of Science ID

WOS:000344524100020

Author(s)
Yaakobi, Eitan
Shpilka, Amir
Date Issued

2014

Publisher

Institute of Electrical and Electronics Engineers

Published in
Ieee Transactions On Information Theory
Volume

60

Issue

11

Start page

7006

End page

7015

Subjects

Coding theory

•

write-once memories

•

flash memories

•

WOM-codes

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
CIB  
Available on Infoscience
December 30, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/109744
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés