Remarks on the generalized cyclotomic sequences of length $$2p^{m}$$
- PDF / 179,144 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 167 Views
Remarks on the generalized cyclotomic sequences of length 2 pm Lin Tan · Hong Xu · Wen-Feng Qi
Received: 22 August 2012 / Revised: 12 September 2012 / Accepted: 14 September 2012 / Published online: 2 November 2012 © Springer-Verlag Berlin Heidelberg 2012
Abstract This paper presents some nonrandom distribution properties of two generalized cyclotomic binary sequences of length 2 p m constructed by Zhang et al. (Appl Algebra Eng Commun Comput 21:93–108, 2010). Using these properties we further study the k-error linear complexity and autocorrelation of these sequences. For some small values of k, the upper bounds on the k-error linear complexity are derived, which are far less than their linear complexity. Finally the bounds on the autocorrelation of these sequences are also presented. Our results show that there exist some drawbacks in application of these two sequences. Keywords Cyclotomic sequences · Distribution · Linear complexity · k-error linear complexity · Autocorrelation 1 Introduction Pseudorandom sequences are widely used in cryptography and communication. A good pseudorandom sequence must be unpredictable, i.e., it must be computationally infeasible to recover more of the sequence from a captured segment. In certain applications of pseudorandom sequences, some pseudorandom properties are needed
This work was supported by the NSF of China under Grant Numbers 61070178, 61272042 and 61100200. L. Tan (B) · H. Xu · W.-F. Qi Department of Applied Mathematics, Zhengzhou Information Science and Technology Institute, P. O. Box 1001-745, 450002 Zhengzhou, People’s Republic of China e-mail: [email protected] H. Xu e-mail: [email protected] W.-F. Qi e-mail: [email protected]
123
222
L. Tan et al.
such as good distribution properties, good correlation, large linear complexity and large k-error linear complexity. The linear complexity LC(s) of a sequence s is the length of the shortest linear feedback shift register that can generate it. The k-error linear complexity LCk (s) of s is the minimum linear complexity that can be obtained for s by modifying up to k terms in one period (and modifying all other periods in the same way), which is a measure of the stability of linear complexity for sequences [8,12]. The cyclotomic sequences constructed via cyclotomic classes are widely studied for their good autocorrelation and large linear complexity. Ding et al. [4] determined the linear complexity of Legendre sequences and introduced the generalized cyclotomy [5]. Then the generalized cyclotomic sequences with good properties were constructed and studied [3,6,7,9,13–15]. The linear complexity and autocorrelation of generalized cyclotomic sequences of length pq were determined in [6] and [7]. Bai et al. [1] constructed a new generalized cyclotomic sequence of length pq and studied its linear complexity. Meidl [10] studied the k-error linear complexity and autocorrelation of generalized cyclotomic sequences constructed by Bai et al., and showed certain drawbacks of this construction. The linear complexity of generaliz
Data Loading...