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 and 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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[9]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans on Information Theory, 15 (1969), 122-127.
[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.
[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.
[12]	R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986, chapter 4. doi: 10.1007/978-3-642-82865-2.
[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.
[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.
[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.
[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.
[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
[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.

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[9]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans on Information Theory, 15 (1969), 122-127.
[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.
[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.
[12]	R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: Springer-Verlag, 1986, chapter 4. doi: 10.1007/978-3-642-82865-2.
[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.
[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.
[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.
[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.
[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
[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.

[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 and 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 and 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]	Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022003
[12]	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 and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[13]	Xiaojie Wang. Weak error estimates of the exponential Euler scheme for semi-linear SPDEs without Malliavin calculus. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 481-497. doi: 10.3934/dcds.2016.36.481
[14]	Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465
[15]	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 and Optimization, 2012, 2 (3) : 547-570. doi: 10.3934/naco.2012.2.547
[16]	Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334
[17]	Alfredo Lorenzi, Luca Lorenzi. A strongly ill-posed integrodifferential singular parabolic problem in the unit cube of $\mathbb{R}^n$. Evolution Equations and Control Theory, 2014, 3 (3) : 499-524. doi: 10.3934/eect.2014.3.499
[18]	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
[19]	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 and Related Fields, 2021, 11 (3) : 601-624. doi: 10.3934/mcrf.2021014
[20]	Stefano Galatolo. Orbit complexity and data compression. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477

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