Font Size: a A A

Research On Several Pseudorandom Sequences

Posted on:2006-02-25Degree:DoctorType:Dissertation
Country:ChinaCandidate:H G HuFull Text:PDF
GTID:1118360182957570Subject:Communication and Information System
Abstract/Summary:PDF Full Text Request
Pseudorandom sequences are widely used in cryptography, communcia-tions, computation, control, etc. The design and analysis of pseudorandom sequences are hot research topics in the world all the time. Looking for new method to design more sequences with nice properties, as well as looking for stronger mathematical tool to analyze the properties of existing sequences in detail, is very valuable.In this dissertation, we carry out deep research on some problems in the field of pseudorandom sequences. These problems are: feedback with carry shift register (FCSR), the 2-adic complexity of binary sequences, the relationship between the generalized discrete Fourier transform and the 1-error linear complexity of periodic sequences, the distribution of independent r-pattern and partial period properties of two classes of binary sequences derived from Z2l, pseudorandom sequences from function field, etc.Our main contributions are listed below:1) The explicit formula for the distribution of FCSR sequences is derived. With the aid of this formula, we analyze the distributional properties of FCSR sequences in detail. We also discuss the common autocorrelations and arithemetic autocorrelations of FCSR sequences, and the linear complexityof some binary FCSR sequences under 1 or 2 symbols suhstitution withenevery period is proved to be large under some conditions.2) A significant difference between the linear complexity and the 2-adic complexity is pointed out, and the influence of this difference on the sequence synthesis problem is discussed. Based on this observation, we propose a more reasonable concept of the symmetric 2-adic complexity. The expected values of the 2-adic complexity and the symmetric 2-adic complexity of periodicbinary sequences are discussed. Nontrivial lower bounds on the k-error 2-adic complexity and the symmetric 2-adic complexity of periodic binary sequences are given.3) We point out that the contents of two papers in IEEE Transactions on Information Theory are essentially the same.4) We construct many periodic sequences with very large 1-error linear complexity over Fq by the generalized discrete Fourier transform of periodic sequences. The results of Niederreiter are improved.5) With the help of certain exponential sums over Galois rings, we analyze the independent r-pattern distribution in two classes of binary sequences derived from Zy. They are both proved to be asymptotically uniform. The new results improve the known ones.6) We estimate some incomplete exponential sums over Galois rings by certain hybrid exponential sums over Galois rings.7) By the incomplete exponential sums over Galois rings derived by us, we analyze the partial period distribution and partial period r-pattern distribution in two classes of binary sequences derived from Z2i.8) By the Kummer extensions of function fields, we construct a new class of binary sequences with large linear complexity and low correlation. We also give some examples when the underlying function fields are elliptic function fields. In some cases, our results are better than those of Xing et al.
Keywords/Search Tags:linear complexity, k-error linear complexity, FCSR, 2-adic complexity, k-error 2-adic complexity, exponential sum over Galois rings, in complete exponential sum over Galois rings, r-pattern of periodic sequences, function field
PDF Full Text Request
Related items