Please use this identifier to cite or link to this item:
Title: Locally-constrained de Bruijn codes: properties, enumeration, code constructions, and applications
Authors: Chee, Yeow Meng
Etzion, Tuvi
Kiah, Han Mao
Marcovich, Sagi
Vardy, Alexander
Vu, Van Khu
Yaakobi, Eitan
Keywords: Engineering::Computer science and engineering
Issue Date: 2021
Source: Chee, Y. M., Etzion, T., Kiah, H. M., Marcovich, S., Vardy, A., Vu, V. K. & Yaakobi, E. (2021). Locally-constrained de Bruijn codes: properties, enumeration, code constructions, and applications. IEEE Transactions On Information Theory, 67(12), 7857-7875.
Project: MOE2019-T2-2-171 
Journal: IEEE Transactions on Information Theory 
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 the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called locally-constrained de Bruijn sequences and a set of such sequences will be called a locally-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 locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the ℓ-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes.
ISSN: 0018-9448
DOI: 10.1109/TIT.2021.3112300
Rights: © 2021 IEEE. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Citations 50

Updated on Feb 1, 2023

Page view(s)

Updated on Feb 3, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.