American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021019
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $

Lin Yi , Xiangyong Zeng , , Zhimin Sun and  Shasha Zhang

Hubei Key Laboratory of Applied Mathematics, Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, China

* Corresponding author: Xiangyong Zeng

Received  January 2021 Revised  April 2021 Early access June 2021

Fund Project: The work was supported by Application foundation frontier project of Wuhan Science and Technology Bureau under Grant 2020010601012189, and by the National Nature Science Foundation of China (NSFC) under Grant 62072161. The work of Sun was supported by the Natural Science Foundation of Hubei under Grant 2019CFB544. The work of Zhang was supported by the Research Foundation of Education Bureau of Hubei Province, China under Grant D2020104

In this paper, a new class of generalized cyclotomic binary sequences with period $ 4p^n $ is proposed. These sequences are almost balanced, and the explicit formulas of their linear complexity and autocorrelation are presented.

Keywords: Binary sequence, generalized cyclotomy, linear complexity, autocorrelation, almost balanced.
Mathematics Subject Classification: Primary: 94A55; Secondary: 94A60.
Citation: Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, doi: 10.3934/amc.2021019
References:
[1]

E. Bai, X. Liu and G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length $pq$, IEEE Trans. Inf. Theory, 51 (2005), 1849-1853.  doi: 10.1109/TIT.2005.846450.

[2]

D.M. Burton, Elementary Number Theory, McGram-Hill, New York, 1998.

[3]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier Science B. V., Amsterdam, 2004.

[4]

C. Ding, Linear complexity of generalized cyclotomic binary sequences of order $2$, Finite Fields Appl., 3 (1997), 159-174.  doi: 10.1006/ffta.1997.0181.

[5]

C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44 (1998), 1699-1702.  doi: 10.1109/18.681354.

[6]

C. Ding and T. Helleseth, New generalized cyclotomy and its applications, Finite Fields Appl., 4 (1998), 140-166.  doi: 10.1006/ffta.1998.0207.

[7]

C. Ding and T. Helleseth, Generalized cyclotomy codes of length $p^{m_{1}}_{1}p^{m_{2}}_{2}\cdots p^{m_{t}}_{t}$, IEEE Trans. Inf. Theory, 45 (1999), 467-474.  doi: 10.1109/18.748996.

[8]

X. Dong, Linear complexity of generalized cyclotomic binary sequences of length $4p^n$, Inf. Sci. Lett., 4 (2015), 67-70. 

[9]

V. Edemskiy, About computation of the linear complexity of generalized cyclotomic sequences with period $p^{n+1}$, Des. Codes Cryptogr., 61 (2011), 251-260.  doi: 10.1007/s10623-010-9474-9.

[10]

V. Edemskiy and O. Antonova, The evaluation of the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2^np^m$, International Journal of Mathematical Models and Methods in Applied Sciences, 9 (2015), 512-517. 

[11]

V. Edemskiy, C. Li, X. Zeng and T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period $p^n$, Des. Codes Cryptogr., 87 (2018), 1183-1197.  doi: 10.1007/s10623-018-0513-2.

[12]

V. Edemskiy and C. Wu, On the linear complexity of binary sequences derived from generalized cyclotomic classes modulo $2^np^m$, WSEAS Transactions on Mathematics, 18 (2019), 197-202. 

[13]

C. Fan and G. Ge, A unified approach to Whiteman's and Ding-Helleseth's generalized cyclotomy over residue class rings, IEEE Trans. Inf. Theory, 60 (2014), 1326-1336.  doi: 10.1109/TIT.2013.2290694.

[14] S. W. Golomb and G. Gong, Signal Design for Good Correlation, for Wireless Communications, Cryptography and Radar Applications, Cambridge University Press, Cambridge, 2005.  doi: 10.1017/CBO9780511546907.
[15]

P. Ke, J. Zhang and S. Zhang, On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2p^n$, Des. Codes Cryptogr., 67 (2013), 325-339.  doi: 10.1007/s10623-012-9610-9.

[16]

Y. J. Kim, S. Y. Jin and H. Y. Song, Linear complexity and autocorrelation of prime cube sequences, AAECC, LNCS, 4851 (2007), 188-197.  doi: 10.1007/978-3-540-77224-8_23.

[17]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.

[18]

M. B. Nathnson, Elementary Methods in Number Theory, Springer, Berlin, GTM 195, 2003.

[19]

A. L. Whiteman, A family of difference sets, Illinois J. Math., 6 (1962), 107-121. 

[20]

Z. Xiao, X. Zeng, C. Li and T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483-1497.  doi: 10.1007/s10623-017-0408-7.

[21]

T. Yan, B. Huang and G. Xiao, Cryptographic properties of some binary generalized cyclotomic sequences with length $p^2$, Inf. Sci., 178 (2008), 1078-1086.  doi: 10.1016/j.ins.2007.02.040.

[22]

T. Yan, S. Li and G. Xiao, On the linear complexity of generalized cyclotomic sequences with period $p^m$, Appl. Math. Lett., 21 (2008), 187-193.  doi: 10.1016/j.aml.2007.03.011.

[23]

T. Yan and X. Li, Some notes on the generalized cyclotomic binary sequences of length $2p^m$ and $p^m$, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 96 (2013), 2049-2051.  doi: 10.1007/s00200-012-0177-5.

[24]

T. Yan, R. Sun and G. Xiao, Autocorrelation and linear complexity of the new generalized cyclotomic sequences, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 90 (2007), 857-864. 

[25]

X. Zeng, H. Cai, X. Tang and Y. Yang, Optimal frequency hopping sequences of odd length, IEEE Trans. Inf. Theory, 59 (2013), 3237-3248.  doi: 10.1109/TIT.2013.2237754.

[26]

J. Zhang, C. Zhao and X. Ma, Linear complexity of generalized cyclotomic binary sequences of length $2p^m$, Applicable Algebra in Engineering Communication and Computing, 21 (2010), 93-108.  doi: 10.1007/s00200-009-0116-2.

show all references

References:
[1]

E. Bai, X. Liu and G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length $pq$, IEEE Trans. Inf. Theory, 51 (2005), 1849-1853.  doi: 10.1109/TIT.2005.846450.

[2]

D.M. Burton, Elementary Number Theory, McGram-Hill, New York, 1998.

[3]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier Science B. V., Amsterdam, 2004.

[4]

C. Ding, Linear complexity of generalized cyclotomic binary sequences of order $2$, Finite Fields Appl., 3 (1997), 159-174.  doi: 10.1006/ffta.1997.0181.

[5]

C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44 (1998), 1699-1702.  doi: 10.1109/18.681354.

[6]

C. Ding and T. Helleseth, New generalized cyclotomy and its applications, Finite Fields Appl., 4 (1998), 140-166.  doi: 10.1006/ffta.1998.0207.

[7]

C. Ding and T. Helleseth, Generalized cyclotomy codes of length $p^{m_{1}}_{1}p^{m_{2}}_{2}\cdots p^{m_{t}}_{t}$, IEEE Trans. Inf. Theory, 45 (1999), 467-474.  doi: 10.1109/18.748996.

[8]

X. Dong, Linear complexity of generalized cyclotomic binary sequences of length $4p^n$, Inf. Sci. Lett., 4 (2015), 67-70. 

[9]

V. Edemskiy, About computation of the linear complexity of generalized cyclotomic sequences with period $p^{n+1}$, Des. Codes Cryptogr., 61 (2011), 251-260.  doi: 10.1007/s10623-010-9474-9.

[10]

V. Edemskiy and O. Antonova, The evaluation of the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2^np^m$, International Journal of Mathematical Models and Methods in Applied Sciences, 9 (2015), 512-517. 

[11]

V. Edemskiy, C. Li, X. Zeng and T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period $p^n$, Des. Codes Cryptogr., 87 (2018), 1183-1197.  doi: 10.1007/s10623-018-0513-2.

[12]

V. Edemskiy and C. Wu, On the linear complexity of binary sequences derived from generalized cyclotomic classes modulo $2^np^m$, WSEAS Transactions on Mathematics, 18 (2019), 197-202. 

[13]

C. Fan and G. Ge, A unified approach to Whiteman's and Ding-Helleseth's generalized cyclotomy over residue class rings, IEEE Trans. Inf. Theory, 60 (2014), 1326-1336.  doi: 10.1109/TIT.2013.2290694.

[14] S. W. Golomb and G. Gong, Signal Design for Good Correlation, for Wireless Communications, Cryptography and Radar Applications, Cambridge University Press, Cambridge, 2005.  doi: 10.1017/CBO9780511546907.
[15]

P. Ke, J. Zhang and S. Zhang, On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2p^n$, Des. Codes Cryptogr., 67 (2013), 325-339.  doi: 10.1007/s10623-012-9610-9.

[16]

Y. J. Kim, S. Y. Jin and H. Y. Song, Linear complexity and autocorrelation of prime cube sequences, AAECC, LNCS, 4851 (2007), 188-197.  doi: 10.1007/978-3-540-77224-8_23.

[17]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.

[18]

M. B. Nathnson, Elementary Methods in Number Theory, Springer, Berlin, GTM 195, 2003.

[19]

A. L. Whiteman, A family of difference sets, Illinois J. Math., 6 (1962), 107-121. 

[20]

Z. Xiao, X. Zeng, C. Li and T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483-1497.  doi: 10.1007/s10623-017-0408-7.

[21]

T. Yan, B. Huang and G. Xiao, Cryptographic properties of some binary generalized cyclotomic sequences with length $p^2$, Inf. Sci., 178 (2008), 1078-1086.  doi: 10.1016/j.ins.2007.02.040.

[22]

T. Yan, S. Li and G. Xiao, On the linear complexity of generalized cyclotomic sequences with period $p^m$, Appl. Math. Lett., 21 (2008), 187-193.  doi: 10.1016/j.aml.2007.03.011.

[23]

T. Yan and X. Li, Some notes on the generalized cyclotomic binary sequences of length $2p^m$ and $p^m$, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 96 (2013), 2049-2051.  doi: 10.1007/s00200-012-0177-5.

[24]

T. Yan, R. Sun and G. Xiao, Autocorrelation and linear complexity of the new generalized cyclotomic sequences, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 90 (2007), 857-864. 

[25]

X. Zeng, H. Cai, X. Tang and Y. Yang, Optimal frequency hopping sequences of odd length, IEEE Trans. Inf. Theory, 59 (2013), 3237-3248.  doi: 10.1109/TIT.2013.2237754.

[26]

J. Zhang, C. Zhao and X. Ma, Linear complexity of generalized cyclotomic binary sequences of length $2p^m$, Applicable Algebra in Engineering Communication and Computing, 21 (2010), 93-108.  doi: 10.1007/s00200-009-0116-2.

Table 1.  The autocorrelation distribution of the binary sequence of period $ 108 $
$ R_{S^{(d,e)}}(\tau) $ $ \tau $
$ -68 $ $ 1, 11, 13, 23, 25, 35, 37, 47, 49, 59, 61, 71, 73, 83, 85, 95, 97,107 $
$ 32 $ $ 2, 10, 14, 22, 26, 34, 38, 46, 50, 58, 62, 70, 74, 82, 86, 94, 98,106 $
$ -4 $ $ 3, 9, 33, 39, 69, 75, 99,105 $
$ -32 $ $ 4, 8, 16, 20, 28, 32, 40, 44, 52, 56, 64, 68, 76, 80, 88, 92,100,104 $
$ 68 $ $ 5, 7, 17, 19, 29, 31, 41, 43, 53, 55, 65, 67, 77, 79, 89, 91,101,103 $
$ -80 $ $ 6, 30, 42, 66, 78,102 $
$ 80 $ $ 12, 24, 48, 60, 84, 96 $
$ 4 $ $ 15, 21, 45, 51, 57, 63, 87, 93,99 $
$ -96 $ $ 18, 90 $
$ 0 $ $ 27, 81 $
$ 96 $ $ 36, 72 $
$ -104 $ $ 54 $
Table Options

Download as excel

$ R_{S^{(d,e)}}(\tau) $ $ \tau $
$ -68 $ $ 1, 11, 13, 23, 25, 35, 37, 47, 49, 59, 61, 71, 73, 83, 85, 95, 97,107 $
$ 32 $ $ 2, 10, 14, 22, 26, 34, 38, 46, 50, 58, 62, 70, 74, 82, 86, 94, 98,106 $
$ -4 $ $ 3, 9, 33, 39, 69, 75, 99,105 $
$ -32 $ $ 4, 8, 16, 20, 28, 32, 40, 44, 52, 56, 64, 68, 76, 80, 88, 92,100,104 $
$ 68 $ $ 5, 7, 17, 19, 29, 31, 41, 43, 53, 55, 65, 67, 77, 79, 89, 91,101,103 $
$ -80 $ $ 6, 30, 42, 66, 78,102 $
$ 80 $ $ 12, 24, 48, 60, 84, 96 $
$ 4 $ $ 15, 21, 45, 51, 57, 63, 87, 93,99 $
$ -96 $ $ 18, 90 $
$ 0 $ $ 27, 81 $
$ 96 $ $ 36, 72 $
$ -104 $ $ 54 $
[1]

Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015
[2]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[3]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[4]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[5]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[6]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[7]

Kai-Uwe Schmidt, Jonathan Jedwab, Matthew G. Parker. Two binary sequence families with large merit factor. Advances in Mathematics of Communications, 2009, 3 (2) : 135-156. doi: 10.3934/amc.2009.3.135
[8]

Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031
[9]

Fuqing Sun, Qin Yue, Xia Li. on the 2-adic complexity of cyclotomic binary sequences of order three. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022049
[10]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475
[11]

Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115
[12]

Yang Yang, Xiaohu Tang, Guang Gong. New almost perfect, odd perfect, and perfect sequences from difference balanced functions with d-form property. Advances in Mathematics of Communications, 2017, 11 (1) : 67-76. doi: 10.3934/amc.2017002
[13]

Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117
[14]

Huaning Liu, Xi Liu. On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021008
[15]

Tomás Caraballo, David Cheban. Almost periodic and almost automorphic solutions of linear differential equations. Discrete and Continuous Dynamical Systems, 2013, 33 (5) : 1857-1882. doi: 10.3934/dcds.2013.33.1857
[16]

Xiaoshan Quan, Qin Yue, Liqin Hu. Some constructions of (almost) optimally extendable linear codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022027
[17]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399
[18]

Yansheng Wu, Jong Yoon Hyun, Qin Yue. Optimal binary linear codes from posets of the disjoint union of two chains. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022042
[19]

Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic and Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283
[20]

Martin Redmann, Melina A. Freitag. Balanced model order reduction for linear random dynamical systems driven by Lévy noise. Journal of Computational Dynamics, 2018, 5 (1&2) : 33-59. doi: 10.3934/jcd.2018002

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (421)
  • HTML views (450)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy