The Adjacency Graphs of LFSRs With Primitive-Like Characteristic Polynomials
Ming Li, Dongdai Lin · IEEE Transactions on Information Theory · 2016
We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form$l(x)p(x)$, where$l(x)$is a polynomial of small degree and$p(x)$is a primitive polynomial. It is shown that their adjacency graphs are closely related to the association graph of$l(x)$and the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of the method, we explicitly calculate the adjacency graphs of LFSRs with the characteristic polynomials of the form$(1+x+x^{3}+x^{4})p(x)$, and construct a large class of De Bruijn sequences from them.