The Linear Complexity of Sequences with Desirable Correlation

PhD Thesis Proposal Defence


Title: "The Linear Complexity of Sequences with Desirable Correlation"

by

Mr. Qi WANG


Abstract:

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

In this thesis proposal, the linear complexity of series of sequences with 
desirable correlation is investigated. The proposal 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 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 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 FH sequences 
with large linear complexity, results on how to choose a proper power are 
given.


Date:  			Monday, 1 November 2010

Time:           	2:00pm - 4:00pm

Venue:          	Room 3304
 			lifts 17/18

Committee Members:      Prof. Cunsheng Ding (Supervisor)
 			Dr. Ke Yi (Chairperson)
 			Dr. Lei Chen
 			Dr. Wai-Ho Mow (ECE)


**** ALL are Welcome ****