The Linear Complexity of Sequences with Desirable Correlation

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis 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 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 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 
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 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.


Date:			Monday, 16 May 2011

Time:			2:00pm – 4:00pm

Venue:			Room 3408
 			Lifts 17/18

Chairman:		Prof. Christopher Leung (CIVL)

Committee Members:	Prof. Cunsheng Ding (Supervisor)
 			Prof. Huamin Qu
 			Prof. Ke Yi
                         Prof. Wai-Ho Mow (ECE)
 			Prof. Alexander Pott (Math., Otto-von-Guericke Univ.)
                         Prof. Fangguo Zhang (Inf. Sci. & Tech., Sun Yat-sen Univ.)


**** ALL are Welcome ****