• 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 2n-periodic binary sequences

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.

Citation: Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-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. EtzionN. KalouptsidisN. KolokotronisK. 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. FuH. 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. KolokotronisP. 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. KurosawaF. SatoT. 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. ZhouW. 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

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. EtzionN. KalouptsidisN. KolokotronisK. 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. FuH. 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. KolokotronisP. 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. KurosawaF. SatoT. 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. ZhouW. 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]

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]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

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

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[12]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[13]

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

[14]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[15]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[16]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[17]

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

[18]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[19]

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

[20]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]