将m-序列转化为de Bruijn序列

Question

在他的论文“de序列控制的交流步进发生器”中，C.G. Günther在第三页指出

de Bruijn序列(.)可以很容易地从m序列(最大长度LFSR序列)中得到。

不幸的是，他在论文中没有给出这样做的方法，而我在我自己的研究中一直找不到这样的方法。有人能告诉我根特先生在那里想些什么吗？有一个简单的电路把m-序列转换成de Bruijn序列吗？

Answer 1

de Bruijn序列，如N.G. de Bruijn's 一个组合问题，Proc.K. Ned.阿卡德。“湿”，第49卷，第758-764页，1946年(归属于Ir )。( K. Posthumus)

2^n数字0或1的有序循环，使得该循环的n连续数字的2^n可能有序集都不同。

n=3的示例是序列00010111，生成集合000、001、010、101、011、111、110、100。

给出了一个长度为2^n的degree序列，由长度为2^n-1的任意M序列 (即从非零状态开始的n本原多项式的循环LFSR输出 )通过在具有n-1连续0的单子序列中插入单个0得到。

更新每一个评论：我们可以实现一个电路输出一个de序列的长度2^n使用n D型触发器连接为一个最大长度Fibonacci LFSR与n级，通过添加一个额外的XOR项，等于在反馈端的n-1触发器输出的NOR。在下面的绘图中(输出上面的示例序列)，添加的门是NOR1和XOR2。

注意0:当n的级数变大时，带有n-1输入的NOR门会变得很烦人；可以用重置来交换\lceil\log_2(n)\rceil-bit计数器，计算输出中的连续零数，在达到n-1连续零时给出1，并输出附加的XOR项。

注1:本文只对ASG的控制生成器使用deciding生成器，以决定另外两个生成器中的哪个是时钟。对另外两个生成器中的任何一个也使用de生成器是值得怀疑的:注意，如果控制生成器有c位、从生成器x位，并且两者都是de，则当从发生器是最大长度的LFSR时，从输出的总体周期是2^{\max(c,x+1)}，而不是2^c\cdot(2^x-1)。

注2:我不明白为什么如果控制生成器是最大长度的LFSR，而不是de生成器，并且有两个最大长度的LFSR，只要\gcd(2^{c-1}-1,2^x-1)是小以及\gcd(2^x-1,2^y-1)#qcStackCode#，c (resp )，为什么ASG的安全性会被削弱。x，y)是控制生成器(resp )的位数。当控制生成器输出0 (另一个从生成器)时，从生成器锁定。原纸暗示了另一篇论文(提交给IEEE信息论上的事务处理，但我找不到它)，它涵盖了最大长度LFSR作为控制生成器的情况。这似乎也是关于ASG的这文章和它的一些参考文献中的情况。

延迟添加:这在软件中也很容易。假设x^\mathtt n+x^\mathtt k+1是GF(2)上的一个原始三项式(可以从关于GF(2)到400度的本原三宫类的J rg Arndt完备列表获得合适的常数\mathtt n和\mathtt k )。如果x是至少\mathtt n位宽的无符号整数变量，则C表达式

x = ((((x>>k)^x)&1)<<(n-1))|(x>>1);

使用周期2^\mathtt n-1 (当从任何小于2^\mathtt n的正x开始时)容易地实现LFSR。我们可以把这个改为

x = ((((x>>k)^x^!(x>>1))&1)<<(n-1))|(x>>1);

它实现具有周期2^\mathtt n的NLFSR (当从任何小于2^\mathtt n的非负x开始时)。