
Previous Article
An extension of hybrid method without extrapolation step to equilibrium problems
 JIMO Home
 This Issue

Next Article
Minimization of the coefficient of variation for patient waiting system governed by a generic maximum waiting policy
Structure analysis on the kerror linear complexity for 2^{n}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 
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 inclusionexclusion principle, we obtain the complete characterization of the $i$th descent point (critical point) of the kerror 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.
References:
[1] 
Z. L. Chang, X. Y. Wang, On the First and Second Critical Error Linear Complexity of Binary $2^n$periodic Sequences, Chinese Journal of Electronics, 22 (2013), 16. 
[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: SpringerVerlag, 1991. 
[3] 
T. Etzion, N. Kalouptsidis, N. Kolokotronis, K. Limniotis, K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Transactions on Information Theory, 55 (2009), 46814686. 
[4] 
F. Fu, H. Niederreiter, M. Su, The characterization of $2^n$periodic binary sequences with fixed 1error linear complexity, Gong G., Helleseth T., Song H.Y., Yang K. (eds.) SETA 2006, LNCS, 4086 (2006), 88103. 
[5] 
R. A. Games, 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), 144146. 
[6] 
N. Kolokotronis, P. Rizomiliotis, N. Kalouptsidis, Minimum linear span approximation of binary sequences, IEEE Transactions on Information Theory, 48 (2002), 27582764. 
[7] 
K. Kurosawa, F. Sato, T. Sakata, W. Kishimoto, A relationship between linear complexity and $k$error linear complexity, IEEE Transactions on Information Theory, 46 (2000), 694698. 
[8] 
A. Lauder, K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Transactions on Information Theory, 49 (2003), 273280. 
[9] 
J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans on Information Theory, 15 (1969), 122127. 
[10] 
W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Cryptogr., 33 (2004), 109122. 
[11] 
W. Meidl, On the stablity of $2^n$periodic binary sequences, IEEE Transactions on Information Theory, 51 (2005), 11511155. 
[12] 
R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: SpringerVerlag, 1986, chapter 4. 
[13] 
M. Stamp, C. F. Martin, An algorithm for the $k$error linear complexity of binary sequences with period $2^{n}$, IEEE Trans. Inform. Theory, 39 (1993), 13981401. 
[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), 279296. 
[15] 
J. Q. Zhou, W. Q. Liu, The $k$error linear complexity distribution for $2^n$periodic binary sequences, Des. Codes Cryptogr., 73 (2014), 5575. 
[16] 
J. Q. Zhou, W. Q. Liu, G. L. Zhou, Cube theory and stable $k$error linear complexity for periodic sequences, Inscrypt, LNCS, 8567 (2013), 7085. 
[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, W. F. Qi, The 2error linear complexity of $2^n$periodic binary sequences with linear complexity $2^n$1, Journal of Electronics (China), 24 (2007), 390395. 
show all references
References:
[1] 
Z. L. Chang, X. Y. Wang, On the First and Second Critical Error Linear Complexity of Binary $2^n$periodic Sequences, Chinese Journal of Electronics, 22 (2013), 16. 
[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: SpringerVerlag, 1991. 
[3] 
T. Etzion, N. Kalouptsidis, N. Kolokotronis, K. Limniotis, K. G. Paterson, Properties of the error linear complexity spectrum, IEEE Transactions on Information Theory, 55 (2009), 46814686. 
[4] 
F. Fu, H. Niederreiter, M. Su, The characterization of $2^n$periodic binary sequences with fixed 1error linear complexity, Gong G., Helleseth T., Song H.Y., Yang K. (eds.) SETA 2006, LNCS, 4086 (2006), 88103. 
[5] 
R. A. Games, 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), 144146. 
[6] 
N. Kolokotronis, P. Rizomiliotis, N. Kalouptsidis, Minimum linear span approximation of binary sequences, IEEE Transactions on Information Theory, 48 (2002), 27582764. 
[7] 
K. Kurosawa, F. Sato, T. Sakata, W. Kishimoto, A relationship between linear complexity and $k$error linear complexity, IEEE Transactions on Information Theory, 46 (2000), 694698. 
[8] 
A. Lauder, K. Paterson, Computing the error linear complexity spectrum of a binary sequence of period $2^n$, IEEE Transactions on Information Theory, 49 (2003), 273280. 
[9] 
J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans on Information Theory, 15 (1969), 122127. 
[10] 
W. Meidl, How many bits have to be changed to decrease the linear complexity?, Des. Codes Cryptogr., 33 (2004), 109122. 
[11] 
W. Meidl, On the stablity of $2^n$periodic binary sequences, IEEE Transactions on Information Theory, 51 (2005), 11511155. 
[12] 
R. A. Rueppel, Analysis and Design of Stream Ciphers, Berlin: SpringerVerlag, 1986, chapter 4. 
[13] 
M. Stamp, C. F. Martin, An algorithm for the $k$error linear complexity of binary sequences with period $2^{n}$, IEEE Trans. Inform. Theory, 39 (1993), 13981401. 
[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), 279296. 
[15] 
J. Q. Zhou, W. Q. Liu, The $k$error linear complexity distribution for $2^n$periodic binary sequences, Des. Codes Cryptogr., 73 (2014), 5575. 
[16] 
J. Q. Zhou, W. Q. Liu, G. L. Zhou, Cube theory and stable $k$error linear complexity for periodic sequences, Inscrypt, LNCS, 8567 (2013), 7085. 
[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, W. F. Qi, The 2error linear complexity of $2^n$periodic binary sequences with linear complexity $2^n$1, Journal of Electronics (China), 24 (2007), 390395. 
[1] 
Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the $k$error linear complexity of $2^n$periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429444. doi: 10.3934/amc.2017036 
[2] 
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) : 369379. doi: 10.3934/amc.2010.4.369 
[3] 
Idan Goldenberg, David Burshtein. Error bounds for repeataccumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555570. doi: 10.3934/amc.2011.5.555 
[4] 
Giuseppe Bianchi, Lorenzo Bracciale, Keren CensorHillel, Andrea Lincoln, Muriel Médard. The oneoutofk retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95112. doi: 10.3934/amc.2016.10.95 
[5] 
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) : 297312. doi: 10.3934/amc.2014.8.297 
[6] 
Siqi Li, Weiyi Qian. Analysis of complexity of primaldual interiorpoint algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 3746. doi: 10.3934/naco.2015.5.37 
[7] 
Xiaojie Wang. Weak error estimates of the exponential Euler scheme for semilinear SPDEs without Malliavin calculus. Discrete & Continuous Dynamical Systems  A, 2016, 36 (1) : 481497. doi: 10.3934/dcds.2016.36.481 
[8] 
Georg Vossen, Stefan Volkwein. Model reduction techniques with aposteriori error analysis for linearquadratic optimal control problems. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 465485. doi: 10.3934/naco.2012.2.465 
[9] 
Walter Alt, Robert Baier, Matthias Gerdts, Frank Lempio. Error bounds for Euler approximation of linearquadratic control problems with bangbang solutions. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 547570. doi: 10.3934/naco.2012.2.547 
[10] 
Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems  A, 2001, 7 (3) : 477486. doi: 10.3934/dcds.2001.7.477 
[11] 
Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems  A, 2010, 28 (4) : 12991309. doi: 10.3934/dcds.2010.28.1299 
[12] 
Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The crosscorrelation 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) : 409424. doi: 10.3934/amc.2013.7.409 
[13] 
Alfredo Lorenzi, Luca Lorenzi. A strongly illposed integrodifferential singular parabolic problem in the unit cube of $\mathbb{R}^n$. Evolution Equations & Control Theory, 2014, 3 (3) : 499524. doi: 10.3934/eect.2014.3.499 
[14] 
Navin Keswani. Homotopy invariance of relative etainvariants and $C^*$algebra $K$theory. Electronic Research Announcements, 1998, 4: 1826. 
[15] 
L. Búa, T. Mestdag, M. Salgado. Symmetry reduction, integrability and reconstruction in $k$symplectic field theory. Journal of Geometric Mechanics, 2015, 7 (4) : 395429. doi: 10.3934/jgm.2015.7.395 
[16] 
Steffen Klassert, Daniel Lenz, Peter Stollmann. Delone measures of finite local complexity and applications to spectral theory of onedimensional continuum models of quasicrystals. Discrete & Continuous Dynamical Systems  A, 2011, 29 (4) : 15531571. doi: 10.3934/dcds.2011.29.1553 
[17] 
Daijun Jiang, Hui Feng, Jun Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems & Imaging, 2015, 9 (1) : 163188. doi: 10.3934/ipi.2015.9.163 
[18] 
Wacław Marzantowicz, Piotr Maciej Przygodzki. Finding periodic points of a map by use of a kadic expansion . Discrete & Continuous Dynamical Systems  A, 1999, 5 (3) : 495514. doi: 10.3934/dcds.1999.5.495 
[19] 
Marek Galewski, Renata Wieteska. Multiple periodic solutions to a discrete $p^{(k)}$  Laplacian problem. Discrete & Continuous Dynamical Systems  B, 2014, 19 (8) : 25352547. doi: 10.3934/dcdsb.2014.19.2535 
[20] 
José Ignacio AlvarezHamelin, Luca Dall'Asta, Alain Barrat, Alessandro Vespignani. Kcore decomposition of Internet graphs: hierarchies, selfsimilarity and measurement biases. Networks & Heterogeneous Media, 2008, 3 (2) : 371393. doi: 10.3934/nhm.2008.3.371 
2016 Impact Factor: 0.994
Tools
Metrics
Other articles
by authors
[Back to Top]