Periods on The Cascade Connection of an LFSR and an NFSR

YANG Yinghua; ZENG Xiangyong; XU Yunge

doi:10.1049/cje.2019.01.018

Volume 28 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2019 > 28(2): 301-308

YANG Yinghua, ZENG Xiangyong, XU Yunge, “Periods on The Cascade Connection of an LFSR and an NFSR,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 301-308, 2019, 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,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 301-308, 2019, doi: 10.1049/cje.2019.01.018

YANG Yinghua, ZENG Xiangyong, XU Yunge, “Periods on The Cascade Connection of an LFSR and an NFSR,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 301-308, 2019, doi: 10.1049/cje.2019.01.018

Citation:

PDF( 334 KB)

Periods on The Cascade Connection of an LFSR and an NFSR

doi: 10.1049/cje.2019.01.018

Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan 430062, China

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

Abstract

Abstract

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 2ⁿ-1 is achievable for a positive integer n.
- Stream cipher,
- Cascade connection,
- Grain-like NFSR,
- Period

FullText(HTML)

References(22)

References

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)

Relative Articles

Supplements(0)

Cited By

Proportional views