

























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$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。