Structure analysis on the k-error linear complexity for 2n-periodic binary sequences

Jianqin Zhou; Wanquan Liu; Xifeng Wang

doi:10.3934/jimo.2017016

Previous Article
Minimization of the coefficient of variation for patient waiting system governed by a generic maximum waiting policy
JIMO Home
This Issue
Next Article
An extension of hybrid method without extrapolation step to equilibrium problems

October 2017, 13(4): 1743-1757. doi: 10.3934/jimo.2017016

Structure analysis on the k-error linear complexity for 2ⁿ-periodic binary sequences

Jianqin Zhou ^1,2, , Wanquan Liu ^1, and Xifeng Wang ^2,

1.	Department of Computing, Curtin University, Perth, WA 6102, Australia
2.	School of Computer Science, Anhui Univ. of Technology, Ma'anshan 243032, China

The reviewing process of the paper was handled by Changzhi Wu as Guest Editor

Received December 2014 Published December 2016

Fund Project: The research was partially supported by Anhui Natural Science Foundation (No.1208085MF106) and Provincial Natural Science Research Project of Anhui Colleges (No.KJ2013Z025).

In this paper, in order to characterize the critical error linear complexity spectrum (CELCS) for $2^n$-periodic binary sequences, we first propose a decomposition based on the cube theory. Based on the proposed $k$-error cube decomposition, and the famous inclusion-exclusion principle, we obtain the complete characterization of the $i$th descent point (critical point) of the k-error linear complexity for $i=2,3$. In fact, the proposed constructive approach has the potential to be used for constructing $2^n$-periodic binary sequences with the given linear complexity and $k$-error linear complexity (or CELCS), which is a challenging problem to be deserved for further investigation in future.

Keywords: Periodic sequence, linear complexity, k-error linear complexity, cube theory, k-error cube decomposition.

Mathematics Subject Classification: Primary: 94A55, 94A60; Secondary: 11B50.

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

References:

[1]	Z. L. Chang and X. Y. Wang, On the First and Second Critical Error Linear Complexity of Binary $2^n$-periodic Sequences, Chinese Journal of Electronics, 22 (2013), 1-6. Google Scholar
[2]	C. S. Ding, G. Z. Xiao and W. J. Shan, The Stability Theory of Stream Ciphers[M], Lecture Notes in Computer Science, Vol. 561. Berlin/ Heidelberg, Germany: Springer-Verlag, 1991. doi: 10.1007/3-540-54973-0. Google Scholar
[3]	T. Etzion, N. Kalouptsidis, N. Kolokotronis, K. Limniotis and K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Transactions on Information Theory, 55 (2009), 4681-4686. doi: 10.1109/TIT.2009.2027495. Google Scholar
[4]	F. Fu, H. Niederreiter and M. Su, The characterization of $2^n$-periodic binary sequences with fixed 1-error linear complexity, Gong G., Helleseth T., Song H.-Y., Yang K. (eds.) SETA 2006, LNCS, 4086 (2006), 88-103. doi: 10.1007/11863854_8. Google Scholar
[5]	R. A. Games and A. H. Chan, A fast algorithm for determining the complexity of a binary sequence with period $2^n$, IEEE Trans on Information Theory, 29 (1983), 144-146. doi: 10.1109/TIT.1983.1056619. Google Scholar
[6]	N. Kolokotronis, P. Rizomiliotis and N. Kalouptsidis, Minimum linear span approximation of binary sequences, IEEE Transactions on Information Theory, 48 (2002), 2758-2764. doi: 10.1109/TIT.2002.802621. Google Scholar
[7]	K. Kurosawa, F. Sato, T. Sakata and W. Kishimoto, A relationship between linear complexity and $k$-error linear complexity, IEEE Transactions on Information Theory, 46 (2000), 694-698. doi: 10.1109/18.825845. Google Scholar
[8]	A. Lauder and K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Transactions on Information Theory, 49 (2003), 273-280. doi: 10.1109/TIT.2002.806136. Google Scholar
[9]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans on Information Theory, 15 (1969), 122-127. Google Scholar
[10]	W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Cryptogr., 33 (2004), 109-122. doi: 10.1023/B:DESI.0000035466.28660.e9. Google Scholar
[11]	W. Meidl, On the stablity of $2^n$-periodic binary sequences, IEEE Transactions on Information Theory, 51 (2005), 1151-1155. doi: 10.1109/TIT.2004.842709. Google Scholar
[12]	R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986, chapter 4. doi: 10.1007/978-3-642-82865-2. Google Scholar
[13]	M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^{n}$, IEEE Trans. Inform. Theory, 39 (1993), 1398-1401. doi: 10.1109/18.243455. Google Scholar
[14]	J. Q. Zhou, On the $k$-error linear complexity of sequences with period 2$p^n$ over GF(q), Des. Codes Cryptogr., 58 (2011), 279-296. doi: 10.1007/s10623-010-9379-7. Google Scholar
[15]	J. Q. Zhou and W. Q. Liu, The $k$-error linear complexity distribution for $2^n$-periodic binary sequences, Des. Codes Cryptogr., 73 (2014), 55-75. doi: 10.1007/s10623-013-9805-8. Google Scholar
[16]	J. Q. Zhou, W. Q. Liu and G. L. Zhou, Cube theory and stable $k$-error linear complexity for periodic sequences, Inscrypt, LNCS, 8567 (2013), 70-85. doi: 10.1007/978-3-319-12087-4_5. Google Scholar
[17]	J. Q. Zhou and W. Q. Liu, On the $k$-error linear complexity for $2^n$-periodic binary sequences via Cube Theory, 2013, http://arxiv.org/abs/1309.1829 Google Scholar
[18]	F. X. Zhu and W. F. Qi, The 2-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$-1, Journal of Electronics (China), 24 (2007), 390-395. Google Scholar

show all references

The reviewing process of the paper was handled by Changzhi Wu as Guest Editor

References:

[1]	Z. L. Chang and X. Y. Wang, On the First and Second Critical Error Linear Complexity of Binary $2^n$-periodic Sequences, Chinese Journal of Electronics, 22 (2013), 1-6. Google Scholar
[2]	C. S. Ding, G. Z. Xiao and W. J. Shan, The Stability Theory of Stream Ciphers[M], Lecture Notes in Computer Science, Vol. 561. Berlin/ Heidelberg, Germany: Springer-Verlag, 1991. doi: 10.1007/3-540-54973-0. Google Scholar
[3]	T. Etzion, N. Kalouptsidis, N. Kolokotronis, K. Limniotis and K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Transactions on Information Theory, 55 (2009), 4681-4686. doi: 10.1109/TIT.2009.2027495. Google Scholar
[4]	F. Fu, H. Niederreiter and M. Su, The characterization of $2^n$-periodic binary sequences with fixed 1-error linear complexity, Gong G., Helleseth T., Song H.-Y., Yang K. (eds.) SETA 2006, LNCS, 4086 (2006), 88-103. doi: 10.1007/11863854_8. Google Scholar
[5]	R. A. Games and A. H. Chan, A fast algorithm for determining the complexity of a binary sequence with period $2^n$, IEEE Trans on Information Theory, 29 (1983), 144-146. doi: 10.1109/TIT.1983.1056619. Google Scholar
[6]	N. Kolokotronis, P. Rizomiliotis and N. Kalouptsidis, Minimum linear span approximation of binary sequences, IEEE Transactions on Information Theory, 48 (2002), 2758-2764. doi: 10.1109/TIT.2002.802621. Google Scholar
[7]	K. Kurosawa, F. Sato, T. Sakata and W. Kishimoto, A relationship between linear complexity and $k$-error linear complexity, IEEE Transactions on Information Theory, 46 (2000), 694-698. doi: 10.1109/18.825845. Google Scholar
[8]	A. Lauder and K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Transactions on Information Theory, 49 (2003), 273-280. doi: 10.1109/TIT.2002.806136. Google Scholar
[9]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans on Information Theory, 15 (1969), 122-127. Google Scholar
[10]	W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Cryptogr., 33 (2004), 109-122. doi: 10.1023/B:DESI.0000035466.28660.e9. Google Scholar
[11]	W. Meidl, On the stablity of $2^n$-periodic binary sequences, IEEE Transactions on Information Theory, 51 (2005), 1151-1155. doi: 10.1109/TIT.2004.842709. Google Scholar
[12]	R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986, chapter 4. doi: 10.1007/978-3-642-82865-2. Google Scholar
[13]	M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^{n}$, IEEE Trans. Inform. Theory, 39 (1993), 1398-1401. doi: 10.1109/18.243455. Google Scholar
[14]	J. Q. Zhou, On the $k$-error linear complexity of sequences with period 2$p^n$ over GF(q), Des. Codes Cryptogr., 58 (2011), 279-296. doi: 10.1007/s10623-010-9379-7. Google Scholar
[15]	J. Q. Zhou and W. Q. Liu, The $k$-error linear complexity distribution for $2^n$-periodic binary sequences, Des. Codes Cryptogr., 73 (2014), 55-75. doi: 10.1007/s10623-013-9805-8. Google Scholar
[16]	J. Q. Zhou, W. Q. Liu and G. L. Zhou, Cube theory and stable $k$-error linear complexity for periodic sequences, Inscrypt, LNCS, 8567 (2013), 70-85. doi: 10.1007/978-3-319-12087-4_5. Google Scholar
[17]	J. Q. Zhou and W. Q. Liu, On the $k$-error linear complexity for $2^n$-periodic binary sequences via Cube Theory, 2013, http://arxiv.org/abs/1309.1829 Google Scholar
[18]	F. X. Zhu and W. F. Qi, The 2-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$-1, Journal of Electronics (China), 24 (2007), 390-395. Google Scholar

[1]	Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2ⁿ-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[2]	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
[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]	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
[5]	Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95
[6]	Idan Goldenberg, David Burshtein. Error bounds for repeat-accumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555-570. doi: 10.3934/amc.2011.5.555
[7]	Stefano Maset. Conditioning and relative error propagation in linear autonomous ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2879-2909. doi: 10.3934/dcdsb.2018165
[8]	Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[9]	Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[10]	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, 2021 doi: 10.3934/amc.2021019
[11]	Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[12]	Xiaojie Wang. Weak error estimates of the exponential Euler scheme for semi-linear SPDEs without Malliavin calculus. Discrete & Continuous Dynamical Systems, 2016, 36 (1) : 481-497. doi: 10.3934/dcds.2016.36.481
[13]	Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465
[14]	Walter Alt, Robert Baier, Matthias Gerdts, Frank Lempio. Error bounds for Euler approximation of linear-quadratic control problems with bang-bang solutions. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 547-570. doi: 10.3934/naco.2012.2.547
[15]	Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334
[16]	Alfredo Lorenzi, Luca Lorenzi. A strongly ill-posed integrodifferential singular parabolic problem in the unit cube of $\mathbb{R}^n$. Evolution Equations & Control Theory, 2014, 3 (3) : 499-524. doi: 10.3934/eect.2014.3.499
[17]	Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409
[18]	Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021, 11 (3) : 601-624. doi: 10.3934/mcrf.2021014
[19]	Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477
[20]	Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299

American Institute of Mathematical Sciences

Structure analysis on the k-error linear complexity for 2ⁿ-periodic binary sequences

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences