On the generalization of error-correcting WOM codes

被引：22

作者：

Jiang, Anxiao ^{[1
]}

机构：

[1] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA

来源：

2007 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-7 | 2007年

关键词：

D O I：

10.1109/ISIT.2007.4557417

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

WOM (Write Once Memory) codes are codes for efficiently storing and updating data in a memory whose state transition is irreversible. Storage media that can be classified as WOM includes flash memories, optical disks and punch cards. Error-correcting WOM codes can correct errors besides its regular data updating capability. They are increasingly important for electronic memories using MLCs (multi-level cells), where the stored data are prone to errors. In this paper, we study error-correcting WOM codes that generalize the classic models. In particular, we study codes for jointly storing and updating multiple variables - instead of one variable - in WOMs with multi-level cells. The error-correcting codes we study here are also a natural extension of the recently proposed floating codes [7]. We analyze the performance of the generalized error-correcting WOM codes and present several bounds. The number of valid states for a code is an important measure of its complexity. We present three optimal codes for storing two binary variables in n q-ary cells, where n = 1, 2, 3, respectively. We prove that among all the codes with the minimum number of valid states, the three codes maximize the total number of times the variables can be updated.

引用

页码：1391 / 1395

页数：5

共 12 条

[1] LINEAR BINARY CODE FOR WRITE-ONCE MEMORIES [J].

COHEN, GD ;

GODLEWSKI, P ;

MERKX, F .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1986, 32 (05) :697-700

[2]

Fiat A., 1984, IEEE Transactions on Information Theory, VIT-30, P470, DOI 10.1109/TIT.1984.1056918

[3] On the capacity of generalized write-once memory with state transitions described by an arbitrary directed acyclic graph [J].

Fu, FW ;

Vinck, AJH .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (01) :308-313

[4] On the capacity and error-correcting codes of write-efficient memories [J].

Fu, Fang-Wei, 2000, IEEE, Piscataway, NJ, United States (46)

[5] On-chip error correcting techniques for new-generation Flash memories [J].

Gregori, S ;

Cabrini, A ;

Khouri, O ;

Torelli, G .

PROCEEDINGS OF THE IEEE, 2003, 91 (04) :602-616

[6] ON THE CAPACITY OF PERMANENT MEMORY [J].

HEEGARD, C .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (01) :34-42

[7]

JIANG A, 2007, P IEEE INT S INF THE

[8] ON THE GENERAL DEFECTIVE CHANNEL WITH INFORMED ENCODER AND CAPACITIES OF SOME CONSTRAINED MEMORIES [J].

KUZNETSOV, AV ;

HANVINCK, AJ .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1994, 40 (06) :1866-1871

[9]

Merkx F., 1984, Traitement du Signal, V1, P227

[10] HOW TO REUSE A WRITE-ONCE MEMORY [J].

RIVEST, RL ;

SHAMIR, A .

INFORMATION AND CONTROL, 1982, 55 (1-3) :1-19

← 1 2 →