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: |
[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.
![]() |