A Caltech Library Service

Trajectory Codes for Flash Memory

Jiang, Anxiao (Andrew) and Langberg, Michael and Schwartz, Moshe and Bruck, Jehoshua (2010) Trajectory Codes for Flash Memory. California Institute of Technology , Pasadena, CA. (Unpublished)

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Flash memory is well-known for its inherent asymmetry: the flash-cell charge levels are easy to increase but are hard to decrease. In a general rewriting model, the stored data changes its value with certain patterns. The patterns of data updates are determined by the data structure and the application, and are independent of the constraints imposed by the storage medium. Thus, an appropriate coding scheme is needed so that the data changes can be updated and stored efficiently under the storage-medium's constraints. In this paper, we define the general rewriting problem using a graph model. It extends many known rewriting models such as floating codes, WOM codes, buffer codes, etc. We present a new rewriting scheme for flash memories, called the trajectory code, for rewriting the stored data as many times as possible without block erasures. We prove that the trajectory code is asymptotically optimal in a wide range of scenarios. We also present randomized rewriting codes optimized for expected performance (given arbitrary rewriting sequences). Our rewriting codes are shown to be asymptotically optimal.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription Paper
Langberg, Michael0000-0002-7470-0718
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:This work was supported in part by the NSF CAREER Award CCF-0747415, the NSF grant ECCS-0802107, the ISF grant 480/08, the Open University of Israel Research Fund (grants no. 46109 and 101163), the GIF grant 2179-1785.10/2007, and the Caltech Lee Center for Advanced Networking. The material in this paper was presented in part at the IEEE International Symposium on Information Theory (ISIT 2009), Seoul, South Korea, June 2009
Group:Parallel and Distributed Systems Group
Funding AgencyGrant Number
Israeli Science Foundation480/08
Open University of Israel46109
Open University of Israel101163
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:flash memory, asymmetric memory, rewriting, write-once memory, floating codes, buffer codes
Record Number:CaltechPARADISE:2010.ETR104
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26135
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Jan 2011
Last Modified:02 Jun 2023 00:07

Repository Staff Only: item control page