产生二元M序列的一个新算法

A new algorithm of generating binary M sequences

de Bruijn序列是一类最长的非线性移位寄存器序列,也称它为M序列。文章在纯轮换移位寄存器的状态图中,定义了圈的“夫妻数”,并利用“夫妻数”的特性,给出了二元M序列的一个新的生成算法,其算法能生成2s.g(n,s)个n级M序列。

De Bruijn sequences, i.e. M sequences, are the longest nonl, inear shift register sequences. The pairs of cycles of GpCR are defined in this paper. By use of the character of the pairs, a new recursive algorithm is presented for the generation of binary M sequences. It generates 2^s·g（n,s） M sequences of span.