Run Length Limited de Bruijn sequence and its applications in Quantum Communication

Thời gian: 15:00 đến 17:00 Ngày 17/06/2022

Địa điểm: C101, VIASM

Báo cáo viên: Nguyen Tien Long

Tóm tắt:

The de Bruijn based timing and synchronization (dBTS) system has been proposed and studied recently for some channels requiring reliable synchronization, such as quantum communication. To avoid a long period of no-pulse in the dBTS system, we propose to study the run length limited de Bruijn sequences which not only are run length limited sequences but also can be used to locate the location of any substring. Such subjects are expected to have various applications and they also present some interesting theoretical questions in combinatorics, algorithms and coding theory. In this work, we are the first to provide an explicit formula of the maximal length of the run length limited de Bruijn sequences. Besides that, using Lyndon words, we present an efficient construction of a run length limited de Bruijn sequence with the maximal length. Furthermore, we also provide a sub-linear decoding algorithm which can locate the position of an arbitrary substring.