Trace Representation And Linear Complexity Of Several Classes Of Periodic Sequences

Periodic binary and quaternary sequences are widely used in stream cipher system-s,coding theory and direct-sequence code-division multiple-access systems due to their simplicity of implementation.Linear complexity is an important indicator for measuring the unpredictability of sequences,and sequences used in stream ciphers and spread spec-trum communication systems must have high linear complexity.Using trace functions to construct pseudo-random sequences is one of the important methods for sequence design.Since the 1980s,people have designed many sequences and sequence families with high lin-ear complexity and good correlation properties by using the elegent algebraic characteristics of trace functions.On the other hand,trace functions are also very useful for the engineering implementation of sequences and the analysis of their random properties.If a sequence can be expressed by trace functions,its linear complexity can be further determined according to the coefficients and form of its trace representation,and a linear feedback shift regis-ter for generating the sequence can be obtained.In this thesis,we mainly investigate the trace representation and linear complexity over Galois rings or finite fields of several classes sequences based on classical cyclotomy and achieve the following results:（1）Let p=ef+1 be an odd prime,where e≡0（mod 4）.A family of balanced quaternary sequences is defined by using the classical cyclotomic classes of order0)with respect toin this paper.We derive general formulas for their linear complexity and trace representation over Z₄by computing the discrete Fourier transform of these sequences.As an application,the linear complexity and trace representation over Z₄are given for two types of specific sequences with low autocorrelation,namely Tang-Lindner sequence and Michel-Wang sequence.Furthermore,by counting the number of nonzero coefficients in their defining polynomials,we explicitly determine the linear complexity of these two types of quaternary sequences over Z₄.（2）The low correlation Michel-Wang sequence can be mapped to a sequence over the finite field F₄by inverse Gray mapping.We determine the exact linear complexity and minimal polynomial of the sequence over F₄by investigating the roots of its sequence polynomial in the splitting field of x^p-1 over F₄.（3）We regard the DHL sequence as a sequence over the finite field F_q of odd charac-teristic.By using the properties of classical cyclotomy of order 4 and the basic theory of trace function,the Mattson-Solomon polynomial of the DHL sequence is determined,and a trace representation of the DHL sequence over a field of characteristicis obtained.On this basis,a general formula for the linear complexity of the DHL sequence over F_q is given.