论文标题
纠正$ k $删除和插入赛道内存
Correcting $k$ Deletions and Insertions in Racetrack Memory
论文作者
论文摘要
开发赛道内存系统的主要挑战之一是控制轨道变化的精度有限，这反过来影响了阅读和编写数据的可靠性。当前打击赛道记忆中缺失的建议是使用冗余的人每条轨道，从而导致多个副本（潜在错误），并通过解决序列重建问题的专业版本来恢复数据。使用这种方法，构建了$ k $ demotion校正$ n $的$ d \ ge 2 $ heads track，并构建了带有冗余$ \ log \ log \ log n + 4 $的$ d \ ge 2 $ heads。但是，已知的方法要求$ k \ le d $，即，头部（$ d $）的数量大于或等于可更正删除的数量（$ k $）。在这里，我们解决了一个问题：如果$ k $ ddeotion代码（$ k $是常数）可以实现的最佳冗余，如果固定为$ d $（由于实现约束）是什么？我们的关键结果之一是对这个问题的答案，即，我们构建可以纠正$ k $删除的代码，对于任何$ k $，超出已知限制$ d $。代码具有$ 4K \ log \ log n+o（\ log \ log n）$ k \ le 2d-1 $的冗余。 In addition, when $k \ge 2d$, our codes have $2 \lfloor k/d\rfloor \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 $\lfloor k/d\rfloor \log n+o(\log n)$.我们代码的编码/解码复杂性为$ O（n \ log^{2k} n）$。最后，我们提出了一个一般问题：在$ d $ dub-head -head赛车记忆中校正最多校正$ k $删除和插入的代码的最佳冗余是什么？我们证明，足以纠正$ K $删除和插入错误的组合的冗余与$ K $删除错误的情况相似。
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 \ge 2$ heads per-track, with redundancy $\log \log n + 4$ were constructed. However, the known approach requires that $k \le 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 \le 2d-1$. In addition, when $k \ge 2d$, our codes have $2 \lfloor k/d\rfloor \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 $\lfloor k/d\rfloor \log n+o(\log n)$. The encoding/decoding complexity of our codes is $O(n\log^{2k}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.
