Abstract | ||
---|---|---|
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
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>
(log
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>
n) +4 redundant bits. This result improves upon a recent one that requires roughly log
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>
n redundant bits. We then extend this construction to correct d deletions using d heads with at most log
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>
(log
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>
n) +c redundant bits. Lastly, we extend our results and derive codes for the classical reconstruction problem by Levenshtein over the insertion/deletion channel. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/ITW.2018.8613352 | 2018 IEEE Information Theory Workshop (ITW) |
Keywords | Field | DocType |
sticky insertion,classical reconstruction problem,insertion/deletion channel,racetrack memories,magnetic cells,read heads,shifting operation,position errors,code construction | Discrete mathematics,Reconstruction problem,Computer science,Redundancy (engineering),Deletion channel,Decoding methods,Frequency modulation,Code (cryptography),Special case,Encoding (memory) | Conference |
ISSN | ISBN | Citations |
2475-420X | 978-1-5386-3600-8 | 0 |
PageRank | References | Authors |
0.34 | 9 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yeow Meng Chee | 1 | 593 | 62.01 |
Ryan Gabrys | 2 | 101 | 17.14 |
Alexander Vardy | 3 | 2736 | 272.53 |
Van Khu Vu | 4 | 9 | 5.34 |
Eitan Yaakobi | 5 | 604 | 70.41 |