Constrained de Bruijn Codes: Properties, Enumeration, Constructions, and Applications

arXiv2005.03102MaRDI QIDQ6340196

Van Khu Vu, Eitan yaakobi, Yeow Meng Chee, Tuvi Etzion, Alexander Vardy, Han Mao Kiah

Publication date: 6 May 2020

Abstract: The de Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize sequences in the de Bruijn graph are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called constrained de Bruijn sequences and a set of such sequences will be called a constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the $ell$-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size on previously known codes.

This page was built for publication: Constrained de Bruijn Codes: Properties, Enumeration, Constructions, and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340196)