Maximal Length Constrained de Bruijn Sequences

YM Chee, TL Nguyen, VD Tran - 2023 IEEE International …, 2023 - ieeexplore.ieee.org
2023 IEEE International Symposium on Information Theory (ISIT), 2023ieeexplore.ieee.org
The run length limited de Bruijn (RLLdB) sequences have been studied recently owing to
their application in communication systems. In each RLLdB sequence, all length-k
substrings are distinct and each substring is a run length limited sequence, where there are
at most s consecutive symbol 0's. In previous work, the maximal length RLLdB sequence
was designed only for the case s= 1. In this work, we propose to study a more generalised
problem of constrained de Bruijn sequence, called weight bounded run length limited de …
The run length limited de Bruijn (RLLdB) sequences have been studied recently owing to their application in communication systems. In each RLLdB sequence, all length-k substrings are distinct and each substring is a run length limited sequence, where there are at most s consecutive symbol 0’s. In previous work, the maximal length RLLdB sequence was designed only for the case s = 1.In this work, we propose to study a more generalised problem of constrained de Bruijn sequence, called weight bounded run length limited de Bruijn (WRdB) sequence. In each WRdB sequence, all length-k substrings are distinct and each length-k substring satisfies both constraints: the number of consecutive symbol 0’s is at most s, and the number of symbol 1’s is at least l. We aim to design a WRdB sequence with maximal length in all cases.Firstly, we build a constrained de Bruijn graph that represents a WRdB sequence and use some properties of the graph to show an upper bound on the maximal length of the sequence. Next, using Lyndon words, we present a construction of a WRdB sequence. Finally, we compute the length of the constructed WRdB sequence and show that it has the maximal length.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果