The adjacency graphs of FSRs with a class of affine characteristic functions

In the past decades, the construction of de Bruijn sequences has been extensively studied. Let ϕ be the one-to-one map from F2[x] to the set of all linear Boolean functions and the symbol “⁎” denote the product of two Boolean functions f(x0,x1,...,xn) and g(x0,x1,...,xm) given byf(g(x0,x1,...,xm),g(x1,x2,...,xm+1),...,g(xn,xn+1,...,xn+m)). Then in this paper, a feedback shift register (FSR) with the characteristic function (l+1)⁎ϕ(p(x)) is considered to construct de Bruijn sequences for the first time, where (l+1) is an affine Boolean function and p(x) is a primitive polynomial over F2 of degree n>2 with ϕ−1(l) not divisible by p(x). In specific, we determine the cycle structure and the adjacency graphs of this type of FSRs. As an example, we present the adjacency graph of FSRs with characteristic functions of the form ((x0+x1+x2+x3+1)⁎ϕ(p(x))) and calculate the total number of de Bruijn sequences constructed from these FSRs. Note that it is the first time that the FSRs with affine characteristic functions are considered to construct de Bruijn sequences, and thus a new class of de Bruijn sequences are derived.