Novel way to research nonlinear feedback shift register

Dawei Zhao, Haipeng Peng, Lixiang Li, SiLi Hui, Yixian YangScience China Information Sciences 2014 · OpenReview

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.
BibTeX
@article{zhao2014novel,
  author = {Dawei Zhao and Haipeng Peng and Lixiang Li and SiLi Hui and Yixian Yang},
  title = {{Novel way to research nonlinear feedback shift register}},
  journal = {Science China Information Sciences},
  year = {2014},
  url = {https://openreview.net/forum?id=S1rl-KEynM_},
}

Loading related content...

Figure