YANG Yinghua, ZENG Xiangyong, XU Yunge. Periods on The Cascade Connection of an LFSR and an NFSR[J]. Chinese Journal of Electronics, 2019, 28(2): 301-308. doi: 10.1049/cje.2019.01.018
Citation: YANG Yinghua, ZENG Xiangyong, XU Yunge. Periods on The Cascade Connection of an LFSR and an NFSR[J]. Chinese Journal of Electronics, 2019, 28(2): 301-308. doi: 10.1049/cje.2019.01.018

Periods on The Cascade Connection of an LFSR and an NFSR

doi: 10.1049/cje.2019.01.018
Funds:  This work was supported by the National Natural Science Foundation of China (No.61472120) and National Natural Science Foundation of Hubei Province of China (No. 2017CFB143).
More Information
  • Corresponding author: ZENG Xiangyong (corresponding author) was born in Hubei Province, China, in 1973. He received the M.S and Ph.D. degrees in Beijing Normal University. Since 2009, he has been a professor of Hubei University. He serves as an Associate Editor for the Springer journal Cryptography and Communications, Discrete Structures, Boolean Functions and Sequences. His research interests include cryptography, sequence and coding theory. (Email:xzeng@hubu.edu.cn)
  • Received Date: 2016-12-29
  • Rev Recd Date: 2017-11-19
  • Publish Date: 2019-03-10
  • We study the periods of sequences produced by the cascade connection of two Feedback shift registers (FSRs). The period of the cascade connection is the period of the longest sequences it produces. An upper bound for the period of the cascade connection of a Nonlinear feedback shift register (NFSR) into a Linear feedback shift register (LFSR) is established. In addition, the cascade connection of an n-stage maximum-length LFSR into an n-stage NFSR is called an (n + n)-stage Grain-like NFSR, and we propose two families of (n + n)- stage Grain-like NFSRs such that the minimal period 2n-1 is achievable for a positive integer n.
  • loading
  • S.W. Golomb, Shift Register Sequences, Agean Park Press, New York, USA, 1982.
    S.W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, Cambridge University Press, New York, 2005.
    C. Cannière and B. Preneel, “Trivium”, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, Vol.4986, pp.244-266, 2008.
    M. Hell, T. Johansson, A. Maximov, et al., “The Grain family of stream ciphers”, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, Vol.4986, pp.179-190, 2008.
    H. Fredricksen, “A survey of full length nonlinear shift register cycle algorithms”, SIAM Review, Vol.24, No.2, pp.195-221, 1982.
    T. Etzion and A. Lempel, “Algorithms for the generation of full-length shift-register sequences”, IEEE Transactions on Information Theory, Vol.30, No.3, pp.480-484, 1984.
    C.Y. Li, X.Y. Zeng, C.L. Li, et al., “Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials”, IEEE Transactions on Information Theory, Vol.62, No.1, pp.610-624, 2016.
    W.W. Liang, X.Y. Zeng and Y.G. Xu, “The periods of a class of nonlinear feedback shift register sequences”, Chinese Journal of Electronics, Vol.25, No.2, pp.296-303, 2016.
    Z.W. Tang, W.F. Qi and T. Tian, “On characteristic functions of de Bruijn sequences”, Chinese Journal of Electronics, Vol.25, No.2, pp.304-311, 2016.
    M. Li and D.D. Lin, “The adjacency graphs of LFSRs with primitive-like characteristic polynomials”, IEEE Transactions on Information Theory, Vol.63, No.2, pp.1325-1335,2017.
    J.H. Zhong and D.D Lin, “Driven stability of nonlinear feedback shift registers with inputs”, IEEE Transactions on Communications, Vol.64, No.6, pp.2274-2284, 2016.
    H.Y. Wang, J.H. Zhong and D.D. Lin, “Linearization of multivalued nonlinear feedback shift registers”, Journal of Systems Science and Complexity, Vol.30, No.2, pp.1-16, 2015.
    D.H. Green and K.R. Dimond, “Nonlinear product-feedback shift registers”, Proceedings of the Institution of Electrical Engineers, Vol.117, No.4, pp.681-686, 1970.
    J. Mykkeltveit, M.K. Siu and P. Tong, “On the cycle structure of some nonlinear shift register sequences”, Information and Control, Vol.43, No.2, pp.202-215, 1979.
    Z. Ma, W.F. Qi and T. Tian, “On the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR”, Journal of Complexity, Vol.29, No.2, pp.173-181, 2013.
    J.M. Zhang, W.F. Qi, T. Tian, et al., “Further results on the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR”, IEEE Transactions on Information Theory, Vol.61, No.1, pp.645-654, 2015.
    T. Tian and W.F. Qi, “On the density of irreducible NFSR”, IEEE Transactions on Information Theory, Vol.59, No.6, pp.1006-1012, 2013.
    T. Tian and W.F. Qi, “On the largest affine sub-families of a family of NFSR sequences,” Designs, Codes and Cryptography, Vol.71, No.1, pp.163-181, 2014.
    H.G. Hu and G. Gong, “Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions”, International Journal of Foundations of Computer Science, Vol.22, No.6, pp.1317-1329, 2011.
    R. Lidl and H. Niederreiter, Finite Fields: Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, England, 1997.
    Y.P. Jiang and D.D. Lin, “On affine sub-families of Grain-like structures”, Designs, Codes and Cryptography, Vol.82, No.3, pp.531-542, 2017.
    X.X. Zhao and W.F. Qi, “The construction of de Bruijn sequences based on cascade connection”, Journal of Cryptologic Research, Vol.2, No.3, pp.245-257, 2015. (in Chinese)
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (139) PDF downloads(179) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return