Novel way to research nonlinear feedback shift register

• Published in: Science China. Information sciences 2014-09, Vol.57 (9), p.157-170
• Main Authors: Zhao, DaWei, Peng, HaiPeng, Li, LiXiang, Hui, SiLi, Yang, YiXian
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Science; Information Systems and Communication Service; Nonlinear feedback; Research Paper; Shift registers; Tensors; 代数方程; 动力学方程; 周期序列; 布尔网络; 广义技术; 张量积; 线性反馈移位寄存器; 连接算法
• ISSN: 1674-733X; 1869-1919
• DOI: 10.1007/s11432-013-5058-4

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-lshortest n-stage feedback shift registers（nFSR） and at least 2^2^n-（l-n）-1/2^2^n-l-1shortest 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-1different full-length nNLFSRs,respectively.