The cycle structure of NFSR(f^d) and its applications

Let NFSR(f ) denote the nonlinear feedback shift register (NFSR) with characteristic function f = x₀ ⊕ g(x₁,x₂,…,x_n− 1) ⊕ x_n. In this paper, the cycle structure of NFSR(f^d) is discussed, where \(f^{d}=x_{0}\oplus g(x_{d},x_{2d},{\ldots } ,x_{(n-1)d})\oplus x_{nd}\) is also a characteristic function determined by f and a given integer d. If the cycle structure of NFSR(f ) is known, then it is shown that the cycle structure of NFSR(f^d) can be completely determined. Moreover, with these results, three applications of the cycle structure of NFSR(f^d) are presented: Firstly, the cycle structure of NFSR(f^d) is discussed when f belongs to a class of symmetric characteristic functions. Compared with the previous work, our result can cover more cases while the proof is more straightforward. Secondly, we show the cycle structure of NFSR(f^d) when f is a characteristic function of de Bruijn sequences and d = 2^k. At last, a new necessary condition for f to be a characteristic function of de Bruijn sequences is presented, which can partially support the observation proposed in Çalik et al. (IEICE Trans. Fund. Electron. Commun. Comput. Sci. E93-A,(6), 1226–1231 2012) and Chan et al. (Lect. Notes Comput. Sci. 809, 166–173 1993).