De Bruijn Sequences, Adjacency Graphs, and Cyclotomy
De Bruijn Sequences, Adjacency Graphs, and Cyclotomy
复制标题
De Bruijn 序列、邻接图和环切法
DOI：
10.1109/tit.2017.2787742
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
Lin Dongdai
中科院分区：
文献类型：
--
作者：
Li Ming;Lin Dongdai
研究了用可约特征多项式连接线性反馈移位寄存器的循环构造De Bruijn序列的问题。连接圈的主要困难是求出圈间共轭对的位置，并将共轭对在圈中的分布定义为邻接图。设<inline-formula><tex-math notation="LaTeX">$l（x）$</tex-math></inline-formula>是一个特征多项式，$<inline-formula><tex-math notation="LaTeX">l（x）=l_{1}（x）l_{2}（x）\cdots l_{r}（x）$</tex-math></inline-formula>是<inline-formula><tex-math notation="LaTeX">$l（x）$</tex-math></inline-formula>分解成两两互质因子。首先，我们给出了<inline-formula><tex-math notation="LaTeX">$\mathrm {FSR}（l（x））$</tex-math></inline-formula>的邻接图与<inline-formula><tex-math notation="LaTeX">$\mathrm {FSR}（l_{i}（x））$</tex-math></inline-formula>，<inline-formula><tex-math notation="LaTeX">$1\leq i\leq r$</tex-math></inline-formula>的关联图之间的联系。通过这种联系，将<inline-formula><tex-math notation="LaTeX">$\mathrm {FSR}（l（x））$的邻接图的</tex-math></inline-formula>确定问题分解为<inline-formula><tex-math notation="LaTeX">$\mathrm {FSR}（l_{i}（x））$</tex-math></inline-formula>，<inline-formula><tex-math notation="LaTeX">$1\leq i\leq r$</tex-math></inline-formula>的关联图的确定问题，从而使问题的处理更加容易。然后，我们研究了具有不可约特征多项式的LFSR的结合图，并给出了这些结合图与有限域上的分圆数之间的关系。最后，作为这些结果的应用，我们明确地确定了一些LFSR的邻接图，并表明我们的结果覆盖了以前的结果。
We study the problem of constructing De Bruijn sequences by joining cycles of linear feedback shift registers (LFSRs) with reducible characteristic polynomials. The main difficulty for joining cycles is to find the location of conjugate pairs between cycles, and the distribution of conjugate pairs in cycles is defined to be adjacency graphs. Let <inline-formula> <tex-math notation="LaTeX">$l(x)$ </tex-math></inline-formula> be a characteristic polynomial, and <inline-formula> <tex-math notation="LaTeX">$l(x)=l_{1}(x)l_{2}(x)\cdots l_{r}(x)$ </tex-math></inline-formula> be a decomposition of <inline-formula> <tex-math notation="LaTeX">$l(x)$ </tex-math></inline-formula> into pairwise co-prime factors. First, we show a connection between the adjacency graph of <inline-formula> <tex-math notation="LaTeX">$\mathrm {FSR}(l(x))$ </tex-math></inline-formula> and the association graphs of <inline-formula> <tex-math notation="LaTeX">$\mathrm {FSR}(l_{i}(x))$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$1\leq i\leq r$ </tex-math></inline-formula>. By this connection, the problem of determining the adjacency graph of <inline-formula> <tex-math notation="LaTeX">$\mathrm {FSR}(l(x))$ </tex-math></inline-formula> is decomposed to the problem of determining the association graphs of <inline-formula> <tex-math notation="LaTeX">$\mathrm {FSR}(l_{i}(x))$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$1\leq i\leq r$ </tex-math></inline-formula>, which is much easier to handle. Then, we study the association graphs of LFSRs with irreducible characteristic polynomials and give a relationship between these association graphs and the cyclotomic numbers over finite fields. At last, as an application of these results, we explicitly determine the adjacency graphs of some LFSRs and show that our results cover the previous ones.