Reliability is an inherent challenge for the emerging nonvolatile technology of racetrack memories, and there exists a fundamental relationship between codes designed for racetrack memories and codes with constrained periodicity. Previous works have sought to construct codes that avoid periodicity in windows, yet have either only provided existence proofs or required high redundancy. This paper provides the first constructions for avoiding periodicity that are both efficient (average-linear time) and with low redundancy (near the lower bound). The proposed algorithms are based on iteratively repairing windows which contain periodicity until all the windows are valid. Intuitively, such algorithms should not converge as there is no monotonic progression; yet, we prove convergence with average-linear time complexity by exploiting subtle properties of the encoder. Overall, we both provide constructions that avoid periodicity in all windows, and we also study the cardinality of such constraints.
翻译:可靠性是新出现的非挥发性种族轨记记忆技术的固有挑战,而且为种族轨记设计的代码与有限制的周期性代码之间存在基本关系。 先前的工程试图建立避免窗口周期性的代码,但仅提供存在证明或要求高冗余。 本文提供了避免周期性的第一个工程,既有效( 平均线性时间), 也低冗余( 更低的界限) 。 拟议的算法基于迭代性修复窗口, 包括周期性, 直到所有窗口都有效为止。 直觉上, 这种算法不应该因为没有单体进程而趋同; 然而,我们通过利用编码器的微妙特性而证明与平均线性时间复杂性趋同。 总的来说, 我们两者都提供避免所有窗口周期性( 平均线性时间) 和低冗余( 更低约束度) 。 拟议的算法基于迭代修复窗口, 包括周期性窗口, 直至所有窗口都有效为止。 直觉上, 这种算法不应该因没有单体进过程而趋近; 然而,我们证明我们通过利用编码与平均线性的时间复杂性与平均时间复杂性相趋同。 。 总体而言,我们都提供避免所有窗口周期性的构造,我们也都提供避免周期性的构造,我们也研究这些制约的构造。