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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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. Inf. Theory, 29 (1983), 144-146.  doi: 10.1109/TIT.1983.1056619.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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. Inf. Theory, 29 (1983), 144-146.  doi: 10.1109/TIT.1983.1056619.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[15]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

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

[2]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266

[3]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[4]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[5]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302

[6]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[7]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322

[8]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168

[9]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[10]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[11]

Jan Bouwe van den Berg, Elena Queirolo. A general framework for validated continuation of periodic orbits in systems of polynomial ODEs. Journal of Computational Dynamics, 2021, 8 (1) : 59-97. doi: 10.3934/jcd.2021004

[12]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[13]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]