Reconstruction from Deletions in Racetrack Memories

In this work, we study a special case of the reconstruction problem in order to combat position errors in racetrack memories. In these memories, the information is stored in magnetic cells that can be sensed by shifting them under read heads. However, since this shifting operation is not error free, recent work has been dedicated towards correcting these so-called position errors, which manifest themselves as deletions and sticky insertions. A deletion is the event where the cells are over-shifted, and a sticky insertion occurs when the cells are not shifted.We first present a code construction that uses two heads to correct two deletions with at most log
₂
(log
₂
n) +4 redundant bits. This result improves upon a recent one that requires roughly log
₂
n redundant bits. We then extend this construction to correct d deletions using d heads with at most log
₂
(log
₂
n) +c redundant bits. Lastly, we extend our results and derive codes for the classical reconstruction problem by Levenshtein over the insertion/deletion channel.