Construction of de Bruijn sequences from product of two irreducible polynomials
Construction of de Bruijn sequences from product of two irreducible polynomials
复制标题
DOI：
10.1007/s12095-017-0219-8
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Zuling Chang;M. F. Ezerman;S. Ling;Huaxiong Wang
中科院分区：
文献类型：
--
作者：
Zuling Chang;M. F. Ezerman;S. Ling;Huaxiong Wang
本文研究了一类特征多项式为f（x）= p（x）q（x）的线性反馈移位寄存器（LFSR），其中p（x）和q（x）是n~2 [x]中不同的不可约多项式.𝔽的LFSR的重要性质，如循环结构和邻接图，推导。给出了确定属于每个循环的状态的方法和寻找任何一对循环共有的所有共轭对的通用算法。该过程显式地确定邻接图中的边及其标签。将所得结果与循环连接方法相结合，有效地构造了一类新的de Bruijn序列.给出了所得序列的数目的估计。在某些情况下，使用分圆数，我们可以精确地确定该数。
We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomialf(x) =p(x)q(x) wherep(x) andq(x) are distinct irreducible polynomials in 𝔽2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly.