The Taub Faculty of Computer Science Events and Talks

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. Orian Leitersdorf is currently studying towards the B.Sc, M.Sc., and Ph.D. degrees at the Technion, Haifa, Israel. He is a scholar at both the Technion Excellence Program and the Technion Lapidim CS Excellence Program, and is also a recipient of the Gutwirth Excellence Scholarship. His current research aims to advance digital processing-in-memory (PIM) towards fundamental applications (e.g., matrix operations, graph algorithms, cryptography) while also addressing challenges such as reliability. Further, his research interests also include several topics in theoretical computer science, including coding theory.