Font Size: a A A

The Construction And Property Analysis Of Pseudo-random Sequences

Posted on:2015-10-31Degree:DoctorType:Dissertation
Country:ChinaCandidate:X P LiFull Text:PDF
GTID:1108330464468886Subject:Cryptography
Abstract/Summary:PDF Full Text Request
Pseudo-random sequences are widely used in spread spectrum communication systems, code division multiple access systems, global positioning systems, and stream ciphers etc. In these applications, especially for pseudo-random sequences with good properties have strong demand. The autocorrelation and linear complexity are two important prop-erties of pseudo-random sequence. This dissertation mainly investigates the construction and randomness of three kinds of binary generalized cyclotomic sequences with length pq, two kinds of binary generalized cyclotomic sequences of length pm and 2pm, and quater-nary sequences with good autocorrelation.The main results are shown as follows:1. Two classes of Whiteman’s generalized cyclotomic sequences of order 2 are con-structed. One of them is balanced, and the other is’t balanced. Their linear complex-ity and minimal polynomials are calculated by the factoring of polynomials theory and the roots of their characteristic polynomials, respectively. The results show that these sequences have high linear complexity for most of choices of primes p and q. So theses sequences can resist an attack from the application of Berlekamp-Massey algorithm.2. A new class of balanced Whiteman’s generalized cyclotomic sequence of order 4 is constructed. Its linear complexity and minimal polynomial are also determined by the factoring of polynomials theory and the roots of its characteristic polynomial, respectively. Its linear complexity can take the values pq, pq-(p-1)/2, or pq-(q-1)/2. The result shows that its linear complexity is larger than half of its period. By B-M algorithm, the sequence is considered to be good from the viewpoint of linear complexity.3. We present two mappings which both map two binary variables to a quaternary variable. Two quaternary sequences are constructed using two binary sequence pairs and one of the mappings. The relationship between the cross-correlation func-tion of the constructed quaternary sequences and the that of the employed binary sequences is derived. Specially, the two quaternary sequences are identical if the em-ployed two binary sequence pairs are identical, and the autocorrelation function of the quaternary sequence is represented by the correlation function of the employed binary sequences. Using the other mapping, similar results can be obtained. When the employed binary sequences are two shifted versions of a binary sequence with length 2T, the autocorrelation function of the constructed quaternary sequence is equal to that of the binary sequence under a certain condition. And the constructed quaternary sequence is balanced under certain condition. Moreover, two quaternary sequences are constructed by binary sequences with good autocorrelation and our defined mappings. And a new balanced quaternary sequence with good autocorrela-tion is derived by interleaving the constructed quaternary sequences. Additionally, binary sequence pairs are constructed by interleaving the Legendre sequence and its companion. Then a quaternary sequence with good autocorrelation can be deduced by our defined mapping and the constructed binary sequence pairs.4. Two kinds of binary generalized cyclotomic sequences of length pm and 2pm, defined by Yan and Ke in [78,151] respectively, are investigated. Based on the algebraic structure of these sequences, the corresponding reference sequences can be given by changing a few bits of the original sequences. Using these reference sequences, we give some upper bounds of their k-error linear complexity for some certain values of the parameter k. Meanwhile, we point out these sequences don’t satisfy ideal (p-1)-tuple distributions. The results show that these sequences should be carefully selected in stream cipher systems, even though they have high linear complexity.
Keywords/Search Tags:generalized cyclotomic sequences, linear complexity, k-error linear complex- ity, quaternary sequences, autocorrelation function
PDF Full Text Request
Related items