August  2017, 11(3): 429-444. doi: 10.3934/amc.2017036

Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences

1. 

Department of Computing, Curtin University, Perth, WA 6102, Australia

2. 

School of Computer Science, Anhui Univ. of Technology, Maanshan, Anhui 243032, China

Received  September 2014 Revised  August 2015 Published  August 2017

In this paper, a new constructive approach of determining the first descent point distribution for the $k$-error linear complexity of $2^n$-periodic binary sequences is developed using the sieve method and Games-Chan algorithm. First, the linear complexity for the sum of two sequences with the same linear complexity and minimum Hamming weight is completely characterized and this paves the way for the investigation of the $k$-error linear complexity. Second we derive a full representation of the first descent point spectrum for the $k$-error linear complexity. Finally, we obtain the complete counting functions on the number of $2^n$-periodic binary sequences with given $2^m$-error linear complexity and linear complexity $2^n-(2^{i_1}+2^{i_2}+···+2^{i_m})$, where $0≤ i_1<i_2<···<i_m<n. $ In summary, we depict a full picture on the first descent point of the $k$-error linear complexity for $2^n$-periodic binary sequences and this will help us construct some sequences with requirements on linear complexity and $k$-error complexity.

Citation: 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
References:
[1]

C. S. Ding, Lower bounds on the weight complexity of cascaded binary sequences, in Proc. Auscrypt'90 Adv. Crypt. , Springer-Verlag, 1990, 39–43. doi: 10.1007/BFb0030350.

[2]

C. S. Ding, G. Z. Xiao and W. J. Shan, The Stability Theory of Stream Ciphers, SpringerVerlag, Berlin, 1991, 85–88. doi: 10.1007/3-540-54973-0.

[3]

T. EtzionN. KalouptsidisN. KolokotronisK. Limniotis and K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Trans. Inf. Theory, 55 (2009), 4681-4686.  doi: 10.1109/TIT.2009.2027495.

[4]

F. Fu, H. Niederreiter and M. Su, The characterization of 2n-periodic binary sequences with fixed 1-error linear complexity, in SETA 2006 (eds. G. Gong et al), Springer, 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. Inf. Theory, 29 (1983), 144-146.  doi: 10.1109/TIT.1983.1056619.

[6]

Y. K. HanJ. H. Chung and K. Yang, On the $k$-error linear complexity of $p^m$-periodic binary sequences, IEEE Trans. Inf. Theory, 53 (2007), 2297-2304.  doi: 10.1109/TIT.2007.896863.

[7]

T. KaidaS. Uehara and K. Imamura, An algorithm for the $k$-error linear complexity of sequences over GF($p^m$) with period $p^n$, $p$ a prime, Inf. Comput., 151 (1999), 134-147.  doi: 10.1006/inco.1998.2768.

[8]

R. Kavuluru, Characterization of $2^n$-periodic binary sequences with fixed 2-error or 3-error linear complexity, Des. Codes Crypt., 53 (2009), 75-97.  doi: 10.1007/s10623-009-9295-x.

[9]

N. KolokotronisP. Rizomiliotis and N. Kalouptsidis, Minimum linear span approximation of binary sequences, IEEE Trans. Inf. Theory, 48 (2002), 2758-2764.  doi: 10.1109/TIT.2002.802621.

[10]

K. KurosawaF. SatoT. Sakata and W. Kishimoto, A relationship between linear complexity and $k$-error linear complexity, IEEE Trans. Inf. Theory, 46 (2000), 694-698.  doi: 10.1109/18.825845.

[11]

A. Lauder and K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Trans. Inf. Theory, 49 (2003), 273-280.  doi: 10.1109/TIT.2002.806136.

[12]

W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Crypt., 33 (2004), 109-122.  doi: 10.1023/B:DESI.0000035466.28660.e9.

[13]

W. Meidl, On the stablity of $2^n$-periodic binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1151-1155.  doi: 10.1109/TIT.2004.842709.

[14]

F. Pi and W. F. Qi, The 4-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n-2^m-2^l$, ACTA Electr. Sin. (in Chinese), 39 (2011), 2914-2920. 

[15]

R. A. Rueppel, Analysis and Design of Stream Ciphers Springer-Verlag, Berlin, 1986. doi: 10.1007/978-3-642-82865-2.

[16]

M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^n$, IEEE Trans. Inf. Theory, 39 (1993), 1398-1401.  doi: 10.1109/18.243455.

[17]

G. Z. XiaoS. M. WeiK. Y. Lam and K. Imamura, A fast algorithm for determining the linear complexity of a sequence with period $p^n$ over $GF(q)$, IEEE Trans. Inf. Theory, 46 (2000), 2203-2206.  doi: 10.1109/18.868492.

[18]

J. Q. Zhou, On the $k$-error linear complexity of sequences with period 2$p^n$ over GF(q), Des. Codes Crypt., 58 (2011), 279-296.  doi: 10.1007/s10623-010-9379-7.

[19]

J. Q. Zhou and W. Q. Liu, The $k$-error linear complexity distribution for $2^n$-periodic binary sequences, Des. Codes Crypt., 73 (2014), 55-75.  doi: 10.1007/s10623-013-9805-8.

[20]

J. Q. Zhou, J. Liu and W. Q. Liu, The 4-error linear complexity distribution for $2^n$-periodic binary sequences 2013, preprint, arXiv: 1310.0132 doi: 10.1007/s10623-013-9805-8.

[21]

J. Q. Zhou, W. Q. Liu and G. L. Zhou, Cube theory and stable k-error linear complexity for periodic sequences, in Inscrypt 2013, Springer, 70–85. doi: 10.1007/978-3-319-12087-4_5.

[22]

F. X. Zhu and W. F. Qi, The 2-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$-1, J. Electronics (China), 24 (2007), 390-395.  doi: 10.1007/s11767-006-0005-9.

show all references

References:
[1]

C. S. Ding, Lower bounds on the weight complexity of cascaded binary sequences, in Proc. Auscrypt'90 Adv. Crypt. , Springer-Verlag, 1990, 39–43. doi: 10.1007/BFb0030350.

[2]

C. S. Ding, G. Z. Xiao and W. J. Shan, The Stability Theory of Stream Ciphers, SpringerVerlag, Berlin, 1991, 85–88. doi: 10.1007/3-540-54973-0.

[3]

T. EtzionN. KalouptsidisN. KolokotronisK. Limniotis and K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Trans. Inf. Theory, 55 (2009), 4681-4686.  doi: 10.1109/TIT.2009.2027495.

[4]

F. Fu, H. Niederreiter and M. Su, The characterization of 2n-periodic binary sequences with fixed 1-error linear complexity, in SETA 2006 (eds. G. Gong et al), Springer, 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. Inf. Theory, 29 (1983), 144-146.  doi: 10.1109/TIT.1983.1056619.

[6]

Y. K. HanJ. H. Chung and K. Yang, On the $k$-error linear complexity of $p^m$-periodic binary sequences, IEEE Trans. Inf. Theory, 53 (2007), 2297-2304.  doi: 10.1109/TIT.2007.896863.

[7]

T. KaidaS. Uehara and K. Imamura, An algorithm for the $k$-error linear complexity of sequences over GF($p^m$) with period $p^n$, $p$ a prime, Inf. Comput., 151 (1999), 134-147.  doi: 10.1006/inco.1998.2768.

[8]

R. Kavuluru, Characterization of $2^n$-periodic binary sequences with fixed 2-error or 3-error linear complexity, Des. Codes Crypt., 53 (2009), 75-97.  doi: 10.1007/s10623-009-9295-x.

[9]

N. KolokotronisP. Rizomiliotis and N. Kalouptsidis, Minimum linear span approximation of binary sequences, IEEE Trans. Inf. Theory, 48 (2002), 2758-2764.  doi: 10.1109/TIT.2002.802621.

[10]

K. KurosawaF. SatoT. Sakata and W. Kishimoto, A relationship between linear complexity and $k$-error linear complexity, IEEE Trans. Inf. Theory, 46 (2000), 694-698.  doi: 10.1109/18.825845.

[11]

A. Lauder and K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Trans. Inf. Theory, 49 (2003), 273-280.  doi: 10.1109/TIT.2002.806136.

[12]

W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Crypt., 33 (2004), 109-122.  doi: 10.1023/B:DESI.0000035466.28660.e9.

[13]

W. Meidl, On the stablity of $2^n$-periodic binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1151-1155.  doi: 10.1109/TIT.2004.842709.

[14]

F. Pi and W. F. Qi, The 4-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n-2^m-2^l$, ACTA Electr. Sin. (in Chinese), 39 (2011), 2914-2920. 

[15]

R. A. Rueppel, Analysis and Design of Stream Ciphers Springer-Verlag, Berlin, 1986. doi: 10.1007/978-3-642-82865-2.

[16]

M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^n$, IEEE Trans. Inf. Theory, 39 (1993), 1398-1401.  doi: 10.1109/18.243455.

[17]

G. Z. XiaoS. M. WeiK. Y. Lam and K. Imamura, A fast algorithm for determining the linear complexity of a sequence with period $p^n$ over $GF(q)$, IEEE Trans. Inf. Theory, 46 (2000), 2203-2206.  doi: 10.1109/18.868492.

[18]

J. Q. Zhou, On the $k$-error linear complexity of sequences with period 2$p^n$ over GF(q), Des. Codes Crypt., 58 (2011), 279-296.  doi: 10.1007/s10623-010-9379-7.

[19]

J. Q. Zhou and W. Q. Liu, The $k$-error linear complexity distribution for $2^n$-periodic binary sequences, Des. Codes Crypt., 73 (2014), 55-75.  doi: 10.1007/s10623-013-9805-8.

[20]

J. Q. Zhou, J. Liu and W. Q. Liu, The 4-error linear complexity distribution for $2^n$-periodic binary sequences 2013, preprint, arXiv: 1310.0132 doi: 10.1007/s10623-013-9805-8.

[21]

J. Q. Zhou, W. Q. Liu and G. L. Zhou, Cube theory and stable k-error linear complexity for periodic sequences, in Inscrypt 2013, Springer, 70–85. doi: 10.1007/978-3-319-12087-4_5.

[22]

F. X. Zhu and W. F. Qi, The 2-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$-1, J. Electronics (China), 24 (2007), 390-395.  doi: 10.1007/s11767-006-0005-9.

[1]

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

[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]

Hongwei Jiao, Junqiao Ma, Peiping Shen, Yongjian Qiu. Effective algorithm and computational complexity for solving sum of linear ratios problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022135

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Stefano Galatolo. Orbit complexity and data compression. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477

[12]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299

[13]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[14]

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

[15]

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

[16]

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

[17]

Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385

[18]

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

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (181)
  • HTML views (71)
  • Cited by (0)

Other articles
by authors

[Back to Top]