A Caltech Library Service

Correcting Deletions in Multiple-Heads Racetrack Memories

Sima, Jin and Bruck, Jehoshua (2019) Correcting Deletions in Multiple-Heads Racetrack Memories. In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 1367-1371. ISBN 9781538692912.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


One of the main challenges in developing racetrack memory systems is the limited precision in controlling the track shifts, that in turn affects the reliability of reading and writing the data. The current proposal for combating deletions in racetrack memories is to use redundant heads per-track resulting in multiple copies (potentially erroneous) and solving a specialized version of a sequence reconstruction problem. Using this approach, k-deletion correcting codes of length n, with d heads per-track, with redundancy log log n + 4 were constructed. However, the code construction requires that k ≤ d. For k > d, the best known construction improves slightly over the classic one head deletion code. Here we address the question: What is the best redundancy that can be achieved for a k-deletion code (k is a constant) if the number of heads is fixed at d (due to area limitations)? Our key result is an answer to this question, namely, we construct codes that can correct k deletions, for any k beyond the known limit of d. The code has O(k^4 dlog log n) redundancy for the case when k ≤ 2d − 1. In addition, when k ≥ 2d, the code has 2⌊k/d⌋ log n + o(log n) redundancy.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2019 IEEE. The work was supported in part by NSF grants CCF-1816965 and CCF-1717884.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20191004-100332823
Persistent URL:
Official Citation:J. Sima and J. Bruck, "Correcting Deletions in Multiple-Heads Racetrack Memories," 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp. 1367-1371. doi: 10.1109/ISIT.2019.8849783
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99074
Deposited By: George Porter
Deposited On:04 Oct 2019 18:10
Last Modified:16 Nov 2021 17:43

Repository Staff Only: item control page