Novel way to research nonlinear feedback shift register

Abstract

In this paper, we regard the nonlinear feedback shift register (NLFSR) as a special Boolean network, and use semi-tensor product of matrices and matrix expression of logic to convert the dynamic equations of NLFSR into an equivalent algebraic equation. Based on them, we propose some novel and generalized techniques to study NLFSR. First, a general method is presented to solve an open problem of how to obtain the properties (the number of fixed points and the cycles with different lengths) of the state sequences produced by a given NLFSR, i.e., the analysis of a given NLFSR. We then show how to construct all $2^{2^n - (l - n)} /2^{2^n - l}$ shortest n-stage feedback shift registers (nFSR) and at least $2^{2^n - (l - n) - 1} /2^{2^n - l - 1}$ shortest n-stage nonlinear feedback shift registers (nNLFSR) which can output a given nonperiodic/periodic sequence with length l. Besides, we propose two novel cycles joining algorithms for the construction of full-length nNLFSR. Finally, two algorithms are presented to construct $2^{2^{n - 2} - 1}$ different full-length nNLFSRs, respectively.