A Caltech Library Service

Correcting k Deletions and Insertions in Racetrack Memory

Sima, Jin and Bruck, Jehoshua (2022) Correcting k Deletions and Insertions in Racetrack Memory. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


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. A current proposal for combating deletions in racetrack memories is to use redundant heads per-track resulting in multiple copies (potentially erroneous) and recovering the data by solving a specialized version of a sequence reconstruction problem. Using this approach, k-deletion correcting codes of length n, with d≥2 heads per-track, with redundancy loglogn+4 were constructed. However, the known approach requires that k≤d, namely, that the number of heads (d) is larger than or equal to the number of correctable deletions (k). 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 implementation constraints)? One of our key results 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 4k log log n + o(log log n) redundancy for k ≤ 2d − 1. In addition, when k ≥ 2d, our codes have 2⌊k/d⌋log n + o (log n) redundancy, that we prove it is order-wise optimal, specifically, we prove that the redundancy required for correcting k deletions is at least ⌊k/d⌋log n + o(log n). The encoding/decoding complexity of our codes is O(n log²ᵏ n). Finally, we ask a general question: What is the optimal redundancy for codes correcting a combination of at most k deletions and insertions in a d-head racetrack memory? We prove that the redundancy sufficient to correct a combination of k deletion and insertion errors is similar to the case of k deletion errors.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Record Number:CaltechAUTHORS:20220804-201302433
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116131
Deposited By: George Porter
Deposited On:11 Aug 2022 23:35
Last Modified:11 Aug 2022 23:35

Repository Staff Only: item control page