Pseudo random sequences have many applications in code division multiple access (CDMA) communication systems, global positioning systems (GPS), stream ciphers, etc. In applications, since sequences generated by deterministic methods are not truly random, certain desirable properties of sequences are singled out to refer to randomness. On two important measures about randomness of sequences are concentrated: one is the correlation, and the other is the linear complexity. Binary sequences are required to have the impulse-like autocorrelation function, and such binary sequences have a one-to-one correspondence to certain combinatorial designs. Besides, in frequency hopping (FH) CDMA systems, the maximum Hamming correlation among all the FH sequences in the FH sequence set should meet some...[ Read more ]

Pseudo random sequences have many applications in code division multiple access (CDMA) communication systems, global positioning systems (GPS), stream ciphers, etc. In applications, since sequences generated by deterministic methods are not truly random, certain desirable properties of sequences are singled out to refer to randomness. On two important measures about randomness of sequences are concentrated: one is the correlation, and the other is the linear complexity. Binary sequences are required to have the impulse-like autocorrelation function, and such binary sequences have a one-to-one correspondence to certain combinatorial designs. Besides, in frequency hopping (FH) CDMA systems, the maximum Hamming correlation among all the FH sequences in the FH sequence set should meet some theoretical bounds. For all these sequences, large linear complexity is desirable for both cryptographic and anti-jamming purposes.

In this thesis, the linear complexity of a series of sequences with desirable correlation is investigated. The thesis is composed of three main parts. In the first part (Chapter 3), the first and only construction of binary sequences with the three-level autocorrelation values {−1, 3,N} is studied. Both the linear complexities and the minimal polynomials of binary sequences obtained from two classes of difference sets with Singer parameters are explicitly determined. In the second part (Chapter 4), two interleaving constructions of binary sequences with optimal autocorrelation {0,−4,N} of period N ≡ 0 (mod 4) are investigated. General results on the minimal polynomials of binary sequences generated by these two constructions are given. The linear complexities of all the classes of generated sequences are established depending on those of binary sequences with ideal autocorrelation. A close relation between the two constructions is also revealed. In the last part (Chapter 5), the linear complexities of the FH sequences in several optimal sets are derived. Furthermore, the linear complexities of the transformed FH sequences by applying a power permutation are determined. In order to construct optimal sets of FH sequences with large linear complexity, results on how to choose a proper power are given.