Structure analysis on the k-error linear complexity for 2n-periodic binary sequences

Jianqin Zhou; Wanquan Liu; Xifeng Wang

doi:10.3934/jimo.2017016

Article Contents

2017, Volume 13, Issue 4: 1743-1757. Doi: 10.3934/jimo.2017016

This issue Previous Article An extension of hybrid method without extrapolation step to equilibrium problems Next Article Minimization of the coefficient of variation for patient waiting system governed by a generic maximum waiting policy

Structure analysis on the k-error linear complexity for 2ⁿ-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

Received: November 30, 2014

Published: November 2017

The research was partially supported by Anhui Natural Science Foundation (No.1208085MF106) and Provincial Natural Science Research Project of Anhui Colleges (No.KJ2013Z025).

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94A55, 94A60; Secondary: 11B50.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.