论文标题
有效产生的二元de bruijn序列的家族
An Efficiently Generated Family of Binary de Bruijn Sequences
论文作者
论文摘要
我们研究了如何从具有反馈函数的简单线性反馈移位寄存器$ f（x_0，x_1，\ ldots，x__ {n-1}）= x_0 + x_1 + x_1 + x_1 + x__ {n-1} $使用$ n \ geq 3 $，使用周期加入方法的方法。根据此类LFSR的属性，我们提出了两个新的通用后继规则，每个规则至少产生$ 2^{n-3} $ de bruijn序列。这两个类别基于Gabric，Sawada，Williams和Wong在离散数学卷中提出的框架上。 341，没有。 11，第2977--2987页，2018年11月。在这里，我们在每个周期中为独特确定的状态介绍了新的有用选择，以设计有效的继任规则。这些选择大大增加了可以生成的de bruijn序列的数量。在每个班级中，接下来的价格$ o（n）$时间和$ o（n）$空间用于固定$ n $。
We study how to generate binary de Bruijn sequences efficiently from the class of simple linear feedback shift registers with feedback function $f(x_0, x_1, \ldots, x_{n-1}) = x_0 + x_1 + x_{n-1}$ for $n \geq 3$, using the cycle joining method. Based on the properties of this class of LFSRs, we propose two new generic successor rules, each of which produces at least $2^{n-3}$ de Bruijn sequences. These two classes build upon a framework proposed by Gabric, Sawada, Williams and Wong in Discrete Mathematics vol. 341, no. 11, pp. 2977--2987, November 2018. Here we introduce new useful choices for the uniquely determined state in each cycle to devise valid successor rules. These choices significantly increase the number of de Bruijn sequences that can be generated. In each class, the next bit costs $O(n)$ time and $O(n)$ space for a fixed $n$.
