Binary Pseudorandom Sequences With Good Autocorrelation

Sequences have important applications in ranging systems,spread spectrum communication systems,multi-terminal system identification,code division multiple access(CDMA) communications systems,global positioning systems(GPS),software testing,circuit testing,computer simulation,and stream ciphers.Sequences having desirable properties are strongly needed in these applications,of which randomness and complexity are the most important two.Randomness refers to the unpredictability of the sequence,while complexity describes the difficulty of replicating the sequence.In this dissertation,we concentrate on two main properties of binary sequences.One is the autocorrelation,which describes the randomness of the sequence,and the other is linear complexity which is the most popular measure for complexity.Unfortunately,there are not always binary sequences with ideal autocorrelation, say,perfect sequences.Hence,it is natural to construct binary sequences with "best possible" autocorrelation,that is,binary sequences with optimal autocorrelation,which have close connections with certain combinatorial designs.Difference sets form the periodic binary sequence with two level autocorrelation.Almost difference sets form the periodic binary sequence with three level autocorrelation.So the construction of binary sequences with optimal autocorrelation turns on the construction of difference sets or almost difference sets.In this dissertation,we give a well rounded treatment of binary sequences with optimal autocorrelation,survey known constructions for binary sequences with optimal autocorrelation,and present a new one,and discuss the linear complexities of these binary sequences with optimal autocorrelation.We focus on the binary pseudorandom sequences with good autocorrelation.We investigate the structure, the property and construction method with optimal autocorrelation of the binary pseudorandom sequences in this dissertation.We present the structure,the property and construction method of the d-decimated sequences and some sequences with low autocorrelation.The main research work and key contributions of this dissertation are as follows.(1) We present a general construction method of binary sequence with almost optimal autocorrelation.We prove its correctness and calculate the out-of-phase autocorrelation values.We construct a series of binary sequences with the out-of-phase autocorrelation values in {-1,3}.(2) We give examples for the new constructions and verify their linear complexity and other random properties.They have big linear complexity and low autocorrelation.The experimental results show that the newly constructed binary sequences have good linear complexity,low autocorrelation value,good balance and long period.We compare the known binary sequences with optimal autocorrelation with our new construction.Our new construction produces binary sequences with good random property according to both theoretical and experimental results.(3) We study the relationship between autocorrecation values and the cyclotomaic numbers of order d.We give the calculation method of linear complexity of decimated sequences.We present the autocorrelation of decimated sequences by using trace mapping and cyclotomic classes.We give the relation between balanceness and autocorrelation and shows that the autocorrelation values of d-decimated version sequence is at most(d + 3)/2-valued.We obtain the relationship between the linear complexity of d-decimated sequences and cyclotomic numbers of order d.Hence it may be concluded that computing the autocorrelation values of d -decimated version sequence is as difficult as computing the cyclotomic numbers of order d.We construct a number of classes of binary sequences with 3-level autocorrelation by using above results.(4) We present a general method to construct binary sequences with at most 4-level autocorrelation based cyclic difference sets.We construct 49 classes of sequences with at most 4-level autocorrelation,and give some examples and prove the correctness of our conclusions.The exact autocorrelation values can be computed directly with the parameters about the difference sets given in this dissertation.