De Bruijn Sequences, Adjacency Graphs, and Cyclotomy
Ming Li, Dongdai Lin · IEEE Transactions on Information Theory · 2017
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$l(x)$be a characteristic polynomial, and$l(x)=l_{1}(x)l_{2}(x)\cdots l_{r}(x)$be a decomposition of$l(x)$into pairwise co-prime factors. First, we show a connection between the adjacency graph of$\mathrm {FSR}(l(x))$and the association graphs of$\mathrm {FSR}(l_{i}(x))$,$1\leq i\leq r$. By this connection, the problem of determining the adjacency graph of$\mathrm {FSR}(l(x))$is decomposed to the problem of determining the association graphs of$\mathrm {FSR}(l_{i}(x))$,$1\leq i\leq r$, 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.