ncts

The de Bruijn graph, its sequences, and their various generalizations, have found many applications, including cryptography, wireless sensor network, robot localization, quantum communication.

In this talk, motivated by some applications for emerging memory technologies, including racetrack memories and DNA based storage, we generalize the window property of de Bruijn sequences to define a new combinatorial object, called locally-constrained de Bruijn sequence. In a [b,k]-locally-constrained de Bruijn sequence, any subset of b consecutive substrings of length k contains exactly b distint k-tuples.

A set of such sequences will be called a locally-constrained de Bruijn code. We investigate several properties of these sequences and propose various enumeration techniques to design these codes.

Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the l-symbol read channel and in the racetrack memory channel.