-
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
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 |
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.
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 2n-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 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]