Correcting Multiple Deletions and Insertions in Racetrack Memory.

Racetrack memory is a tape-like structure where data is stored sequentially as a track of single-bit memory cells. The cells are accessed through read/write ports, called heads. When reading/writing the data, the heads stay fixed and the track is shifting. One of the main challenges in developing race track 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 race track 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, withd=2heads per-track, with redundancy log log n+ 4were 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 asymptotically optimal order of redundancy that can be achieved for a k-deletion code(kis 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 codes have asymptotically8klog log n + o (log log n) redundancy ford = k = 2d-1. In addition, whenk=2d, our codes have asymptotically2?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/2d?logn+o(log n). The encoding/decoding complexity of our codes is O(nlog2k+1n). Finally, we ask a general question :What is the order-wise optimal redundancy for codes correcting a combination of at most k deletions and insertions in ad-head race track memory? We prove that the redundancy used for a combination of k deletion and insertion errors is asymptotically the same as that needed in the case of k deletion errors