二元de Bruijn序列的一个生成算法

Algorithm of generating binary de Bruijn sequences

文章在纯轮换移位寄存器的状态图中,定义了圈的"比重",并利用"比重"的特性,给出了2元deBruijn序列的一个生成算法,其算法速度较快;同时该算法能生成2s.g(n,s)个n级de Bruijn序列,其中1≤s≤2(n-24),g(n,s)=n-2l-6-[n-l 2+l1-6]。

The de Bruijn sequences are the longest nonlinear shift register sequences. The weight of cycles of CPCR is defined in this paper. By making use of the characteristic of the weight, a new recursive algorithm is presented for the generation of binary de Bruijn sequences. It generates 2s· g（n,s） de Bruijnsequences of span, of which 1≤S≤2（n-4）/2,g（n,s）=n-2l-6-[（n-2l-6/l＋1].