Stability of nonlinear feedback shift registers

详细信息    查看全文

• 作者：Jianghua Zhong ; Dongdai Lin
• 关键词：nonlinear feedback shift register ; stability ; Boolean function ; Boolean network ; semi ; tensor product
• 刊名：SCIENCE CHINA Information Sciences
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：59
• 期：1
• 页码：1-12
• 全文大小：339 KB
• 参考文献：1.Massey J L, Liu R W. Application of Lyapnunov’s direct method to the error-propagation effect in convolutional codes. IEEE Trans Inf Theory, 1964, 10: 248–250CrossRef MATH
  2.Laselle J, Lefschetz S. Stability by Liapunov’s Direct method with Applications. New York: Academic Press, 1961
  3.Mowle F J. Relations between Pn cycles and stable feedback shift registers. IEEE Trans Electron Comput, 1996, EC-15: 375–378CrossRef
  4.Mowle F J. An algorithm for generating stable feedback shift registers of order n. J ACM, 1967, 14: 529–542CrossRef MATH
  5.Fontaine C. Nonlinear feedback shift register. In: van Tilborg H C A, Jajodia S, eds., Encryclopedia of Cryptography and Security. New York: Springer, 2011. 846–848
  6.Golomb S W. Shift Register Sequences. Laguna Hills: Holden-Day, 1967MATH
  7.Qi H. On shift register via semi-tensor product approach. In: Proceedings of the 32nd Chinese Control Conference. Piscataway: IEEE Conference Publication Operations, 2013. 208–212
  8.Zhong J, Lin D. On maximum length nonlinear feedback shift registers using a Boolean network approach. In: Proceedings of the 33rd Chinese Control Conference. Piscataway: IEEE Conference Publication Operations, 2014. 2502–2507
  9.Zhao D, Peng H, Li L, et al. Novel way to research nonlinear feedback shift register. Sci China Inf Sci, 2014, 9: 092114MathSciNet
  10.Kauffman S A. Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol, 1969, 22: 437–467MathSciNet CrossRef
  11.Harris S E, Sawhill B K, Wuensche A, et al. A model of transcriptional regulatory networks based on biases in the observed regulation rules. Complexity, 2002, 7: 23–40CrossRef
  12.Huang S, Ingber I. Shape-dependent control of cell growth, differentiation, and apotosis: switching between attractors in cell regulatory networks. Exp Cell Res, 2000, 261: 91–103CrossRef
  13.Shmulevich I, Dougherty R, Kim S, et al. Probabilistic Boolean neworks: a rule-based uncertainty model for gene regulatory networks. Bioinformatics, 2002, 2: 261–274CrossRef
  14.Albert R, Barabasi A L. Dynamics of complex systems: scaling laws or the period of Boolean networks. Phys Rev Lett, 2000, 84: 5660–5663CrossRef
  15.Aldana M. Boolean dynamics of networks with scale-free topology. Phys D, 2003, 185: 45–66MathSciNet CrossRef MATH
  16.Samuelsson B, Troein C. Superpolynomial growth in the number of attractots in Kauffman networks. Phys Rev Lett, 2003, 90: 098701MathSciNet CrossRef MATH
  17.Cheng D. Input-state approach to Boolean networks. IEEE Trans Neural Netw, 2009, 20: 512–521CrossRef
  18.Cheng D. Disturbance decoupling of Boolean control networks. IEEE Trans Automat Control, 2011, 56: 2–10MathSciNet CrossRef
  19.Cheng D, Qi H. Linear representation of dynamics of Boolean networks. IEEE Trans Automat Control, 2010, 55: 2251–2258MathSciNet CrossRef
  20.Cheng D, Qi H. State-space analysis of Boolean networks. IEEE Trans Neural Netw, 2010, 21: 584–594MathSciNet CrossRef
  21.Cheng D, Qi H, Li Z. Analysis and Control of Boolean networks. London: Springer-Verlag, 2011CrossRef MATH
  22.Zhong J, Lu J, Huang T, et al. Synchronization of master-slave Booleannet works with impulsive effects: necessaryandsufficient criteria. Neurocomputing, 2014, 143: 269–274CrossRef
  23.Chen H, Sun J. A new approach for global controllability of higher order Boolean control network. Neural Netw, 2013, 39: 12–17CrossRef MATH
  24.Wang Y, Li H. On definition and construction of Lyapunov functions for Boolean networks. In: Proceeding of the 10th World Congress on Intelligent Control and Automation. Piscataway: IEEE Conference Publication Operations, 2012. 1247–1252CrossRef
  25.Cheng D, Qi H, Li Z, et al. Stability and stabilization of Boolean networks. Int J Robust Nonlinear Contr, 2011, 21: 134–156MathSciNet CrossRef MATH
  26.Li F, Sun J. Stability and stabilization of multivalued logical network. Nonlinear Anal-Real World App, 2011, 12: 3701–3712CrossRef MATH
  27.Li F, Sun J. Stability and stabilization of Boolean networks with impulsive effects. Syst Control Lett, 2012, 61: 1–5MathSciNet CrossRef MATH
  28.Liu Y, Lu J, Wu B. Some necessary and sufficient conditions for the output controllability of temporal Boolean control networks. ESAIM Control Optim Calc Var, 2014, 20: 158–173MathSciNet CrossRef MATH
  29.Zhong J, Lu J, Liu Y, et al. Synchronization in an array of output-coupled Boolean networks with time delay. IEEE Trans Neural Netw Learn Syst, 2014, 25: 2288–2294CrossRef
  30.Roger A H, Johnson C R. Topics in Matrix Analysis. Cambridge: Cambridge University Press, 1991MATH
  31.Qi H, Cheng D. Logic and logic-based control. J Contr Theory Appl, 2008, 6: 123–133MathSciNet MATH
  32.Cheng D, Qi H, Zhao Y. An Introduction to Semi-tensor Product of Matrices and its Applications. Singapore: World Scientific Publishing Company, 2012CrossRef MATH
  
• 作者单位：Jianghua Zhong (1) (2)
  Dongdai Lin (1)
  
  1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China
  2. Institute of Complexity Science, Qingdao University, Qingdao, 266071, China
  
• 刊物类别：Computer Science
• 刊物主题：Chinese Library of Science
  Information Systems and Communication Service
  
• 出版者：Science China Press, co-published with Springer
• ISSN：1869-1919

文摘

Convolutional codes have been widely used in many applications such as digital video, radio, and mobile communication. Nonlinear feedback shift registers (NFSRs) are the main building blocks in convolutional decoders. A decoding error may result in a succession of further decoding errors. However, a stable NFSR can limit such an error-propagation. This paper studies the stability of NFSRs using a Boolean network approach. A Boolean network is an autonomous system that evolves as an automaton through Boolean functions. An NFSR can be viewed as a Boolean network. Based on its Boolean network representation, some sufficient and necessary conditions are provided for globally (locally) stable NFSRs. To determine the global stability of an NFSR with its stage greater than 1, the Boolean network approach requires lower time complexity of computations than the exhaustive search and the Lyapunov’s direct method.